{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:44:09Z","timestamp":1773931449995,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"S4","license":[{"start":{"date-parts":[[2006,12,1]],"date-time":"2006-12-01T00:00:00Z","timestamp":1164931200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2006,12]]},"DOI":"10.1186\/1471-2105-7-s4-s4","type":"journal-article","created":{"date-parts":[[2006,12,12]],"date-time":"2006-12-12T19:59:31Z","timestamp":1165953571000},"source":"Crossref","is-referenced-by-count":42,"title":["A fast parallel algorithm for finding the longest common sequence of multiple biosequences"],"prefix":"10.1186","volume":"7","author":[{"given":"Yixin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Wan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,12,12]]},"reference":[{"key":"1327_CR1","volume-title":"Shanghai Science and Technology Publishing Company","author":"B Hao","year":"2000","unstructured":"Hao B, Zhang SY: The manual of bioinformatics. Shanghai Science and Technology Publishing Company 2000."},{"key":"1327_CR2","volume-title":"Tsinghua University Publishing Company","author":"YD Li","year":"2000","unstructured":"Li YD, Sun ZR, et al.: Bioinformatics \u2013 The practice guide for the analysis of gene and protein. Tsinghua University Publishing Company 2000."},{"issue":"3","key":"1327_CR3","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF02427852","volume":"17","author":"EW Edmiston","year":"1988","unstructured":"Edmiston EW, Core NG, Saltz JH, et al.: Parallel processing of biological sequence comparison algorithms. International Journal of Parallel Programming 1988, 17(3):259\u2013275.","journal-title":"International Journal of Parallel Programming"},{"key":"1327_CR4","first-page":"257","volume-title":"Proceedings of the 1988 International Conference on Parallel Processing","author":"E Lander","year":"1988","unstructured":"Lander E: Protein sequence comparison on a data parallel computer. Proceedings of the 1988 International Conference on Parallel Processing 1988, 257\u2013263."},{"key":"1327_CR5","volume-title":"Technical Report","author":"AR Galper","year":"1990","unstructured":"Galper AR, Brutlag DL: Parallel similarity search and alignment with the dynamic programming method. In Technical Report. California: Stanford University; 1990."},{"key":"1327_CR6","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"TF Smith","year":"1990","unstructured":"Smith TF, Waterman MS: Identification of common molecular subsequence. Journal of Molecular Biology 1990, 215: 403\u2013410.","journal-title":"Journal of Molecular Biology"},{"issue":"3","key":"1327_CR7","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 1970, 48(3):443\u2013453.","journal-title":"J Mol Biol"},{"key":"1327_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321958.321970","volume":"23","author":"A Aho","year":"1976","unstructured":"Aho A, Hirschberg D, Ullman J: Bounds on the complexity of the longest common subsequence problem. J Assoc Comput Mach 1976, 23: 1\u201312.","journal-title":"J Assoc Comput Mach"},{"key":"1327_CR9","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O: An improved algorithm for matching biological sequences. J Molec Biol 1982, 162: 705\u2013708.","journal-title":"J Molec Biol"},{"key":"1327_CR10","first-page":"11","volume":"4","author":"EW Mayers","year":"1998","unstructured":"Mayers EW, Miller W: Optimal alignment in linear space. Comput Appl Biosci 1998, 4: 11\u201317.","journal-title":"Comput Appl Biosci"},{"issue":"6","key":"1327_CR11","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS: A Linear space algorithm for computing maximal Common Subsequences. Commun ACM 1975, 18(6):341\u2013343.","journal-title":"Commun ACM"},{"key":"1327_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0020-0255(97)10013-5","volume":"106","author":"Y Pan","year":"1998","unstructured":"Pan Y, Li K: Linear array with a reconfigurable pipelined bus system \u2013 concepts and applications. Journal of Information Science 1998, 106: 237\u2013258.","journal-title":"Journal of Information Science"},{"key":"1327_CR13","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1006\/jpdc.1999.1534","volume":"57","author":"JF Myoupo","year":"1999","unstructured":"Myoupo JF, David Seme D: Time-efficient parallel algorithms for the longest common subsequence and related problems. Journal of Parallel and Distributed Computing 1999, 57: 212\u2013223.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"1327_CR14","first-page":"39","volume-title":"Seventh International Symposium on String Processing Information Retrieval","author":"L Bergroth","year":"2000","unstructured":"Bergroth L, Hakonen H, Raita T: A survey of longest common subsequence algorithms. Seventh International Symposium on String Processing Information Retrieval 2000, 39\u201348."},{"key":"1327_CR15","first-page":"497","volume-title":"Proc 29th Ann IEEE Symp Foundations of Comput Sci","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal A, Park J: Notes on searching in multidimensional monotone Arrays. Proc 29th Ann IEEE Symp Foundations of Comput Sci 1988, 497\u2013512."},{"key":"1327_CR16","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1137\/0219066","volume":"19","author":"A Apostolico","year":"1990","unstructured":"Apostolico A, Atallah M, Larmore L, Mcfaddin S: Efficient parallel algorithms for string editing and related problems. SIAM J Computing 1990, 19: 968\u2013988.","journal-title":"SIAM J Computing"},{"key":"1327_CR17","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/71.298210","volume":"5","author":"M Lu","year":"1994","unstructured":"Lu M, Lin H: Parallel algorithms for the longest common subsequence Problem. IEEE Transaction on Parallel and Distributed System 1994, 5: 835\u2013848.","journal-title":"IEEE Transaction on Parallel and Distributed System"},{"key":"1327_CR18","first-page":"18","volume-title":"4th International Conference on High Performance Computing","author":"KN Babu","year":"1997","unstructured":"Babu KN, Systems W, Saxena S: Parallel algorithms for the longest common subsequence problem. 4th International Conference on High Performance Computing 1997, 18\u201321."},{"key":"1327_CR19","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0020-0190(85)90058-4","volume":"21","author":"Y Robert","year":"1985","unstructured":"Robert Y, Tchuente M: A Systolic Array for the Longest Common Subsequence Problem. Inform Process Lett 1985, 21: 191\u2013198.","journal-title":"Inform Process Lett"},{"key":"1327_CR20","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1109\/TC.1987.5009449","volume":"C-36","author":"JH Chang","year":"1987","unstructured":"Chang JH, Ibarra OH, Pallis MA: Parallel parsing on a one-way array of finite-state machines. IEEE Trans Computers 1987, C-36: 64\u201375.","journal-title":"IEEE Trans Computers"},{"key":"1327_CR21","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0167-9260(98)00003-0","volume":"25","author":"G Luce","year":"1998","unstructured":"Luce G, Myoupo JF: Systolic-based parallel architecture for the longest common subsequences problem. Integration 1998, 25: 53\u201370.","journal-title":"Integration"},{"key":"1327_CR22","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2004.02.011","volume":"90","author":"V Freschi","year":"2004","unstructured":"Freschi V, Bogliolo A: Longest common subsequence between run-length-encoded strings:a new algorithm with improved parallelism. Information Processing Letters 2004, 90: 167\u2013173.","journal-title":"Information Processing Letters"},{"key":"1327_CR23","doi-asserted-by":"publisher","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"DJ Lipman","year":"1989","unstructured":"Lipman DJ, Altschul SF, Kececioglu JD: A tool for multiple sequence alignment. Proc Natl Acad Sci USA 1989, 86: 4412\u20134415.","journal-title":"Proc Natl Acad Sci USA"},{"key":"1327_CR24","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H Carrillo","year":"1988","unstructured":"Carrillo H, Lipman DJ: The multiple sequence alignment problem in biology. SIAM J Appl Math 1988, 48: 1073\u20131082.","journal-title":"SIAM J Appl Math"},{"key":"1327_CR25","first-page":"625","volume":"13","author":"J Stoye","year":"1997","unstructured":"Stoye J, Moulton V, Dress AW: DCA: an efficient implementation of the divide-andconquer approach to simultaneous multiple sequence alignment. Comput Appl Biosci 1997, 13: 625\u20136.","journal-title":"Comput Appl Biosci"},{"issue":"9","key":"1327_CR26","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1093\/bioinformatics\/16.9.808","volume":"16","author":"K Reinert","year":"2000","unstructured":"Reinert K, Stoye J, Will T: An iterative method for faster sum-of-pair multiple sequence alignment. Bioinformatics 2000, 16(9):808\u2013814.","journal-title":"Bioinformatics"},{"key":"1327_CR27","doi-asserted-by":"publisher","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","volume":"22","author":"JD Thompson","year":"1994","unstructured":"Thompson JD, Higgins DG, Gibson TJ: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice. Nucleic Acids Research 1994, 22: 4673\u20134680.","journal-title":"Nucleic Acids Research"},{"key":"1327_CR28","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/BF02603120","volume":"25","author":"DF Feng","year":"1987","unstructured":"Feng DF, Doolittle RF: Progressive sequence alignment as a prerequisite to correct phylogenetic trees. J Mol Evol 1987, 25: 351\u2013360.","journal-title":"J Mol Evol"},{"key":"1327_CR29","unstructured":"[\n                    http:\/\/www.tigr.org\/tdb\/benchmark\n                    \n                  ]"},{"key":"1327_CR30","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic local alignment search tool. J Mol Biol 1990, 215: 403\u2013410.","journal-title":"J Mol Biol"},{"key":"1327_CR31","unstructured":"[\n                    http:\/\/alpha10.bioch.virginia.edu\/fasta_www\/cgi\/\n                    \n                  ]"},{"key":"1327_CR32","unstructured":"[\n                    http:\/\/www.ebi.ac.uk\/services\/\n                    \n                  ]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-S4-S4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-7-S4-S4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-7-S4-S4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,23]],"date-time":"2019-01-23T07:57:02Z","timestamp":1548230222000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-7-S4-S4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":32,"journal-issue":{"issue":"S4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["1327"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-7-s4-s4","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]},"article-number":"S4"}}