{"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":"graphs must be unrolled to align with POA (was: 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":7,"created_at":"2016-01-15T16:22:53Z","updated_at":"2016-01-22T12:12:12Z","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/173901585","html_url":"https://github.com/ekg/vg/issues/182#issuecomment-173901585","issue_url":"https://api.github.com/repos/ekg/vg/issues/182","id":173901585,"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-22T12:12:12Z","updated_at":"2016-01-22T12:12:12Z","body":"Note that the example shows the unrolling for the entire graph, not just the strongly connected component."}}