{"action":"created","issue":{"url":"https://api.github.com/repos/ekg/vg/issues/182","labels_url":"https://api.github.com/repos/ekg/vg/issues/182/labels{/name}","comments_url":"https://api.github.com/repos/ekg/vg/issues/182/comments","events_url":"https://api.github.com/repos/ekg/vg/issues/182/events","html_url":"https://github.com/ekg/vg/issues/182","id":126905438,"number":182,"title":"flipping breaks inverting 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":4,"created_at":"2016-01-15T16:22:53Z","updated_at":"2016-01-19T17:17:43Z","closed_at":null,"body":"This fails. The alignment gets corrupted by the node flipping process that's used to prep the graph for partial order alignment. (To be pushed soon as a test:)\r\n\r\n```bash\r\nvg align -s AGTCCTTGAAAGAGGGCAAAATAAACTGTTAGTAGAGCCAGGTCTGAAAACAACACTTTCTTGC inverting/m.vg >/dev/null\r\n```\r\n\r\nIt exposed my own confusion. The inversions are being broken. This isn't quite what I'd expected (or hoped) it does.\r\n\r\nFor example. Before, input:\r\n\r\n```json\r\n{\"node\": [{\"sequence\": \"GTATTTTTAGTA\", \"id\": 2308}, {\"sequence\": \"T\", \"id\": 2309}, {\"sequence\": \"CTAATTTTT\", \"id\": 2310}, {\"sequence\": \"CA\", \"id\": 2311}, {\"sequence\": \"GG\", \"id\": 2312}, {\"sequence\": \"ACGCCC\", \"id\": 2313}, {\"sequence\": \"C\", \"id\": 2314}, {\"sequence\": \"T\", \"id\": 2315}, {\"sequence\": \"C\", \"id\": 173}, {\"sequence\": \"C\", \"id\": 2316}, {\"sequence\": \"GAGACGGGGTTTCACCATGTT\", \"id\": 2323}, {\"sequence\": \"T\", \"id\": 171}, {\"sequence\": \"C\", \"id\": 172}, {\"sequence\": \"TACTAAAAATA\", \"id\": 174}, {\"sequence\": \"TGGC\", \"id\": 181}, {\"sequence\": \"A\", \"id\": 2317}, {\"sequence\": \"GGTCAGGCTGGTCTCGACTCC\", \"id\": 2324}, {\"sequence\": \"TC\", \"id\": 170}, {\"sequence\": \"T\", \"id\": 175}, {\"sequence\": \"C\", \"id\": 176}, {\"sequence\": \"GGTGTGG\", \"id\": 180}, {\"sequence\": \"AT\", \"id\": 182}, {\"sequence\": \"GG\", \"id\": 183}, {\"sequence\": \"GGGATTACAGGCGCACACC\", \"id\": 2318}, {\"sequence\": \"TGACCTCCTGATCTGCCCCCC\", \"id\": 2325}], \"edge\": [{\"from\": 2309, \"to\": 2308}, {\"from\": 2310, \"to\": 2308}, {\"from\": 2308, \"to\": 2323}, {\"from\": 2310, \"to\": 2309}, {\"from\": 2311, \"to\": 2310}, {\"from\": 2312, \"to\": 2310}, {\"from\": 2313, \"to\": 2311}, {\"from\": 2313, \"to\": 2312}, {\"from\": 2314, \"to\": 2313}, {\"from\": 2315, \"to\": 2313}, {\"from\": 2316, \"to\": 2314}, {\"from\": 2316, \"to\": 2315}, {\"from\": 173, \"to\": 2308, \"to_end\": true}, {\"from\": 173, \"to\": 174}, {\"from\": 2317, \"to\": 2316}, {\"from\": 2323, \"to\": 2324}, {\"from\": 171, \"to\": 173}, {\"from\": 172, \"to\": 173}, {\"from\": 174, \"to\": 175}, {\"from\": 174, \"to\": 176}, {\"from\": 2316, \"to\": 181, \"from_start\": true}, {\"from\": 181, \"to\": 182}, {\"from\": 181, \"to\": 183}, {\"from\": 2318, \"to\": 2317}, {\"from\": 2324, \"to\": 2325}, {\"from\": 170, \"to\": 171}, {\"from\": 170, \"to\": 172}, {\"from\": 180, \"to\": 181}]}\r\n```\r\n\r\nLooks like:\r\n\r\n![screenshot from 2016-01-15 16-14-40](https://cloud.githubusercontent.com/assets/145425/12358019/21d9c382-bba3-11e5-9e7f-6a04380371ce.png)\r\n\r\nBut [after the initial flip, things get funny](https://github.com/ekg/vg/blob/0675976923c8788bfd5e956b976326f430e99e9e/src/vg.cpp#L5416).\r\n\r\n```json\r\n{\"node\": [{\"sequence\": \"TACTAAAAATAC\", \"id\": 2308}, {\"sequence\": \"A\", \"id\": 2309}, {\"sequence\": \"AAAAATTAG\", \"id\": 2310}, {\"sequence\": \"TG\", \"id\": 2311}, {\"sequence\": \"CC\", \"id\": 2312}, {\"sequence\": \"GGGCGT\", \"id\": 2313}, {\"sequence\": \"G\", \"id\": 2314}, {\"sequence\": \"A\", \"id\": 2315}, {\"sequence\": \"C\", \"id\": 173}, {\"sequence\": \"G\", \"id\": 2316}, {\"sequence\": \"GAGACGGGGTTTCACCATGTT\", \"id\": 2323}, {\"sequence\": \"T\", \"id\": 171}, {\"sequence\": \"C\", \"id\": 172}, {\"sequence\": \"TACTAAAAATA\", \"id\": 174}, {\"sequence\": \"TGGC\", \"id\": 181}, {\"sequence\": \"T\", \"id\": 2317}, {\"sequence\": \"GGTCAGGCTGGTCTCGACTCC\", \"id\": 2324}, {\"sequence\": \"TC\", \"id\": 170}, {\"sequence\": \"T\", \"id\": 175}, {\"sequence\": \"C\", \"id\": 176}, {\"sequence\": \"GGTGTGG\", \"id\": 180}, {\"sequence\": \"AT\", \"id\": 182}, {\"sequence\": \"GG\", \"id\": 183}, {\"sequence\": \"GGTGTGCGCCTGTAATCCC\", \"id\": 2318}, {\"sequence\": \"TGACCTCCTGATCTGCCCCCC\", \"id\": 2325}], \"edge\": [{\"from\": 2308, \"to\": 2309}, {\"from\": 2308, \"to\": 2310}, {\"from\": 2309, \"to\": 2310}, {\"from\": 2310, \"to\": 2311}, {\"from\": 2310, \"to\": 2312}, {\"from\": 2311, \"to\": 2313}, {\"from\": 2312, \"to\": 2313}, {\"from\": 2313, \"to\": 2314}, {\"from\": 2313, \"to\": 2315}, {\"from\": 2314, \"to\": 2316}, {\"from\": 2315, \"to\": 2316}, {\"from\": 173, \"to\": 174}, {\"from\": 173, \"to\": 2308}, {\"from\": 2316, \"to\": 2317}, {\"from\": 2323, \"to\": 2324}, {\"from\": 171, \"to\": 173}, {\"from\": 172, \"to\": 173}, {\"from\": 174, \"to\": 175}, {\"from\": 174, \"to\": 176}, {\"from\": 181, \"to\": 182}, {\"from\": 181, \"to\": 183}, {\"from\": 2317, \"to\": 2318}, {\"from\": 2324, \"to\": 2325}, {\"from\": 170, \"to\": 171}, {\"from\": 170, \"to\": 172}, {\"from\": 180, \"to\": 181}]}\r\n```\r\n\r\n![screenshot from 2016-01-15 16-16-45](https://cloud.githubusercontent.com/assets/145425/12358071/62d3bb2c-bba3-11e5-987d-3defdb75e84b.png)\r\n\r\nI honestly think I hadn't thought this all the way through.\r\n\r\nHere's what I'd like:\r\n\r\nLoops and inversions get unrolled into new nodes so the graph becomes partially ordered and compatible with gssw, but still contains the same sequence space as the input up to a given length of cycle expansions --- probably on the order of a read length. The translation is recorded. Then the alignment is modified so the path points at the original nodes in their correct orientation.\r\n\r\n:tada: `VG::unroll`"},"comment":{"url":"https://api.github.com/repos/ekg/vg/issues/comments/172923315","html_url":"https://github.com/ekg/vg/issues/182#issuecomment-172923315","issue_url":"https://api.github.com/repos/ekg/vg/issues/182","id":172923315,"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},"created_at":"2016-01-19T17:17:42Z","updated_at":"2016-01-19T17:17:42Z","body":"> The algorithm creates a lot of redundant nodes, but we don't know how to merge them efficiently without creating cycles.\r\n\r\nWe can use partial order alignment to merge them without generating cycles.\r\n\r\nWe'd want to use partial order to partial order alignment to minimize runtime. I don't have an implemenation of this, and I'm not sure how easy it will be to adapt something like the original [POA](http://sourceforge.net/projects/poamsa/). Also, it might not help much in terms of removing redundancy, and further it might be very expensive even if completed in `O(log(N))` steps for N sequences. It could still be useful if it were cached for the entire graph during the indexing step."}}