{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T16:07:56Z","timestamp":1743091676418,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031368042"},{"type":"electronic","value":"9783031368059"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-36805-9_15","type":"book-chapter","created":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T23:03:04Z","timestamp":1688079784000},"page":"218-230","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Extended Pairwise Sequence Alignment"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8015-6237","authenticated-orcid":false,"given":"Eloi","family":"Araujo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6809-3547","authenticated-orcid":false,"given":"F\u00e1bio V.","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5472-6670","authenticated-orcid":false,"given":"Luiz C.","family":"Rozante","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5615-1746","authenticated-orcid":false,"given":"Nalvo F.","family":"Almeida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,6,30]]},"reference":[{"issue":"3","key":"15_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Araujo, E., Martinez, F.V., Higa, C.H.A., Soares, J.: Matrices inducing generalized metric on sequences. Discrete Appl. Math. (2023, to appear)","DOI":"10.1016\/j.dam.2023.02.011"},{"key":"15_CR3","unstructured":"Araujo, E., Rozante, L.C., Rubert, D.P., Martinez, F.V.: Algorithms for normalized multiple sequence alignments. In: Proceedings of ISAAC. LIPIcs, vol. 212, pp. 40:1\u201340:16 (2021)"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In: Proceedings of STOC, pp. 51\u201358 (2015)","DOI":"10.1145\/2746539.2746612"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2015.03.016","volume":"582","author":"C Barton","year":"2015","unstructured":"Barton, C., Flouri, T., Iliopoulos, C.S., Pissis, S.P.: Global and local sequence alignment with a bounded number of gaps. Theor. Comput. Sci. 582, 1\u201316 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"8184","DOI":"10.1109\/ACCESS.2016.2614494","volume":"4","author":"RK Chaurasiya","year":"2016","unstructured":"Chaurasiya, R.K., Londhe, N.D., Ghosh, S.: A novel weighted edit distance-based spelling correction approach for improving the reliability of Devanagari script-based P300 speller system. IEEE Access 4, 8184\u20138198 (2016)","journal-title":"IEEE Access"},{"issue":"13","key":"15_CR7","doi-asserted-by":"publisher","first-page":"3497","DOI":"10.1093\/nar\/gkg500","volume":"31","author":"R Chenna","year":"2003","unstructured":"Chenna, R., et al.: Multiple sequence alignment with the Clustal series of programs. Nucleic Acids Res. 31(13), 3497\u20133500 (2003)","journal-title":"Nucleic Acids Res."},{"key":"15_CR8","unstructured":"Fisman, D., Grogin, J., Margalit, O., Weiss, G.: The Normalized Edit Distance with Uniform Operation Costs is a Metric. arXiv:2201.06115 (2022)"},{"issue":"6","key":"15_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R Floyd","year":"1962","unstructured":"Floyd, R.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962)","journal-title":"Commun. ACM"},{"issue":"15","key":"15_CR10","doi-asserted-by":"publisher","first-page":"4846","DOI":"10.1128\/JB.186.15.4846-4852.2004","volume":"186","author":"P Foster","year":"2004","unstructured":"Foster, P.: Adaptive mutation in Escherichia coli. J. Bacteriol. 186(15), 4846\u20134852 (2004)","journal-title":"J. Bacteriol."},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"de la Higuera, C., Mic\u00f3, L.: A contextual normalised edit distance. In: Proceedings of ICDEW, pp. 354\u2013361. IEEE (2008)","DOI":"10.1109\/SISAP.2008.17"},{"issue":"10","key":"15_CR12","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1093\/bioinformatics\/14.10.846","volume":"14","author":"K Karplus","year":"1998","unstructured":"Karplus, K., Barrett, C., Hughey, R.: Hidden Markov models for detecting remote protein homologies. Bioinformatics 14(10), 846\u2013856 (1998)","journal-title":"Bioinformatics"},{"issue":"8","key":"15_CR13","first-page":"707","volume":"10","author":"V Levenshtein","year":"1966","unstructured":"Levenshtein, V.: Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Doklady 10(8), 707\u2013710 (1966)","journal-title":"Sov. Phys. Doklady"},{"issue":"12","key":"15_CR14","doi-asserted-by":"publisher","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"DJ Lipman","year":"1989","unstructured":"Lipman, D.J., Altschul, S.F., Kececioglu, J.D.: A tool for multiple sequence alignment. PNAS 86(12), 4412\u20134415 (1989)","journal-title":"PNAS"},{"issue":"4693","key":"15_CR15","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.1126\/science.2983426","volume":"227","author":"DJ Lipman","year":"1985","unstructured":"Lipman, D.J., Pearson, W.R.: Rapid and sensitive protein similarity searches. Science 227(4693), 1435\u20131441 (1985)","journal-title":"Science"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Ichinose, M., Iizuka, M., Kusumi, J., Takefu, M.: Models of compensatory molecular evolution: effects of back mutation. J. Theor. Biol. 323(0), 1\u201310 (2013)","DOI":"10.1016\/j.jtbi.2013.01.011"},{"issue":"9","key":"15_CR17","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1109\/34.232078","volume":"15","author":"A Marzal","year":"1993","unstructured":"Marzal, A., Vidal, E.: Computation of normalized edit distance and applications. IEEE T. Pattern Anal. 15(9), 926\u2013932 (1993)","journal-title":"IEEE T. Pattern Anal."},{"issue":"3","key":"15_CR18","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman, S.B., Wunsch, C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48(3), 443\u2013453 (1970)","journal-title":"J. Mol. Biol."},{"issue":"1","key":"15_CR19","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C Notredame","year":"2000","unstructured":"Notredame, C., Higgins, D.G., Heringa, J.: T-Coffee: a novel method for fast and accurate multiple sequence alignment. J. Mol. Biol. 302(1), 205\u2013217 (2000)","journal-title":"J. Mol. Biol."},{"key":"15_CR20","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1038\/35080556","volume":"2","author":"S Rosenberg","year":"2001","unstructured":"Rosenberg, S.: Evolving responsively: adaptive mutation. Nat. Rev. Genet. 2, 504\u2013515 (2001)","journal-title":"Nat. Rev. Genet."},{"key":"15_CR21","unstructured":"Setubal, J.C., Meidanis, J.: Introduction to Computational Molecular Biology. PWS Pub. (1997)"},{"issue":"1","key":"15_CR22","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"TF Smith","year":"1981","unstructured":"Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences. J. Mol. Biol. 147(1), 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Sun, Y., et al.: ICDAR 2019 competition on large-scale street view text with partial labeling-RRC-LSVT. In: Proceedings of ICDAR, pp. 1557\u20131562. IEEE (2019)","DOI":"10.1109\/ICDAR.2019.00250"},{"issue":"1","key":"15_CR24","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on Boolean matrices. J. ACM 9(1), 11\u201312 (1962)","journal-title":"J. ACM"},{"issue":"6","key":"15_CR25","doi-asserted-by":"publisher","first-page":"1091","DOI":"10.1109\/TPAMI.2007.1078","volume":"29","author":"L Yujian","year":"2007","unstructured":"Yujian, L., Bo, L.: A normalized Levenshtein distance metric. IEEE T. Pattern Anal. 29(6), 1091\u20131095 (2007)","journal-title":"IEEE T. Pattern Anal."}],"container-title":["Lecture Notes in Computer Science","Computational Science and Its Applications \u2013 ICCSA 2023"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-36805-9_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,29]],"date-time":"2023-06-29T23:04:34Z","timestamp":1688079874000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-36805-9_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031368042","9783031368059"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-36805-9_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"30 June 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICCSA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computational Science and Its Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 July 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iccsa2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iccsa.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Custom based on Cyberchair 4","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"283","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"67","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8,5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"PHD Showcase Papers: 6(for main conf) \/ For ICCSA 2023 Workshops 876 subm sent, 350 full papers and 29 short papers accepted, additional PHD Showcase Papers: 2","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}