Algorithms for Strings and Sequences: Pairwise Alignment

Pairwise alignment between two biological sequences, like DNA, RNA, or proteins, is a classical and well studied problem in bioinformatics. This latter problem can be found indeed in many biological analyses such as those involving data coming from sequencing processes. In this contribution we will formalize the computational problem, and we will present its two most common variants, that is global and the local alignment. More precisely, we will describe the dynamic programming algorithm proposed by Needleman and Wunsch for finding an optimal global pairwise alignment of two strings with respect to a given scoring function, and the algorithm proposed by Smith and Waterman for the local version. We will provide the details of both the algorithms and some examples showing their application in reconstructing optimal alignments. Finally, we will also discuss some scoring functions that are used in practice to deal with the pairwise alignment of biological sequences.