Global Suboptimal Pairwise Sequence Alignment in Linear Space Using Pair Hidden Markov Models

摘要

Global pairwise sequence alignment is an important tool in many bioinformatics applications. There are two main approaches for pairwise sequence alignment: the standard dynamic programming approach and the statistical alignment approach based on pair Hidden Markov models (HMM). Standard algorithms implementing both approaches suffer from the high storage demands needed to save the backtracking pointers needed to obtain the actual sequence alignment. There are several alternative algorithms that deal with the storage demands such as the alignment in linear space or using divideand-conquer methods. However, these methods either do not provide the actual alignment or increase the implementation complicity. In this paper, we present a new technique for global sequence alignment based on combining the linear space implementation and Pair Hidden Markov models. We demonstrate how the proposed method can be applied to global pairwise alignment of DNA sequences, in addition to obtaining an approximate pair HMM for the two sequences. Since the traceback step does not exist in proposed approach, it may find application in the alignment of large biological sequences.