Gapless alignment revisited

The purpose of sequence alignment is to detect mutual similarity, characterized by the so-called "alignment score", between sequences compared. To quantitatively assess the confidence level of an alignment result requires the knowledge of alignment score statistics under a certain null model and is the central issue in sequence alignment. In this thesis, the score statistics of Markov null model were revisited and the score statistics of non-Markov null model were investigated for two state-of-the-art algorithms, namely, the gapless Smith-Waterman and Hybrid algorithms. These two algorithms were further used to find highly related signals in unrelated sequences and in weakly related sequences corresponding, respectively, to Markov null model and non-Markov null model. The confidence levels of these models were also studied. Since the sequence similarity we are interested in comes from evolutionary history, we also investigated the relationship between sequence alignment, the tool to find similarity, and evolution. The average evolution distance between the daughter sequences was found and compared with their expected values, for individual trees and as an average over many trees.