Learning nonsingular phylogenies and hidden Markov models

Details Learning nonsingular phylogenies and hidden Markov models Learning nonsingular phylogenies and hidden Markov models

2005-02-18

arxiv.org/abs/cs/0502076v2

Annals of Applied Probability 2006, Vol. 16, No. 2, 583-614

Computer Science

Learning

Published at http://dx.doi.org/10.1214/105051606000000024 in the Annals of Applied Probability (http://www.imstat.org/aap/) by

Scientific paper

10.1214/105051606000000024

In this paper we study the problem of learning phylogenies and hidden Markov models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning hidden Markov models without the nonsingularity condition is at least as hard as learning parity with noise, a well-known learning problem conjectured to be computationally hard. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and hidden Markov models.

Affiliated with

Also associated with

No associations

Rating

Learning nonsingular phylogenies and hidden Markov models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning nonsingular phylogenies and hidden Markov models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning nonsingular phylogenies and hidden Markov models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-387835