Parallel syntenic alignments

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 O ((p)-(mn)) time and O (m + (p)-(n)) memory per processor, where m and n P P are the respective lengths of the two genomic sequences. Our algorithm is time optimal with respect to the corresponding sequential algorithm and can use 0 ( n) processors, where n is the length of the larger log n sequence. Using an implementation of this parallel algorithm, we report the alignment of human chromosome 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.