Mathematical Understanding of Sequence Alignment and Phylogenetic Algorithms: A Comprehensive Review of Computation of Different Methods

Abstract

Pairwise sequence alignment is one of the ways to position two biological sequences to identify regions of similarity that may suggest the functional, structural and evolutionary relationship among proteins and nucleic acids. There are two strategies in pairwise alignment: local sequence alignment (Smith Waterman algorithm) and global sequence alignment (Needleman Wunsch algorithm). In the prior approach, two sequences that may or may not be related, are aligned to find regions of local similarities in large sequences, whereas in the later one, two sequences of same length are aligned to identify their conserved regions. Moreover, similarities and divergence between biological sequences also has to be rationalized and visualized in the form of phylogenetic trees, so the dendrogram construction approaches were developed and divided into distance-based and character-based methods. In this review article, different algorithms of sequence alignment and phylogenetic tree construction were meditated with examples and compared by looking into the background computation for the better understanding of the algorithms, which will be helpful for molecular biology, computational sciences and mathematics/statistics novices. Phylogenetic trees are constructed through various methods, some are computationally robust but does not provide precise evolutionary insight, whereas some provide accurate evolutionary understandings, but computationally exhaustive and cumbersome. So, there is a need to understand the implicit mathematics and intricate computation behind the dendrogram construction for improving the existing algorithms and developing new methods.  

Keywords: Local sequence alignment; Global sequence alignment; UPGMA; Neighbour joining; Fitch Margoliash; Maximum-Parsimony; Maximum-Likelihood