{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:30Z","timestamp":1759638750658},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2013,12]]},"abstract":"Abstract<\/jats:title>\n \n Abstract<\/jats:title>\n We propose three algorithms for string edit distance with duplications and contractions. These include an efficient general algorithm and two improvements which apply under certain constraints on the cost function. The new algorithms solve a more general problem variant and obtain better time complexities with respect to previous algorithms. Our general algorithm is based on min-plus multiplication of square matrices and has time and space complexities of O<\/jats:italic> (|\u03a3<\/jats:italic>|MP<\/jats:italic> (n<\/jats:italic>)) and O<\/jats:italic> (|\u03a3<\/jats:italic>|n<\/jats:italic>\n 2<\/jats:sup>), respectively, where |\u03a3<\/jats:italic>| is the alphabet size, n<\/jats:italic> is the length of the strings, and MP<\/jats:italic> (n<\/jats:italic>) is the time bound for the computation of min-plus matrix multiplication of two n<\/jats:italic>\u2009\u00d7\u2009n<\/jats:italic>\u2009matrices (currently,<\/jats:p>\n \n \n \n MP<\/mml:mtext>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n O<\/mml:mi>\n \n \n \n \n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n log<\/mml:mtext>\n <\/mml:mrow>\n \n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mover>\n log<\/mml:mtext>\n n<\/mml:mi>\n <\/mml:mrow>\n \n \n \n log<\/mml:mtext>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mover>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:inline-formula> due to an algorithm by Chan).<\/jats:p>\n For integer cost functions, the running time is further improved to \n \n O<\/mml:mi>\n \n \n \n \n |<\/mml:mo>\n \u03a3<\/mml:mo>\n |<\/mml:mo>\n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n \n \n \n log<\/mml:mtext>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mover>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:inline-formula>. In addition, this variant of the algorithm is online, in the sense that the input strings may be given letter by letter, and its time complexity bounds the processing time of the first n<\/jats:italic> given letters. This acceleration is based on our efficient matrix-vector min-plus multiplication algorithm, intended for matrices and vectors for which differences between adjacent entries are from a finite integer interval D<\/jats:italic>. Choosing a constant \n \n \n \n 1<\/mml:mn>\n <\/mml:mrow>\n \n \n \n log<\/mml:mtext>\n <\/mml:mrow>\n \n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:munder>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <<\/mml:mo>\n \u03bb<\/mml:mo>\n <<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:math>\n <\/jats:inline-formula>, the algorithm preprocesses an n<\/jats:italic>\u2009\u00d7\u2009n<\/jats:italic>\u2009matrix in \n \n O<\/mml:mi>\n \n \n \n \n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n +<\/mml:mo>\n \u03bb<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n \n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:inline-formula> time and \n \n O<\/mml:mi>\n \n \n \n \n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n +<\/mml:mo>\n \u03bb<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n \n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n \n \n \u03bb<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n log<\/mml:mtext>\n <\/mml:mrow>\n \n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:munderover>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:inline-formula> space. Then, it may multiply the matrix with any given n<\/jats:italic>-length vector in \n \n O<\/mml:mi>\n \n \n \n \n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n \n \n \n \u03bb<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n \n log<\/mml:mtext>\n <\/mml:mrow>\n \n |<\/mml:mo>\n D<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:munderover>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:inline-formula> time. Under some discreteness assumptions, this matrix-vector min-plus multiplication algorithm applies to several problems from the domains of context-free grammar parsing and RNA folding and, in particular, implies the asymptotically fastest \n \n O<\/mml:mi>\n \n \n \n \n \n \n n<\/mml:mi>\n <\/mml:mrow>\n \n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n \n \n \n log<\/mml:mtext>\n <\/mml:mrow>\n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mover>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:inline-formula> time algorithm for single-strand RNA folding with discrete cost functions.<\/jats:p>\n Finally, assuming a different constraint on the cost function, we present another version of the algorithm that exploits the run-length encoding of the strings and runs in \n \n O<\/mml:mi>\n \n \n \n \n |<\/mml:mo>\n \u03a3<\/mml:mo>\n |<\/mml:mo>\n nMP<\/mml:mtext>\n (<\/mml:mo>\n \u00f1<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u00f1<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:math>\n <\/jats:inline-formula> time and \n \n O<\/mml:mi>\n (<\/mml:mo>\n |<\/mml:mo>\n \u03a3<\/mml:mo>\n |<\/mml:mo>\n n\u00f1<\/mml:mi>\n )<\/mml:mo>\n <\/mml:math>\n <\/jats:inline-formula> space, where \n \n \u00f1<\/mml:mo>\n <\/mml:math>\n <\/jats:inline-formula> is the length of the run-length encoding of the strings.<\/jats:p>\n <\/jats:sec>","DOI":"10.1186\/1748-7188-8-27","type":"journal-article","created":{"date-parts":[[2013,10,29]],"date-time":"2013-10-29T12:22:30Z","timestamp":1383049350000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient edit distance with duplications and contractions"],"prefix":"10.1186","volume":"8","author":[{"given":"Tamar","family":"Pinhas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Zakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dekel","family":"Tsur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,29]]},"reference":[{"issue":"11","key":"231_CR1","doi-asserted-by":"publisher","first-page":"2117","DOI":"10.1093\/hmg\/8.11.2117","volume":"8","author":"MA Jobling","year":"1999","unstructured":"Jobling MA, Heyer E, Dieltjes P, de Knijff P:Y-chromosome-specific microsatellite mutation rates re-examined using a minisatellite, MSY1. Human Mol Genet. 1999, 8 (11): 2117-2120. 10.1093\/hmg\/8.11.2117.","journal-title":"Human Mol Genet"},{"issue":"3\u20134","key":"231_CR2","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1089\/10665270360688066","volume":"10","author":"S B\u00e9rard","year":"2003","unstructured":"B\u00e9rard S, Rivals E:Comparison of minisatellites. J Comput Biol. 2003, 10 (3\u20134): 357-372.","journal-title":"J Comput Biol"},{"issue":"8","key":"231_CR3","first-page":"707","volume":"10","author":"V Levenshtein","year":"1966","unstructured":"Levenshtein V:Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady. 1966, 10 (8): 707-710.","journal-title":"Soviet Physics Doklady"},{"key":"231_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to computational biology: maps, sequences and genomes","author":"M Waterman","year":"1995","unstructured":"Waterman M: Introduction to computational biology: maps, sequences and genomes. 1995, London: Chapman & Hall\/CRC"},{"issue":"3","key":"231_CR5","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 sequence of two proteins. J Mol Biol. 1970, 48 (3): 443-453.","journal-title":"J Mol Biol"},{"issue":"2\u20134","key":"231_CR6","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.jda.2004.08.014","volume":"3","author":"B Behzadi","year":"2005","unstructured":"Behzadi B, Steyaert JM:An improved algorithm for generalized comparison of minisatellites. J Discrete Algorithms. 2005, 3 (2\u20134): 375-389.","journal-title":"J Discrete Algorithms"},{"key":"231_CR7","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-540-30219-3_25","volume":"3240","author":"B Behzadi","year":"2004","unstructured":"Behzadi B, Steyaert JM:The minisatellite transformation problem revisited: A run length encoded approach. Lecture Notes in Comput-Sci. 2004, 3240: 290-301. 10.1007\/978-3-540-30219-3_25.","journal-title":"Lecture Notes in Comput-Sci"},{"key":"231_CR8","first-page":"303","volume":"2","author":"S B\u00e9rard","year":"2006","unstructured":"B\u00e9rard S, Nicolas F, Buard J, Gascuel O, Rivals E:A fast and specific alignment method for minisatellite maps. Evol Bioinformatics Online. 2006, 2: 303-","journal-title":"Evol Bioinformatics Online"},{"issue":"2","key":"231_CR9","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1142\/S0219720009004060","volume":"7","author":"MI Abouelhoda","year":"2009","unstructured":"Abouelhoda MI, Giegerich R, Behzadi B, Steyaert JM:Alignment of minisatellite maps based on run-length encoding scheme. J Bioinformatics Comput Biol. 2009, 7 (2): 287-308. 10.1142\/S0219720009004060.","journal-title":"J Bioinformatics Comput Biol"},{"issue":"2","key":"231_CR10","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"LG Valiant","year":"1975","unstructured":"Valiant LG:General context-free recognition in less than cubic time. J Comput Syst Sci. 1975, 10 (2): 308-314. 10.1016\/S0022-0000(75)80046-8.","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"231_CR11","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1186\/1748-7188-6-20","volume":"6","author":"S Zakov","year":"2011","unstructured":"Zakov S, Tsur D, Ziv-Ukelson M:Reducing the worst case running times of a family of RNA and CFG problems, using valiant\u2019s approach. Algorithms Mol Biol. 2011, 6 (1): 20-[http:\/\/www.almob.org\/content\/6\/1\/20], []","journal-title":"Algorithms Mol Biol"},{"issue":"5","key":"231_CR12","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1137\/08071990X","volume":"39","author":"TM Chan","year":"2010","unstructured":"Chan TM:More algorithms for all-pairs shortest paths in weighted graphs. SIAM J Comput. 2010, 39 (5): 2075-2089. 10.1137\/08071990X. 2007:590\u2013598.","journal-title":"SIAM J Comput"},{"key":"231_CR13","first-page":"995","volume-title":"Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"R Williams","year":"2007","unstructured":"Williams R:Matrix-vector multiplication in sub-quadratic time:(some preprocessing required). Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 2007, 995-1001. Philadelphia, PA, USA: SIAM."},{"key":"231_CR14","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/1748-7188-5-13","volume":"5","author":"Y Frid","year":"2010","unstructured":"Frid Y, Gusfield D:A simple, practical and complete\"Equation missing\" No EquationSource Format=\"TEX\", only image and EquationSource Format=\"MATHML\" -time Algorithm for RNA folding using the Four-Russians Speedup. Algorithms Mol Biol. 2010, 5: 13.","journal-title":"Algorithms Mol Biol"},{"issue":"11","key":"231_CR15","doi-asserted-by":"publisher","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","volume":"77","author":"R Nussinov","year":"1980","unstructured":"Nussinov R, Jacobson AB:Fast algorithm for predicting the secondary structure of single-stranded RNA. PNAS. 1980, 77 (11): 6309-6313.","journal-title":"PNAS"},{"key":"231_CR16","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C: Introduction to Algorithms. 2001, Cambridge, MA: MIT Press."},{"key":"231_CR17","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek WJ, Paterson MS:A faster algorithm computing string edit distances. J Comput Syst Sci. 1980, 20: 18-31. 10.1016\/0022-0000(80)90002-1.","journal-title":"J Comput Syst Sci"},{"key":"231_CR18","first-page":"1209","volume":"11","author":"VL Arlazarov","year":"1970","unstructured":"Arlazarov VL, Dinic EA, Kronod MA, Faradzev IA:On economical construction of the transitive closure of an oriented graph. Sov Math Dokl. 1970, 11: 1209-1210.","journal-title":"Sov Math Dokl"},{"key":"231_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. 1997, ISBN0521585198, Cambridge: Cambridge University Press."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-8-27.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T19:17:53Z","timestamp":1630610273000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-8-27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,29]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["231"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-8-27","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,29]]},"assertion":[{"value":"13 August 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2013","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"27"}}