Learning nonsingular phylogenies and hidden Markov models

• 成果类型: Article
• 署名作者: Mossel, Elchanan; Roch, Sebastien
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051606000000024
• 发表日期: 2006
• 页码: 583-614
• 关键词: evolutionary trees; maximum-likelihood; reconstruction; complexity

摘要

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 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.