{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:32:39Z","timestamp":1725550359356},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540290087"},{"type":"electronic","value":"9783540318125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11557067_31","type":"book-chapter","created":{"date-parts":[[2005,10,20]],"date-time":"2005-10-20T14:02:33Z","timestamp":1129816953000},"page":"376-388","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Parameterized Algorithm for Biopolymer Structure-Sequence Alignment"],"prefix":"10.1007","author":[{"given":"Yinglei","family":"Song","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chunmei","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiuzhen","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell L.","family":"Malmberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liming","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Applied Mathematics\u00a023, 11\u201324 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1126\/science.1853201","volume":"253","author":"J. Bowie","year":"1991","unstructured":"Bowie, J., Luthy, R., Eisenberg, D.: A method to identify protein sequences that fold into a known three-dimensional structure. Science\u00a0253, 164\u2013170 (1991)","journal-title":"Science"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0959-440X(95)80082-4","volume":"5","author":"S.H. Bryant","year":"1995","unstructured":"Bryant, S.H., Altschul, S.F.: Statistics of sequence-structure threading. Curr. Opinion Struct. Biol.\u00a05, 236\u2013244 (1995)","journal-title":"Curr. Opinion Struct. Biol."},{"key":"31_CR6","unstructured":"Brown, M., Wilson, C.: RNA pseudoknot modeling using intersections of stochastic context free grammars with applications to database search. In: Pacific Symposium on Biocomputing, pp. 109\u2013125 (1995)"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Cai, L., Malmberg, R., Wu, Y.: Stochastic Modeling of Pseudoknot Structures: A Grammatical Approach. Bioinformatics\u00a019, i66\u2013i73 (2003)","DOI":"10.1093\/bioinformatics\/btg1007"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1042\/0264-6021:3430115","volume":"1","author":"T. Dandekar","year":"1999","unstructured":"Dandekar, T., Schuster, S., Snel, B., Huynen, M., Bork, P.: Pathway alignment: application to the comparative analysis of glycolytic enzymes. Biochemical Journal.\u00a01, 115\u2013124 (1999)","journal-title":"Biochemical Journal."},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1016\/j.cub.2004.05.054","volume":"14","author":"A.T. Dandjinou","year":"2004","unstructured":"Dandjinou, A.T., L\u00e9vesque, N., Larose, S., Lucier, J., Elela, S.A., Wellinger, R.J.: A phylogenetically based secondary structure for the yeast telomerase RNA. Current Biology\u00a014, 1148\u20131158 (2004)","journal-title":"Current Biology"},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1038\/80729","volume":"7","author":"J.A. Doudna","year":"2000","unstructured":"Doudna, J.A.: Structural genomics of RNA. Nature Structural Biology\u00a07(11) supp., 954\u2013956 (2000)","journal-title":"Nature Structural Biology"},{"key":"31_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0092-8674(02)00727-4","volume":"109","author":"S.R. Eddy","year":"2002","unstructured":"Eddy, S.R.: Computational genomics of non-coding RNA genes. Cell\u00a0109, 137\u2013140 (2002)","journal-title":"Cell"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","volume":"22","author":"S. Eddy","year":"1994","unstructured":"Eddy, S., Durbin, R.: RNA sequence analysis using covariance models. Nucleic Acids Research\u00a022, 2079\u20132088 (1994)","journal-title":"Nucleic Acids Research"},{"issue":"3","key":"31_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications\u00a03.3, 1\u201327 (1999)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1128\/JVI.78.2.669-682.2004","volume":"78","author":"S.J. Geobel","year":"2004","unstructured":"Geobel, S.J., Hsue, B., Dombrowski, T.F., Masters, P.S.: Characterization of the RNA components of a Putative Molecular Switch in the 3\u2019 Untranslated Region of the Murine Coronavirus Genome. Journal of Virology\u00a078, 669\u2013682 (2004)","journal-title":"Journal of Virology"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1093\/nar\/gkg006","volume":"31","author":"S. Griffiths-Jones","year":"2003","unstructured":"Griffiths-Jones, S., Bateman, A., Marshall, M., Khanna, A., Eddy, S.R.: Rfam: an RNA family database. Nucleic Acids Research\u00a031, 439\u2013441 (2003)","journal-title":"Nucleic Acids Research"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/1471-2105-4-44","volume":"4","author":"R.J. Klein","year":"2003","unstructured":"Klein, R.J., Eddy, S.R.: RSEARCH: Finding Homologs of Single Structured RNA Sequences. BMC Bioinformatics\u00a04, 44 (2003)","journal-title":"BMC Bioinformatics"},{"key":"31_CR18","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1093\/protein\/7.9.1069","volume":"7","author":"R.H. Lathrop","year":"1994","unstructured":"Lathrop, R.H.: The protein threading problem with sequence amino acid interaction preferences is NP-complete. Protein Engineering\u00a07, 1069\u20131068 (1994)","journal-title":"Protein Engineering"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Lathrop, R.H., Rogers Jr., R.G., Bienkowska, J., Bryant, B.K.M., Buturovic, L.J., Gaitatzes, C., Nambudripad, R., White, J.V., Smith, T.F.: Analysis and algorithms for protein sequence-structure alignment. In: Salzberg, Searls, Kasif (eds.) Computational Methods in Molecular Biology. Elsevier, Amsterdam (1998)","DOI":"10.1016\/S0167-7306(08)60469-X"},{"issue":"3","key":"31_CR20","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1089\/cmb.1998.5.517","volume":"5","author":"H.-P. Lenhof","year":"1998","unstructured":"Lenhof, H.-P., Reinert, K., Vingron, M.: A polyhedral approach to RNA sequence structure alignment. Journal of Computational Biology\u00a05(3), 517\u2013530 (1998)","journal-title":"Journal of Computational Biology"},{"key":"31_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1007\/11428848_123","volume-title":"Computational Science \u2013 ICCS 2005","author":"C. Liu","year":"2005","unstructured":"Liu, C., Song, Y., Malmberg, R., Cai, L.: Profiling and searching for RNA pseudoknot structures in genomes. In: Sunderam, V.S., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2005. LNCS, vol.\u00a03515, pp. 968\u2013975. Springer, Heidelberg (2005)"},{"key":"31_CR22","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1093\/nar\/25.5.955","volume":"25","author":"T.M. Lowe","year":"1997","unstructured":"Lowe, T.M., Eddy, S.R.: tRNAscan-SE: A Program for improved detection of transfer RNA genes in genomic sequence. Nucleic Acids Research\u00a025, 955\u2013964 (1997)","journal-title":"Nucleic Acids Research"},{"issue":"3","key":"31_CR23","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1089\/106652700750050862","volume":"7","author":"S.B. Lyngso","year":"2000","unstructured":"Lyngso, S.B., Pedersen, C.N.: RNA pseudoknot prediction in energy-based models. Journal of Computational Biololgy\u00a07(3), 409\u2013427 (2000)","journal-title":"Journal of Computational Biololgy"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J. Matousek","year":"1992","unstructured":"Matousek, J., Thomas, R.: On the complexity of finding iso- and other morphisms for partial k-trees. Discrete Mathematics\u00a0108, 343\u2013364 (1992)","journal-title":"Discrete Mathematics"},{"key":"31_CR25","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1126\/science.285.5428.751","volume":"285","author":"E.M. Marcotte","year":"1999","unstructured":"Marcotte, E.M., Matteo, P., Ng, H.L., Rice, D.W., Yeates, T.O., Eisenberg, D.: Detecting protein function and protein-protein interactions from genome sequences. Science\u00a0285, 751\u2013753 (1999)","journal-title":"Science"},{"issue":"3","key":"31_CR26","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1006\/jmbi.1998.2487","volume":"286","author":"N. Nameki","year":"1999","unstructured":"Nameki, N., Felden, B., Atkins, J.F., Gesteland, R.F., Himeno, H., Muto, A.: Functional and structural analysis of a pseudoknot upstream of the tag-encoded sequence in E. coli tmRNA. Journal of Molecular Biology\u00a0286(3), 733\u2013744 (1999)","journal-title":"Journal of Molecular Biology"},{"issue":"2","key":"31_CR27","first-page":"92","volume":"15","author":"D.D. Pervouchine","year":"2004","unstructured":"Pervouchine, D.D.: IRIS: Intermolecular RNA Interaction Search. Genome Informatics\u00a015(2), 92\u2013101 (2004)","journal-title":"Genome Informatics"},{"key":"31_CR28","doi-asserted-by":"crossref","unstructured":"Reinert, K., Lenhof, H.-P., Mutzel, P., Mehlhorn, K., Kececioglu, J.D.: A branch-and-cut algorithm for multiple sequence alignment. In: Proceedings of the first annual international conference on Computational molecular biology, pp. 241\u2013250 (1997)","DOI":"10.1145\/267521.267845"},{"key":"31_CR29","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1186\/1471-2105-2-8","volume":"2","author":"E. Rivas","year":"2001","unstructured":"Rivas, E., Eddy, S.R.: Noncoding RNA gene detection using comparative sequence analysis. BMC Bioinformatics\u00a02, 8 (2001)","journal-title":"BMC Bioinformatics"},{"key":"31_CR30","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"31_CR31","doi-asserted-by":"crossref","unstructured":"Song, Y., Liu, C., Malmberg, R., Pan, F., Cai, L.: Tree decomposition based fast search of RNA secondary structures in genomes. In: Proceedings of 2005 IEEE Computational Systems Biology Conference (2005), (in press)","DOI":"10.1109\/CSB.2005.52"},{"key":"31_CR32","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0304-3975(98)00090-5","volume":"210","author":"Y. Uemura","year":"1999","unstructured":"Uemura, Y., Hasegawa, A., Kobayashi, Y., Yokomori, T.: Tree adjoining grammars for RNA structure prediction. Theoretical Computer Science\u00a0210, 277\u2013303 (1999)","journal-title":"Theoretical Computer Science"},{"key":"31_CR33","doi-asserted-by":"publisher","first-page":"1589","DOI":"10.1093\/bioinformatics\/btg224","volume":"19","author":"G. Wang","year":"2003","unstructured":"Wang, G., Dunbrack Jr., R.L.: PISCES: a protein sequence culling server. Bioinformatics\u00a019, 1589\u20131591 (2003)","journal-title":"Bioinformatics"},{"key":"31_CR34","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1093\/bioinformatics\/16.3.257","volume":"16","author":"D. Xu","year":"2000","unstructured":"Xu, D., Unseren, M.A., Xu, Y., Uberbacher, E.C.: Sequence-structure specificity of a knowledge based energy function at the secondary structure level. Bioinformatics\u00a016, 257\u2013268 (2000)","journal-title":"Bioinformatics"},{"key":"31_CR35","doi-asserted-by":"crossref","unstructured":"Xu, J.: Rapid side-chain packing via tree decomposition. In: Proceedings of 2005 International Conference on Research in Computational Biology (to appear)","DOI":"10.1007\/11415770_32"},{"issue":"1","key":"31_CR36","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0219720003000186","volume":"1","author":"J. Xu","year":"2003","unstructured":"Xu, J., Li, M., Kim, D., Xu, Y.: RAPTOR: optimal protein threading by linear programming. Journal of Bioinformatics and Computational Biology\u00a01(1), 95\u2013113 (2003)","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"31_CR37","doi-asserted-by":"crossref","unstructured":"Xu, Y., Xu, D., Uberbacher, E.C.: An efficient computational method for globally optimal threading. Journal of Computational Biology\u00a05(3), 597\u2013614","DOI":"10.1089\/cmb.1998.5.597"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11557067_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:48:14Z","timestamp":1605642494000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11557067_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540290087","9783540318125"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/11557067_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}