Effective ambiguity checking in biosequence analysis

Reeder J, Steffen P, Giegerich R (2005)
BMC Bioinformatics 6(1).

Download
OA
Journal Article | Published | English
Author
Abstract
Background: Ambiguity 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. Results: We 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. Conclusion: Our mechanical proof procedure and our testing methods provide a powerful arsenal of methods to ensure non-ambiguity.
Publishing Year
ISSN
PUB-ID

Cite this

Reeder J, Steffen P, Giegerich R. Effective ambiguity checking in biosequence analysis. BMC Bioinformatics. 2005;6(1).
Reeder, J., Steffen, P., & Giegerich, R. (2005). Effective ambiguity checking in biosequence analysis. BMC Bioinformatics, 6(1).
Reeder, J., Steffen, P., and Giegerich, R. (2005). Effective ambiguity checking in biosequence analysis. BMC Bioinformatics 6.
Reeder, J., Steffen, P., & Giegerich, R., 2005. Effective ambiguity checking in biosequence analysis. BMC Bioinformatics, 6(1).
J. Reeder, P. Steffen, and R. Giegerich, “Effective ambiguity checking in biosequence analysis”, BMC Bioinformatics, vol. 6, 2005.
Reeder, J., Steffen, P., Giegerich, R.: Effective ambiguity checking in biosequence analysis. BMC Bioinformatics. 6, (2005).
Reeder, Janina, Steffen, Peter, and Giegerich, Robert. “Effective ambiguity checking in biosequence analysis”. BMC Bioinformatics 6.1 (2005).
Main File(s)
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

7 Citations in Europe PMC

Data provided by Europe PubMed Central.

A folding algorithm for extended RNA secondary structures.
Honer zu Siederdissen C, Bernhart SH, Stadler PF, Hofacker IL., Bioinformatics 27(13), 2011
PMID: 21685061
Semantics and ambiguity of stochastic RNA family models.
Giegerich R, Honer zu Siederdissen C., IEEE/ACM Trans Comput Biol Bioinform 8(2), 2011
PMID: 21233528
Automated protein subfamily identification and classification.
Brown DP, Krishnamurthy N, Sjolander K., PLoS Comput. Biol. 3(8), 2007
PMID: 17708678
Structural analysis of aligned RNAs.
Voss B., Nucleic Acids Res. 34(19), 2006
PMID: 17020924
Complete probabilistic analysis of RNA shapes.
Voss B, Giegerich R, Rehmsmeier M., BMC Biol. 4(), 2006
PMID: 16480488
Versatile and declarative dynamic programming using pair algebras.
Steffen P, Giegerich R., BMC Bioinformatics 6(), 2005
PMID: 16156887

14 References

Data provided by Europe PubMed Central.

Complete suboptimal folding of RNA and the stability of secondary structures.
Wuchty S, Fontana W, Hofacker IL, Schuster P., Biopolymers 49(2), 1999
PMID: 10070264
Explaining and Controlling Ambiguity in Dynamic Programming
Giegerich R., 2000
Three Models for the Description of Language
Chomsky N., 1956

Aho A, Ullman J., 1973
A Discipline of Dy namic Programming over Sequence Data
Giegerich R, Meyer C, Steffen P., 2004
Effective Ambiguity Checking in Biosequence Analysis
AUTHOR UNKNOWN, 0
The algebraic theory of context-free languages
Chomsky N, Schützenberger MP., 1963
On the Translation of Languages from Left to Right
Knuth D., 1965
COCOM tool set
AUTHOR UNKNOWN, 0
YACC: Yet Another Compiler Compiler
Johnson SC., 1975
Bison parser generator
AUTHOR UNKNOWN, 0
Advanced Tools for RNA Secondary Structure Analysis
Voss B., 2004

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 15967024
PubMed | Europe PMC

Search this title in

Google Scholar