Effective ambiguity checking in biosequence analysis
<p>Abstract</p> <p>Background</p> <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. Se...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2005-06-01
|
| Series: | BMC Bioinformatics |
| Online Access: | http://www.biomedcentral.com/1471-2105/6/153 |
| _version_ | 1818392491694489600 |
|---|---|
| author | Giegerich Robert Steffen Peter Reeder Janina |
| author_facet | Giegerich Robert Steffen Peter Reeder Janina |
| author_sort | Giegerich Robert |
| collection | DOAJ |
| description | <p>Abstract</p> <p>Background</p> <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.</p> <p>Results</p> <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 <it>just-in-time </it>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.</p> <p>Conclusion</p> <p>Our mechanical proof procedure and our testing methods provide a powerful arsenal of methods to ensure non-ambiguity.</p> |
| first_indexed | 2024-12-14T05:30:16Z |
| format | Article |
| id | doaj.art-0e315703f26f4aa5b207e61faf86c5c6 |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-12-14T05:30:16Z |
| publishDate | 2005-06-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-0e315703f26f4aa5b207e61faf86c5c62022-12-21T23:15:21ZengBMCBMC Bioinformatics1471-21052005-06-016115310.1186/1471-2105-6-153Effective ambiguity checking in biosequence analysisGiegerich RobertSteffen PeterReeder Janina<p>Abstract</p> <p>Background</p> <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.</p> <p>Results</p> <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 <it>just-in-time </it>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.</p> <p>Conclusion</p> <p>Our mechanical proof procedure and our testing methods provide a powerful arsenal of methods to ensure non-ambiguity.</p>http://www.biomedcentral.com/1471-2105/6/153 |
| spellingShingle | Giegerich Robert Steffen Peter Reeder Janina Effective ambiguity checking in biosequence analysis BMC Bioinformatics |
| title | Effective ambiguity checking in biosequence analysis |
| title_full | Effective ambiguity checking in biosequence analysis |
| title_fullStr | Effective ambiguity checking in biosequence analysis |
| title_full_unstemmed | Effective ambiguity checking in biosequence analysis |
| title_short | Effective ambiguity checking in biosequence analysis |
| title_sort | effective ambiguity checking in biosequence analysis |
| url | http://www.biomedcentral.com/1471-2105/6/153 |
| work_keys_str_mv | AT giegerichrobert effectiveambiguitycheckinginbiosequenceanalysis AT steffenpeter effectiveambiguitycheckinginbiosequenceanalysis AT reederjanina effectiveambiguitycheckinginbiosequenceanalysis |