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.

Journal Article | Published | English

No fulltext has been uploaded

Author
;
Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

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.
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.
This data publication is cited in the following publications:
This publication cites the following data publications:

2 Citations in Europe PMC

Data provided by Europe PubMed Central.

Ambivalent covariance models.
Janssen S, Giegerich R., BMC Bioinformatics 16(), 2015
PMID: 26017195

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 21233528
PubMed | Europe PMC

Search this title in

Google Scholar