Effective ambiguity checking in biosequence analysis

BackgroundAmbiguity is a problem in biosequence analysis that arises in various analysis tasks solved via dynamic programming, and in particular, in the modeling of families of RNA secondary structures with stochastic context free grammars. Several types of analysis are invalidated by the presence of ambiguity. As this problem inherits undecidability (as we show here) from the namely problem for context free languages, there is no complete algorithmic solution to the problem of ambiguity checking.ResultsWe explain frequently observed sources of ambiguity, and show how to avoid them. We suggest four testing procedures that may help to detect ambiguity when present, including a just-in-time test that permits to work safely with a potentially ambiguous grammar. We introduce, for the special case of stochastic context free grammars and RNA structure modeling, an automated partial procedure for proving non-ambiguity. It is used to demonstrate non-ambiguity for several relevant grammars.ConclusionOur mechanical proof procedure and our testing methods provide a powerful arsenal of methods to ensure non-ambiguity.

• Publication year

  2005

• Venue

  BMC Bioinformatics

• Publication date

  2005-06-20

• Fields of study

  Biology, Medicine, Computer Science

• Identifiers
  DOI 10.1186/1471-2105-6-153PMID 15967024PMCID 1215473
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Effective ambiguity checking in biosequence analysis

  2005cited by this paper
• A discipline of dynamic programming over sequence data

  2004influential reference
• Advanced tools for RNA secondary structure analysis

  2004cited by this paper
• Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction

  2004influential reference
• Explaining and Controlling Ambiguity in Dynamic Programming

  2000influential reference
• Complete suboptimal folding of RNA and the stability of secondary structures.

  1999cited by this paper
• Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information

  1981cited by this paper
• Yacc: Yet Another Compiler-Compiler

  1978cited by this paper
• The Theory of Parsing, Translation, and Compiling

  1972cited by this paper
• Computer programming and formal systems

  1965cited by this paper
• On the Translation of Languages from Left to Right

  1965cited by this paper
• The Algebraic Theory of Context-Free Languages*

  1963cited by this paper
• Three models for the description of language

  1956cited by this paper

• Network Analysis with Stochastic Grammars

  2015cites this paper
• An Unambiguous And Complete Dynamic Programming Algorithm For Tree Alignment

  2015cites this paper
• Inference of population history and patterns from molecular data

  2015cites this paper
• Yield grammar analysis and product optimization in a domain-specific language for dynamic programming

  2014cites this paper
• Deep metazoan phylogeny : the backbone of the tree of life : new insights from analyses of molecules, morphology, and theory of data analysis

  2014cites this paper
• Kisses, ambivalent models and more: Contributions to the analysis of RNA secondary structure

  2014cites this paper
• Introduction to stochastic context free grammars.

  2014cites this paper
• On LR Parsing with Selective Delays

  2013influential citation
• Avoiding Ambiguity and Assessing Uniqueness in Minisatellite Alignment

  2013cites this paper
• Technical Report : An n-free-passes CYK algorithm for error-correction and the prediction of non-canonical base-pairs in RNA secondary structure

  2013cites this paper
• Parallelization of Bioinformatics Algorithm using Genetic Algorithm on Multicore platform

  2012cites this paper
• Evolving stochastic context--free grammars for RNA secondary structure prediction

  2012cites this paper
• An investigation into the practical implications of grammar ambiguity in RNA secondary structure prediction

  2011influential citation
• An evolutionary algorithm for stochastic context-free grammar design , with applications to RNA secondary structure prediction

  2011cites this paper
• Sparsification in Algebraic Dynamic Programming

  2011cites this paper
• A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms

  2011cites this paper
• Semantics and Ambiguity of Stochastic RNA Family Models

  2011influential citation
• Discriminative structured models for biological sequence analysis

  2009cites this paper
• An experimental ambiguity detection tool

  2008cites this paper
• List of Contributing Authors

  2008cites this paper
• Analyzing Ambiguity of Context-Free Grammars

  2007cites this paper
• The most probable annotation problem in HMMs and its application to bioinformatics

  2007cites this paper
• Automated Protein Subfamily Identification and Classification

  2007cites this paper
• Conservative Ambiguity Detection in Context-Free Grammars

  2007influential citation
• Approximating Context-Free Grammars for Parsing and Verification. (Approximation de grammaires algébriques pour l'analyse syntaxique et la vérification)

  2007cites this paper
• MODULAR SYNTAX DEMANDS VERIFICATION

  2006cites this paper
• Complete probabilistic analysis of RNA shapes

  2006cites this paper
• Structural analysis of aligned RNAs

  2006cites this paper
• Compiling a domain specific language for dynamic programming

  2006cites this paper
• CONTRAfold: RNA secondary structure prediction without physics-based models

  2006cites this paper
• Effective ambiguity checking in biosequence analysis

  2005cites this paper
• Versatile and declarative dynamic programming using pair algebras

  2005cites this paper