A Parallel Processing System for a BLAST Program
Abstract
BLAST (Basic Local Alignment Search Tool) is one of the most widely used search tools, which identifies statistically significant matches between newly sequenced segments of genetic material or proteins and databases of known nucleotide or amino acid sequences. Such searches allow scientists to make inferences about the structures and functions of their discoveries, or to screen new sequences for further investigation. Although BLAST has been designed and optimized for speed, its major drawback is that it consumes a large amount of CPU time, memory, and I/O; searching a large number of queries against a large database can take a very long time. A preliminary study of BLAST indicated that its running time is proportional to the size of the database, and that BLAST shows its highest efficiency when the whole database can be held in memory. As genome databases are enormous and doubling in size roughly every 1.3 years, it is important to improve performance in memory-limited environments.
This thesis proposes separating the database into smaller parts, each sized to fit the available memory, and searching each part separately on a node of a parallel system. The implemented system eliminates swapping time, as demonstrated by a super-linear speedup in the results.
Thesis details
| Title | A Parallel Processing System for a BLAST Program |
| Author | Warin Wattanapornprom |
| Degree | M.Sc. in Computer Science |
| Department | Computer Engineering, Faculty of Engineering |
| Institution | Chulalongkorn University |
| Advisor | Assoc. Prof. Prabhas Chongstitvatana |
| Co-advisor | Dr. Natawut Nupairoj |
| Academic year | 2002 |
| ISBN | 974-17-1195-6 |
| Keywords | Parallel system, memory-limited, BLAST, distributed database, clustering |
Related publication
Improving the Performance of BLAST in a Memory-Limited Environment — Warin Wattanapornprom, Natawut Nupairoj and Prabhas Chongstitvatana. Department of Computer Engineering, Chulalongkorn University.
Abstract. BLAST has become an important tool for research in bioinformatics, since it helps scientists make inferences about the functions of proteins. BLAST's database is enormous and has been growing every day, which lowers the program's performance. This paper presents an alternative way to improve BLAST's performance on a single machine by reducing the overhead of disk swapping. It reports on the progress made in designing and developing a parallel system environment for BLAST: a preliminary experiment characterizing BLAST's memory behaviour, the performance-improvement method and its results, and a discussion of the prototype implementation and future work.
Key words: BLAST, distributed database, parallel search, clustering, memory-limited.