Parametric inference for biological sequence analysis
- 8 November 2004
- journal article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 101 (46) , 16138-16143
- https://doi.org/10.1073/pnas.0406011101
Abstract
One of the major successes in computational biology has been the unification, by using the graphical model formalism, of a multitude of algorithms for annotating and comparing biological sequences. Graphical models that have been applied to these problems include hidden Markov models for annotation, tree models for phylogenetics, and pair hidden Markov models for alignment. A single algorithm, the sum-product algorithm, solves many of the inference problems that are associated with different statistical models. This article introduces the polytope propagation algorithm for computing the Newton polytope of an observation from a graphical model. This algorithm is a geometric version of the sum-product algorithm and is used to analyze the parametric behavior of maximum a posteriori inference calculations for graphical models.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- CpG Islands in vertebrate genomesPublished by Elsevier ,2004
- SLAM: Cross-Species Gene Finding and Alignment with a Generalized Pair Hidden Markov ModelGenome Research, 2003
- Comprehensive analysis of CpG islands in human chromosomes 21 and 22Proceedings of the National Academy of Sciences, 2002
- Extended convex hullComputational Geometry, 2001
- Initial sequencing and analysis of the human genomeNature, 2001
- Factor graphs and the sum-product algorithmIEEE Transactions on Information Theory, 2001
- [28] Parametric and inverse-parametric sequence alignment with XPARALPublished by Elsevier ,1996
- Parametric optimization of sequence alignmentAlgorithmica, 1994
- The Collapsed Gibbs Sampler in Bayesian Computations with Applications to a Gene Regulation ProblemJournal of the American Statistical Association, 1994
- Parametric sequence comparisons.Proceedings of the National Academy of Sciences, 1992