Semantics and Ambiguity of Stochastic RNA Family Models

Giegerich R, Hoener Zu Siederdissen C (2011)
IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(2): 499-516.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
;
Abstract / Bemerkung
Stochastic models, such as hidden Markov models or stochastic context-free grammars (SCFGs) can fail to return the correct, maximum likelihood solution in the case of semantic ambiguity. This problem arises when the algorithm implementing the model inspects the same solution in different guises. It is a difficult problem in the sense that proving semantic nonambiguity has been shown to be algorithmically undecidable, while compensating for it (by coalescing scores of equivalent solutions) has been shown to be NP-hard. For stochastic context-free grammars modeling RNA secondary structure, it has been shown that the distortion of results can be quite severe. Much less is known about the case when stochastic context-free grammars model the matching of a query sequence to an implicit consensus structure for an RNA family. We find that three different, meaningful semantics can be associated with the matching of a query against the model-a structural, an alignment, and a trace semantics. Rfam models correctly implement the alignment semantics, and are ambiguous with respect to the other two semantics, which are more abstract. We show how provably correct models can be generated for the trace semantics. For approaches, where such a proof is not possible, we present an automated pipeline to check post factum for ambiguity of the generated models. We propose that both the structure and the trace semantics are worth-while concepts for further study, possibly better suited to capture remotely related family members.
Erscheinungsjahr
Zeitschriftentitel
IEEE/ACM Transactions on Computational Biology and Bioinformatics
Band
8
Zeitschriftennummer
2
Seite
499-516
ISSN
PUB-ID

Zitieren

Giegerich R, Hoener Zu Siederdissen C. Semantics and Ambiguity of Stochastic RNA Family Models. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2011;8(2):499-516.
Giegerich, R., & Hoener Zu Siederdissen, C. (2011). Semantics and Ambiguity of Stochastic RNA Family Models. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(2), 499-516. doi:10.1109/TCBB.2010.12
Giegerich, R., and Hoener Zu Siederdissen, C. (2011). Semantics and Ambiguity of Stochastic RNA Family Models. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8, 499-516.
Giegerich, R., & Hoener Zu Siederdissen, C., 2011. Semantics and Ambiguity of Stochastic RNA Family Models. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(2), p 499-516.
R. Giegerich and C. Hoener Zu Siederdissen, “Semantics and Ambiguity of Stochastic RNA Family Models”, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 8, 2011, pp. 499-516.
Giegerich, R., Hoener Zu Siederdissen, C.: Semantics and Ambiguity of Stochastic RNA Family Models. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 8, 499-516 (2011).
Giegerich, Robert, and Hoener Zu Siederdissen, Christian. “Semantics and Ambiguity of Stochastic RNA Family Models”. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8.2 (2011): 499-516.

3 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

Product Grammars for Alignment and Folding.
Höner Zu Siederdissen C, Hofacker IL, Stadler PF., IEEE/ACM Trans Comput Biol Bioinform 12(3), 2015
PMID: 26357262
Ambivalent covariance models.
Janssen S, Giegerich R., BMC Bioinformatics 16(), 2015
PMID: 26017195

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 21233528
PubMed | Europe PMC

Suchen in

Google Scholar