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 条
[41]   Meaningful Alignments [J].
Agnès Desolneux ;
Lionel Moisan ;
Jean-Michel Morel .
International Journal of Computer Vision, 2000, 40 :7-23
[42]   GALAXY ALIGNMENTS [J].
ARP, H .
JOURNAL OF ASTROPHYSICS AND ASTRONOMY, 1990, 11 (04) :411-443
[43]   MEGALITHIC ALIGNMENTS [J].
MICHELL, J .
NATURE, 1974, 250 (5468) :618-618
[44]   Material Alignments [J].
Gutierrez, Maria Paz .
TECHNOLOGY-ARCHITECTURE + DESIGN, 2021, 5 (01) :115-118
[45]   UNASSIGNED SYNTENIC GROUPS AND THEORETICAL CONSIDERATIONS [J].
MCKUSICK, VA ;
EDWARDS, JH .
CYTOGENETICS AND CELL GENETICS, 1975, 14 (3-6) :196-198
[46]   Syntenic reconstruction of microbial chromosomal mutations [J].
Cutler, RW ;
Gambis, A .
NANOTECH 2003, VOL 1, 2003, :21-23
[47]   CHROMOSOMAL ASSIGNMENT OF BOVINE SYNTENIC GROUPS [J].
GUNAWARDANA, A ;
SOLINAS, S ;
SCHOBERLEIN, A ;
EGGEN, A ;
THREADGILL, DW ;
THREADGILL, DS ;
DIETZ, AB ;
GEORGES, M ;
WOMACK, JE ;
FRIES, R ;
STRANZINGER, G .
CYTOGENETICS AND CELL GENETICS, 1991, 58 (3-4) :2126-2126
[48]   On maximal instances for the original syntenic distance [J].
Chauve, C ;
Fertin, G .
THEORETICAL COMPUTER SCIENCE, 2004, 326 (1-3) :29-43
[49]   NASP: a parallel program for identifying evolutionarily conserved nucleic acid secondary structures from nucleotide sequence alignments [J].
Semegni, J. Y. ;
Wamalwa, M. ;
Gaujoux, R. ;
Harkins, G. W. ;
Gray, A. ;
Martin, D. P. .
BIOINFORMATICS, 2011, 27 (17) :2443-2445
[50]   DEPENDENCE OF ELECTRICAL-CONDUCTIVITY ON FILM THICKNESS IN POLYACETYLENE - EFFECTS OF MECHANICALLY FORCED PARALLEL AND INPLANE ALIGNMENTS OF FIBRILS [J].
AKAGI, K ;
SHIRAKAWA, H .
SYNTHETIC METALS, 1993, 60 (02) :85-92