In C++ I want to implement a simple class that performs overlap layout consensus assembly 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). 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
read 3                   tTGACTTcATGGCGTAA CTA
read 4                     GACTTGATGGCGTAA CTAAG
read 5                           ATGGCGTAA CTAAGATCG
     pos           111111111122222222223333333333444


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?


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.

  • $\begingroup$ 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. $\endgroup$ – Daniel Standage Jan 15 '19 at 18:58

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 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). It is not often used, though.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.