Rapidly evolving viruses, such as HIV, can exist as very diverse populations, even within a single host, with each virus particle having a potentially different genome. The details of these populations can have medical relevance, contributing to our understanding of phenomena such as viral transmission dynamics between hosts, evolution to escape anti-viral therapy, evolution in response to the host immune system, and more.

 

One state-of-the-art window into these populations is next generation sequencing, which, in a very high-throughput manner, converts physical DNA into digital read-outs of the input gene sequences, listing the individual nucleotides (A, C, G or T) that comprise the DNA strands. For our purposes, we will be considering data from targeted viral gene sequencing, which proceeds by first isolating the viral particles, and then amplifying the genomic region of interest, which makes multiple DNA copies of each initial viral template sequence. This amplified DNA is then fed into the sequencer, generating the digital sequences.

 

This is where the trouble begins. Because of the DNA amplification process, there are many more sequences than there were initial viral particles. Furthermore, there are too many sequence reads for the kinds of analyses that we typically want to conduct. Finally, each sequence read is noisy, containing sequencing errors, which can be simply incorrect nucleotides, or, more problematically, inserted or deleted nucleotides.

 

See more background at: http://en.wikipedia.org/wiki/Multiple_sequence_alignment and http://en.wikipedia.org/wiki/Phylogenetics