{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:49:49Z","timestamp":1758271789065,"version":"3.37.3"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T00:00:00Z","timestamp":1570147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872281"],"award-info":[{"award-number":["61872281"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007128","name":"Natural Science Foundation of Shaanxi Province","doi-asserted-by":"publisher","award":["2016JZ022"],"award-info":[{"award-number":["2016JZ022"]}],"id":[{"id":"10.13039\/501100007128","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Multiple longest common subsequence (MLCS) problem is searching all longest common subsequences of multiple character sequences. It appears in many fields such as data mining, DNA alignment, bioinformatics, text editing and so on. With the increasing in sequence length and number of sequences, the existing dynamic programming algorithms and the dominant point-based algorithms become ineffective and inefficient, especially for large-scale MLCS problems.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>In this paper, by considering the characteristics of DNA sequences with many consecutively repeated characters, we first design a character merging scheme which merges the consecutively repeated characters in the sequences. As a result, it shortens the length of sequences considered and saves the space of storing all sequences. To further reduce the space and time costs, we construct a weighted directed acyclic graph which is much smaller than widely used directed acyclic graph for MLCS problems. Based on these techniques, we propose a fast and memory efficient algorithm for MLCS problems. Finally, the experiments are conducted and the proposed algorithm is compared with several state-of-the art algorithms. The experimental results show that the proposed algorithm performs better than the compared state-of-the art algorithms in both time and space costs.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/www.ncbi.nlm.nih.gov\/nuccore and https:\/\/github.com\/liusen1006\/MLCS.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz725","type":"journal-article","created":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T11:28:48Z","timestamp":1569497328000},"page":"1066-1073","source":"Crossref","is-referenced-by-count":15,"title":["A fast and memory efficient MLCS algorithm by character merging for DNA sequences alignment"],"prefix":"10.1093","volume":"36","author":[{"given":"Sen","family":"Liu","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Xidian University , Xi\u2019an, China"}]},{"given":"Yuping","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University , Xi\u2019an, China"}]},{"given":"Wuning","family":"Tong","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University , Xi\u2019an, China"}]},{"given":"Shiwei","family":"Wei","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xidian University , Xi\u2019an, China"}]}],"member":"286","published-online":{"date-parts":[[2019,10,4]]},"reference":[{"key":"2023013110104480800_btz725-B1","doi-asserted-by":"crossref","first-page":"94.","DOI":"10.1186\/1471-2105-15-94","article-title":"The number of alignments between two DNA sequences","volume":"15","author":"Andrade","year":"2014","journal-title":"BMC Bioinform"},{"key":"2023013110104480800_btz725-B2","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1016\/j.cell.2017.01.030","article-title":"Next-generation sequencing of circulating tumor DNA for early cancer detection","volume":"168","author":"Aravanis","year":"2017","journal-title":"Cell"},{"key":"2023013110104480800_btz725-B3","doi-asserted-by":"crossref","first-page":"1850015","DOI":"10.1142\/S0219720018500154","article-title":"A hybrid solver for protein multiple sequence alignment problem","volume":"16","author":"Chaabane","year":"2018","journal-title":"J. Bioinform. Comput. Biol"},{"key":"2023013110104480800_btz725-B4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-7-S4-S4","article-title":"A fast parallel algorithm for finding the longest common sequence of multiple biosequences","volume":"7","author":"Chen","year":"2006","journal-title":"BMC Bioinform"},{"key":"2023013110104480800_btz725-B5","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2009","edition":"3rd edn."},{"volume-title":"Fast Linear-space Computations of Longest Common Subsequences","year":"1992","author":"Guerra","key":"2023013110104480800_btz725-B6"},{"key":"2023013110104480800_btz725-B7","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1162\/evco_a_00204","article-title":"A new algorithm using the non-dominated tree to improve non-dominated sorting","volume":"26","author":"Gustavsson","year":"2018","journal-title":"Evol. Comput"},{"key":"2023013110104480800_btz725-B8","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","article-title":"Algorithms for the longest common subsequence problem","volume":"24","author":"Hirschberg","year":"1977","journal-title":"J. ACM"},{"key":"2023013110104480800_btz725-B9","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01934514","article-title":"Computing a longest common subsequence for a set of strings","volume":"24","author":"Hsu","year":"1984","journal-title":"BIT Numer. Math"},{"key":"2023013110104480800_btz725-B10","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","article-title":"A fast algorithm for computing longest common subsequences","volume":"20","author":"Hunt","year":"1977","journal-title":"Commun. ACM"},{"key":"2023013110104480800_btz725-B11","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1109\/71.674320","article-title":"Parallel computation in biological sequence analysis","volume":"9","author":"Kim","year":"1998","journal-title":"IEEE Trans. Parallel Distr. Syst"},{"volume-title":"Technical report TR01-148","year":"2001","author":"Korkin","key":"2023013110104480800_btz725-B12"},{"first-page":"1170","year":"2016","author":"Li","key":"2023013110104480800_btz725-B13"},{"key":"2023013110104480800_btz725-B14","first-page":"322","article-title":"The complexity of some problems on subsequences and supersequences","volume-title":"J. ACM.","author":"Maier","year":"1978"},{"key":"2023013110104480800_btz725-B15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","article-title":"A faster algorithm computing string edit distances","volume":"20","author":"Masek","year":"1980","journal-title":"J. Comput. Syst. Sci"},{"key":"2023013110104480800_btz725-B16","doi-asserted-by":"crossref","first-page":"104.","DOI":"10.3389\/fgene.2017.00104","article-title":"A novel efficient graph model for the multiple longest common subsequences (MLCS) problem","volume":"8","author":"Peng","year":"2017","journal-title":"Front. Genet"},{"key":"2023013110104480800_btz725-B17","doi-asserted-by":"crossref","DOI":"10.1007\/s10535-009-0094-z","article-title":"Understanding bioinformatics","volume":"53","author":"Podlipn\u00e1","year":"2009","journal-title":"Biologia Plantarum"},{"key":"2023013110104480800_btz725-B18","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1073\/pnas.69.1.4","article-title":"Matching sequences under deletion-insertion constraints","volume":"69","author":"Sankoff","year":"1972","journal-title":"Proc. Natl. Sci. USA"},{"key":"2023013110104480800_btz725-B19","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol"},{"key":"2023013110104480800_btz725-B20","first-page":"S1781","article-title":"A comparative analysis of multiple sequence alignments for biological data","volume":"26 (Suppl. 1)","author":"Umar","year":"2015","journal-title":"Biomed. Mater. Eng"},{"key":"2023013110104480800_btz725-B21","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1109\/TKDE.2010.123","article-title":"A fast multiple longest common subsequence (MLCS) algorithm","volume":"23","author":"Wang","year":"2011","journal-title":"IEEE Trans. Knowl. Data Eng"},{"key":"2023013110104480800_btz725-B22","article-title":"An efficient parallel algorithm for longest common subsequence problem on gpus","volume":"2183","author":"Yang","year":"2010","journal-title":"Lect. Notes Eng. Comput. Sci"},{"key":"2023013110104480800_btz725-B23","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1109\/TPDS.2012.202","article-title":"A new progressive algorithm for a multiple longest common subsequences problem and its efficient parallelization","volume":"24","author":"Yang","year":"2013","journal-title":"IEEE Trans. Parallel Distr. Syst"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz725\/30160034\/btz725.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/4\/1066\/48982631\/bioinformatics_36_4_1066.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/4\/1066\/48982631\/bioinformatics_36_4_1066.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T19:45:45Z","timestamp":1675194345000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/4\/1066\/5581348"}},"subtitle":[],"editor":[{"given":"John","family":"Hancock","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,10,4]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz725","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2020,2,15]]},"published":{"date-parts":[[2019,10,4]]}}}