Sequence databases like GenBank (http://www.ncbi.nlm.nih.gov/genbank/) grew rapidly
in the 1980s, and thus performing a full dynamic programming comparison of any query
sequence to every known sequence soon became computationally very costly. Consequently,
the alignment of a query sequence against a database motivated the development of a
heuristic algorithm [1], which was implemented in the FASTA program suite [2]. The
basic principle of this algorithm is to exclude large parts of the database from the expensive
dynamic programming comparison by quickly identifying candidate sequences that share
short sections (k-tuples) of very similar sequence with the query. FASTA was then followed
by the BLAST program [3], with additional speed advantages and a new feature, which
estimates the statistical likelihood that each matching sequence had been found by chance.
BLAST is still one of the most used search program for biological sequence databases [4].
With the introduction of ultra-high-throughput sequencing technologies in 2007, other
alignment challenges emerged. This chapter describes these efforts and the current state of
the art in NGS alignment algorithms. Computational biologists have developed more than 70
read mapping to date [5]. A full list of sequence alignment software tools can be found at
https://en.wikipedia.org/wiki/List_of_sequence_alignment_software#Short-Read_
Sequence_Alignment. Actually, describing all of these tools is beyond the scope of this
chapter, however main algorithmic strategies of these tools are depicted below.
Sequence alignment (Fig. 9.1) is widely used in molecular biology to find similar DNA,
RNA, or protein sequences. These algorithms generally fall into two categories: global
(Needleman–Wunsch), which aligns the entire sequence, and local (Smith–Waterman),
which only look for highly similar subsequences.
9.2.1 Global Alignment (Needleman–Wunsch Algorithm)
Statistically the space for possible solutions is huge; however, we are interested in optimal
alignments with minimal errors like indels or mismatches. The so-called unit edit distance
(edist) is the number of mismatches, insertions, and deletions in an optimal sequence
alignment. The main aim is to minimize the edist by tabulating partial solutions in a (m
Fig. 9.1 Alignment definition. Sequence alignment is a way of arranging the sequences of DNA,
RNA, or protein to identify regions of similarity. The basic principle is comparable to a puzzle (left).
An optimal alignment means, an alignment with minimal errors like deletions, insertions, or
mismatches—no error is defined as a match (right)
9 Alignment
113
in the 1980s, and thus performing a full dynamic programming comparison of any query
sequence to every known sequence soon became computationally very costly. Consequently,
the alignment of a query sequence against a database motivated the development of a
heuristic algorithm [1], which was implemented in the FASTA program suite [2]. The
basic principle of this algorithm is to exclude large parts of the database from the expensive
dynamic programming comparison by quickly identifying candidate sequences that share
short sections (k-tuples) of very similar sequence with the query. FASTA was then followed
by the BLAST program [3], with additional speed advantages and a new feature, which
estimates the statistical likelihood that each matching sequence had been found by chance.
BLAST is still one of the most used search program for biological sequence databases [4].
With the introduction of ultra-high-throughput sequencing technologies in 2007, other
alignment challenges emerged. This chapter describes these efforts and the current state of
the art in NGS alignment algorithms. Computational biologists have developed more than 70
read mapping to date [5]. A full list of sequence alignment software tools can be found at
https://en.wikipedia.org/wiki/List_of_sequence_alignment_software#Short-Read_
Sequence_Alignment. Actually, describing all of these tools is beyond the scope of this
chapter, however main algorithmic strategies of these tools are depicted below.
Sequence alignment (Fig. 9.1) is widely used in molecular biology to find similar DNA,
RNA, or protein sequences. These algorithms generally fall into two categories: global
(Needleman–Wunsch), which aligns the entire sequence, and local (Smith–Waterman),
which only look for highly similar subsequences.
9.2.1 Global Alignment (Needleman–Wunsch Algorithm)
Statistically the space for possible solutions is huge; however, we are interested in optimal
alignments with minimal errors like indels or mismatches. The so-called unit edit distance
(edist) is the number of mismatches, insertions, and deletions in an optimal sequence
alignment. The main aim is to minimize the edist by tabulating partial solutions in a (m
Fig. 9.1 Alignment definition. Sequence alignment is a way of arranging the sequences of DNA,
RNA, or protein to identify regions of similarity. The basic principle is comparable to a puzzle (left).
An optimal alignment means, an alignment with minimal errors like deletions, insertions, or
mismatches—no error is defined as a match (right)
9 Alignment
113