{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T13:52:05Z","timestamp":1752673925358},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"S1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2009,1]]},"DOI":"10.1186\/1471-2105-10-s1-s10","type":"journal-article","created":{"date-parts":[[2009,1,30]],"date-time":"2009-01-30T15:04:44Z","timestamp":1233327884000},"source":"Crossref","is-referenced-by-count":7,"title":["Improved algorithms for approximate string matching (extended abstract)"],"prefix":"10.1186","volume":"10","author":[{"given":"Dimitris","family":"Papamichail","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georgios","family":"Papamichail","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,30]]},"reference":[{"key":"3193_CR1","first-page":"8","volume":"1","author":"V Levenstein","year":"1965","unstructured":"Levenstein V: Binary codes capable of correcting spurious insertions and deletions of ones. Probl Inf Transmission 1965, 1: 8\u201317.","journal-title":"Probl Inf Transmission"},{"key":"3193_CR2","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/BF01074755","volume":"4","author":"T Vintsyuk","year":"1968","unstructured":"Vintsyuk T: Speech discrimination by dynamic programming. Cybernetics 1968, 4: 52\u201358. 10.1007\/BF01074755","journal-title":"Cybernetics"},{"key":"3193_CR3","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: A general method applicable to the search for similarities in the amino acid sequences of two proteins. J Mol Biol. 1970, 48: 443\u2013453. 10.1016\/0022-2836(70)90057-4","journal-title":"J Mol Biol"},{"key":"3193_CR4","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D Sankoff","year":"1972","unstructured":"Sankoff D: Matching sequences under deletion\/insertion constraints. Proceedings of the National Academy of Sciences of the USA 1972, 69: 4\u20136. 10.1073\/pnas.69.1.4","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"key":"3193_CR5","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/0126070","volume":"26","author":"P Sellers","year":"1974","unstructured":"Sellers P: On the theory and computation of evolutionary distances. SIAM J Appl Math 1974, 26: 787\u2013793. 10.1137\/0126070","journal-title":"SIAM J Appl Math"},{"key":"3193_CR6","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R Wagner","year":"1974","unstructured":"Wagner R, Fisher M: The string to string correction problem. J ACM 1974, 21: 168\u2013178. 10.1145\/321796.321811","journal-title":"J ACM"},{"key":"3193_CR7","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/321879.321880","volume":"22","author":"D Lowrance","year":"1975","unstructured":"Lowrance D, Wagner R: An extension of the string-to-string correction problem. J ACM 1975, 22: 177\u2013183. 10.1145\/321879.321880","journal-title":"J ACM"},{"key":"3193_CR8","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W Masek","year":"1980","unstructured":"Masek W, Paterson M: A faster algorithm for computing string edit distances. J Comput Syst 1980, 20: 18\u201331. 10.1016\/0022-0000(80)90002-1","journal-title":"J Comput Syst"},{"issue":"5","key":"3193_CR9","first-page":"1209","volume":"11","author":"VL Arlazarov","year":"1970","unstructured":"Arlazarov VL, Dinic EA, A KM, Faradzev IA: On economic construction of the transitive closure of a directed graph. Soviet Math 1970, 11(5):1209\u20131212.","journal-title":"Soviet Math"},{"issue":"6","key":"3193_CR10","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS: A Linear Space Algorithm for Computing Maximal Common Subsequences. Communications of the ACM 1975, 18(6):341\u2013343. 10.1145\/360825.360861","journal-title":"Communications of the ACM"},{"key":"3193_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E Ukkonen","year":"1985","unstructured":"Ukkonen E: Algorithms for approximate string matching. Information and Control 1985, 64: 100\u2013118. 10.1016\/S0019-9958(85)80046-2","journal-title":"Information and Control"},{"key":"3193_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"EW Myers","year":"1986","unstructured":"Myers EW: An O(ND) difference algorithm and its variations. Algorithmica 1986, 1: 251\u2013266. 10.1007\/BF01840446","journal-title":"Algorithmica"},{"key":"3193_CR13","volume-title":"PhD thesis","author":"DR Powell","year":"2001","unstructured":"Powell DR: Algorithms for Sequence Alignment. PhD thesis. Monash University, School of Computer Science and Software Engineering; 2001."},{"key":"3193_CR14","unstructured":"Ribosomal Database Project (RDP)[\n                    http:\/\/rdp.cme.msu.edu\n                    \n                  ]"},{"key":"3193_CR15","unstructured":"Edit distance algorithm implementations[\n                    http:\/\/www.cs.miami.edu\/~dimitris\/edit_distance\n                    \n                  ]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-S1-S10.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-10-S1-S10\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-S1-S10.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,23]],"date-time":"2019-01-23T02:33:15Z","timestamp":1548210795000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-S1-S10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":15,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["3193"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-s1-s10","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]},"article-number":"S10"}}