{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:15Z","timestamp":1750309395750,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"\n The Longest Common Subsequence (LCS) problem is a well-known and studied problem in computer science and bioinformatics. It consists in finding the longest subsequence that is common to two or more given sequences. In this article, we address the problem of finding all LCS for the Sequential Substring Constrained-LCS (SSCLCS) problem, called the Multiple SSCLCS problem. To solve this problem, we first propose a dominant point-based sequential algorithm, designed on a new Leveled Direct Acyclic Graph (DAG) that gives the correct evaluation order of subproblems to avoid redundancy due to overlap. Depending on whether the constraints may overlap or not, it requires\n \n \\(O(S|\\Sigma |^{K+1}+r+n|\\Sigma |)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(O(S|\\Sigma |^{K+1}+n|\\Sigma |)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n time with\n \n \\(O(Max\\_level+n|\\Sigma |)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space.\n S<\/jats:italic>\n is the number of partial SSCLCS in a node,\n K<\/jats:italic>\n is the number of DAG levels,\n n<\/jats:italic>\n is the length of sequences,\n r<\/jats:italic>\n is the total length of constraints,\n \n \\(Max\\_level\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of nodes in the largest level of the DAG, and\n \n \\(|\\Sigma |\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the length of the alphabet. Then, we derive a coarse-grained multicomputer parallel solution requiring\n \n \\(O(\\tfrac{S|\\Sigma |^{K+1}+r+n|\\Sigma |}{p})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(O(\\tfrac{S|\\Sigma |^{K+1}+n|\\Sigma |}{p})\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n execution time,\n \n \\(O(Max\\_level+n|\\Sigma |)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n memory space and\n \n \\(O(K)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n communication rounds.\n p<\/jats:italic>\n is the number of processors. Experimental results showed that the parallel algorithm is, respectively, 14.43\u00d7 and 19.19\u00d7 faster than the sequential algorithm on 32 and 64 processors.\n <\/jats:p>","DOI":"10.1145\/3696657","type":"journal-article","created":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T10:51:16Z","timestamp":1727088676000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Dominant Point-Based Sequential and Parallel Algorithms for the Multiple Sequential Substring Constrained-LCS Problem"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4036-7574","authenticated-orcid":false,"given":"Hermann","family":"Bogning Tepiele","sequence":"first","affiliation":[{"name":"Mathematics and Computer Science, University of Dschang, Dschang, Cameroon"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3836-1859","authenticated-orcid":false,"given":"Vianney","family":"Kengne Tchendji","sequence":"additional","affiliation":[{"name":"Mathematics and Computer Science, University of Dschang, Dschang, Cameroon"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3693-9576","authenticated-orcid":false,"given":"Mathias","family":"Akong Onabid","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Bamenda, Bambili, Cameroon"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3657-2556","authenticated-orcid":false,"given":"Jean Fr\u00e9d\u00e9ric","family":"Myoupo","sequence":"additional","affiliation":[{"name":"Computer Science Lab-MIS, Universit\u00e9 de Picardie Jules Verne, Amiens, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1706-2430","authenticated-orcid":false,"given":"Armel","family":"Nkonjoh Ngomade","sequence":"additional","affiliation":[{"name":"Computer Engineering, University of Ebolowa, Ebolowa, Cameroon"}]}],"member":"320","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.12.001"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-012-9588-2"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840365"},{"key":"e_1_3_2_5_2","article-title":"Sketching, streaming, and fine-grained complexity of (weighted) LCS","volume":"1810","author":"Bringmann Karl","year":"2018","unstructured":"Karl Bringmann and Bhaskar Ray Chaudhury. 2018. Sketching, streaming, and fine-grained complexity of (weighted) LCS. CoRR abs\/1810.01238 (2018). arXiv:1810.01238http:\/\/arxiv.org\/abs\/1810.01238","journal-title":"CoRR"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-009-9262-5"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-S4-S4"},{"key":"e_1_3_2_8_2","first-page":"32","volume-title":"the 27th Workshop on Combinatorial Mathematics and Computation Theory (Taichung, Taiwan)","author":"Chen Yi-Ching","year":"2010","unstructured":"Yi-Ching Chen. 2010. Algorithms for the hybrid constrained longest common subsequence problem. In the 27th Workshop on Combinatorial Mathematics and Computation Theory (Taichung, Taiwan). 32\u201337."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.02.008"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"Crochemore Maxime","year":"2007","unstructured":"Maxime Crochemore, Christophe Hancart, and Thierry Lecroq. 2007. Algorithms on Strings. Cambridge University Press."},{"key":"e_1_3_2_11_2","unstructured":"Universit\u00e9 de Picardie Jules Verne. 2023. Plateforme MatriCS. https:\/\/www.matrics.u-picardie.fr\/. [Online; accessed 21-August-2023]."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161154"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000241"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0109-4"},{"key":"e_1_3_2_15_2","first-page":"97","volume-title":"Recent Advances in Parallel Virtual Machine and Message Passing Interface, 11th European PVM\/MPI Users\u2019 Group Meeting, Budapest, Hungary, September 19\u201322, 2004, Proceedings (Lecture Notes in Computer Science)","volume":"3241","author":"Gabriel Edgar","year":"2004","unstructured":"Edgar Gabriel, Graham E. Fagg, George Bosilca, Thara Angskun, Jack J. Dongarra, Jeffrey M. Squyres, Vishal Sahay, Prabhanjan Kambadur, Brian Barrett, Andrew Lumsdaine, Ralph H. Castain, David J. Daniel, Richard L. Graham, and Timothy S. Woodall. 2004. Open MPI: Goals, concept, and design of a next generation MPI implementation. In Recent Advances in Parallel Virtual Machine and Message Passing Interface, 11th European PVM\/MPI Users\u2019 Group Meeting, Budapest, Hungary, September 19\u201322, 2004, Proceedings (Lecture Notes in Computer Science), Dieter Kranzlm\u00fcller, P\u00e9ter Kacsuk, and Jack J. Dongarra (Eds.), Vol. 3241. Springer, 97\u2013104. 10.1007\/978-3-540-30218-6_19"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/EMPDP.2003.1183610"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.12.004"},{"key":"e_1_3_2_18_2","first-page":"301","volume-title":"21st International Conference on Computers and Their Applications (CATA-2006) (Seattle, Washington, March 23\u201325, 2006)","author":"Garcia Thierry","year":"2006","unstructured":"Thierry Garcia and David Sem\u00e9. 2006. A load balancing technique for some coarse-grained multicomputer algorithms. In 21st International Conference on Computers and Their Applications (CATA-2006) (Seattle, Washington, March 23\u201325, 2006). ISCA, 301\u2013306."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511574931"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934514"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.11.006"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1155\/2012\/310328"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321880"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.298210"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/322063.322075"},{"key":"e_1_3_2_28_2","first-page":"1038","volume-title":"2018 International Conference on High Performance Computing and Simulation (HPCS 2018), Orleans, France, July 16\u201320, 2018","author":"Myoupo Jean Fr\u00e9d\u00e9ric","year":"2018","unstructured":"Jean Fr\u00e9d\u00e9ric Myoupo, Armel Nkonjoh Ngomade, and Vianney Kengne Tchendji. 2018. Coarse-grained multicomputer based-parallel algorithms for the longest common subsequence problem with a string-exclusion constraint. In 2018 International Conference on High Performance Computing and Simulation (HPCS 2018), Orleans, France, July 16\u201320, 2018. IEEE, 1038\u20131044. 10.1109\/HPCS.2018.00163"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"101070","DOI":"10.1016\/j.jocs.2019.101070","article-title":"A dominant point-based parallel algorithm that finds all longest common subsequences for a constrained-MLCS problem","volume":"40","author":"Ngomade Armel Nkonjoh","year":"2020","unstructured":"Armel Nkonjoh Ngomade, Jean Fr\u00e9d\u00e9ric Myoupo, and Vianney Kengne Tchendji. 2020. A dominant point-based parallel algorithm that finds all longest common subsequences for a constrained-MLCS problem. Journal of Computational Science 40 (2020), 101070.","journal-title":"Journal of Computational Science"},{"key":"e_1_3_2_30_2","unstructured":"U.S. National Library of Medicine. 2019. National Center for Biotechnology Information. https:\/\/www.ncbi.nlm.nih.gov\/genbank\/. [Online; accessed 06-Febrary-2020]."},{"key":"e_1_3_2_31_2","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 Zhan","year":"2017","unstructured":"Zhan Peng and Yuping Wang. 2017. A novel efficient graph model for the multiple longest common subsequences (MLCS) problem. Frontiers in Genetics 8 (2017), 104.","journal-title":"Frontiers in Genetics"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2019.102598"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2022.102927"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.07.001"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2012.08.002"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2309.09072"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_3_2_39_2","article-title":"An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusion constrains","volume":"1303","author":"Wang Lei","year":"2013","unstructured":"Lei Wang, Xiaodong Wang, Yingjie Wu, and Daxin Zhu. 2013. An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusion constrains. CoRR abs\/1303.1872 (2013). arXiv:1303.1872http:\/\/arxiv.org\/abs\/1303.1872","journal-title":"CoRR"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.123"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-39077-2_2"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2304464"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.202"},{"key":"e_1_3_2_44_2","article-title":"An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring inclusive constraints","volume":"1505","author":"Zhu Daxin","year":"2015","unstructured":"Daxin Zhu, Lei Wang, Yingjie Wu, and Xiaodong Wang. 2015. An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring inclusive constraints. CoRR abs\/1505.06529 (2015). arXiv:1505.06529http:\/\/arxiv.org\/abs\/1505.06529","journal-title":"CoRR"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696657","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696657","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:57:43Z","timestamp":1750294663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696657"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3696657"],"URL":"https:\/\/doi.org\/10.1145\/3696657","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"2023-08-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}