The consensus string problem and the complexity of comparing hidden Markov models.

DOI10.1016/S0022-0000(02)00009-0zbMath1059.68048MaRDI QIDQ1872725

Christian N. S. Pedersen, Rune B. Lyngsø

Publication date: 14 May 2003

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (14)

Learning probabilistic automata using residuals ⋮ The most probable annotation problem in HMMs and its application to bioinformatics ⋮ Converging from branching to linear metrics on Markov chains ⋮ L_p DISTANCE AND EQUIVALENCE OF PROBABILISTIC AUTOMATA ⋮ A comprehensive review of quantum random number generators: concepts, classification and the origin of randomness ⋮ ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATA ⋮ Computation of distances for regular and context-free probabilistic languages ⋮ On Computing the Total Variation Distance of Hidden Markov Models. ⋮ Absolute convergence of rational series is semi-decidable ⋮ Absolute Convergence of Rational Series Is Semi-decidable ⋮ Probabilistic automata of bounded ambiguity ⋮ Probabilistic Automata of Bounded Ambiguity ⋮ Sequence annotation with HMMs: new problems and their complexity ⋮ The complexity of estimating min-entropy

Uses Software

• Pfam

Cites Work

• Stochastic models for heterogeneous DNA sequences
• On the computational complexity of approximating distributions by probabilistic automata
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The consensus string problem and the complexity of comparing hidden Markov models.