{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T04:14:45Z","timestamp":1728360885808},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,6,20]],"date-time":"2005-06-20T00:00:00Z","timestamp":1119225600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"},{"start":{"date-parts":[[2005,6,20]],"date-time":"2005-06-20T00:00:00Z","timestamp":1119225600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                        <jats:title>Background<\/jats:title>\n                        <jats:p>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.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Results<\/jats:title>\n                        <jats:p>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 <jats:italic>just-in-time<\/jats:italic> 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.<\/jats:p>\n                     <\/jats:sec><jats:sec>\n                        <jats:title>Conclusion<\/jats:title>\n                        <jats:p>Our mechanical proof procedure and our testing methods provide a powerful arsenal of methods to ensure non-ambiguity.<\/jats:p>\n                     <\/jats:sec>","DOI":"10.1186\/1471-2105-6-153","type":"journal-article","created":{"date-parts":[[2005,6,21]],"date-time":"2005-06-21T13:30:13Z","timestamp":1119360613000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Effective ambiguity checking in biosequence analysis"],"prefix":"10.1186","volume":"6","author":[{"given":"Janina","family":"Reeder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Steffen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Giegerich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"478_CR1","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"R Dowell","year":"2004","unstructured":"Dowell R, Eddy SR: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics 2004, 5: 71. 10.1186\/1471-2105-5-71","journal-title":"BMC Bioinformatics"},{"key":"478_CR2","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","volume":"49","author":"S Wuchty","year":"1999","unstructured":"Wuchty S, Fontana W, Hofacker I, Schuster P: Complete Suboptimal Folding of RNA and the Stability of Secondary Structures. Biopolymers 1999, 49: 145\u2013165. 10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","journal-title":"Biopolymers"},{"key":"478_CR3","first-page":"46","volume-title":"Proc. Combinatorial Pattern Matching, Springer LNCS 1848","author":"R Giegerich","year":"2000","unstructured":"Giegerich R: Explaining and Controlling Ambiguity in Dynamic Programming. Proc. Combinatorial Pattern Matching, Springer LNCS 1848 2000, 46\u201359."},{"key":"478_CR4","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","volume":"2","author":"N Chomsky","year":"1956","unstructured":"Chomsky N: Three Models for the Description of Language. IRE Transactions on information theory 1956, 2: 113\u2013124. 10.1109\/TIT.1956.1056813","journal-title":"IRE Transactions on information theory"},{"key":"478_CR5","volume-title":"The Theory of Parsing, Translation and Compiling","author":"A Aho","year":"1973","unstructured":"Aho A, Ullman J: The Theory of Parsing, Translation and Compiling. Englewood Cliffs, NJ: Prentice-Hall; 1973. [I and II]"},{"issue":"3","key":"478_CR6","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","volume":"51","author":"R Giegerich","year":"2004","unstructured":"Giegerich R, Meyer C, Steffen P: A Discipline of Dy namic Programming over Sequence Data. Science of Computer Programming 2004, 51(3):215\u2013263. 10.1016\/j.scico.2003.12.005","journal-title":"Science of Computer Programming"},{"key":"478_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker M, Stiegler P: Optimal Computer Folding of Large RNA Sequences using Thermodynamics and Auxiliary Information. Nucleic Acids Research 1981, 9: 133\u2013148.","journal-title":"Nucleic Acids Research"},{"key":"478_CR8","unstructured":"Effective Ambiguity Checking in Biosequence Analysis[http:\/\/bibiserv.techfak.uni-bielefeld.de\/adp\/ambiguity\/]"},{"key":"478_CR9","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/S0049-237X(08)72023-8","volume-title":"Computer Programming and Formal Systems","author":"N Chomsky","year":"1963","unstructured":"Chomsky N, Sch\u00fctzenberger MP: The algebraic theory of context-free languages. In Computer Programming and Formal Systems. Edited by: Braffort P, Hirschberg D. Amsterdam: North-Holland; 1963:118\u2013161."},{"issue":"6","key":"478_CR10","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/S0019-9958(65)90426-2","volume":"8","author":"D Knuth","year":"1965","unstructured":"Knuth D: On the Translation of Languages from Left to Right. Information and Control 1965, 8(6):607\u2013639. 10.1016\/S0019-9958(65)90426-2","journal-title":"Information and Control"},{"key":"478_CR11","unstructured":"COCOM tool set[http:\/\/cocom.sourceforge.net\/]"},{"key":"478_CR12","volume-title":"Computing Science TR","author":"SC Johnson","year":"1975","unstructured":"Johnson SC: YACC: Yet Another Compiler Compiler. Computing Science TR 1975., 32:"},{"key":"478_CR13","unstructured":"Bison parser generator[http:\/\/www.gnu.org\/software\/bison\/]"},{"key":"478_CR14","volume-title":"PhD thesis","author":"B Voss","year":"2004","unstructured":"Voss B: Advanced Tools for RNA Secondary Structure Analysis. PhD thesis. University of Bielefeld; 2004."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-153.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/1471-2105-6-153\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-153.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T12:13:25Z","timestamp":1728303205000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6,20]]},"references-count":14,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["478"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-153","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2005,6,20]]},"assertion":[{"value":"22 December 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"153"}}