{"action":"created","issue":{"url":"https://api.github.com/repos/ga4gh/schemas/issues/275","labels_url":"https://api.github.com/repos/ga4gh/schemas/issues/275/labels{/name}","comments_url":"https://api.github.com/repos/ga4gh/schemas/issues/275/comments","events_url":"https://api.github.com/repos/ga4gh/schemas/issues/275/events","html_url":"https://github.com/ga4gh/schemas/issues/275","id":65932382,"number":275,"title":"graph subsetting operations and serialization format","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":10,"created_at":"2015-04-02T13:59:39Z","updated_at":"2015-04-03T14:10:48Z","closed_at":null,"body":"I'd like to query a part of the graph using coordinates against an arbitrary reference path encoded in it.\r\n\r\nI have a implementation of this kind of feature that can serve as a conceptual starting point. In `vg` you'd do this like `vg find -n 314159 -c 10 x.vg >q.vg`, and q.vg would then contain a subgraph with all nodes and edges reached in a breadth first search of 10 steps starting at node 314159. I use a context size defined in nodes rather than edges because it is simpler in many situations, and in practice I construct graphs with a maximum node size of 50bp using `vg construct ... -m 50`, but it seems possible to do this using an actual base distance rather than a number of steps in a BFS. You can also do `vg find -p chr19:100-200 x.vg` to get the graph overlapping a particular range in any named path that has been stored in the graph (in this case `chr19`). `vg find` can also take a specific kmer and return the subgraph associated with that kmer (which may not be fully-connected).\r\n\r\nThere are other typical operations that I've found useful when generating subsets of variation graphs, which are perhaps best summarized by the interface to `vg find`:\r\n\r\n```text\r\nusage: vg find [options] <graph.vg> >sub.vg\r\noptions:\r\n    -n, --node ID          find node, return 1-hop context as graph\r\n    -f, --edges-from ID    return edges from node with ID\r\n    -t, --edges-to ID      return edges from node with ID\r\n    -k, --kmer STR         return a graph of edges and nodes matching this kmer\r\n    -T, --table            instead of a graph, return a table of kmers\r\n    -c, --context STEPS    expand the context of the kmer hit subgraphs\r\n    -s, --sequence STR     search for sequence STR using --kmer-size kmers\r\n    -j, --kmer-stride N    step distance between succesive kmers in sequence (default 1)\r\n    -z, --kmer-size N      split up --sequence into kmers of size N\r\n    -C, --kmer-count       report approximate count of kmer (-k) in db\r\n    -p, --path TARGET      find the node(s) in the specified path range TARGET=path[:pos1[-pos2]]\r\n    -P, --position-in PATH find the position of the node (specified by -n) in the given path\r\n    -r, --node-range N:M   get nodes from N to M\r\n    -d, --db-name DIR      use this db (defaults to <graph>.index/)\r\n```\r\n\r\nMy point is that the natural way to interrogate the graph involves queries over kmers, sequences, path positions, node ids, edge ids, and node id ranges. The return from such a query should be a subgraph, and ideally one with a 1:1 mapping to components in the source graph.\r\n\r\nThings are pretty straightforward in variation graphs (as in vg). These are collections of three types of objects: (1) nodes with sequences, (2) edges between node ends representing allowed linkages, and (3) paths over nodes and edges which define coordinate systems and names. Making subsets of this structure is trivial. You just collect the nodes, connected edges, and path annotations to create a subgraph that is a strict subset of the components of the original graph.\r\n\r\nBut how do we generate subgraphs of a side graph?\r\n\r\nThere seem to be some conceptual hurdles to generating subsets from the side graph model. Useful side graph subsets are not directly equivalent to subsets of the components original side graph. If nodes are long (and some in the side graph are effectively as long as whole chromosomes) then we need to generate new synthetic nodes that start and end within those from the graph we are querying.\r\n\r\n1. As joins are defined with node-relative coordinates, then the entire coordinate system within the subgraph needs to be modified relative to the original graph in order to maintain a consistent structure.\r\n2. Alternatively, we could maintain offsets relative to the original nodes in our subgraph representation to allow mapping back into the original coordinate space.\r\n3. Yet another possibility would be to define the subset as a side graph built on the original graph. This would seem to introduce new problems by making it impossible to relate sides within this directly back to the original graph.\r\n\r\nThese are not insignificant issues. We can pick a solution among these and it will work. However, it will add nontrivial complexity to the model. Subsetting the graph is just about the most basic thing you can do, and it should not present a conceptual hurdle to users and developers.\r\n\r\nThis is not just a theoretical critique. Some months ago I began to implement (2) but stopped as it required the addition of additional fields defining relative offsets to \"real\" nodes to each component of the graph. The semantics of the graph would then change whether or not a node was in \"offset\" space. The coordination of these offsets seemed extremely likely to generate bugs. (As described above, I resolved the problem of graph subsets by breaking up the graph into pieces of a consistent maximum size.)\r\n\r\nThe side graph makes great sense to me as a way to define a coordinate system, but very little sense as the basis for the data model that's used to store, query, and transmit the graph.\r\n\r\nThere is a reasonable alternative. We can maintain a side graph coordinate system to provide distinct names for all the sequences and paths in the graph. However, this can be a purely virtual thing, in that we can allow any underlying graph structure to be returned from queries. Provided the nodes and edges in a sequence/variation graph are annotated with their coordinates in the side graph, we will get all the benefits of the side graph without the awkwardness of defining standard algorithms to manipulate it."},"comment":{"url":"https://api.github.com/repos/ga4gh/schemas/issues/comments/89300878","html_url":"https://github.com/ga4gh/schemas/issues/275#issuecomment-89300878","issue_url":"https://api.github.com/repos/ga4gh/schemas/issues/275","id":89300878,"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":"2015-04-03T14:10:48Z","updated_at":"2015-04-03T14:10:48Z","body":"@lh3 I think there is a misunderstanding. I'm saying that if you have a serialized version of a subset the side graph, you'll want to specify the source offset in the original graph, or it won't be possible to project things from the subset back into the general graph coordinate space. This offset effectively propagates across all the entities in the subgraph, whether you record it everywhere or not. I can't use the original coordinates on a subset of the graph any more than we can use the whole-genome relative coordinates when working with substrings from the reference genome. So as far as I can tell, this is in principle exactly the same as what @adamnovak is suggesting.\r\n\r\nThe difference is one of perspective. In practice \"just marking the sequence as a subsequence\" must be accounted for within each method that works with the graph entity. This adds complexity without obvious benefit. Now every element would need to have an optional offset field, or we need to have two different types of elements, one with offsets and one without."}}