{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:53:05Z","timestamp":1740135185854,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T00:00:00Z","timestamp":1662508800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T00:00:00Z","timestamp":1662508800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772124","61772124"],"award-info":[{"award-number":["61772124","61772124"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772124","61772124"],"award-info":[{"award-number":["61772124","61772124"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772124"],"award-info":[{"award-number":["61772124"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>In various fields, searching for the Longest Common Subsequences (LCS) of Multiple (i.e., three or more) sequences (MLCS) is a classic but difficult problem to solve. The primary bottleneck in this problem is that present state-of-the-art algorithms require the construction of a huge graph (called a direct acyclic graph, or DAG), which the computer usually has not enough space to handle. Because of their massive time and space consumption, present algorithms are inapplicable to issues with lengthy and large-scale sequences.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>A mini Directed Acyclic Graph (mini-DAG) model and a novel Path Elimination Algorithm are proposed to address large-scale MLCS issues efficiently. In mini-DAG, we employ the branch and bound approach to reduce paths during DAG construction, resulting in a very mini DAG (mini-DAG), which saves memory space and search time.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>Empirical experiments have been performed on a standard benchmark set of DNA sequences. The experimental results show that our model outperforms the leading algorithms, especially for large-scale MLCS problems.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s12859-022-04906-5","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T08:03:54Z","timestamp":1662537834000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A fast and efficient path elimination algorithm for large-scale multiple common longest sequence problems"],"prefix":"10.1186","volume":"23","author":[{"given":"Changyong","family":"Yu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengxi","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhai","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tianmei","family":"Ren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"issue":"7800","key":"4906_CR1","doi-asserted-by":"publisher","first-page":"S10","DOI":"10.1038\/d41586-020-00845-4","volume":"579","author":"B Nogrady","year":"2020","unstructured":"Nogrady B. How cancer genomics is transforming diagnosis and treatment. Nature. 2020;579(7800):S10\u20131.","journal-title":"Nature"},{"issue":"4","key":"4906_CR2","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1016\/j.cell.2017.01.030","volume":"168","author":"A Aravanis","year":"2017","unstructured":"Aravanis A, Lee M, Klausner R. Next-generation sequencing of circulating tumor DNA for early cancer detection. Cell. 2017;168(4):571\u20134.","journal-title":"Cell"},{"issue":"12","key":"4906_CR3","doi-asserted-by":"publisher","first-page":"2293","DOI":"10.1016\/j.patcog.2005.11.012","volume":"39","author":"DS Huang","year":"2006","unstructured":"Huang DS, Zhao XM, Huang GB, Cheung YM. Classifying protein sequences using hydropathy blocks. Pattern Recognit. 2006;39(12):2293\u2013300.","journal-title":"Pattern Recognit."},{"issue":"2","key":"4906_CR4","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1016\/j.patcog.2006.02.026","volume":"40","author":"D Pham","year":"2007","unstructured":"Pham D. Spectral distortion measures for biological sequence comparisons and database searching. Pattern Recognit. 2007;40(2):516\u201329.","journal-title":"Pattern Recognit."},{"issue":"502","key":"4906_CR5","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2020.107516","volume":"107","author":"L Ou-Yang","year":"2020","unstructured":"Ou-Yang L, Zhang X-F, Yan H. Sparse regularized low-rank tensor regression with applications in genomic data analysis. Pattern Recognit. 2020;107(502): 107516.","journal-title":"Pattern Recognit."},{"issue":"1","key":"4906_CR6","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\u2013insertion constraints. Proc Natl Acad Sci USA. 1972;69(1):4\u20136.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"4","key":"4906_CR7","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"DS Hirschberg","year":"1977","unstructured":"Hirschberg DS. Algorithms for the longest common subsequence problem. J ACM. 1977;24(4):664\u201375.","journal-title":"J ACM"},{"issue":"1","key":"4906_CR8","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 M. A faster algorithm computing string edit distances. J Comput Syst Sci. 1980;20(1):18\u201331.","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"4906_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF01934514","volume":"24","author":"WJ Hsu","year":"1984","unstructured":"Hsu WJ, Du HW. Computing the longest common subsequence for a set of strings. BIT. 1984;24(1):45\u201359.","journal-title":"BIT"},{"issue":"1","key":"4906_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90132-Y","volume":"92","author":"A Apostolico","year":"1992","unstructured":"Apostolico A, Browne S, Guerra C. Fast linear-space computations of longest common subsequences. Theor ComputerScience. 1992;92(1):3\u201317.","journal-title":"Theor ComputerScience"},{"issue":"2","key":"4906_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/34.192484","volume":"15","author":"J Gregor","year":"1993","unstructured":"Gregor J, Thomason MG. Dynamic programming alignment of sequences representing cyclic patterns. IEEE Trans Pattern Anal Mach Intell. 1993;15(2):129\u201335.","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"2\u20133","key":"4906_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.ipl.2006.11.006","volume":"102","author":"R-S Huang","year":"2007","unstructured":"Huang R-S, Yang C-B, Tseng K-T, Peng Y-H, Ann H-Y. Dynamic programming algorithms for the mosaic longest common subsequence problem. Inf Process Lett. 2007;102(2\u20133):99\u2013103.","journal-title":"Inf Process Lett"},{"issue":"11","key":"4906_CR13","doi-asserted-by":"publisher","first-page":"2599","DOI":"10.1109\/TKDE.2014.2304464","volume":"26","author":"J Yang","year":"2014","unstructured":"Yang J, Xu Y, Shang Y, Chen G, Peng Y-H, Ann H-Y. A space-bounded anytime algorithm for the multiple longest common subsequence problem. IEEE Trans Knowl Data Eng. 2014;26(11):2599\u2013609.","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"4906_CR14","first-page":"469","volume":"92","author":"K Hakata","year":"1992","unstructured":"Hakata K, Imai H. The longest common subsequence problem for small alphabet size between many strings. ISAAC. 1992;92:469\u201378.","journal-title":"ISAAC"},{"issue":"2","key":"4906_CR15","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1080\/10556789808805713","volume":"10","author":"K Hakata","year":"1998","unstructured":"Hakata K, Imai H. Algorithms for the longest common subsequence problem for multiple strings based on geometric maxima. Optim Methods Softw. 1998;10(2):223\u201360.","journal-title":"Optim Methods Softw"},{"key":"4906_CR16","unstructured":"Korkin D. A new dominant point-based parallel algorithm for multiple longest common subsequence problem. Technical Report TR01-148, Univ. of New Brunswick, Tech. Rep. 2001."},{"issue":"S4","key":"4906_CR17","doi-asserted-by":"publisher","first-page":"S4","DOI":"10.1186\/1471-2105-7-S4-S4","volume":"7","author":"Y Chen","year":"2006","unstructured":"Chen Y, Wan A, Liu W. A fast parallel algorithm for finding the longest common sequence of multiple biosequences. BMC Bioinform. 2006;7(S4):S4.","journal-title":"BMC Bioinform"},{"key":"4906_CR18","doi-asserted-by":"crossref","unstructured":"Korkin D, Wang Q, Shang Y.: An efficient parallel algorithm for the multiple longest common subsequence (MLCS) problem. ICPP. 2008;354\u2013363","DOI":"10.1109\/ICPP.2008.79"},{"issue":"3","key":"4906_CR19","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1109\/TKDE.2010.123","volume":"23","author":"Q Wang","year":"2011","unstructured":"Wang Q, Korkin D, Shang Y. A fast multiple longest common subsequence (MLCS) algorithm. IEEE Trans Knowl Data Eng. 2011;23(3):321\u201334.","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"4906_CR20","doi-asserted-by":"crossref","unstructured":"Li Y, Wang Y, Zhang Z, Wang Y, Ma D, Huang J.: A novel fast and memory-efficient parallel MLCS algorithm for long and large-scale sequences alignments. ICDE. 2016;1170\u20131181","DOI":"10.1109\/ICDE.2016.7498322"},{"issue":"4","key":"4906_CR21","doi-asserted-by":"crossref","first-page":"1066","DOI":"10.1093\/bioinformatics\/btz725","volume":"36","author":"S Liu","year":"2019","unstructured":"Liu S, Wang Y, Tong W, Wei S. A fast and memory efficient MLCS algorithm by character merging for DNA sequences alignment. Bioinformatics. 2019;36(4):1066\u201379.","journal-title":"Bioinformatics"},{"issue":"10","key":"4906_CR22","doi-asserted-by":"publisher","first-page":"3035","DOI":"10.1093\/bioinformatics\/btaa134","volume":"36","author":"S Wei","year":"2020","unstructured":"Wei S, Wang Y, Yang Y, Liu S. A path recorder algorithm for Multiple Longest Common Subsequences (MLCS) problems. Bioinformatics. 2020;36(10):3035\u201342.","journal-title":"Bioinformatics"},{"issue":"1","key":"4906_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T Smith","year":"1981","unstructured":"Smith T, Waterman M. Identification of common molecular subsequences. J Mol Biol. 1981;147(1):195\u20137.","journal-title":"J Mol Biol"},{"key":"4906_CR24","doi-asserted-by":"publisher","first-page":"104","DOI":"10.3389\/fgene.2017.00104","volume":"8","author":"Z Peng","year":"2017","unstructured":"Peng Z, Wang Y. A novel efficient graph model for the multiple longest common subsequences (MLCS) problem. Front Genet. 2017;8:104.","journal-title":"Front Genet"},{"issue":"4","key":"4906_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2021.108059","volume":"119","author":"C Wang","year":"2021","unstructured":"Wang C, Wang Y, Cheung Y. A branch and bound irredundant graph algorithm for large-scale MLCS problems. Pattern Recognit. 2021;119(4): 108059.","journal-title":"Pattern Recognit"},{"key":"4906_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2020.106499","volume":"95","author":"M Djukanovic","year":"2020","unstructured":"Djukanovic M, Raidl G-R, Blum C. finding longest common subsequences: new anytime A* search results. Appl Soft Comput. 2020;95: 106499.","journal-title":"Appl Soft Comput"},{"issue":"1","key":"4906_CR27","doi-asserted-by":"crossref","first-page":"1287","DOI":"10.1609\/aaai.v24i1.7493","volume":"24","author":"Q Wang","year":"2010","unstructured":"Wang Q, Pan M, Shang Y. A fast heuristic search algorithm for finding the longest common subsequence of multiple strings. AAAI. 2010;24(1):1287\u201392.","journal-title":"AAAI"},{"issue":"1","key":"4906_CR28","first-page":"382","volume":"1","author":"P Judea","year":"1984","unstructured":"Judea P. Heuristics-intelligent search strategies for computer problem solving. Fri. 1984;1(1):382.","journal-title":"Fri"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-022-04906-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-022-04906-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-022-04906-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,18]],"date-time":"2023-02-18T09:44:11Z","timestamp":1676713451000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-022-04906-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,7]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["4906"],"URL":"https:\/\/doi.org\/10.1186\/s12859-022-04906-5","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2022,9,7]]},"assertion":[{"value":"27 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"366"}}