Computational Biology
@ Comenius University in Bratislava

Michal Nanasi, Tomas Vinar, Brona Brejova. Probabilistic approaches to alignment with tandem repeats. Algorithms for Molecular Biology, 9(1):3. 2014. Early version appeared in WABI 2013.

Download preprint: not available

Download from publisher: http://www.almob.org/content/9/1/3

Related web page: not available

Bibliography entry: BibTeX

See also: early version

Abstract:

BACKGROUND: Short tandem repeats are ubiquitous in genomic sequences and due to
their complex evolutionary history pose a challenge for sequence alignment tools. 
RESULTS: To better account for the presence of tandem repeats in pairwise
sequence alignments, we propose a simple tractable pair hidden Markov model that
explicitly models their presence. Using the framework of gain functions, we design
several optimization criteria for decoding this model and describe resulting
decoding algorithms, ranging from the traditional Viterbi and posterior decoding 
to block-based decoding algorithms tailored to our model. We compare the accuracy
of individual decoding algorithms on simulated and real data and find that our
approach is superior to the classical three-state pair HMM. CONCLUSIONS: Our study
illustrates versatility of pair hidden Markov models coupled with appropriate
decoding criteria as a modeling tool for capturing complex sequence features.