urbanslug / biod Goto Github PK

Add the Burrows Wheeler Transform to BioD.

Implementation plan:

• Generate the burrows wheeler matrix
• Add support for LF-mapping
• Implement run length encoding on the suffix array
• Reverse the burrows-wheeler transform

Add a template for standardizing the reporting of issues the repository.
Add templates for:

• Bug report
• Feature request

Is your feature request related to a problem? Please describe

We should have graph support in BioD but we don't yet.

Describe the solution you'd like

Implement a graph as an adjacency matrix

Describe alternatives you've considered

Implementing a graph as an adjacency list

Because the adjacency-list representation provides a compact way to represent sparse graphs—those for which |E| is much less than |V|2—it is usually the method of choice. Most of the graph algorithms presented in this book assume that an input graph is represented in adjacency- list form. We may prefer an adjacency-matrix representation, however, when the graph is dense—|E| is close to |V|2—or when we need to be able to tell quickly if there is an edge connecting two given vertices.[1]

Implementation plan

• Add a Struct representation of a vertex V with the properties:
  • Base
  • ID
• Represent the edges as a matrix

Additional context

We'd like to build various graph traversal methods on top of this.

References

1. CLRS Introduction To Algorithms

There are really no usage docs of BioD.

Describe the solution you'd like

Some examples of usage of BioD in Markdown or some other format that isn't code examples.

Describe alternatives you've considered

• Following the documentation on the usage which leads to example D source files. I found it hard to understand without help.

Additional context

It would be nice if there was a single compiled library of BioD without having to refer to where BioD source code is.

Is your feature request related to a problem? Please describe

BioD needs to have variant graph support

Describe the solution you'd like

To add both graph representation (nodes and edges) as well as indexing on the nodes.

Describe alternatives you've considered

Implementing the graph and indexing myself and not importing C++ libs but that didn't seem like a smart idea because it would take too much time.

Additional context

There is still quite a bit of figuring out in the area as evidenced by work on odgi and xg.

Implementation plan

• Use https://github.com/jltsiren/gbwt for indexing
• Use https://github.com/vgteam/xg for building out the vairant graph
• [ ]