Parallel syntenic alignments

被引：0

作者：

Futamura, N ^{[1
]}

Aluru, S ^{[1
]}

Huang, XQ ^{[1
]}

机构：

[1] Iowa State Univ, Ames, IA 50011 USA

来源：

HIGH PERFORMANCE COMPUTING - HIPC 2002, PROCEEDINGS | 2002年 / 2552卷

关键词：

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：420 / 430

页数：11

共 50 条

[21] Alector: A Parallel Corpus of Simplified French Texts with Alignments of Misreadings by Poor and Dyslexic Readers [J].

Gala, Nuria ;

Tack, Anais ;

Javourey-Drevet, Ludivine ;

Francois, Thomas ;

Ziegler, Johannes C. .

PROCEEDINGS OF THE 12TH INTERNATIONAL CONFERENCE ON LANGUAGE RESOURCES AND EVALUATION (LREC 2020), 2020, :1353-1361

[22] The alignments [J].

Zimmer, Paul .

GEORGIA REVIEW, 2006, 60 (3-4) :791-802

[23] RHESUS SYNTENIC GROUP IN MAN [J].

RENWICK, JH .

NATURE, 1971, 234 (5330) :475-&

[24] Gene prediction by syntenic alignment [J].

Adi, SS ;

Ferreira, CE .

ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, PROCEEDINGS, 2005, 3594 :246-250

[25] Alignments and Trimmed Alignments: Their Characteristics and Phylogenetic Trees [J].

Wu, Guang ;

Yan, Shaomin .

2024 24TH INTERNATIONAL CONFERENCE ON TRANSPARENT OPTICAL NETWORKS, ICTON 2024, 2024,

[26] A simple approximation algorithm for nonoverlapping local alignments (weighted independent sets of axis parallel rectangles) [J].

Berman, P ;

DasGupta, B .

BIOCOMPUTING, 2002, 1 :129-138

[27] BUILDING MULTIPLE ALIGNMENTS FROM PAIRWISE ALIGNMENTS [J].

MILLER, W .

COMPUTER APPLICATIONS IN THE BIOSCIENCES, 1993, 9 (02) :169-176

[28] Efficient parallel algorithm for multiple sequence alignments with regular expression constraints on graphics processing units [J].

Lin, Chun Yuan ;

Lin, Yu Shiang .

INTERNATIONAL JOURNAL OF COMPUTATIONAL SCIENCE AND ENGINEERING, 2014, 9 (1-2) :11-20

[29] Parallel Reconstruction of Neighbor-Joining Trees for Large Multiple Sequence Alignments using CUDA [J].

Liu, Yongchao ;

Schmidt, Bertil ;

Maskell, Douglas L. .

2009 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL & DISTRIBUTED PROCESSING, VOLS 1-5, 2009, :1538-1545

[30] On the complexity and approximation of syntenic distance [J].

DasGupta, B ;

Jiang, T ;

Kannan, S ;

Li, M ;

Sweedyk, E .

DISCRETE APPLIED MATHEMATICS, 1998, 88 (1-3) :59-82

← 1 2 3 4 5 →