{"action":"opened","issue":{"url":"https://api.github.com/repos/ekg/vg/issues/143","labels_url":"https://api.github.com/repos/ekg/vg/issues/143/labels{/name}","comments_url":"https://api.github.com/repos/ekg/vg/issues/143/comments","events_url":"https://api.github.com/repos/ekg/vg/issues/143/events","html_url":"https://github.com/ekg/vg/issues/143","id":115036161,"number":143,"title":"alignment does traverse reversing edges","user":{"login":"ekg","id":145425,"avatar_url":"https://avatars.githubusercontent.com/u/145425?v=3","gravatar_id":"","url":"https://api.github.com/users/ekg","html_url":"https://github.com/ekg","followers_url":"https://api.github.com/users/ekg/followers","following_url":"https://api.github.com/users/ekg/following{/other_user}","gists_url":"https://api.github.com/users/ekg/gists{/gist_id}","starred_url":"https://api.github.com/users/ekg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ekg/subscriptions","organizations_url":"https://api.github.com/users/ekg/orgs","repos_url":"https://api.github.com/users/ekg/repos","events_url":"https://api.github.com/users/ekg/events{/privacy}","received_events_url":"https://api.github.com/users/ekg/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-11-04T11:49:51Z","updated_at":"2015-11-04T11:49:51Z","closed_at":null,"body":"## GSSW prep is too reductive\r\n\r\nI think this is a known problem to others, but I'm just remembering it and thinking about how to handle it. Here's a basic example graph:\r\n\r\n![screenshot from 2015-11-04 10 14 10](https://cloud.githubusercontent.com/assets/145425/10935255/d2724052-82dc-11e5-9fad-40cdd0ac2912.png)\r\n\r\n```js\r\n{\"node\": [{\"sequence\": \"CAAATAAGGCTTGGAAATTTT\", \"id\": 1}, {\"sequence\": \"CTGG\", \"id\": 2}, {\"sequence\": \"AGTTC\", \"id\": 3}, {\"sequence\": \"GACCCCCG\", \"id\": 4}, {\"sequence\": \"TATTATATTCCAACTCTCTG\", \"id\": 5}], \"edge\": [{\"from\": 1, \"to\": 2}, {\"from\": 4, \"to\": 1, \"to_end\": true}, {\"from\": 2, \"to\": 3}, {\"from\": 3, \"to\": 5}, {\"from_start\": true, \"from\": 5, \"to\": 4}]}\r\n```\r\n\r\nWhen made ready for alignment, it looks like:\r\n\r\n![screenshot from 2015-11-04 10 15 25](https://cloud.githubusercontent.com/assets/145425/10935284/fb86e15a-82dc-11e5-9003-7fe1cc48be19.png)\r\n\r\n```js\r\n{\"node\": [{\"sequence\": \"N\", \"id\": 6}, {\"sequence\": \"CAAATAAGGCTTGGAAATTTT\", \"id\": 1}, {\"sequence\": \"CTGG\", \"id\": 2}, {\"sequence\": \"AGTTC\", \"id\": 3}, {\"sequence\": \"GACCCCCG\", \"id\": 4}, {\"sequence\": \"TATTATATTCCAACTCTCTG\", \"id\": 5}], \"edge\": [{\"from\": 6, \"to\": 1}, {\"from\": 1, \"to\": 2}, {\"from\": 2, \"to\": 3}, {\"from\": 3, \"to\": 5}, {\"from\": 6, \"to\": 4}]}\r\n```\r\n\r\nToo much information is lost in the preparation for GSSW to correctly obtain an alignment here.\r\n\r\n## Example\r\n\r\nThis has consequences for `vg msga`. We might edit this graph:\r\n\r\n![image](https://cloud.githubusercontent.com/assets/145425/10937183/0c5f6856-82e9-11e5-83a2-3dec0c068591.png)\r\n\r\n```js\r\n{\"node\": [{\"sequence\": \"CAAATAAGGCTTGGAAATTTTCTGG\", \"id\": 1}, {\"sequence\": \"AGTTCTATTATATTCCAACTCTCTG\", \"id\": 2}], \"edge\": [{\"from\": 1, \"to\": 2}]}\r\n```\r\n\r\nWith this alignment:\r\n\r\n![screenshot from 2015-11-04 11 44 35](https://cloud.githubusercontent.com/assets/145425/10937247/711cf47a-82e9-11e5-8b65-ef1d68f6270a.png)\r\n\r\n```js\r\n{\"sequence\": \"CAGAGAGTTGGAATATAATAGACCCCCGAAAATTTCCAAGCCTTATTTG\", \"path\": {\"mapping\": [{\"position\": {\"node_id\": 2, \"offset\": 24}, \"edit\": [{\"from_length\": 20, \"to_length\": 20}, {\"to_length\": 8, \"sequence\": \"GACCCCCG\"}], \"is_reverse\": true, \"rank\": 1}, {\"position\": {\"node_id\": 1, \"offset\": 20}, \"edit\": [{\"from_length\": 21, \"to_length\": 21}], \"is_reverse\": true, \"rank\": 2}]}}\r\n```\r\n\r\nYielding the graph which I mentioned above.\r\n\r\nWe can't properly align to it due to the modification of the graph that's used for GSSW alignment:\r\n\r\n![screenshot from 2015-11-04 11 38 46](https://cloud.githubusercontent.com/assets/145425/10937106/b4594406-82e8-11e5-9277-37d4710e20a9.png)\r\n\r\n```js\r\n{\"sequence\": \"CAGAGAGTTGGAATATAATAGACCCCCGAAAATTTCCAAGCCTTATTTG\", \"path\": {\"mapping\": [{\"position\": {\"node_id\": 5, \"offset\": 19}, \"edit\": [{\"from_length\": 20, \"to_length\": 20}, {\"to_length\": 8, \"sequence\": \"GACCCCCG\"}], \"is_reverse\": true, \"rank\": 1}, {\"position\": {\"node_id\": 1, \"offset\": 20}, \"edit\": [{\"from_length\": 21, \"to_length\": 21}], \"is_reverse\": true, \"rank\": 2}]}}\r\n```\r\n\r\nOne consequence of this is that we sometimes fail to annotate paths that have been use to generate the graph. This could cause some of the problems that @glennhickey has seen with vg graphs for the ga4gh construction bakeoff."}}