Answers.Body: <p>For short reads, mainstream assemblers don't have a consensus step. The contig path directly spells the consensus sequence.</p>
  
  <p>For long reads, the most popular way to derive a consensus is via partial-order alignment (POA). This is used by error correctors (similar to consensus) like pbdagcon and falcon_sense, and consensus tools like canu, racon, wtdbg2 and nanopolish. Basically, you start with an empty directed acyclic graph (DAG), align each read in turn to the graph and augment the DAG by inserting unaligned segments. When you align all reads onto the DAG, the most weighted path is taken as the consensus. You should read <a href="http://simpsonlab.github.io/2015/05/01/understanding-poa/" rel="nofollow noreferrer">Jared Simpson's blog</a> on this topic. It is much more detailed than "basically". You should also read the papers on all the mentioned tools above if you want to implement by yourself.</p>
  
  <p>An alternative approach is Gene Myers' realigner (<a href="http://myerslab.mpi-cbg.de/wp-content/uploads/2014/06/realigner.pdf" rel="nofollow noreferrer">PDF here</a>). It is not often used, though.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-16T02:05:21.090Z
Answers.LastActivityDate: 2019-01-16T02:05:21.090Z
Answers.UserDisplayName: user172818
Body: <h2>Background</h2>
  
  <p>In C++ I want to implement a simple class that performs <a href="http://www.cs.jhu.edu/~langmea/resources/lecture_notes/assembly_olc.pdf" rel="nofollow noreferrer">overlap layout consensus assembly</a> but I can not figure out the most logical data structure to use for the consensus alignment step. </p>
  
  <p><a href="https://ocw.mit.edu/courses/biology/7-91j-foundations-of-computational-and-systems-biology-spring-2014/lecture-slides/MIT7_91JS14_Lecture6.pdf" rel="nofollow noreferrer">This is the step where all of the reads from the overlap graph are aligned and the consensus is called (slide 48)</a>. An example alignment is below. Asterisks above the column indicate some disagreement among all reads. Alignment position is shown above and below for convenience.</p>
  
  <pre><code>                         *    * *         *
       pos           111111111122222222223333333333444
           0123456789012345678901234567890123456789012
  read 1   TAGATTACACAGATTACTGAT TGA
  read 2      ATTACACAGATTACTGACTTGATG CGTAAACTA
  read 3                   tTGACTTcATGGCGTAA CTA
  read 4                     GACTTGATGGCGTAA CTAAG
  read 5                           ATGGCGTAA CTAAGATCG
       pos           111111111122222222223333333333444
           0123456789012345678901234567890123456789012
  </code></pre>
  
  <h2>Question:</h2>
  
  <p><strong>Q1:</strong> What is the most logical way to implement the consensus alignment step in a OLC assembler? </p>
  
  <p><strong>Q2:</strong> What are the pros and cons of this and other possibilities?</p>
  
  <h2>Ideas</h2>
  
  <h3>Idea - Vector of vectors. One column per position.</h3>
  
  <p>My initial idea for a data structure to store the alignment is to use one vector per read to store the read's character at that position. We would end up with j arrays (number of reads) all of length i (the total length of the overlapped alignments). This, however, would be space-inefficient if the locus were large and many positions in the vectors would contain a null value. In the example alignment above the first 23 positions of read 5 would be null values.</p>
  
  <h3>Idea - Graph. One node per position.</h3>
  
  <p>In another implementation idea, each position in the alignment would be represented by a node in a directed graph. Each node would have a property keeping track of the nucleotide counts at each position and might keep the read id's stored as well if there is a good reason to do so. </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-15T18:58:26.827Z
Comments.Text: Implementing data structures and algorithms from scratch is a great way to build understanding and intuition. But if your goal is to create production-ready software, you may consider API calls to a mature third-party library such as [fermi-lite](https://github.com/lh3/fermi-lite).
Comments.UserDisplayName: Daniel Standage
Tags: <assembly><algorithms><c++>
Title: How is consensus alignment for OLC assembly usually implemented?
ThreadText: # How is consensus alignment for OLC assembly usually implemented?
  
  (Asked by: username_0 on 2019-01-15)
  
  ## Background
  
  In C++ I want to implement a simple class that performs [overlap layout consensus assembly](http://www.cs.jhu.edu/~langmea/resources/lecture_notes/assembly_olc.pdf) but I can not figure out the most logical data structure to use for the consensus alignment step.
  
  [This is the step where all of the reads from the overlap graph are aligned and the consensus is called (slide 48)](https://ocw.mit.edu/courses/biology/7-91j-foundations-of-computational-and-systems-biology-spring-2014/lecture-slides/MIT7_91JS14_Lecture6.pdf). An example alignment is below. Asterisks above the column indicate some disagreement among all reads. Alignment position is shown above and below for convenience.
  
  ```
                           *    * *         *
       pos           111111111122222222223333333333444
           0123456789012345678901234567890123456789012
  read 1   TAGATTACACAGATTACTGAT TGA
  read 2      ATTACACAGATTACTGACTTGATG CGTAAACTA
  read 3                   tTGACTTcATGGCGTAA CTA
  read 4                     GACTTGATGGCGTAA CTAAG
  read 5                           ATGGCGTAA CTAAGATCG
       pos           111111111122222222223333333333444
           0123456789012345678901234567890123456789012
  
  ```
  
  ## Question:
  
  **Q1:** What is the most logical way to implement the consensus alignment step in a OLC assembler?
  
  **Q2:** What are the pros and cons of this and other possibilities?
  
  ## Ideas
  
  ### Idea - Vector of vectors. One column per position.
  
  My initial idea for a data structure to store the alignment is to use one vector per read to store the read's character at that position. We would end up with j arrays (number of reads) all of length i (the total length of the overlapped alignments). This, however, would be space-inefficient if the locus were large and many positions in the vectors would contain a null value. In the example alignment above the first 23 positions of read 5 would be null values.
  
  ### Idea - Graph. One node per position.
  
  In another implementation idea, each position in the alignment would be represented by a node in a directed graph. Each node would have a property keeping track of the nucleotide counts at each position and might keep the read id's stored as well if there is a good reason to do so.
  
  **Tags:** assembly, algorithms, c++
  
  > **Comments:**
  > **username_1**: Implementing data structures and algorithms from scratch is a great way to build understanding and intuition. But if your goal is to create production-ready software, you may consider API calls to a mature third-party library such as [fermi-lite](https://github.com/lh3/fermi-lite).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-01-16. Score: 2 | Accepted answer
  
  For short reads, mainstream assemblers don't have a consensus step. The contig path directly spells the consensus sequence.
  
  For long reads, the most popular way to derive a consensus is via partial-order alignment (POA). This is used by error correctors (similar to consensus) like pbdagcon and falcon\_sense, and consensus tools like canu, racon, wtdbg2 and nanopolish. Basically, you start with an empty directed acyclic graph (DAG), align each read in turn to the graph and augment the DAG by inserting unaligned segments. When you align all reads onto the DAG, the most weighted path is taken as the consensus. You should read [Jared Simpson's blog](http://simpsonlab.github.io/2015/05/01/understanding-poa/) on this topic. It is much more detailed than "basically". You should also read the papers on all the mentioned tools above if you want to implement by yourself.
  
  An alternative approach is Gene Myers' realigner ([PDF here](http://myerslab.mpi-cbg.de/wp-content/uploads/2014/06/realigner.pdf)). It is not often used, though.
  
  
  ---
  
  