Peter Kovac, Brona Brejova, Tomas Vinar.
Aligning Sequences with Repetitive Motifs.
In Information Technologies - Applications and Theory (ITAT),
pp. 41-48, 2012. Best paper award.
Preprint, 618Kb | Download from publisher | BibTeX
Pairwise sequence alignment is among the most intensively studied problems in computational biology. We present a method for alignment of two sequences con- taining repetitive motifs. This is motivated by biological studies of proteins with zinc finger domain, an important group of regulatory proteins. Due to their evolutionary his- tory, sequences of these proteins contain a variable number of different zinc fingers (short subsequences with specific symbols at each position). Our algorithm uses two types of hidden Markov models (HMM): pair HMMs and profile HMMs. Profile HMMs describe the structure of sequence motifs. Pair HMMs as- sign a probability to alignment of two motifs. Combination of the these two types of models yields an algorithm that uses different score when aligning conserved vs. variable motif residues. The dynamic programming algorithm that computes the motif alignments is based on the well known Viterbi algorithm. We evaluated our model on sequences of zinc finger proteins and compared it with existing alterna- tives.