Efficient clustering of large EST data sets on parallel computers

被引:50
作者
Kalyanaraman, A
Aluru, S [1 ]
Kothari, S
Brendel, V
机构
[1] Iowa State Univ Sci & Technol, Dept Comp Sci, Ames, IA 50011 USA
[2] Iowa State Univ Sci & Technol, Dept Elect & Comp Engn, Ames, IA 50011 USA
[3] Iowa State Univ Sci & Technol, Dept Zool & Genet, Ames, IA 50011 USA
[4] Iowa State Univ Sci & Technol, Dept Stat, Ames, IA 50011 USA
基金
美国国家科学基金会;
关键词
D O I
10.1093/nar/gkg379
中图分类号
Q5 [生物化学]; Q7 [分子生物学];
学科分类号
071010 ; 081704 ;
摘要
Clustering expressed sequence tags (ESTs) is a powerful strategy for gene identification, gene expression studies and identifying important genetic variations such as single nucleotide polymorphisms. To enable fast clustering of large-scale EST data, we developed PaCE (for (P) under bar arallel (C) under bar lustering of (E) under bar STs), a software program for EST clustering on parallel computers. In this paper, we report on the design and development of PaCE and its evaluation using Arabidopsis ESTs. The novel features of our approach include: (i) design of memory efficient algorithms to reduce the memory required to linear in the size of the input, (ii) a combination of algorithmic techniques to reduce the computational work without sacrificing the quality of clustering, and (iii) use of parallel processing to reduce run-time and facilitate clustering of larger data sets. Using a combination of these techniques, we report the clustering of 168 200 Arabidopsis ESTs in 15 min on an IBM xSeries cluster with 30 dual-processor nodes. We also clustered 327 632 rat ESTs in 47 min and 420 694 Triticum aestivum ESTs in 3 h and 15 min. We demonstrate the quality of our software using benchmark Arabidopsis EST data, and by comparing it with CAP3, a software widely used for EST assembly. Our software allows clustering of much larger EST data sets than is possible with current software. Because of its speed, it also facilitates multiple runs with different parameters, providing biologists a tool to better analyze EST sequence data. Using PaCE, we clustered EST data from 23 plant species and the results are available at the PlantGDB website.
引用
收藏
页码:2963 / 2974
页数:12
相关论文
共 18 条
[11]   The TIGR Gene Indices: reconstruction and representation of expressed gene sequences [J].
Quackenbush, J ;
Liang, F ;
Holt, I ;
Pertea, G ;
Upton, J .
NUCLEIC ACIDS RESEARCH, 2000, 28 (01) :141-145
[12]   Pieces of the puzzle: expressed sequence tags and the catalog of human genes [J].
Schuler, GD .
JOURNAL OF MOLECULAR MEDICINE-JMM, 1997, 75 (10) :694-698
[13]   Functional annotation of a full-length Arabidopsis cDNA collection [J].
Seki, M ;
Narusaka, M ;
Kamiya, A ;
Ishida, J ;
Satou, M ;
Sakurai, T ;
Nakajima, M ;
Enju, A ;
Akiyama, K ;
Oono, Y ;
Muramatsu, M ;
Hayashizaki, Y ;
Kawai, J ;
Carninci, P ;
Itoh, M ;
Ishii, Y ;
Arakawa, T ;
Shibata, K ;
Shinagawa, A ;
Shinozaki, K .
SCIENCE, 2002, 296 (5565) :141-145
[14]  
Setubal J. C., 1997, Introduction to Computational Molecular Biology
[15]   IDENTIFICATION OF COMMON MOLECULAR SUBSEQUENCES [J].
SMITH, TF ;
WATERMAN, MS .
JOURNAL OF MOLECULAR BIOLOGY, 1981, 147 (01) :195-197
[16]  
SUTTON G, 1996, GENOME SCI TECHNOL, V1, P9
[17]   EFFICIENCY OF A GOOD BUT NOT LINEAR SET UNION ALGORITHM [J].
TARJAN, RE .
JOURNAL OF THE ACM, 1975, 22 (02) :215-225
[18]  
ZHU W, 2003, IN PRESS PLANT PHYSL