Aarhus University Seal / Aarhus Universitets segl

Engineering of Algorithms for Hidden Markov models and Tree Distances

Research output: Book/anthology/dissertation/reportPh.D. thesis

  • Andreas Sand, Denmark
Bioinformatics is an interdisciplinary scientific field that combines biology with
mathematics, statistics and computer science in an effort to develop computational
methods for handling, analyzing and learning from biological data.
In the recent decades, the amount of available biological data has grown exponentially
because of drastic improvements in the technology behind DNA
and RNA sequencing, and focus on the research field has increased due to its
potential to expand our knowledge about biological mechanisms and to improve
public health. There has therefore been a continuously growing demand
for software tools that can exploit the larger and larger amounts of data to
obtain more precise results. An important challenge in the development of
such tools is to improve their running times. Two ways to meet this challenge
is through optimization of the underlying algorithms and through adaptation
of the algorithms to exploit the parallel architecture of modern computers.
In this PhD dissertation, I present my work with algorithmic optimizations
and parallelizations in primarily two areas in algorithmic bioinformatics: algorithms
for analyzing hidden Markov models and algorithms for computing
distance measures between phylogenetic trees.
Hidden Markov models is a class of probabilistic models that is used in
a number of core applications in bioinformatics such as modeling of proteins,
gene finding and reconstruction of species and population histories. I show how
a relatively simple parallelization can speed up all the classical algorithms for
analyses and training of hidden Markov models. And I show how two particularly
important algorithms, the forward algorithm and the Viterbi algorithm,
can be accelerated through a reformulation of the algorithms and a somewhat
more complicated parallelization. Lastly, I show how hidden Markov models
can be trained orders of magnitude faster on a given input by rethinking the
forward algorithm such that it can automatically adapt itself to the input. Together,
these optimization have enabled us to perform analysis of full genomes
in a few minutes and thereby changed the way we work with hidden Markov
Phylogenetic trees describe the evolutionary relationship between sets of
individuals, species, genes or other biological units. When these relationships
cannot be directly observed but need to be inferred from biological data, different
reconstruction methods or different data sets will often suggest slightly
different trees. Distance measures for pairs of trees are therefore useful to measure
the incongruence between two inferred trees quantitatively and to evaluate
the predictive power of different tree reconstruction methods. I present my
contribution to the theoretically fastest set of algorithms presently available
to compute two closely related measures of tree distance, the triplet distance
and the quartet distance. And I further demonstrate that they are also the
fastest algorithms in almost all cases when tested in practice.
Original languageEnglish
PublisherDepartment of Computer Science, Aarhus University
Number of pages238
Publication statusPublished - 14 Jul 2014

See relations at Aarhus University Citationformats

ID: 79146993