No Access

PARALLEL SYNTENIC ALIGNMENTS

NATSUHIKO FUTAMURA

Department of Electrical and Computer Engineering, Department of Computer Science, Iowa State University, USA

Search for more papers by this author

SRINIVAS ALURU

Department of Electrical and Computer Engineering, Department of Computer Science, Iowa State University, USA

Research supported by NSF Career under CCR-0096288 and NSF EIA-0130861.

Search for more papers by this author

, and

XIAOQIU HUANG

Department of Electrical and Computer Engineering, Department of Computer Science, Iowa State University, USA

Research supported by NIH Grants R01 HG01502-05 and R01 HG01676-05 from NHGRI.

Search for more papers by this author

https://doi.org/10.1142/S0129626403001604Cited by:3 (Source: Crossref)

Abstract

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 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 processors, where n is the length of the larger sequence. The space requirement of the algorithm is 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.

Keywords:

References

S. Aluru, N. Futamura and K. Mehrotra, Proc. International Parallel Processing Symposium (1999) pp. 653–659. Google Scholar
M. A. Ansari-Lariet al., Genome Research 8, 29 (1998). Web of Science, Google Scholar
S. Batzoglouet al., Genome Research 10, 950 (2000). Crossref, Web of Science, Google Scholar
A. L. Delcheret al., Nucleic Acids Research 27, 2369 (1999). Crossref, Web of Science, Google Scholar
E. W. Edmiston and R. A. Wagner, Proc. International Conference on Parallel Processing (1987) pp. 78–80. Google Scholar
E. W. Edmistonet al., International Journal of Parallel Programming 17(3), 259 (1988). Crossref, Web of Science, Google Scholar
O. Gotoh, Journal of Molecular Biology 162, 705 (1982). Crossref, Web of Science, Google Scholar
D. S. Hirschberg, Communications of the ACM 18(6), 341 (1975). Crossref, Web of Science, Google Scholar
X. Huang, International Journal of Parallel Programming 18(3), 223 (1989). Crossref, Web of Science, Google Scholar
X. Huang, Computer Applications in the Biosciences 6(4), 373 (1990). Google Scholar
X. Huang and K. Chao, Bioinformatics 19(2), 228 (2003). Crossref, Web of Science, Google Scholar
N. Jareborg, E. Birney and R. Durbin, Genome Research 9, 815 (1999). Crossref, Web of Science, Google Scholar
E. Lander, J. P. Mesirov and W. Taylor, Proc. International Conference on Parallel Processing (1988) pp. 257–263. Google Scholar
E. W. Mayers and W. Miller, Computer Applications in the Biosciences 4(1), 11 (1988). Google Scholar
S. B. Needleman and C. D. Wunsch, Journal of Molecular Biology 48, 443 (1970). Crossref, Web of Science, Google Scholar
S. Schwartzet al., Genome Research 10, 577 (2000). Crossref, Web of Science, Google Scholar
A. Smit and p. Green, http://ftp.genome.washington.edu/RM/RepeatMasker.html, 1999 . Google Scholar
T. F. Smith and M. S. Waterman, Journal of Molecular Biology 147, 195 (1981). Crossref, Web of Science, Google Scholar