Andreas Sand

Mr. Andreas Sand


Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
22 November 2013 in BMC Bioinformatics
Verified
Journal Article
Open access
PDF file
ASAndreas Sand
Andreas Sand
MKMartin Kristiansen
Martin Kristiansen
CPChristian Nørgaard Storm Pedersen
Christian Nørgaard Storm Pedersen
TMThomas Mailund
Thomas Mailund
Hidden Markov models are widely used for genome analysis as they combine ease of modelling with efficient analysis algorithms. Calculating the likelihood of a model using the forward algorithm has worst case time complexity linear in the length of the sequence and quadratic in the number of states in the model. For genome analysis, however, the length runs to millions or billions of observations, and when maximising the likelihood hundreds of evaluations are often needed. A time efficient forward algorithm is therefore a key ingredient in an efficient hidden Markov model library.

26 September 2013 in Biology
Verified
Journal Article
Open access
PDF file
ASAndreas Sand
Andreas Sand
MHMorten K. Holt
Morten K. Holt
JJJens Johansen
Jens Johansen
RFRolf Fagerberg
Rolf Fagerberg
GBGerth Stølting Brodal
Gerth Stølting Brodal
TMThomas Mailund
Thomas Mailund
Distance measures between trees are useful for comparing trees in a systematic manner, and several different distance measures have been proposed. The triplet and quartet distances, for rooted and unrooted trees, respectively, are defined as the number of subsets of three or four leaves, respectively, where the topologies of the induced subtrees differ. These distances can trivially be computed by explicitly enumerating all sets of three or four leaves and testing if the topologies are different, but this leads to time complexities at least of the order n3 or n4 just for enumerating the sets. The different topologies can be counte dimplicitly, however, and in this paper, we review a series of algorithmic improvements that have been used during the last decade to develop more efficient algorithms by exploiting two different strategies for this; one based on dynamic programming and another based oncoloring leaves in one tree and updating a hierarchical decomposition of the other.

21 January 2013 in BMC Bioinformatics
Verified
Journal Article
Open access
PDF file
ASAndreas Sand
Andreas Sand
GBGerth Stølting Brodal
Gerth Stølting Brodal
RFRolf Fagerberg
Rolf Fagerberg
CPChristian Nørgaard Storm Pedersen
Christian Nørgaard Storm Pedersen
TMThomas Mailund
Thomas Mailund
The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n 2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.

8 November 2013 in Biology
Verified
Journal Article
Open access
PDF file
PTPaula Tataru
Paula Tataru
ASAndreas Sand
Andreas Sand
AHAsger Hobolth
Asger Hobolth
TMThomas Mailund
Thomas Mailund
CPChristian Nørgaard Storm Pedersen
Christian Nørgaard Storm Pedersen
Hidden Markov Models (HMMs) are widely used probabilistic models, particularly for annotating sequential data with an underlying hidden structure. Patterns in the annotation are often more relevant to study than the hidden structure itself. A typical HMM analysis consists of annotating the observed data using a decoding algorithm and analyzing the annotation to study patterns of interest. For example, given an HMM modeling genes in DNA sequences, the focus is on occurrences of genes in the annotation. In this paper, we define a pattern through a regular expression and present a restriction of three classical algorithms to take the number of occurrences of the pattern in the hidden sequence into account. We present a new algorithm to compute the distribution of the number of pattern occurrences, and we extend the two most widely used existing decoding algorithms to employ information from this distribution. We show experimentally that the expectation of the distribution of the number of pattern occurrences gives a highly accurate estimate, while the typical procedure can be biased in the sense that the identified number of pattern occurrences does not correspond to the true number. We furthermore show that using this distribution in the decoding algorithms improves the predictive power of the model.

13 July 2013 in Journal of Theoretical Biology
Verified
Journal Article
Closed access
ASAndreas Sand
Andreas Sand
MSMike Steel
Mike Steel