# How is consensus alignment for OLC assembly usually implemented?

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

• 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. Jan 15, 2019 at 18:58