# Presentation: 024497

## Cluster Computing Applications Project Parallelizing BLAST

**Research Alliance of Minorities (RAM), Computer Science and Mathematics Division**

**	****	****William Burke**
**	****	****	****York College, City University of New York**
**	****	****John Mugler and Stephen Scott**
**	****	****	****Oak Ridge National Laboratory**

## Parallelizing the BLAST Algorithm: Feasible or Not?

**	**
**	****Bioinformatics Research needs faster text string matching algorithms. **
**	****The purpose of this project is to analyze the BLAST algorithm:**** **
**	****Define the structure of  BLAST. **
**	****State why it is a valuable Bioinformatics tool.**
**	****Explore parallelizations of BLAST.**
**	****BLAST matches query string fragments against a target database.**** **
**	****Eliminates need to run a full text string comparison. **
**	****Speeds up search database search time.**
**	****Several methods of parallelizing BLAST have been explored.**

**Notes:**
I reformatted the “parallelizing ...” text to center Once query and database string alignments are found (if the fragments match within a certain threshold), the full strings are matched. 

## Introduction

**Cluster infrastructure**
**Open Source Cluster Application Resources (OSCAR)**
**Cluster, Command and Control (C3)**
**eXtreme TORC (XTORC)**
**Cluster applications**
**Bioinformatics Toolsets**
**Basic Local Alignment Sequence Tool (BLAST)**

## Infrastructure Overview

**Infrastructure Overview**

**	****Red Hat Linux 7.2**
**	****OSCAR 1.3**
**	****C3 - **_**[http://www.csm.ornl.gov/torc/C3/](http://www.csm.ornl.gov/torc/C3/)**__** **_
**	****LAM/MPI - **_**[http://www.lam-mpi.org/](http://www.lam-mpi.org/)**__** **_
**	****Maui Scheduler - **_**[http://supercluster.org/maui/](http://supercluster.org/maui/)**__** **_
**	****MPICH - **_**[http://www-unix.mcs.anl.gov/mpi/mpich/](http://www-unix.mcs.anl.gov/mpi/mpich/)**__** **_
**	****OpenSSH - **_**[http://www.openssh.com/](http://www.openssh.com/)**__** **_
**	****OpenSSL - **_**[http://www.openssl.org/](http://www.openssl.org/)**__** **_
**	****PBS - **_**[http://www.openpbs.org/](http://www.openpbs.org/)**__** **_
**	****PVM - http://www.csm.ornl.gov/pvm/ **
**	****SIS - http://www.sisuite.org/ **

**Notes:**
moved the figs around and resized somewhat

Cluster, Command and Control (C3)
Local Area Machine/Message Passing Interface – (LAM/MPI)
Message Passing Interface CHameleon - (MPICH)
SIS – System Installation Suite (SIS)

## Red Hat Linux 7.2

**	****Installation**** **
**	****Configuration**
**	****Administration**
**	****Network Configuration.**
**	****Performance Monitoring.**
**	****Creating Scripts.**

## OSCAR 1.3 and C3 Tools

**	****OSCAR configures the head node. **
**	****OSCAR builds and configures compute nodes.**
**	****C3 reduces time and effort to operate and manage a cluster. **

**Notes:**
list all of oscar components or no oscar components in list – (where you have ssh and pbs) – as written it implies that only ssh/pbs are on compute nodes and this is not true.  (all or nothing!!!)   remove the pbs and openssh logos – will be too many if do all and only few is improper...

## eXtreme TORC powered by OSCAR

**eXtreme TORC powered by OSCAR**

**65 Pentium IV Machines**
**Peak Performance: 129.7 GFLOPS**
**RAM memory: 50.152 GB**

**Disk Capacity: 2.68 TB**
**Dual interconnects**
**Gigabit & Fast Ethernet**

## Slide 8

## Applications Overview

**BLAST a Bioinformatics tool.**
**	**
**http://www.ncbi.nlm.nih.gov/BLAST/blast_overview.html**
**Parallelize BLAST’s algorithm.**

**BLAST**

**Notes:**
BLAST logo is fuzzy – create the text yourself

## BLAST a Bioinformatics Tool

**	****What is BLAST?**** **
**	****A heuristic algorithm used for string matching ****	****query strings to a database.**
**	****How does BLAST algorithm work?**
**	****String fragmentation.**
**	****Statistical means for comparison.**
**	****How can you parallelize BLAST on a computational cluster?**

## The BLAST Search Algorithm

**Query word (W = 3)**
**	****QUERY:****	****GSVEDTTGSQSLAALLNKCKT****PQG****QRLVNQWIKWPLMDKNRIEERLNLVEAFVEDA**
**	****	****	****	****    ****PQG 18**
**	**** ****neighborhood****               PEG 15**
**	**** ****words**** ****	****                     PRG 14**
**	****	****                     ****PKG 14**
**	****	****                     ****PMG**** 13****	****neighborhood**
**	****	****                     ****PSG 13****	****score threshold**
**	****	****                     ****PQN 12****	****( T = 13 )**
**	****                              ****Etc...**
**	****	****      **
**	****QUERY STRING****	****  SLAALLNKCKT****PQG****QWLVNQWIKWPLMDKNRIEERLN****	****365**
**	****	****	****  ****----L--++K-P-G--+-----+-------------N****	**
**	****n DATABASE STRING****	****  GSWNLAALD****KD****PMG****DKNRIEERLNLVEAIKWPLMDJN****	****330**

**The BLAST Search Algorithm**

**Notes:**
why is this text fuzzy – did you cut from somewhere (or is my lasik going bad...)  create the graphic/text yourself using powerpoint so that is sharp image – this will have to project on a screen too and is annoying when is fuzzy!

## Parallelization of BLAST

**	****NBLAST****	****	****	****SLRI Bioinformatics Toolkit**** **
**	****ParAlign**
**	****MOBLAST**** ****         **
**www.usenix.org/publications/library/proceedings/ als2000/michalickova.html**
**	****DNA sequence matching processor**

**Notes:**
is this final slide?  where is conclusion/summary – should have something for that – this slide is a tools used/looked at slide...

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
	This research was performed under the Research Alliance for Minorities Program administered through the Computer Science and Mathematics Division, Oak Ridge National Laboratory.  This Program is sponsored by the Mathematical, Information, and Computational Sciences Division; Office of Advanced Scientific Computing Research; U.S. Department of Energy.  Oak Ridge National Laboratory is managed by UT-Battelle, LLC, for the U.S. Department of Energy under contract DE-AC05-00OR22725. This research used resources of the Center for Computational Sciences at Oak Ridge National Laboratory, which is supported by the Office of Science, U.S. Department of Energy
	This work has been authored by a contractor of the U.S. Government under contract DE-AC05-00OR22725.  Accordingly, the U.S. Government retains a nonexclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes. 
	I would like to extend my thanks to Stephen L. Scott Ph.D., John Mugler, Thomas Naughton, and Brian Luethke for their invaluable mentoring, Michaelangelo Salcedo Ph.D. for his guidance, Debbie McCoy, and Cheryl Hamby for their support in the RAM program.

## Conclusion

**BLAST algorithm has a diverse family **
**   ****	****of programs. **
**Several implementations exist for **
**   ****	****parallelizing the BLAST algorithm.**** **
**Future work to include further **
**   ****	****exploration of the various parallelized**
**   ****	****BLAST algorithms on clusters.**

## Acknowledgements

**	****I would like to extend my thanks to Stephen L. Scott, John Mugler, Thomas Naughton, and Brian Luethke for their invaluable mentoring, Michaelangelo Salcedo for his guidance, Debbie McCoy and Cheryl Hamby for their support in the RAM program.**

## Disclaimer

**This research was performed under the Research Alliance for Minorities Program administered through the Computer Science and Mathematics Division, Oak Ridge National Laboratory.  This Program is sponsored by the Mathematical, Information, and Computational Sciences Division; Office of Advanced Scientific Computing Research; U.S. Department of Energy.  Oak Ridge National Laboratory is managed by UT-Battelle, LLC, for the U.S. Department of Energy under contract DE-AC05-00OR22725. This research used resources of the Center for Computational Sciences at Oak Ridge National Laboratory, which is supported by the Office of Science, U.S. Department of Energy.  This work has been authored by a contractor of the U.S. Government under contract DE-AC05-00OR22725.  Accordingly, the U.S. Government retains a nonexclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes****.  **