title: Sequence alignment as hypothesis testing.
abstract: Sequence alignment depends on the scoring function that defines similarity between pairs of letters. For local alignment, the computational algorithm searches for the most similar segments in the sequences according to the scoring function. The choice of this scoring function is important for correctly detecting segments of interest. We formulate sequence alignment as a hypothesis testing problem, and conduct extensive simulation experiments to study the relationship between the scoring function and the distribution of aligned pairs within the aligned segment under this framework. We cut through the many ways to construct scoring functions and showed that any scoring function with negative expectation used in local alignment corresponds to a hypothesis test between the background distribution of sequence letters and a statistical distribution of letter pairs determined by the scoring function. The results indicate that the log-likelihood ratio scoring function is statistically most powerful and has the highest accuracy for detecting the segments of interest that are defined by the statistical distribution of aligned letter pairs.
authors.affiliation: MOE Key Lab of Bioinformatics and Bioinformatics Division of TNLIST/Department of Automation, Tsinghua University, Beijing, P.R. China.
authors.forename: Lu
authors.initials: L
authors.lastname: Meng
authors.forename: Fengzhu
authors.initials: F
authors.lastname: Sun
authors.forename: Xuegong
authors.initials: X
authors.lastname: Zhang
authors.forename: Michael S
authors.initials: MS
authors.lastname: Waterman
mesh_terms: D000465:Algorithms; D016013:Likelihood Functions; D008433:Mathematics; D008962:Models, Theoretical; D016415:Sequence Alignment