{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T09:18:40Z","timestamp":1700644720636},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,11,2]],"date-time":"2006-11-02T00:00:00Z","timestamp":1162425600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2006,12,28]]},"DOI":"10.1007\/s10878-006-9020-x","type":"journal-article","created":{"date-parts":[[2006,11,2]],"date-time":"2006-11-02T17:46:55Z","timestamp":1162489615000},"page":"179-188","source":"Crossref","is-referenced-by-count":7,"title":["RNA multiple structural alignment with longest common subsequences"],"prefix":"10.1007","volume":"13","author":[{"given":"Sergey","family":"Bereg","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Kubica","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,11,2]]},"reference":[{"key":"9020_CR1","doi-asserted-by":"crossref","unstructured":"Chin FYL, De Santis A, Ferrara AL, Ho NL, Kim SK (2004) A simple algorithm for the constrained sequence problems. Inform Proc Lett 90(4):175\u2013179","DOI":"10.1016\/j.ipl.2004.02.008"},{"key":"9020_CR2","unstructured":"Cormen T, Leiserson C, Rivest R, Stein C (2001) Introduction to Algorithms, 2nd edn, MIT Press"},{"issue":"1","key":"9020_CR3","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0022-5193(65)90096-2","volume":"8","author":"M Dayhoff","year":"1965","unstructured":"Dayhoff M (1965) Computer aids to protein sequence determination. J Theoret Biol 8(1):97\u2013112","journal-title":"J Theoret Biol"},{"issue":"1","key":"9020_CR4","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1038\/scientificamerican0769-86","volume":"221","author":"M Dayhoff","year":"1969","unstructured":"Dayhoff M (1969) Computer analysis of protein evolution. Sci Am 221(1):86\u201395","journal-title":"Sci Am"},{"key":"9020_CR5","doi-asserted-by":"crossref","unstructured":"Davydov E, Batzoglu S (2004) A computational model for RNA multiple structural alignment. In: Proc. 15th Ann. Symp. Combinatorial Pattern Matching, LNCS 3109, pp 254\u2013269","DOI":"10.1007\/978-3-540-27801-6_19"},{"key":"9020_CR6","doi-asserted-by":"crossref","unstructured":"Deng X, Li G, Li Z, Ma B, Wang L (2002) A PTAS for distinguishing (sub)string selection. In: Proc. ICALP\u201902, pp 740\u2013751","DOI":"10.1007\/3-540-45465-9_63"},{"key":"9020_CR7","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1038\/35103511","volume":"2","author":"SR Eddy","year":"2001","unstructured":"Eddy SR (2001) Noncoding RNA genes and the modern RNA world. Nat Rev Genet 2:919\u2013929","journal-title":"Nat Rev Genet"},{"key":"9020_CR8","doi-asserted-by":"crossref","unstructured":"Goldman D, Istrail S, Papadimitriou C (1999) Algorithmic aspects of protein structure similarity. In: Proc. 40th Ann. Symp. Foundations of Computer Science (FOCS\u201999), pp 512\u2013522","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"9020_CR9","unstructured":"Greenberg RI (2003) Bounds on the Number of the Longest Common Subsequence Problem. CoRR cs.DM\/0301030"},{"key":"9020_CR10","unstructured":"Hirschberg D (1975) The longest common subsequence problem. PhD Thesis, Princeton University"},{"key":"9020_CR11","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01934514","volume":"24","author":"WJ Hsu","year":"1984","unstructured":"Hsu WJ, Du MW (1984) Computing a longest common subsequence for a set of strings. BIT 24:45\u201359","journal-title":"BIT"},{"issue":"5","key":"9020_CR12","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T Jiang","year":"1995","unstructured":"Jiang T, Li M (1995) On the approximation of shortest common supersequences and longest common subsequences. SIAM J Comput 24(5):1122\u20131139","journal-title":"SIAM J Comput"},{"key":"9020_CR13","doi-asserted-by":"crossref","unstructured":"Kubica M, Rizzi R, Vialette S, Walen T (2006) Approximation of RNA multiple structural alignment. In: Proc. 17th Ann Symp Combinatorial Pattern Matching, LNCS 4009, pp 211\u2013222","DOI":"10.1007\/11780441_20"},{"key":"9020_CR14","unstructured":"Lanctot K, Li M, Ma B, Wang S, Zhang L (1999) Distinguishing string selection problems. In: Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp 633\u2013642"},{"key":"9020_CR15","doi-asserted-by":"crossref","unstructured":"Li M, Ma B, Wang L (1999) Finding similar regions in many strings. In: Proc. 31st ACM Symp. on Theory of Computing (STOC\u201999), pp 473\u2013482","DOI":"10.1145\/301250.301376"},{"key":"9020_CR16","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier D (1978) The complexity of some problems on subsequences and supersequences. J ACM 25:322\u2013336","journal-title":"J ACM"},{"key":"9020_CR17","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R Nussinov","year":"1978","unstructured":"Nussinov R, Pieczenik G, Griggs J, Kleitman D (1978) Algorithms for loop matching. SIAM J Appl Math 35:68\u201382","journal-title":"SIAM J Appl Math"},{"key":"9020_CR18","doi-asserted-by":"crossref","unstructured":"Rick C (2000) Efficient computation of all longest common subsequences. In: Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT\u201900), pp 407\u2013418","DOI":"10.1007\/3-540-44985-X_35"},{"key":"9020_CR19","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","volume":"285","author":"E Rivas","year":"1999","unstructured":"Rivas E, Eddy SR (1999) A dynamic programming algorithm for RNA structure prediction including pseudoknots. J Mol Biol 285:2053\u20132068","journal-title":"J Mol Biol"},{"key":"9020_CR20","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith TF, Waterman MS (1981) Identification of common molecular subsequences. J Mol Biol 147:195\u2013197","journal-title":"J Mol Biol"},{"key":"9020_CR21","doi-asserted-by":"crossref","unstructured":"Tsai Y-T (2003) The constrained longest common subsequence problem. Inform Proc Lett 88(4):173\u2013176","DOI":"10.1016\/j.ipl.2003.07.001"},{"key":"9020_CR22","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zucker","year":"1981","unstructured":"Zucker M, Stiegler P (1981) Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res 9:133\u2013148","journal-title":"Nucleic Acids Res"},{"key":"9020_CR23","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/0076-6879(89)80106-5","volume":"180","author":"M Zucker","year":"1989","unstructured":"Zucker M (1989) Computer prediction of RNA structure. Methods Enzymol 180:262\u2013288","journal-title":"Methods Enzymol"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9020-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-006-9020-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-006-9020-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:10Z","timestamp":1559276290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-006-9020-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,11,2]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,12,28]]}},"alternative-id":["9020"],"URL":"https:\/\/doi.org\/10.1007\/s10878-006-9020-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,11,2]]}}}