Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model

DOI10.1137/S0097539798342496zbMath1052.68061MaRDI QIDQ2784459

Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

computational learning theoryMarkov modelevolutionary treesPAC-learninglearning of distributions

Mathematics Subject Classification ID

Computational learning theory (68Q32) General topics in the theory of algorithms (68W01)

Related Items (12)

Combining polynomial running time and fast convergence for the disk-covering method. ⋮ Circular Networks from Distorted Metrics ⋮ Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges ⋮ Linear classifiers are nearly optimal when hidden variables have diverse effects ⋮ Separating populations with wide data: a spectral analysis ⋮ Separating Populations with Wide Data: A Spectral Analysis ⋮ Robust Estimators in High-Dimensions Without the Computational Intractability ⋮ PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance ⋮ Phase transition in the sample complexity of likelihood-based phylogeny inference ⋮ Learning nonsingular phylogenies and hidden Markov models ⋮ Phase transitions in phylogeny ⋮ Inverting random functions

This page was built for publication: Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model