{"action":"created","issue":{"url":"https://api.github.com/repos/GFA-spec/GFA-spec/issues/49","repository_url":"https://api.github.com/repos/GFA-spec/GFA-spec","labels_url":"https://api.github.com/repos/GFA-spec/GFA-spec/issues/49/labels{/name}","comments_url":"https://api.github.com/repos/GFA-spec/GFA-spec/issues/49/comments","events_url":"https://api.github.com/repos/GFA-spec/GFA-spec/issues/49/events","html_url":"https://github.com/GFA-spec/GFA-spec/issues/49","id":178937362,"number":49,"title":"The future of the GFA format","user":{"login":"lh3","id":480346,"avatar_url":"https://avatars.githubusercontent.com/u/480346?v=3","gravatar_id":"","url":"https://api.github.com/users/lh3","html_url":"https://github.com/lh3","followers_url":"https://api.github.com/users/lh3/followers","following_url":"https://api.github.com/users/lh3/following{/other_user}","gists_url":"https://api.github.com/users/lh3/gists{/gist_id}","starred_url":"https://api.github.com/users/lh3/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lh3/subscriptions","organizations_url":"https://api.github.com/users/lh3/orgs","repos_url":"https://api.github.com/users/lh3/repos","events_url":"https://api.github.com/users/lh3/events{/privacy}","received_events_url":"https://api.github.com/users/lh3/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/GFA-spec/GFA-spec/labels/question","name":"question","color":"cc317c"}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":15,"created_at":"2016-09-23T17:58:55Z","updated_at":"2016-09-26T04:42:13Z","closed_at":null,"body":"CC @thegenemyers, @richarddurbin, @ekg, @rrwick, @sjackman, @jts, @pb-jchin, @skoren, @aphillippy, @MihaiPop, @ggonnella, @pmelsted, @edawson\r\n\r\n## The current status of GFA1\r\n\r\nThere were two general-purpose assembly formats: [FASTG](http://fastg.sourceforge.net/) and GFA1. With David Jaffe et al's SuperNova assembler apparently [moving away from FASTG](http://support.10xgenomics.com/de-novo-assembly/software/pipelines/1.1/output/graphs), GFA1 is practically the only generic assembly format. I have [written converters](https://github.com/lh3/gfatools) for ABySS, SGA, Velvet, Spades, SOAPdenovo and fermi short-read assemblers. @jts's SGA and @sjackman's ABySS natively support GFA1 output, I believe. @jts's [fork of DALIGNER](https://github.com/jts/DALIGNER) can emit GFA1. @pb-jchin has [written a converter](https://github.com/PacificBiosciences/FALCON/wiki/Convert-FALCON-assembly-graph-to-GFA-format) for FALCON. My miniasm and fermi-lite assemblers output GFA. I believe the vast majority of mainstream assemblers are compatible with GFA1, too. For tools working with variations, @ekg's vg supports GFA output and has an internal data representation conceptually equivalent to GFA1 (vg effectively implements a bidirected graph). SuperNova graph can be converted to GFA1 (not implemented yet). [DISCOVAR](https://software.broadinstitute.org/software/discovar/blog/) outputs FASTG which can also be converted to GFA in principle (not implemented, either). As to tools consuming GFA, @rrwick's Bandage can visualize GFA graphs. I have written [gfaview](https://github.com/lh3/gfaview) to perform graph transformation (e.g. transitive reduction, tip trimming and bubble popping) for long-read graphs. @sjackman has implemented similar transformations for short-read graphs in ABySS. There are already a few libraries in [C++](https://github.com/edawson/gfakluge) and [Ruby](https://github.com/ggonnella/RGFA) to read GFA1. In conclusion, GFA1 is getting used. It is fairly simple yet general enough for all the tools and applications mentioned above.\r\n\r\n## About GFA2\r\n\r\n### The necessity\r\n\r\nGFA2 was proposed because GFA1 does not work when we choose a path at a fork to merge. This leaves an end-to-internal match, which can't be described by GFA1. A few other hypothetical use cases (e.g. alignment between two long haplotypes) have also been raised. So far, I am not sure which implementations output and, more importantly, consume end-to-internal or internal-to-internal matches (NB: containment is a special case of end-to-internal alignment, but it can be described with GFA1). I am happy to update this post if there are any.\r\n\r\n### The GFA2 graph representation\r\n\r\nWhile GFA1 models a directed [skew-symmetric graph](https://en.wikipedia.org/wiki/Skew-symmetric_graph) that is topologically equivalent to bidirected graphs, overlap graphs and string graphs, GFA2 models an undirected multi-graph where mapping coordinates are playing a central role. They represent fundamentally different types of graphs. Although we can see GFA1 as a special case of GFA2, how to understand the graph will be distinct. GFA2 will also have more complex syntax and implementations for what GFA1 is really good at.\r\n\r\n### My take\r\n\r\nSAM/BAM is popular not only because they can store alignments, but more because they enable us to do things to the alignments that would be complex otherwise. Similarly, I see GFA is not just a storage format; it should be a format that helps our analysis. Due to the lack of clear downstream use cases and implementations of GFA2 (e.g. what information do we want to extract from GFA2? how to?), I am unable to evaluate the necessity of the added complexity, especially given that vg and SuperNova can already achieve part of the GFA2 goal with the GFA1 representation only. I am reluctant to add unproven features too early.\r\n\r\n## The future of GFA\r\n\r\nAs the creator of the initial GFA1, I do not see GFA2 is ready to replace GFA1. I foresee the coexistence of GFA1 and GFA2 for a period of time. During this period, developers have to make a choice between GFA1 and GFA2. We may re-evaluate the necessity of GFA2 yearly. I will be happy to phase out GFA1 if GFA2 is proven to be useful with concrete and practical applications. I understand the split is unfortunate, but this seems an unavoidable cost when we explore the unknowns.\r\n\r\n### The future of GFA1\r\n\r\nThe current GFA1 spec was modified from a blog post. I would like to replace it with something a little more formal like [the one here](https://github.com/lh3/gfaview/blob/master/gfa2-ideas.md), with further improvements of course.\r\n\r\nI also want to ask developers on the CC list: how much do CIGAR on L-lines and the lack of segment length on S-lines hurt? Personally, I would really like to change the format, but if you all think you can live with these issues, I am ok to keep them as they are. Once we reach a consensus on this issue, we will try best to maintain the compatibility of GFA1 going forward. We may have new line types, but we don't break existing lines."},"comment":{"url":"https://api.github.com/repos/GFA-spec/GFA-spec/issues/comments/249478182","html_url":"https://github.com/GFA-spec/GFA-spec/issues/49#issuecomment-249478182","issue_url":"https://api.github.com/repos/GFA-spec/GFA-spec/issues/49","id":249478182,"user":{"login":"sjackman","id":291551,"avatar_url":"https://avatars.githubusercontent.com/u/291551?v=3","gravatar_id":"","url":"https://api.github.com/users/sjackman","html_url":"https://github.com/sjackman","followers_url":"https://api.github.com/users/sjackman/followers","following_url":"https://api.github.com/users/sjackman/following{/other_user}","gists_url":"https://api.github.com/users/sjackman/gists{/gist_id}","starred_url":"https://api.github.com/users/sjackman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sjackman/subscriptions","organizations_url":"https://api.github.com/users/sjackman/orgs","repos_url":"https://api.github.com/users/sjackman/repos","events_url":"https://api.github.com/users/sjackman/events{/privacy}","received_events_url":"https://api.github.com/users/sjackman/received_events","type":"User","site_admin":false},"created_at":"2016-09-26T04:42:13Z","updated_at":"2016-09-26T04:42:13Z","body":"Hi, Richard.\r\n\r\n> Clearly for both GFA1 and GFA2 the vertices v are segments, and the function σ(v) maps a segment to its reverse complement, which statisfies properties 1 and 2.\r\n\r\nA vertex in GFA1 is not a segment, but a two-tuple of a segment ID and an orientation, for example, (A, +), which is shortened to simply A+ for convenience. σ(A+) = A-, and σ(A-) = A+ . Each segment is associated with two vertices in the SSG.\r\n\r\nIn a Boolean logic implication graph, a type of skew-symmetric graph, each Boolean variable has two vertices associated with it: \"This graph has a vertex for each variable or negated variable\" from https://en.wikipedia.org/wiki/Skew-symmetric_graph#Satisfiability In GFA1, each segment has two vertices associated with it.\r\n\r\n> For GFA1 the edges are defined as links, and in GFA2 we just call them edges.  For both GFA1 and GFA2 we allow multiple directed edges from node u to node v. For GFA1 we can have 4 types of link between u and v, from the + or - end of u to the + or - end of v.\r\n\r\nWhere each vertex is a tuple of a segment and orientation, only two edges between two vertices u and v are possible.\r\n\r\nu -> v\r\nv -> u\r\n\r\nVery import is that u -> v and u -> σ(v) are different edges between different vertices. If this were not true, GFA1 would be a multigraph.\r\n\r\n> More than one of these types can exist within the same graph, which makes GFA1 mathematically a multigraph.\r\n\r\nGFA1 is a strict directed graph, not a multigraph. A+ and A- are distinct vertices. σ(u) maps u to a different vertex. σ(A+) = A-, and A+ and A- are different vertices, that happen to be associated with the same segment A.\r\n\r\nA+ -> R+\r\nA+ -> R-\r\n\r\nis not a multigraph, because R+ and R- are different vertices.\r\n\r\n> (This assumes that you don’t allow multiple different link lines between the same pair of nodes with the same +/- but different overlap numbers, in which case there would be many more possible edges.) \r\n\r\nI'm making the same assumption.\r\n\r\nCheers,\r\nShaun"}}
{"actor":{"display_login":"sjackman"}}