Positional Statistical Significance in Sequence Alignment

Abstract

Beginning with the concept of near-optimal sequence alignments, we can assign a probability that each element in one sequence is paired in an alignment with each element in another sequence. This involves a sum over the set of all possible pairwise alignments. The method employs a designed hidden Markov model (HMM) and the rigorous forward and forward-backward algorithms of Rabiner. The approach can use any standard sequence-element-to-element probabilistic similarity measures and affine gap penalty functions. This allows the positional alignment statistical significance to be obtained as a function of such variables. A measure of the probabilistic relationship between any single sequence and a set of sequences can be directly obtained. In addition, the employed HMM with the Viterbi algorithm provides a simple link to the standard dynamic programming optimal alignment algorithms.