How is consensus alignment for OLC assembly usually implemented?

Question

Background

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
         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.

Answer 1

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.