Campus Units

Computer Science, Electrical and Computer Engineering

Document Type

Conference Proceeding

Conference

9th International Conference on High-Performance Computing

Publication Version

Accepted Manuscript

Link to Published Version

http://dx.doi.org/10.1007/3-540-36265-7_40

Publication Date

2002

Journal or Book Title

High Performance Computing — HiPC 2002

First Page

420

Last Page

430

DOI

10.1007/3-540-36265-7_40

Conference Title

9th International Conference on High-Performance Computing

Conference Date

December 18–21, 2002

City

Bangalore, India

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 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.

Comments

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.

Copyright Owner

Springer-Verlag Berlin Heidelberg

Language

en

File Format

application/pdf

Published Version

Share

Article Location

 
COinS