Versatile and declarative dynamic programming using pair algebras

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

Download
OA
Journal Article | Published | English
Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

Steffen P, Giegerich R. Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics. 2005;6(1).
Steffen, P., & Giegerich, R. (2005). Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics, 6(1).
Steffen, P., and Giegerich, R. (2005). Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics 6.
Steffen, P., & Giegerich, R., 2005. Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics, 6(1).
P. Steffen and R. Giegerich, “Versatile and declarative dynamic programming using pair algebras”, BMC Bioinformatics, vol. 6, 2005.
Steffen, P., Giegerich, R.: Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics. 6, (2005).
Steffen, Peter, and Giegerich, Robert. “Versatile and declarative dynamic programming using pair algebras”. BMC Bioinformatics 6.1 (2005).
Main File(s)
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

8 Citations in Europe PMC

Data provided by Europe PubMed Central.

Pareto optimization in algebraic dynamic programming.
Saule C, Giegerich R., Algorithms Mol Biol 10(), 2015
PMID: 26150892
Ambivalent covariance models.
Janssen S, Giegerich R., BMC Bioinformatics 16(), 2015
PMID: 26017195
The RNA shapes studio.
Janssen S, Giegerich R., Bioinformatics 31(3), 2015
PMID: 25273103
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, Honer zu Siederdissen C., IEEE/ACM Trans Comput Biol Bioinform 8(2), 2011
PMID: 21233528
Structural analysis of aligned RNAs.
Voss B., Nucleic Acids Res. 34(19), 2006
PMID: 17020924

16 References

Data provided by 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

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 16156887
PubMed | Europe PMC

Search this title in

Google Scholar