{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T18:43:31Z","timestamp":1770489811007,"version":"3.49.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319899282","type":"print"},{"value":"9783319899299","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-89929-9_14","type":"book-chapter","created":{"date-parts":[[2018,4,17]],"date-time":"2018-04-17T18:34:13Z","timestamp":1523990053000},"page":"211-224","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis"],"prefix":"10.1007","author":[{"given":"Sharma V.","family":"Thankachan","sequence":"first","affiliation":[]},{"given":"Chaitanya","family":"Aluru","sequence":"additional","affiliation":[]},{"given":"Sriram P.","family":"Chockalingam","sequence":"additional","affiliation":[]},{"given":"Srinivas","family":"Aluru","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,18]]},"reference":[{"key":"14_CR1","first-page":"218","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Amir Abboud","year":"2014","unstructured":"Abboud, A., Williams, R., Yu, H.: More applications of the polynomial method to algorithm design. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 218\u2013230 (2015)"},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-662-43948-7_4","volume-title":"Automata, Languages, and Programming","author":"A Abboud","year":"2014","unstructured":"Abboud, A., Williams, V.V., Weimann, O.: Consequences of faster alignment of sequences. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 39\u201351. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_4"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-16706-0_1","volume-title":"Research in Computational Molecular Biology","author":"S Aluru","year":"2015","unstructured":"Aluru, S., Apostolico, A., Thankachan, S.V.: Efficient alignment free sequence comparison with bounded mismatches. In: Przytycka, T.M. (ed.) RECOMB 2015. LNCS, vol. 9029, pp. 1\u201312. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-16706-0_1"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-12476-1_2","volume-title":"Algorithms and Applications","author":"A Apostolico","year":"2010","unstructured":"Apostolico, A.: Maximal words in sequence comparisons based on subword composition. In: Elomaa, T., Mannila, H., Orponen, P. (eds.) Algorithms and Applications. LNCS, vol. 6060, pp. 34\u201344. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12476-1_2"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.tcs.2016.01.023","volume":"638","author":"A Apostolico","year":"2016","unstructured":"Apostolico, A., Guerra, C., Landau, G.M., Pizzi, C.: Sequence similarity measures based on bounded hamming distance. Theoret. Comput. Sci. 638, 76\u201390 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"14_CR6","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1093\/bib\/bbt052","volume":"15","author":"O Bonham-Carter","year":"2013","unstructured":"Bonham-Carter, O., Steele, J., Bastola, D.: Alignment-free genetic sequence comparisons: a review of recent approaches by word analysis. Briefings Bioinform. 15(6), 890\u2013905 (2013)","journal-title":"Briefings Bioinform."},{"issue":"2","key":"14_CR7","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1145\/322123.322127","volume":"26","author":"MR Brown","year":"1979","unstructured":"Brown, M.R., Tarjan, R.E.: A fast merging algorithm. J. ACM 26(2), 211\u2013226 (1979)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"14_CR8","first-page":"51","volume":"56","author":"S Burkhardt","year":"2003","unstructured":"Burkhardt, S., K\u00e4rkk\u00e4inen, J.: Better filtering with gapped q-grams. Fundam. Inform. 56(1\u20132), 51\u201370 (2003)","journal-title":"Fundam. Inform."},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/11415770_22","volume-title":"Research in Computational Molecular Biology","author":"D Burstein","year":"2005","unstructured":"Burstein, D., Ulitsky, I., Tuller, T., Chor, B.: Information theoretic approaches to whole genome phylogenies. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS, vol. 3500, pp. 283\u2013295. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11415770_22"},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10930-011-9318-0","volume":"30","author":"G Chang","year":"2011","unstructured":"Chang, G., Wang, T.: Phylogenetic analysis of protein sequences based on distribution of length about common substring. Protein J. 30(3), 167\u2013172 (2011)","journal-title":"Protein J."},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of the 36th Annual ACM Symposium on Theory of computing (STOC), pp. 91\u2013100. ACM (2004)","DOI":"10.1145\/1007352.1007374"},{"issue":"1","key":"14_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1748-7188-7-34","volume":"7","author":"M Comin","year":"2012","unstructured":"Comin, M., Verzotto, D.: Alignment-free phylogeny of whole genomes using underlying subwords. Algorithms Mol. Biol. 7(1), 1 (2012)","journal-title":"Algorithms Mol. Biol."},{"issue":"24","key":"14_CR13","doi-asserted-by":"publisher","first-page":"3221","DOI":"10.1093\/bioinformatics\/btp590","volume":"25","author":"M Domazet-Lo\u0161o","year":"2009","unstructured":"Domazet-Lo\u0161o, M., Haubold, B.: Efficient estimation of pairwise distances between genomes. Bioinformatics 25(24), 3221\u20133227 (2009)","journal-title":"Bioinformatics"},{"key":"14_CR14","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. Cambridge University Press, Cambridge (1997)"},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s11634-009-0041-z","volume":"3","author":"F Guyon","year":"2009","unstructured":"Guyon, F., Brochier-Armanet, C., Gu\u00e9noche, A.: Comparison of alignment free string distances for complete genome phylogeny. Adv. Data Anal. Classif. 3(2), 95\u2013108 (2009)","journal-title":"Adv. Data Anal. Classif."},{"key":"14_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-319-11918-2_14","volume-title":"String Processing and Information Retrieval","author":"G Kucherov","year":"2014","unstructured":"Kucherov, G., Tsur, D.: Improved filters for the approximate suffix-prefix overlap problem. In: Moura, E., Crochemore, M. (eds.) SPIRE 2014. LNCS, vol. 8799, pp. 139\u2013148. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11918-2_14"},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead, B., Salzberg, S.L.: Fast gapped-read alignment with Bowtie 2. Nat. Methods 9(4), 357\u2013359 (2012)","journal-title":"Nat. Methods"},{"issue":"14","key":"14_CR18","doi-asserted-by":"publisher","first-page":"2000","DOI":"10.1093\/bioinformatics\/btu331","volume":"30","author":"C-A Leimeister","year":"2014","unstructured":"Leimeister, C.-A., Morgenstern, B.: kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison. Bioinformatics 30(14), 2000\u20132008 (2014)","journal-title":"Bioinformatics"},{"issue":"14","key":"14_CR19","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li, H., Durbin, R.: Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics 25(14), 1754\u20131760 (2009)","journal-title":"Bioinformatics"},{"issue":"5","key":"14_CR20","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1093\/bib\/bbq015","volume":"11","author":"H Li","year":"2010","unstructured":"Li, H., Homer, N.: A survey of sequence alignment algorithms for next-generation sequencing. Briefings Bioinform. 11(5), 473\u2013483 (2010)","journal-title":"Briefings Bioinform."},{"issue":"15","key":"14_CR21","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R Li","year":"2009","unstructured":"Li, R., Yu, C., Li, Y., Lam, T.-W., Yiu, S.-M., Kristiansen, K., Wang, J.: SOAP2: an improved ultrafast tool for short read alignment. Bioinformatics 25(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-319-23826-5_29","volume-title":"String Processing and Information Retrieval","author":"G Manzini","year":"2015","unstructured":"Manzini, G.: Longest common prefix with mismatches. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 299\u2013310. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23826-5_29"},{"issue":"2","key":"14_CR23","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM (JACM) 23(2), 262\u2013272 (1976)","journal-title":"J. ACM (JACM)"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-662-48221-6_17","volume-title":"Algorithms in Bioinformatics","author":"C Pizzi","year":"2015","unstructured":"Pizzi, C.: A filtering approach for alignment-free biosequences comparison with mismatches. In: Pop, M., Touzet, H. (eds.) WABI 2015. LNCS, vol. 9289, pp. 231\u2013242. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48221-6_17"},{"issue":"3","key":"14_CR25","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1101\/gr.126953.111","volume":"22","author":"JT Simpson","year":"2012","unstructured":"Simpson, J.T., Durbin, R.: Efficient de novo assembly of large genomes using compressed data structures. Genome Res. 22(3), 549\u2013556 (2012)","journal-title":"Genome Res."},{"issue":"3","key":"14_CR26","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"14_CR27","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1089\/cmb.2015.0235","volume":"23","author":"SV Thankachan","year":"2016","unstructured":"Thankachan, S.V., Apostolico, A., Aluru, S.: A provably efficient algorithm for the k-mismatch average common substring problem. J. Comput. Biol. 23(6), 472\u2013482 (2016)","journal-title":"J. Comput. Biol."},{"issue":"6","key":"14_CR28","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1089\/cmb.2015.0217","volume":"23","author":"SV Thankachan","year":"2016","unstructured":"Thankachan, S.V., Chockalingam, S.P., Liu, Y., Apostolico, A., Aluru, S.: ALFRED: a practical method for alignment-free distance computation. J. Comput. Biol. 23(6), 452\u2013460 (2016)","journal-title":"J. Comput. Biol."},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"Thankachan, S.V., Chockalingam, S.P., Liu, Y., Krishnan, A., Aluru, S.: A greedy alignment-free distance estimator for phylogenetic inference. In: Proceedings of 5th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS) (2015)","DOI":"10.1109\/ICCABS.2015.7344711"},{"key":"14_CR30","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ic.2012.02.002","volume":"213","author":"N V\u00e4lim\u00e4ki","year":"2012","unstructured":"V\u00e4lim\u00e4ki, N., Ladra, S., M\u00e4kinen, V.: Approximate all-pairs suffix\/prefix overlaps. Inf. Comput. 213, 49\u201358 (2012)","journal-title":"Inf. Comput."},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory (SWAT), pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-89929-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:11:31Z","timestamp":1709809891000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-89929-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319899282","9783319899299"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-89929-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"18 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RECOMB","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Research in Computational Molecular Biology","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"recomb2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb2018.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}