Learning nonsingular phylogenies and hidden Markov models

DOI10.1145/1060590.1060645zbMath1192.68394arXivcs/0502076OpenAlexW1981651876MaRDI QIDQ5901107

Sebastien Roch, Elchanan Mossel

Publication date: 16 August 2010

Published in: The Annals of Applied Probability, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0502076

zbMATH Keywords

hidden Markov modelsevolutionary treesPAC learningphylogenetic reconstructionefficient reconstruction algorithmsproblem of reconstructing the phylogenetic treesstochastic evolution of genetic data

Mathematics Subject Classification ID

Computational learning theory (68Q32) Taxonomy, cladistics, statistics in mathematical biology (92B10) Learning and adaptive systems in artificial intelligence (68T05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Genetics and epigenetics (92D10)

Related Items

Circular Networks from Distorted Metrics, Noisy tensor completion via the sum-of-squares hierarchy, On the optimization landscape of tensor decompositions, Learning loopy graphical models with latent variables: efficient methods and guarantees, Full reconstruction of non-stationary strand-symmetric models on rooted phylogenies, Combinatorial statistics and the sciences, Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis, A spectral algorithm for learning hidden Markov models, Separating populations with wide data: a spectral analysis, Recovering Structured Probability Matrices, Separating Populations with Wide Data: A Spectral Analysis, Barriers for Rank Methods in Arithmetic Complexity, Spectral learning of weighted automata. A forward-backward perspective, Robust Estimators in High-Dimensions Without the Computational Intractability, Phase transition in the sample complexity of likelihood-based phylogeny inference, Network delay inference from additive metrics, Tensor Decompositions for Learning Latent Variable Models (A Survey for ALT), Statistical and Computational Guarantees for the Baum-Welch Algorithm, Large-Scale Multiple Sequence Alignment and Phylogeny Estimation, Spectral Neighbor Joining for Reconstruction of Latent Tree Models, Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes, A spectral algorithm for latent Dirichlet allocation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Full reconstruction of Markov models on evolutionary trees: identifiability and consistency.
• Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time
• On the computational complexity of approximating distributions by probabilistic automata
• Recovering a tree from the leaf colourations it generates under a Markov model
• A few logs suffice to build (almost) all trees. II
• Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• On the learnability of discrete distributions
• Efficient noise-tolerant learning from statistical queries
• Efficient algorithms for inverting evolution
• Matrix Analysis
• A theory of the learnable
• Learning Integer Lattices
• Biological Sequence Analysis
• A few logs suffice to build (almost) all trees (I)
• Research in Computational Molecular Biology
• Probability
• Noise-tolerant learning, the parity problem, and the statistical query model