{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T03:25:41Z","timestamp":1764905141123},"reference-count":41,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3796,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s0166-218x(02)00288-3","type":"journal-article","created":{"date-parts":[[2003,3,25]],"date-time":"2003-03-25T14:55:35Z","timestamp":1048604135000},"page":"95-117","source":"Crossref","is-referenced-by-count":6,"title":["Weighted sequence graphs: boosting iterated dynamic programming using locally suboptimal solutions"],"prefix":"10.1016","volume":"127","author":[{"given":"Benno","family":"Schwikowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Vingron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/S0166-218X(02)00288-3_BIB1","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/jmbi.1997.0951","article-title":"Prediction of complete gene structures in human genomic DNA","volume":"268","author":"Burge","year":"1997","journal-title":"J. Molecular Biol."},{"issue":"6","key":"10.1016\/S0166-218X(02)00288-3_BIB2","doi-asserted-by":"crossref","first-page":"1381","DOI":"10.1287\/opre.32.6.1381","article-title":"Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming","volume":"32","author":"Byers","year":"1984","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB3","series-title":"Proceedings of the 5th International Conference on Intelligent Systems for Molecular Biology","first-page":"116","article-title":"A probablistic learning approach to whole-genome operon prediction","author":"Craven","year":"2000"},{"issue":"2","key":"10.1016\/S0166-218X(02)00288-3_BIB4","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical improvements in algorithmic efficiency for network flow problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB5","unstructured":"M. Fr\u00f6hlich, M. Werner, Da Vinci V2.0x online documentation, University of Bremen, http:\/\/www.informatik.unibremen.de\/~davinci\/doc_V2.0\/, June 1996."},{"issue":"7","key":"10.1016\/S0166-218X(02)00288-3_BIB6","doi-asserted-by":"crossref","first-page":"1325","DOI":"10.1002\/pro.5560050711","article-title":"The structural alignment between two proteins: is there a unique answer?","volume":"5","author":"Godzik","year":"1996","journal-title":"Protein Sci."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB7","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1006\/jmbi.1996.0679","article-title":"Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments","volume":"264","author":"Gotoh","year":"1996","journal-title":"J. Molecular Biol."},{"issue":"1","key":"10.1016\/S0166-218X(02)00288-3_BIB8","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02460299","article-title":"Efficient methods for multiple sequence alignment with guaranteed error bounds","volume":"55","author":"Gusfield","year":"1993","journal-title":"Bull. Math. Biol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB9","series-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB10","doi-asserted-by":"crossref","unstructured":"D. Gusfield, L. Wang, New uses for uniform lifted alignment, Series in Discrete Mathematics and Theoretical Computer Science, DIMACS, Vol. 47, American Mathematical Society, Providence, RI, 1999, pp. 33\u201352.","DOI":"10.1090\/dimacs\/047\/02"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB11","first-page":"649","article-title":"A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given","volume":"6","author":"Hein","year":"1989","journal-title":"Molecular Biol. Evol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB12","first-page":"669","article-title":"A tree reconstruction method that is economical in the number of pairwise comparisons used","volume":"6","author":"Hein","year":"1989","journal-title":"Molecular Biol. Evol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB13","doi-asserted-by":"crossref","unstructured":"J. Hein, Treealign, in: A.M. Griffin, H.G. Griffin (Eds.), Computer analysis of sequence data, Part II, Methods in Molecular Biology, Vol 25, Human Press, Totowa, USA, 1994, pp. 349\u2013364 (Chapter 28).","DOI":"10.1385\/0-89603-276-0:349"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB14","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02257378","article-title":"The alignment of sets of sequences and the construction of phyletic tress: an integrated method","volume":"20","author":"Hogeweg","year":"1984","journal-title":"J. Molecular Evol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB15","article-title":"The Steiner tree problem","volume":"Vol. 53","author":"Hwang","year":"1992"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB16","doi-asserted-by":"crossref","unstructured":"T. Jiang, E.L. Lawler, L. Wang, Aligning sequences via an evolutionary tree: complexity and approximation (extended abstract), in: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montreal, May 1994, pp. 760\u2013769.","DOI":"10.1145\/195058.195454"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB17","series-title":"Advances in Optimization and Approximation","first-page":"195","article-title":"Optimization problems in molecular biology","author":"Jiang","year":"1994"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB18","doi-asserted-by":"crossref","unstructured":"G. Lancia, R. Ravi, GESTALT: genomic Steiner alignments, in: Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching (CPM \u201999), Springer, Berlin, 1999, pp. 101\u2013114.","DOI":"10.1007\/3-540-48452-3_8"},{"key":"10.1016\/S0166-218X(02)00288-3_BIB19","unstructured":"F. Liu, Tree alignment and reconstruction v1.0, http:\/\/www.dcss.mcmaster.ca\/~filu\/taar_download.html, 1998."},{"issue":"2","key":"10.1016\/S0166-218X(02)00288-3_BIB20","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02459948","article-title":"Sequence comparison with concave weighting functions","volume":"50","author":"Miller","year":"1988","journal-title":"Bull. Math. Biol."},{"issue":"6","key":"10.1016\/S0166-218X(02)00288-3_BIB21","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1089\/10665270050514918","article-title":"Modeling amino acid replacement","volume":"7","author":"M\u00fcller","year":"2000","journal-title":"J. Comput. Biol."},{"issue":"4","key":"10.1016\/S0166-218X(02)00288-3_BIB22","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1089\/cmb.1994.1.349","article-title":"On near-optimal alignments of biological sequences","volume":"1","author":"Naor","year":"1994","journal-title":"J. Comput. Biol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB23","doi-asserted-by":"crossref","unstructured":"S.W. Perrey, J. Stoye, V. Moulton, A.W.M. Dress, On simultaneous versus iterative multiple sequence alignment, Universit\u00e4t Bielefeld, 1997, 111, preprint.","DOI":"10.1016\/S0893-9659(97)00013-X"},{"issue":"6","key":"10.1016\/S0166-218X(02)00288-3_BIB24","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1093\/oxfordjournals.molbev.a026369","article-title":"A fast algorithm for joint reconstruction of ancestral amino acid sequences","volume":"17","author":"Pupko","year":"2000","journal-title":"Molecular Biol. Evol."},{"issue":"3","key":"10.1016\/S0166-218X(02)00288-3_BIB25","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1006\/jmbi.1997.1101","article-title":"Protein fold recognition by prediction-based threading","volume":"270","author":"Rost","year":"1997","journal-title":"J. Molecular Biol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB26","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","article-title":"Minimal mutation trees of sequences","volume":"28","author":"Sankoff","year":"1975","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB27","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01732471","article-title":"Frequency of insertion-deletion, transversion, and transition in evolution of 5S ribosomal RNA","volume":"7","author":"Sankoff","year":"1976","journal-title":"J. Molecular Evol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB28","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1038\/newbio245232a0","article-title":"Evolution of 5S RNA and the non-randomness of base replacement","volume":"245","author":"Sankoff","year":"1973","journal-title":"Nature New Biol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB29","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1016\/0022-2836(91)90667-U","article-title":"A simple method to generate non-trivial alternate alignments of protein sequences","volume":"219","author":"Saqi","year":"1991","journal-title":"J. Molecular Biol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB30","unstructured":"B. Schwikowski, A new algorithmic approach to the construction of multiple alignments and evolutionary trees, GMD Research Series, No. 11, German National Center for Information Technology, St. Augustin, Germany, 1998."},{"issue":"3","key":"10.1016\/S0166-218X(02)00288-3_BIB31","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1089\/cmb.1997.4.415","article-title":"The deferred path heuristic for the generalized tree alignment problem","volume":"4","author":"Schwinkowski","year":"1997","journal-title":"J. Comput. Biol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB32","doi-asserted-by":"crossref","unstructured":"B. Schwikowski, M. Vingron, The deferred path heuristic for the generalized tree alignment problem, in: M. Waterman (Ed.), Proceedings of the Ist Annual International Conference on Computational Molecular Biology (RECOMB), Santa Fe, New Mexico, 1997, ACM Press, New York, pp. 257\u2013266.","DOI":"10.1145\/267521.267884"},{"issue":"1","key":"10.1016\/S0166-218X(02)00288-3_BIB33","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1093\/bioinformatics\/15.1.87","article-title":"BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs","volume":"15","author":"Thompson","year":"1999","journal-title":"Bioinformatics"},{"issue":"13","key":"10.1016\/S0166-218X(02)00288-3_BIB34","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":"10.1016\/S0166-218X(02)00288-3_BIB35","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/S0959-440X(96)80054-6","article-title":"Near-optimal sequence alignments","volume":"6","author":"Vingron","year":"1996","journal-title":"Current Opinion Struct. Biol."},{"issue":"7","key":"10.1016\/S0166-218X(02)00288-3_BIB36","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1093\/protein\/3.7.565","article-title":"Determination of reliable regions in protein sequence alignments","volume":"3","author":"Vingron","year":"1990","journal-title":"Protein Eng."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB37","unstructured":"M. Vingron, A. von Haeseler, Towards integration of multiple alignment and phylogenetic tree construction, Arbeitspapiere der GMD 852, GMD National Research Center for Information Technology, St. Augustin, Germany, June 1994."},{"issue":"1","key":"10.1016\/S0166-218X(02)00288-3_BIB38","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1089\/cmb.1997.4.23","article-title":"Towards integration of multiple alignment and phylogenetic tree construction","volume":"4","author":"Vingron","year":"1997","journal-title":"J. Comput. Biol."},{"issue":"4","key":"10.1016\/S0166-218X(02)00288-3_BIB39","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","article-title":"On the complexity of multiple sequence alignment","volume":"1","author":"Wang","year":"1994","journal-title":"J. Comput. Biol."},{"key":"10.1016\/S0166-218X(02)00288-3_BIB40","doi-asserted-by":"crossref","unstructured":"M. Zuker, Suboptimal sequence alignment in molecular biology, alignment with error analysis, J. Molecular Biol. (1991) 403\u2013420.","DOI":"10.1016\/0022-2836(91)80062-Y"},{"issue":"4","key":"10.1016\/S0166-218X(02)00288-3_BIB41","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02459506","article-title":"RNA secondary structures and their prediction","volume":"46","author":"Zuker","year":"1984","journal-title":"Bull. Math. Biol."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002883?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02002883?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T08:06:02Z","timestamp":1580889962000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02002883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,4]]}},"alternative-id":["S0166218X02002883"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00288-3","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}