{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T00:10:27Z","timestamp":1736640627537,"version":"3.32.0"},"reference-count":20,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,24]],"date-time":"2006-10-24T00:00:00Z","timestamp":1161648000000},"content-version":"vor","delay-in-days":5685,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Concurrency: Pract. Exper."],"published-print":{"date-parts":[[1991,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give two parallel algorithms for sequence comparison on the Connection Machine 2 (CM\u20102). The specific comparison measure we compute is the<jats:italic>edit distance<\/jats:italic>: given a finite alphabet \u2211 and two input sequences<jats:italic>X<\/jats:italic>\u03f5 \u2211<jats:sup>+<\/jats:sup>and<jats:italic>Y<\/jats:italic>\u03f5 \u2211<jats:sup>+<\/jats:sup>the edit distance<jats:italic>d(X,Y)<\/jats:italic>is the minimum cost of transforming<jats:italic>X<\/jats:italic>into<jats:italic>Y<\/jats:italic>via a series of weighted insertions, deletions and substitutions of characters. The edit distance comparison measure is equivalent to or subsumes a broad range of well known sequence comparison measures.<\/jats:p><jats:p>The CM\u20102 is very fast at performing parallel prefix operations. Our contribution consists of casting the problem in terms of these operations. Our first algorithm computes<jats:italic>d(X,Y)<\/jats:italic>using<jats:italic>N<\/jats:italic>processors and<jats:italic>O(M S)<\/jats:italic>time units, where<jats:italic>M<\/jats:italic>= min(|<jats:italic>X<\/jats:italic>|,||<jats:italic>Y<\/jats:italic>|) + 1,<jats:italic>N<\/jats:italic>= max(|<jats:italic>X<\/jats:italic>|,|<jats:italic>Y<\/jats:italic>|) + 1 and<jats:italic>S<\/jats:italic>is the time required for a parallel prefix operation. The second algorithm computes<jats:italic>d(X,Y)<\/jats:italic>using<jats:italic>NM<\/jats:italic>processors and<jats:italic>O<\/jats:italic>((log<jats:italic>N<\/jats:italic>log<jats:italic>M<\/jats:italic>)(<jats:italic>S<\/jats:italic>+<jats:italic>R<\/jats:italic>)) time units, where<jats:italic>R<\/jats:italic>is the time for a \u2018router\u2019 communication step\u2014one in which each processor is able to read data, in parallel, from the memory of any other processor. Our algorithms can also be applied to several variants of the problem, such as subsequence comparisons, and one\u2014many and many\u2010many comparisons on 'sequence databases'.<\/jats:p>","DOI":"10.1002\/cpe.4330030203","type":"journal-article","created":{"date-parts":[[2006,11,17]],"date-time":"2006-11-17T16:15:52Z","timestamp":1163780152000},"page":"89-107","source":"Crossref","is-referenced-by-count":0,"title":["Sequence comparison on the connection machine"],"prefix":"10.1002","volume":"3","author":[{"given":"Mikhail J.","family":"Atallah","sequence":"first","affiliation":[]},{"given":"Scott","family":"McFaddin","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,24]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359846"},{"key":"e_1_2_1_3_2","first-page":"4","volume-title":"Bulletin of Mathematical Biology","author":"Martinez H. M.","year":"1984"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"volume-title":"Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison","year":"1983","author":"Sankoff D.","key":"e_1_2_1_5_2"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"A.AggarwalandJ.Park. Notes on Searching in Multidimensional Monotone Arrays.Proc. 29th Annual Symp. on Foundations of Computer Science pp.497\u2013512.","DOI":"10.1109\/SFCS.1988.21966"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"A. A.Apostolico M. J.Atallah L. L.Larmore S.McFaddin. Efficient Parallel Algorithms for String Editing and Related Problems SIAM Journal on Computing October1990.","DOI":"10.1137\/0219066"},{"key":"e_1_2_1_10_2","unstructured":"T. R.Mathies. A Fast Parallel Algorithm to Determine Edit Distance Unpublished Manuscript(April1988)."},{"volume-title":"Efficient Parallel Algorithms","year":"1988","author":"Gibbons A.","key":"e_1_2_1_11_2"},{"key":"e_1_2_1_12_2","unstructured":"O. H.Ibarra T.Pong S. M.Sohn.Hypercube Algorithms for Some String Comparison Problems.Unpublished Manuscript (January1988)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90125-9"},{"key":"e_1_2_1_14_2","unstructured":"E.EdmistonandR. A.Wagner. Parallelization of the Dynamic Programming Algorithm for Comparison of Sequences Proceedings of 1987 International Conference on Parallel Processingpp.78\u201380(1987)."},{"key":"e_1_2_1_15_2","unstructured":"E.Lander J. P.Mesirov W.TaylorIV. Protein Sequence Comparison on a Data Parallel Computer Proceedings of 1988 International Conference on Parallel Processingpp.257\u2013263(1988)."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/16.5.1861"},{"volume-title":"The Connection Machine","year":"1985","author":"Hillis W. D.","key":"e_1_2_1_17_2"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1958.tb03887.x"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0908023"},{"key":"e_1_2_1_20_2","unstructured":"J.Salmon.Binary Gray Codes and the Mapping of a Physical Lattice into a Hypercube Caltech Concurrent Processor Report (CCP) Hm\u201051 (1983)."},{"key":"e_1_2_1_21_2","unstructured":"G. E.Blelloch.Scan Primitives and Parallel Vector Models Ph.D. Thesis Massachusetts Institute of Technology (1988)."}],"container-title":["Concurrency: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fcpe.4330030203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.4330030203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T23:51:56Z","timestamp":1736639516000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.4330030203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,4]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,4]]}},"alternative-id":["10.1002\/cpe.4330030203"],"URL":"https:\/\/doi.org\/10.1002\/cpe.4330030203","archive":["Portico"],"relation":{},"ISSN":["1040-3108","1096-9128"],"issn-type":[{"type":"print","value":"1040-3108"},{"type":"electronic","value":"1096-9128"}],"subject":[],"published":{"date-parts":[[1991,4]]}}}