{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T22:27:10Z","timestamp":1761863230791},"reference-count":39,"publisher":"Oxford University Press (OUP)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The calculation of reliable alignments for structured RNA is still considered as an open problem. One approach is the incorporation of secondary structure information into the optimization criteria by using a weighted sum of sequence and structure components as an objective function. As it is not clear how to choose the weighting parameters, we use multi-objective optimization to calculate a set of Pareto-optimal RNA sequence-structure alignments. The solutions in this set then represent all possible trade-offs between the different objectives, independent of any previous weighting.<\/jats:p>\n               <jats:p>Results: We present a practical multi-objective dynamic programming algorithm, which is a new method for the calculation of the set of Pareto-optimal solutions to the pairwise RNA sequence-structure alignment problem. In selected examples, we show the usefulness of this approach, and its advantages over state-of-the-art single-objective algorithms.<\/jats:p>\n               <jats:p>Availability and implementation: The source code of our software (ISO C++11) is freely available at http:\/\/sysbio.uni-ulm.de\/?Software and is licensed under the GNU GPLv3.<\/jats:p>\n               <jats:p>Contact: \u00a0hans.kestler@uni-ulm.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt188","type":"journal-article","created":{"date-parts":[[2013,4,26]],"date-time":"2013-04-26T01:21:15Z","timestamp":1366939275000},"page":"1607-1613","source":"Crossref","is-referenced-by-count":14,"title":["Structural RNA alignment by multi-objective optimization"],"prefix":"10.1093","volume":"29","author":[{"given":"Thomas","family":"Schnattinger","sequence":"first","affiliation":[]},{"given":"Uwe","family":"Sch\u00f6ning","sequence":"additional","affiliation":[]},{"given":"Hans A.","family":"Kestler","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2013,4,24]]},"reference":[{"key":"2023062614244008200_btt188-B1","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2010.09.001","article-title":"Sparse RNA folding: time and space efficient algorithms","volume":"9","author":"Backofen","year":"2011","journal-title":"J. Discrete Algorithms"},{"key":"2023062614244008200_btt188-B2","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/j.cell.2012.01.057","article-title":"Cooperative tertiary interaction network guides RNA folding","volume":"149","author":"Behrouzi","year":"2012","journal-title":"Cell"},{"key":"2023062614244008200_btt188-B3","volume-title":"Dynamic Programming","author":"Bellman","year":"1957"},{"key":"2023062614244008200_btt188-B4","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1080\/01621459.1979.10481038","article-title":"Robust locally weighted regression and smoothing scatterplots","volume":"74","author":"Cleveland","year":"1979","journal-title":"J. Am. Stat. Assoc."},{"key":"2023062614244008200_btt188-B5","volume-title":"Multi-Objective Optimization Using Evolutionary Algorithms","author":"Deb","year":"2001"},{"key":"2023062614244008200_btt188-B6","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1038\/418222a","article-title":"The chemical repertoire of natural ribozymes","volume":"418","author":"Doudna","year":"2002","journal-title":"Nature"},{"key":"2023062614244008200_btt188-B7","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1186\/1471-2105-7-400","article-title":"Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints","volume":"7","author":"Dowell","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023062614244008200_btt188-B8","article-title":"Multicriteria optimization","volume-title":"Lecture Notes in Economics and Mathematical Systems","author":"Ehrgott","year":"2000"},{"key":"2023062614244008200_btt188-B9","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/nar\/gki541","article-title":"A benchmark of multiple sequence alignment programs upon structural RNAs","volume":"33","author":"Gardner","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023062614244008200_btt188-B10","doi-asserted-by":"crossref","first-page":"D141","DOI":"10.1093\/nar\/gkq1129","article-title":"Rfam: Wikipedia, clans and the \u2018decimal\u2019 release","volume":"39","author":"Gardner","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023062614244008200_btt188-B11","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s00778-006-0029-7","article-title":"Algorithms and analyses for maximal vector computation","volume":"16","author":"Godfrey","year":"2007","journal-title":"VLDB J."},{"key":"2023062614244008200_btt188-B12","doi-asserted-by":"crossref","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","article-title":"Finding the most significant common sequence and structure motifs in a set of RNA sequences","volume":"25","author":"Gorodkin","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023062614244008200_btt188-B13","first-page":"494","article-title":"The desirability function","volume":"21","author":"Harrington","year":"1965","journal-title":"Ind. Qual. Control"},{"key":"2023062614244008200_btt188-B14","doi-asserted-by":"crossref","first-page":"e193","DOI":"10.1371\/journal.pcbi.0030193","article-title":"Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix","volume":"3","author":"Havgaard","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023062614244008200_btt188-B15","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1137\/0321030","article-title":"Vector-valued dynamic programming","volume":"21","author":"Henig","year":"1983","journal-title":"SIAM J. Control Optimiz."},{"key":"2023062614244008200_btt188-B16","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1287\/moor.10.3.462","article-title":"The principle of optimality in dynamic programming with returns in partially ordered sets","volume":"10","author":"Henig","year":"1985","journal-title":"Math. Oper. Res."},{"key":"2023062614244008200_btt188-B17","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatsh. Chem."},{"key":"2023062614244008200_btt188-B18","doi-asserted-by":"crossref","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","article-title":"Alignment of RNA base pairing probability matrices","volume":"20","author":"Hofacker","year":"2004","journal-title":"Bioinformatics"},{"key":"2023062614244008200_btt188-B19","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1002\/(SICI)1520-6750(200002)47:1<57::AID-NAV4>3.0.CO;2-4","article-title":"Dynamic programming approaches to the multiple criteria knapsack problem","volume":"47","author":"Klamroth","year":"2000","journal-title":"Naval Res. Logist."},{"key":"2023062614244008200_btt188-B20","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1093\/bioinformatics\/btm404","article-title":"Clustal W and Clustal X version 2.0","volume":"23","author":"Larkin","year":"2007","journal-title":"Bioinformatics"},{"key":"2023062614244008200_btt188-B21","volume-title":"Gene Regulation: A Eukaryotic Perspective","author":"Latchman","year":"2005"},{"key":"2023062614244008200_btt188-B22","volume-title":"Entscheidungstheorie","author":"Laux","year":"2005","edition":"6th edn"},{"key":"2023062614244008200_btt188-B23","doi-asserted-by":"crossref","first-page":"2246","DOI":"10.1093\/bioinformatics\/bti349","article-title":"Predicting a set of minimal free energy RNA secondary structures common to two sequences","volume":"21","author":"Mathews","year":"2005","journal-title":"Bioinformatics"},{"key":"2023062614244008200_btt188-B24","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jmbi.2001.5351","article-title":"Dynalign: an algorithm for finding the secondary structure common to two RNA sequences","volume":"317","author":"Mathews","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023062614244008200_btt188-B25","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/0005-2795(75)90109-9","article-title":"Comparison of the predicted and observed secondary structure of t4 phage lysozyme","volume":"405","author":"Matthews","year":"1975","journal-title":"Biochim. Biophys. Acta"},{"key":"2023062614244008200_btt188-B26","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair binding probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"key":"2023062614244008200_btt188-B27","volume-title":"Manual of Political Economy","author":"Pareto","year":"1971"},{"key":"2023062614244008200_btt188-B28","first-page":"565","article-title":"Pareto-optimal alignment of biological sequences","volume":"44","author":"Roytberg","year":"1999","journal-title":"Biophysics"},{"key":"2023062614244008200_btt188-B29","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math."},{"key":"2023062614244008200_btt188-B30","author":"Schnattinger","year":"2012"},{"key":"2023062614244008200_btt188-B31","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/msb.2011.75","article-title":"Fast, scalable generation of high-quality protein multiple sequence alignments using clustal omega","volume":"7","author":"Sievers","year":"2011","journal-title":"Mol. Syst. Biol."},{"key":"2023062614244008200_btt188-B32","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1080\/03052158808940949","article-title":"A multi-objective routing problem revisited","volume":"13","author":"Sniedovich","year":"1988","journal-title":"Eng. Optimiz."},{"key":"2023062614244008200_btt188-B33","doi-asserted-by":"crossref","first-page":"2383","DOI":"10.1093\/bioinformatics\/btq439","article-title":"Multi-objective pairwise RNA sequence alignment","volume":"26","author":"Taneda","year":"2010","journal-title":"Bioinformatics"},{"key":"2023062614244008200_btt188-B34","doi-asserted-by":"crossref","first-page":"2682","DOI":"10.1093\/nar\/27.13.2682","article-title":"A comprehensive comparison of multiple sequence alignment programs","volume":"27","author":"Thompson","year":"1999","journal-title":"Nucleic Acids Res."},{"key":"2023062614244008200_btt188-B35","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1006\/jmbi.1999.3001","article-title":"How RNA folds","volume":"293","author":"Tinoco","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023062614244008200_btt188-B36","first-page":"255","article-title":"DNA and RNA structure prediction","volume-title":"DNA\u2014Protein Sequence Analysis","author":"Westhof","year":"1996"},{"key":"2023062614244008200_btt188-B37","doi-asserted-by":"crossref","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","article-title":"Inferring noncoding RNA families and classes by means of genome-scale structure-based clustering","volume":"3","author":"Will","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023062614244008200_btt188-B38","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/S0092-8240(84)80062-2","article-title":"RNA secondary structures and their prediction","volume":"46","author":"Zuker","year":"1984","journal-title":"Bull. Math. Biol."},{"key":"2023062614244008200_btt188-B39","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","article-title":"Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information","volume":"9","author":"Zuker","year":"1981","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/1607\/50704650\/bioinformatics_29_13_1607.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/1607\/50704650\/bioinformatics_29_13_1607.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T15:25:04Z","timestamp":1687793104000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/13\/1607\/184217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,24]]},"references-count":39,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt188","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2013,7]]},"published":{"date-parts":[[2013,4,24]]}}}