{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:23:49Z","timestamp":1742387029698},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2003,12]]},"abstract":"<jats:p> Given two genomic DNA sequences, the syntenic alignment problem is to compute an ordered list of subsequences for each sequence such that the corresponding subsequence pairs exhibit a high degree of similarity. Syntenic alignments are useful in comparing genomic DNA from related species and in identifying conserved genes. In this paper, we present a parallel algorithm for computing syntenic alignments that runs in [Formula: see text] time, where m and n are the respective lengths of the two genomic sequences, and p is the number of processors used. Our algorithm is time optimal with respect to the corresponding sequential algorithm and can use [Formula: see text] processors, where n is the length of the larger sequence. The space requirement of the algorithm is [Formula: see text] per processor. Using an implementation of this parallel algorithm, we report the alignment of a gene-rich region of human chromosome 12, namely 12p13 and its syntenic region in mouse chromosome 6 (both over 220,000 base pairs in length) in under 24 minutes on a 64-processor IBM xSeries cluster. <\/jats:p>","DOI":"10.1142\/s0129626403001604","type":"journal-article","created":{"date-parts":[[2004,3,5]],"date-time":"2004-03-05T11:52:36Z","timestamp":1078487556000},"page":"689-703","source":"Crossref","is-referenced-by-count":3,"title":["PARALLEL SYNTENIC ALIGNMENTS"],"prefix":"10.1142","volume":"13","author":[{"given":"NATSUHIKO","family":"FUTAMURA","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering,  Department of Computer Science, Iowa State University, USA"}]},{"given":"SRINIVAS","family":"ALURU","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering,  Department of Computer Science, Iowa State University, USA"}]},{"given":"XIAOQIU","family":"HUANG","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering,  Department of Computer Science, Iowa State University, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","unstructured":"S.\u00a0Aluru, N.\u00a0Futamura and K.\u00a0Mehrotra, Proc. International Parallel Processing Symposium (1999)\u00a0pp. 653\u2013659."},{"key":"rf2","first-page":"29","volume":"8","author":"Ansari-Lari M. A.","journal-title":"Genome Research"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1101\/gr.10.7.950"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/27.11.2369"},{"key":"rf5","unstructured":"E. W.\u00a0Edmiston and R. A.\u00a0Wagner, Proc. International Conference on Parallel Processing (1987)\u00a0pp. 78\u201380."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02427852"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(82)90398-9"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407900"},{"key":"rf10","first-page":"373","volume":"6","author":"Huang X.","journal-title":"Computer Applications in the Biosciences"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/19.2.228"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1101\/gr.9.9.815"},{"key":"rf13","unstructured":"E.\u00a0Lander, J. P.\u00a0Mesirov and W.\u00a0Taylor, Proc. International Conference on Parallel Processing (1988)\u00a0pp. 257\u2013263."},{"key":"rf14","first-page":"11","volume":"4","author":"Mayers E. W.","journal-title":"Computer Applications in the Biosciences"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1101\/gr.10.4.577"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626403001604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:15:16Z","timestamp":1565108116000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626403001604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":17,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2003,12]]}},"alternative-id":["10.1142\/S0129626403001604"],"URL":"https:\/\/doi.org\/10.1142\/s0129626403001604","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}