{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T15:31:27Z","timestamp":1774452687702,"version":"3.50.1"},"reference-count":34,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2000,8,1]],"date-time":"2000-08-01T00:00:00Z","timestamp":965088000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4733,"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":[[2000,8]]},"DOI":"10.1016\/s0166-218x(00)00188-8","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T13:13:06Z","timestamp":1027602786000},"page":"113-142","source":"Crossref","is-referenced-by-count":26,"title":["An analytic study of the phase transition line in local sequence alignment with gaps"],"prefix":"10.1016","volume":"104","author":[{"given":"R.","family":"Bundschuh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Hwa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(00)00188-8_BIB1","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1214\/aoap\/1177004903","article-title":"The rate of convergence of the mean length of the longest common subsequence","volume":"4","author":"Alexander","year":"1994","journal-title":"Ann. Appl. Probab."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB3","doi-asserted-by":"crossref","first-page":"106","DOI":"10.2307\/3214238","article-title":"Stochastic scrabbles: a law of large numbers for sequence matching with scores","volume":"25","author":"Arratia","year":"1988","journal-title":"J. Appl. Probab."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB4","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1214\/aoap\/1177005208","article-title":"A phase transition for the score in matching random sequences allowing deletions","volume":"4","author":"Arratia","year":"1994","journal-title":"Ann. Appl. Probab."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB5","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s100510050616","article-title":"Extensive simulations for longest common subsequences","volume":"7","author":"Boutet de Monvel","year":"1999","journal-title":"European Phys. J. B"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB6","unstructured":"R. Bundschuh, High precision simulations of the longest common subsequence problem, in preparation."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB7","unstructured":"R. Bundschuh, T. Hwa, in preparation."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB8","doi-asserted-by":"crossref","first-page":"306","DOI":"10.2307\/3212444","article-title":"Longest common subsequences of two random sequences","volume":"12","author":"Chv\u00e1tal","year":"1975","journal-title":"J. Appl. Probab."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB9","unstructured":"V. Dan\u010d\u0131\u0301k, Expected length of longest common subsequences, Ph.D. Thesis, University of Warwick (1994)."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB10","doi-asserted-by":"crossref","unstructured":"V. Dan\u010d\u0131\u0301k, M. Paterson, Upper bounds for expected length of a longest common subsequence of two random sequences STACS94, Lecture Notes in Computer Science, Vol. 775, Springer, Berlin, 1994, pp. 669\u2013678.","DOI":"10.1007\/3-540-57785-8_180"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB11","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0012-365X(79)90057-8","article-title":"Some limit results for longest common subsequences","volume":"26","author":"Deken","year":"1979","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB12","doi-asserted-by":"crossref","first-page":"1737","DOI":"10.1214\/aop\/1176990232","article-title":"Strong limit theorems of empirical functionals for large exceedances of partial sums of iid variables","volume":"19","author":"Dembo","year":"1991","journal-title":"Ann. Probab."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB13","series-title":"Methods in Enzymology, Vol. 266","author":"Doolittle","year":"1996"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB14","first-page":"75","article-title":"DNA sequence alignment and critical phenomena","volume":"263","author":"Drasdo","year":"1997","journal-title":"Mater. Res. Soc. Symp. Proc."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB15","series-title":"Proceedings of the sixth International Conference on Intelligent Systems for Molecular Biology","first-page":"52","article-title":"Scaling laws and similarity detection in sequence alignment with gaps","author":"Drasdo","year":"1998"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB16","doi-asserted-by":"crossref","first-page":"2591","DOI":"10.1103\/PhysRevLett.76.2591","article-title":"Similarity detection and localization","volume":"76","author":"Hwa","year":"1996","journal-title":"Phys. Rev. Lett."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB17","series-title":"Proceedings of the Second Annual International Conference on Computational Molecular Biology","first-page":"109","article-title":"Optimal detection of sequence similarity by local alignment","author":"Hwa","year":"1998"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB18","doi-asserted-by":"crossref","first-page":"2264","DOI":"10.1073\/pnas.87.6.2264","article-title":"Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes","volume":"87","author":"Karlin","year":"1990","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB19","doi-asserted-by":"crossref","first-page":"5873","DOI":"10.1073\/pnas.90.12.5873","article-title":"Applications and statistics for multiple high-scoring segments in molecular sequences","volume":"90","author":"Karlin","year":"1993","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB20","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/1427732","article-title":"Limit distributions of maximal segmental score among Markov-dependent partial sums","volume":"24","author":"Karlin","year":"1992","journal-title":"Adv. Appl. Probab."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB21","unstructured":"H. Kesten, Aspects of first-passage percolation, Ecole d'Et\u00e9 de Probabilit\u00e9s de Saint Flour XIV, Lecture Notes in Mathematics, Vol. 1180, Springer, Berlin, 1986, pp. 125\u2013264."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB22","series-title":"Solids Far From Equilibrium: Growth, Morphology, and Defects","first-page":"479","article-title":"Kinetic Roughening of Growing Surfaces","author":"Krug","year":"1991"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB23","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1126\/science.2983426","article-title":"Rapid and sensitive protein similarity searches","volume":"227","author":"Lipman","year":"1985","journal-title":"Science"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB24","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB25","doi-asserted-by":"crossref","unstructured":"R. Olsen, T. Hwa, M. L\u00e4ssig, Optimizing Smith-Waterman Alignments, Proceedings of the Fourth Pacific Symposium on Biocomputing, 1998, to appear.","DOI":"10.1142\/9789814447300_0030"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB26","doi-asserted-by":"crossref","unstructured":"M. Paterson, V. Dan\u010d\u0131\u0301k, Longest common subsequences, Proceedings of the 19th international Symposium of Mathematical Foundations of Computer Science 1994, MFSC\u201994, Springer, Berlin, 1994, pp. 127\u2013142.","DOI":"10.1007\/3-540-58338-6_63"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB27","doi-asserted-by":"crossref","first-page":"2444","DOI":"10.1073\/pnas.85.8.2444","article-title":"Improved tools for biological sequence comparison","volume":"85","author":"Pearson","year":"1988","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB28","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1016\/0196-8858(81)90046-4","article-title":"Comparison of biosequences","volume":"2","author":"Smith","year":"1981","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB29","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1214\/aos\/1176349952","article-title":"An Efron-Stein inequality for nonsymmetric statistics","volume":"14","author":"Steele","year":"1986","journal-title":"Ann. Statist."},{"key":"10.1016\/S0166-218X(00)00188-8_BIB30","series-title":"Probability Theory and Combinatorial Optimization","author":"Steele","year":"1997"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB31","author":"Waterman","year":"1989"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB32","series-title":"Introduction to Computational Biology","author":"Waterman","year":"1994"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB33","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1098\/rstb.1994.0077","article-title":"Estimating statistical significance of Sequence alignments","volume":"344","author":"Waterman","year":"1994","journal-title":"Philos. Trans. Roy. Soc. London B"},{"key":"10.1016\/S0166-218X(00)00188-8_BIB34","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1073\/pnas.84.5.1239","article-title":"Phase transitions in sequence matches and nucleic acid structure","volume":"84","author":"Waterman","year":"1987","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00001888?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00001888?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,12]],"date-time":"2020-01-12T20:15:27Z","timestamp":1578860127000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X00001888"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8]]},"references-count":34,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2000,8]]}},"alternative-id":["S0166218X00001888"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(00)00188-8","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2000,8]]}}}