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