Versatile and declarative dynamic programming using pair algebras

Steffen P, Giegerich R (2005)
BMC Bioinformatics 6(1): 224.

Download
OA
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Abstract / Bemerkung
Background: Dynamic programming is a widely used programming technique in bioinformatics. In sharp contrast to the simplicity of textbook examples, implementing a dynamic programming algorithm for a novel and non-trivial application is a tedious and error prone task. The algebraic dynamic programming approach seeks to alleviate this situation by clearly separating the dynamic programming recurrences and scoring schemes. Results: Based on this programming style, we introduce a generic product operation of scoring schemes. This leads to a remarkable variety of applications, allowing us to achieve optimizations under multiple objective functions, alternative solutions and backtracing, holistic search space analysis, ambiguity checking, and more, without additional programming effort. We demonstrate the method on several applications for RNA secondary structure prediction. Conclusion: The product operation as introduced here adds a significant amount of flexibility to dynamic programming. It provides a versatile testbed for the development of new algorithmic ideas, which can immediately be put to practice.
Erscheinungsjahr
Zeitschriftentitel
BMC Bioinformatics
Band
6
Zeitschriftennummer
1
Seite
224
ISSN
PUB-ID

Zitieren

Steffen P, Giegerich R. Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics. 2005;6(1):224.
Steffen, P., & Giegerich, R. (2005). Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics, 6(1), 224. doi:10.1186/1471-2105-6-224
Steffen, P., and Giegerich, R. (2005). Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics 6, 224.
Steffen, P., & Giegerich, R., 2005. Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics, 6(1), p 224.
P. Steffen and R. Giegerich, “Versatile and declarative dynamic programming using pair algebras”, BMC Bioinformatics, vol. 6, 2005, pp. 224.
Steffen, P., Giegerich, R.: Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics. 6, 224 (2005).
Steffen, Peter, and Giegerich, Robert. “Versatile and declarative dynamic programming using pair algebras”. BMC Bioinformatics 6.1 (2005): 224.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
1970-01-01T00:00:00Z

10 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

The RNA shapes studio.
Janssen S, Giegerich R., Bioinformatics 31(3), 2015
PMID: 25273103
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
Pareto optimization in algebraic dynamic programming.
Saule C, Giegerich R., Algorithms Mol Biol 10(), 2015
PMID: 26150892
Combinatorics of locally optimal RNA secondary structures.
Fusy E, Clote P., J Math Biol 68(1-2), 2014
PMID: 23263300
Topology and prediction of RNA pseudoknots.
Reidys CM, Huang FW, Andersen JE, Penner RC, Stadler PF, Nebel ME., Bioinformatics 27(8), 2011
PMID: 21335320
Semantics and ambiguity of stochastic RNA family models.
Giegerich R, Höner zu Siederdissen C., IEEE/ACM Trans Comput Biol Bioinform 8(2), 2011
PMID: 21233528
Locomotif: from graphical motif description to RNA motif search.
Reeder J, Reeder J, Giegerich R., Bioinformatics 23(13), 2007
PMID: 17646322
Structural analysis of aligned RNAs.
Voss B., Nucleic Acids Res 34(19), 2006
PMID: 17020924

16 References

Daten bereitgestellt von Europe PubMed Central.


Gusfield D., 1997

Durbin R, Eddy S, Krogh A, Mitchison G., 1998
On de novo interpretation of tandem mass spectra for peptide identification
Bafna V, Edwards N., 2003
Algebraic Dynamic Programming homepage
AUTHOR UNKNOWN, 0
A Discipline of Dynamic Programming over Sequence Data
Giegerich R, Meyer C, Steffen P., 2004
Algorithms for loop matchings
Nussinov R, Pieczenik G, Griggs J, Kleitman D., 1978

Bellman R., 1957
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
Monotonicity and the principle of optimality
Morin TL., 1982
Abstract shapes of RNA.
Giegerich R, Voss B, Rehmsmeier M., Nucleic Acids Res. 32(16), 2004
PMID: 15371549
Explaining and Controlling Ambiguity in Dynamic Programming
Giegerich R., 2000
Effective ambiguity checking in biosequence analysis.
Reeder J, Steffen P, Giegerich R., BMC Bioinformatics 6(), 2005
PMID: 15967024
Fast and effective prediction of microRNA/target duplexes.
Rehmsmeier M, Steffen P, Hochsmann M, Giegerich R., RNA 10(10), 2004
PMID: 15383676

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 16156887
PubMed | Europe PMC

Suchen in

Google Scholar