Publication details

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

Abstract

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.