assembly-graph.txt 816 Bytes
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
The assembly graph
------------------

|Orgasm| rely on a graph representation of the ongoing assembly. The graph used is what is
called a `De Bruijn graph <https://en.wikipedia.org/wiki/De_Bruijn_graph>`_ but restricted 
to nodes representing substrings of a given length of the genome to reconstruct. 


.. figure:: ./graph.*
  :align: center
  :figwidth: 80 %
  :width: 500

  An example of the underlying graph (adapted from `Compeau et al. (2011) <http://www.nature.com/nbt/journal/v29/n11/full/nbt.2023.html>`_)


In our particular case, we work with words of the length of the reads produced by the shotgun
sequencing. So the graph is also what is called a string graph for our set of reads (see
`Meyers (2005) <http://bioinformatics.oxfordjournals.org/content/21/suppl_2/ii79.abstract>`_
for details).