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 andin identifying conservedgen es. In this paper, we present a parallel algorithm for computing syntenic alignments that runs in O(mn/p) time and O(m + n/p) memory per processor, where m and n are the respective lengths of the two genomic sequences. Our algorithm is time optimal with respect to the corresponding sequential algorithm and can use O(n/log n) processors, where n is the length of the larger sequence. Using an implementation of this parallel algorithm, we report the alignment of human chromosome 12p13 andit s 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.
Available at: http://works.bepress.com/xiaoqiu-huang/24/
This is a manuscript of a proceeding published as Futamura N., Aluru S., Huang X. (2002) Parallel Syntenic Alignments. From the 9th International Conference on High-Performance Computing, Bangalore, India, December 18-21, 2002. doi: 10.1007/3-540-36265-7_40. Posted with permission.