{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T22:08:24Z","timestamp":1762898904384},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We generalize some current approaches for RNA tree alignment, which are traditionally confined to <jats:italic>ordered rooted<\/jats:italic>\u2009mappings, to also consider <jats:italic>unordered unrooted<\/jats:italic> mappings. We define the <jats:italic>Homeomorphic Subtree Alignment<\/jats:italic>\u2009problem (<jats:italic>HSA<\/jats:italic>), and present a new algorithm which applies to several modes, combining global or local, ordered or unordered, and rooted or unrooted tree alignments. Our algorithm generalizes previous algorithms that either solved the problem in an asymmetric manner, or were restricted to the rooted and\/or ordered cases. Focusing here on the most general unrooted unordered case, we show that for input trees <jats:italic>T<\/jats:italic>\u2009and <jats:italic>S<\/jats:italic>, our algorithm has an <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>\u2009+\u2009min(<jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>,<jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>)<jats:italic>L<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>L<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>) time complexity, where <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>,<jats:italic>L<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>\u2009and <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub> are the number of nodes, the number of leaves, and the maximum node degree in <jats:italic>T<\/jats:italic>, respectively (satisfying <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>\u2009\u2264\u2009<jats:italic>L<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>\u2009\u2264\u2009<jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>), and similarly for <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>,<jats:italic>L<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>\u2009and <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>\u2009with respect to the tree <jats:italic>S<\/jats:italic>. This improves the time complexity of previous algorithms for less general variants of the problem.<\/jats:p>\n          <jats:p>In order to obtain this time bound for HSA, we developed new algorithms for a generalized variant of the <jats:italic>Min-Cost Bipartite Matching<\/jats:italic>\u2009problem (<jats:italic>MCM<\/jats:italic>), as well as to two derivatives of this problem, entitled <jats:italic>All-Cavity-MCM<\/jats:italic>\u2009and <jats:italic>All-Pairs-Cavity-MCM<\/jats:italic>. For two input sets of size <jats:italic>n<\/jats:italic>\u2009and <jats:italic>m<\/jats:italic>, where <jats:italic>n<\/jats:italic>\u2009\u2264\u2009<jats:italic>m<\/jats:italic>, <jats:italic>MCM<\/jats:italic>\u2009and both its cavity derivatives are solved in <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\u2009+\u2009<jats:italic>n<\/jats:italic>\n            <jats:italic>m<\/jats:italic>) time, without the usage of priority queues (e.g. Fibonacci heaps) or other complex data structures. This gives the first cubic time algorithm for <jats:italic>All<\/jats:italic>-<jats:italic>Pairs<\/jats:italic>-<jats:italic>Cavity<\/jats:italic>-<jats:italic>MCM<\/jats:italic>, and improves the running times of <jats:italic>MCM<\/jats:italic>\u2009and <jats:italic>All<\/jats:italic>-<jats:italic>Cavity<\/jats:italic>-<jats:italic>MCM<\/jats:italic>\u2009problems in the unbalanced case where <jats:italic>n<\/jats:italic>\u2009\u226a\u2009<jats:italic>m<\/jats:italic>.<\/jats:p>\n          <jats:p>We implemented the algorithm (in all modes mentioned above) as a graphical software tool which computes and displays similarities between secondary structures of RNA given as input, and employed it to a preliminary experiment in which we ran all-against-all inter-family pairwise alignments of RNAse P and Hammerhead RNA family members, exposing new similarities which could not be detected by the traditional rooted ordered alignment approaches. The results demonstrate that our approach can be used to expose structural similarity between some RNAs with higher sensitivity than the traditional <jats:italic>rooted ordered<\/jats:italic>\u2009alignment approaches. Source code and web-interface for our tool can be found in <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/www.cs.bgu.ac.il\/~negevcb\/FRUUT\" ext-link-type=\"uri\">http:\/\/www.cs.bgu.ac.il\/\\~negevcb\/FRUUT<\/jats:ext-link>.<\/jats:p>","DOI":"10.1186\/1748-7188-8-13","type":"journal-article","created":{"date-parts":[[2013,4,16]],"date-time":"2013-04-16T18:14:36Z","timestamp":1366136076000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Unrooted unordered homeomorphic subtree alignment of RNA trees"],"prefix":"10.1186","volume":"8","author":[{"given":"Nimrod","family":"Milo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Zakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erez","family":"Katzenelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eitan","family":"Bachmat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yefim","family":"Dinitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,4,16]]},"reference":[{"issue":"12","key":"194_CR1","doi-asserted-by":"publisher","first-page":"2543","DOI":"10.1046\/j.1432-1033.2003.03634.x","volume":"270","author":"I Agmon","year":"2003","unstructured":"Agmon I, Auerbach T, Baram D, Bartels H, Bashan A, Berisio R, Fucini P, Hansen H, Harms J, Kessler M, et al: On peptide bond formation, translocation, nascent protein progression and the regulatory properties of ribosomes. Eur J Biochem. 2003, 270 (12): 2543-2556. 10.1046\/j.1432-1033.2003.03634.x.","journal-title":"Eur J Biochem"},{"issue":"13","key":"194_CR2","doi-asserted-by":"publisher","first-page":"3429","DOI":"10.1093\/nar\/gkg599","volume":"31","author":"I Hofacker","year":"2003","unstructured":"Hofacker I: Vienna RNA secondary structure server. Nucleic Acids Res. 2003, 31 (13): 3429-10.1093\/nar\/gkg599.","journal-title":"Nucleic Acids Res"},{"issue":"4","key":"194_CR3","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1093\/bioinformatics\/btk010","volume":"22","author":"P Steffen","year":"2006","unstructured":"Steffen P, Voss B, Rehmsmeier M, Reeder J, Giegerich R: RNAshapes: anintegrated RNA analysis package based on abstract shapes. Bioinformatics. 2006, 22 (4): 500-503. 10.1093\/bioinformatics\/btk010.","journal-title":"Bioinformatics"},{"key":"194_CR4","first-page":"159","volume-title":"Bioinformatics Conference, 2003. CSB 2003. Proceedings of the 2003 IEEE","author":"M H\u00f6chsmann","year":"2003","unstructured":"H\u00f6chsmann M, Toller T, Giegerich R, Kurtz S: Local similarity in RNA secondary structures. Bioinformatics Conference, 2003. CSB 2003. Proceedings of the 2003 IEEE. 2003, IEEE, 159-168. 10.1109\/CSB.2003.1227315.."},{"issue":"2","key":"194_CR5","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1089\/10665270252935511","volume":"9","author":"T Jiang","year":"2002","unstructured":"Jiang T, Lin G, Ma B, Zhang K: A general edit distance between RNA structures. J Comput Biol. 2002, 9 (2): 371-388. 10.1089\/10665270252935511.","journal-title":"J Comput Biol"},{"key":"194_CR6","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/3-540-48452-3_21","volume-title":"Combinatorial Pattern Matching","author":"K Zhang","year":"1999","unstructured":"Zhang K, Wang L, Ma B: Computing similarity between RNA structures. Combinatorial Pattern Matching. 1999, Springer, 281-293."},{"issue":"1-3","key":"194_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Bille","year":"2005","unstructured":"Bille P: A survey on tree edit distance and related problems. Theor Comput Sci. 2005, 337 (1-3): 217-239. 10.1016\/j.tcs.2004.12.030.","journal-title":"Theor Comput Sci"},{"key":"194_CR8","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","volume":"143","author":"T Jiang","year":"1995","unstructured":"Jiang T, Wang L, Zhang K: Alignment of trees\u2014an alternative to tree edit. Theor Comput Sci. 1995, 143: 137-148.","journal-title":"Theor Comput Sci"},{"key":"194_CR9","first-page":"126","volume-title":"INTSYS \u201998: Proceedings of the IEEE International Joint Symposia on Intelligence and Systems","author":"K Zhang","year":"1998","unstructured":"Zhang K: Computing similarity between RNA secondary structures. INTSYS \u201998: Proceedings of the IEEE International Joint Symposia on Intelligence and Systems. 1998, Washington: IEEE Computer Society, 126-126."},{"issue":"5","key":"194_CR10","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/0010-4809(89)90039-6","volume":"22","author":"S Le","year":"1989","unstructured":"Le S, Nussinov R, Maizel J: Tree graphs of RNA secondary structures and their comparisons. Comput Biomed Res. 1989, 22 (5): 461-473. 10.1016\/0010-4809(89)90039-6.","journal-title":"Comput Biomed Res"},{"key":"194_CR11","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-21458-5_11","volume-title":"Combinatorial Pattern Matching","author":"S Schirmer","year":"2011","unstructured":"Schirmer S, Giegerich R: Forest alignment with affine gaps and anchors. Combinatorial Pattern Matching. 2011, Springer, 104-117. 10.1007\/978-3-642-21458-5\\_11."},{"issue":"2","key":"194_CR12","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"I Hofacker","year":"1994","unstructured":"Hofacker I, Fontana W, Stadler P, Bonhoeffer L, Tacker M, Schuster P: Fast folding and comparison of RNA secondary structures. Monatshefte fur Chemie\/Chemical Monthly. 1994, 125 (2): 167-188. 10.1007\/BF00818163.","journal-title":"Monatshefte fur Chemie\/Chemical Monthly"},{"key":"194_CR13","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1186\/1471-2105-6-89","volume":"6","author":"J Liu","year":"2005","unstructured":"Liu J, Wang J, Hu J, Tian B: A method for aligning RNA secondary structures and its application to RNA motif detection. BMC Bioinformatics. 2005, 6: 89-10.1186\/1471-2105-6-89.","journal-title":"BMC Bioinformatics"},{"issue":"2","key":"194_CR14","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1109\/TCBB.2008.28","volume":"7","author":"G Blin","year":"2010","unstructured":"Blin G, Denise A, Dulucq S, Herrbach C, Touzet H: Alignments of RNA structures. Comput Biol Bioinformatics, IEEE\/ACM Trans. 2010, 7 (2): 309-322.","journal-title":"Comput Biol Bioinformatics, IEEE\/ACM Trans"},{"key":"194_CR15","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11575832_39","volume-title":"String Processing and Information Retrieval","author":"J Allali","year":"2005","unstructured":"Allali J, Sagot M: A multiple graph layers model with application to RNA secondary structures comparison. String Processing and Information Retrieval. 2005, Springer, 348-359. 10.1007\/11575832\\_39."},{"key":"194_CR16","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.virusres.2005.10.011","volume":"119","author":"E Jan","year":"2006","unstructured":"Jan E: Divergent IRES elements in invertebrates. Virus Res. 2006, 119: 16-28. 10.1016\/j.virusres.2005.10.011.","journal-title":"Virus Res"},{"issue":"5","key":"194_CR17","doi-asserted-by":"publisher","first-page":"e1002031","DOI":"10.1371\/journal.pcbi.1002031","volume":"7","author":"J Perreault","year":"2011","unstructured":"Perreault J, Weinberg Z, Roth A, Popescu O, Chartrand P, Ferbeyre G, Breaker R: Identification of hammerhead ribozymes in all domains of life reveals novel structural variations. PLoS Comput Biol. 2011, 7 (5): e1002031-10.1371\/journal.pcbi.1002031.","journal-title":"PLoS Comput Biol"},{"key":"194_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.1432-1033.1997.t01-3-00001.x","volume":"245","author":"K Birikh","year":"1997","unstructured":"Birikh K, Heaton P, Eckstein F: The structure, function and application of the hammerhead ribozyme. Eur J Biochem. 1997, 245: 1-16. 10.1111\/j.1432-1033.1997.t01-3-00001.x.","journal-title":"Eur J Biochem"},{"issue":"18","key":"194_CR19","doi-asserted-by":"publisher","first-page":"4093","DOI":"10.1093\/nar\/26.18.4093","volume":"26","author":"E Haas","year":"1998","unstructured":"Haas E, Brown J: Evolutionary variation in bacterial RNase P RNAs. Nucleic Acids Res. 1998, 26 (18): 4093-4099. 10.1093\/nar\/26.18.4093.","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"194_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0020-0190(94)90062-0","volume":"49","author":"K Zhang","year":"1994","unstructured":"Zhang K, Jiang T: Some MAX SNP-hard results concerning unordered labeled trees. Inf Process Lett. 1994, 49 (5): 249-254. 10.1016\/0020-0190(94)90062-0.","journal-title":"Inf Process Lett"},{"key":"194_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D Matula","year":"1978","unstructured":"Matula D: Subtree isomorphism in O(n5\/2). Ann Discrete Math. 1978, 2: 91-106.","journal-title":"Ann Discrete Math"},{"key":"194_CR22","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1999.1044","volume":"33","author":"R Shamir","year":"1999","unstructured":"Shamir R, Tsur D: Faster subtree isomorphism. J Algorithms. 1999, 33: 267-280. 10.1006\/jagm.1999.1044.","journal-title":"J Algorithms"},{"key":"194_CR23","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"M Chung","year":"1987","unstructured":"Chung M: O(n2.5) time algorithms for the subgraph homeomorphism problem on trees. J Algorithms. 1987, 8: 106-112. 10.1016\/0196-6774(87)90030-7.","journal-title":"J Algorithms"},{"key":"194_CR24","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1137\/0206053","volume":"6","author":"S Reyner","year":"1977","unstructured":"Reyner S: An analysis of a good algorithm for the subtree problem. SIAM J Comput. 1977, 6: 730-10.1137\/0206053.","journal-title":"SIAM J Comput"},{"issue":"2-4","key":"194_CR25","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/j.jda.2004.08.017","volume":"3","author":"G Valiente","year":"2005","unstructured":"Valiente G: Constrained tree inclusion. J Discrete Algorithms. 2005, 3 (2-4): 431-447. 10.1016\/j.jda.2004.08.017.","journal-title":"J Discrete Algorithms"},{"issue":"3","key":"194_CR26","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1016\/j.jda.2007.07.001","volume":"6","author":"RY Pinter","year":"2008","unstructured":"Pinter RY, Rokhlenko O, Tsur D, Ziv-Ukelson M: Approximate labelled subtree homeomorphism. J Discrete Algorithms. 2008, 6 (3): 480-496. 10.1016\/j.jda.2007.07.001.","journal-title":"J Discrete Algorithms"},{"issue":"3","key":"194_CR27","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF01975866","volume":"15","author":"K Zhang","year":"1996","unstructured":"Zhang K: A constrained edit distance between unordered labeled trees. Algorithmica. 1996, 15 (3): 205-222. 10.1007\/BF01975866.","journal-title":"Algorithmica"},{"issue":"2","key":"194_CR28","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1137\/S0097539797332275","volume":"30","author":"M Kao","year":"2000","unstructured":"Kao M, Lam T, Sung W, Ting H: Cavity matchings, label compressions, and unrooted evolutionary trees. SIAM J Comput. 2000, 30 (2): 602-624. 10.1137\/S0097539797332275.","journal-title":"SIAM J Comput"},{"key":"194_CR29","first-page":"333","volume-title":"Studies in Discrete Optimization","author":"E Dinic","year":"1976","unstructured":"Dinic E: On solution of two assignment problems. Studies in Discrete Optimization. Edited by: Fridman A. 1976, Nauka. Moscow: Nauka, 333-348."},{"issue":"2","key":"194_CR30","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds J, Karp R: Theoretical improvements in algorithmic efficiency for network flow problems. J ACM (JACM). 1972, 19 (2): 248-264. 10.1145\/321694.321699.","journal-title":"J ACM (JACM)"},{"issue":"3","key":"194_CR31","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M Fredman","year":"1987","unstructured":"Fredman M, Tarjan R: Fibonacci heaps and their uses in improved network optimization algorithms. J ACM (JACM). 1987, 34 (3): 596-615. 10.1145\/28869.28874.","journal-title":"J ACM (JACM)"},{"key":"194_CR32","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H Gabow","year":"1989","unstructured":"Gabow H, Tarjan R: Faster scaling algorithms for network problems. SIAM J Comput. 1989, 18: 1013-10.1137\/0218069.","journal-title":"SIAM J Comput"},{"key":"194_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01586040","volume":"54","author":"J Orlin","year":"1992","unstructured":"Orlin J, Ahuja R: New scaling algorithms for the assignment and minimum mean cycle problems. Math Program. 1992, 54: 41-56. 10.1007\/BF01586040.","journal-title":"Math Program"},{"issue":"3","key":"194_CR34","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S Needleman","year":"1970","unstructured":"Needleman S, Wunsch C, et al: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970, 48 (3): 443-453. 10.1016\/0022-2836(70)90057-4.","journal-title":"J Mol Biol"},{"issue":"2","key":"194_CR35","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(90)90109-B","volume":"35","author":"M Maes","year":"1990","unstructured":"Maes M: On a cyclic string-to-string correction problem. Inf Process Lett. 1990, 35 (2): 73-78. 10.1016\/0020-0190(90)90109-B.","journal-title":"Inf Process Lett"},{"issue":"4","key":"194_CR36","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/S0097539795288489","volume":"27","author":"JP Schmidt","year":"1998","unstructured":"Schmidt JP: All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J Comput. 1998, 27 (4): 972-992. 10.1137\/S0097539795288489.","journal-title":"SIAM J Comput"},{"issue":"4","key":"194_CR37","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/s11786-007-0033-3","volume":"1","author":"A Tiskin","year":"2008","unstructured":"Tiskin A: Semi-local string comparison: Algorithmic techniques and applications. Math Comput Sci. 2008, 1 (4): 571-603. 10.1007\/s11786-007-0033-3.","journal-title":"Math Comput Sci"},{"issue":"3","key":"194_CR38","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/0031-3203(94)00109-Y","volume":"28","author":"K Zhang","year":"1995","unstructured":"Zhang K: Algorithms for the constrained editing distance between ordered labeled trees and related problems. Pattern Recognit. 1995, 28 (3): 463-474. 10.1016\/0031-3203(94)00109-Y.","journal-title":"Pattern Recognit"},{"key":"194_CR39","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms, Volume 44","author":"R Tarjan","year":"1983","unstructured":"Tarjan R: Data Structures and Network Algorithms, Volume 44. 1983, Society for, Industrial Mathematics, 10.1137\/1.9781611970265.fm."},{"issue":"3","key":"194_CR40","first-page":"252","volume":"41","author":"R Ahuja","year":"1995","unstructured":"Ahuja R, Magnanti T, Orlin J, Weihe K: Network flows: theory, algorithms and applications. ZOR-Methods Models Oper Res. 1995, 41 (3): 252-254.","journal-title":"ZOR-Methods Models Oper Res"},{"issue":"4","key":"194_CR41","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum M, Floyd R, Pratt V, Rivest R, Tarjan R: Time bounds for selection. J Comput Syst Sci. 1973, 7 (4): 448-461. 10.1016\/S0022-0000(73)80033-9.","journal-title":"J Comput Syst Sci"},{"key":"194_CR42","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E Dijkstra","year":"1959","unstructured":"Dijkstra E: A note on two problems in connexion with graphs. Numerische mathematik. 1959, 1: 269-271. 10.1007\/BF01386390.","journal-title":"Numerische mathematik"},{"key":"194_CR43","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E Lawler","year":"1976","unstructured":"Lawler E: Combinatorial Optimization: Networks and Matroids. 1976, New York: Holt,Rinehart and Winston"},{"key":"194_CR44","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1063\/1.3051024","volume":"16","author":"L Ford Jr","year":"1963","unstructured":"Ford Jr L, Fulkerson D, Ziffer A: Flows in networks. Phys Today. 1963, 16: 54-","journal-title":"Phys Today"},{"issue":"3","key":"194_CR45","first-page":"387","volume":"4","author":"B Shapiro","year":"1986","unstructured":"Shapiro B: An algorithm for comparing multiple RNA secondary structures. Comput Appl Biosci. 1986, 4 (3): 387-393.","journal-title":"Comput Appl Biosci"},{"key":"194_CR46","first-page":"167","volume":"1","author":"M Waterman","year":"1978","unstructured":"Waterman M: Secondary structure of single-stranded nucleic acids. Adv Math Suppl Studies. 1978, 1: 167-212.","journal-title":"Adv Math Suppl Studies"},{"issue":"9","key":"194_CR47","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/bip.360330909","volume":"33","author":"W Fontana","year":"1993","unstructured":"Fontana W, Konings D, Stadler P, Schuster P: Statistics of RNA secondary structures. Biopolymers. 1993, 33 (9): 1389-1404. 10.1002\/bip.360330909.","journal-title":"Biopolymers"},{"key":"194_CR48","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1109\/TCBB.2004.11","volume":"1","author":"M H\u00f6chsmann","year":"2004","unstructured":"H\u00f6chsmann M, Voss B, Giegerich R: Pure multiple RNA secondary structure alignments: a progressive profile approach. IEEE Trans Comput Biol Bioinformatics. 2004, 1: 53-62. 10.1109\/TCBB.2004.11.","journal-title":"IEEE Trans Comput Biol Bioinformatics"},{"key":"194_CR49","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/1471-2105-4-44","volume":"4","author":"R Klein","year":"2003","unstructured":"Klein R, Eddy S: RSEARCH: finding homologs of single structured RNA sequences. BMC Bioinformatics. 2003, 4: 44-10.1186\/1471-2105-4-44.","journal-title":"BMC Bioinformatics"},{"key":"194_CR50","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1186\/1471-2105-9-340","volume":"9","author":"M Andronescu","year":"2008","unstructured":"Andronescu M, Bereg V, Hoos HH, Condon A: RNA STRAND: the RNA secondary structure and statistical analysis database. BMC Bioinformatics. 2008, 9: 340-10.1186\/1471-2105-9-340.","journal-title":"BMC Bioinformatics"},{"key":"194_CR51","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1080\/01621459.1951.10500769","volume":"46","author":"F Massey Jr","year":"1951","unstructured":"Massey Jr F: The Kolmogorov-Smirnov test for goodness of fit. J Am Stat Assoc. 1951, 46: 68-78. 10.1080\/01621459.1951.10500769.","journal-title":"J Am Stat Assoc"},{"issue":"8","key":"194_CR52","doi-asserted-by":"crossref","first-page":"1919","DOI":"10.1128\/jb.177.8.1919-1928.1995","volume":"177","author":"NR Pace","year":"1995","unstructured":"Pace NR, Brown JW: Evolutionary perspective on the structure and function of ribonuclease P, a ribozyme. J Bacteriol. 1995, 177 (8): 1919-1928.","journal-title":"J Bacteriol"},{"key":"194_CR53","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1093\/nar\/27.1.314","volume":"27","author":"J Brown","year":"1999","unstructured":"Brown J: The ribonuclease P database. Nucleic Acids Res. 1999, 27: 314-10.1093\/nar\/27.1.314.","journal-title":"Nucleic Acids Res"},{"issue":"5","key":"194_CR54","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/S0092-8674(00)81134-4","volume":"92","author":"J Murray","year":"1998","unstructured":"Murray J, Terwey D, Maloney L, Karpeisky A, Usman N, Beigelman L, Scott W: The structural basis of hammerhead ribozyme self-cleavage. Cell. 1998, 92 (5): 665-673. 10.1016\/S0092-8674(00)81134-4.","journal-title":"Cell"},{"key":"194_CR55","first-page":"1","volume-title":"RNA and the Regulation of Gene Expression: A Hidden Layer of Complexity","author":"J Hean","year":"2008","unstructured":"Hean J, Weinberg M: The hammerhead ribozyme revisited: new biological insights. RNA and the Regulation of Gene Expression: A Hidden Layer of Complexity. Edited by: Morris KV. 2008, Caister Academic, Pr, 1-1."},{"issue":"26","key":"194_CR56","first-page":"6","volume":"268","author":"H Pley","year":"1965","unstructured":"Pley H, Lindes D, DeLuca-Flaherty C, McKay D: Crystals of a hammerhead ribozyme. J Biol Chem. 1965, 268 (26): 6-","journal-title":"J Biol Chem"},{"key":"194_CR57","first-page":"214","volume-title":"Nucleic Acids Symposium Series, Volume 34","author":"W Scott","year":"1995","unstructured":"Scott W, Finch J, Klug A: The crystal structure of an all-RNA hammerhead ribozyme. Nucleic Acids Symposium Series, Volume 34. 1995, IRL PRESS LTD, 214-216."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-8-13.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T00:57:36Z","timestamp":1630544256000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-8-13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,16]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["194"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-8-13","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,16]]},"assertion":[{"value":"20 December 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2013","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"13"}}