Applications of generalized pair hidden Markov models to alignment and gene finding problems

Hidden Markov models (HMMs) have been successfully applied to a variety of problems in molecular biology, ranging from alignment problems to gene � nding and annotation. Alignment problems can be solved with pair HMMs, while gene � nding programs rely on generalized HMMs in order to model exon lengths. In this paper, we introduce the generalized pair HMM (GPHMM), which is an extension of both pair and generalized HMMs. We show how GPHMMs, in conjunction with approximate alignments, can be used for cross-species gene � nding and describe applications to DNA–cDNA and DNA–protein alignment. GPHMMs provide a unifying and probabilistically sound theory for modeling these problems. Key words: hidden Markov model, alignment, gene � nding, comparative genomics. 1