Julian's Science Experiments
  • Famous Experiments and Inventions
  • The Scientific Method
  • Home Bioinformatics Experiments Bioinformatics Science Fair Projects Biology Jokes Warning!
     
     

    BLAST Algorithm
    Experiments, Studies and Background Information
    For Science Labs, Lesson Plans & Science Fair Projects
    For High School and College Students & Teachers







    BLAST Experiments and Studies

    • BLAST Introduction [View Experiment]
    • Primer-BLAST [View Experiment]
    • Data Parallelism in Bioinformatics Workflows Using Hydra [View Experiment]
    • Digital extractor: analysis of digital differential display output [View Experiment]
    • Characterizing Grid experiments in Bioinformatics for an efficient scheduling [View Experiment]
    • Use BLAST to Predict the Size of the CAPS Amplicons; Extract and Store Predicted CAPS Marker Sequences; Digest CAPS Markers Electronically (In Silico) [View Experiment]
    • Experimenting with database segmentation size vs time performance for mpiBLAST on an IBM HS21 blade cluster [View Experiment]
    • CloudBLAST: Combining MapReduce and Virtualization on Distributed Resources for Bioinformatics Applications [View Experiment]
    • BioCompute: Harnessing Distributed Systems for Bioinformatics Applications [View Experiment]
    • Thesis: Analyzing DNA Sequence using BLAST [View Experiment]
    • Bachelor thesis: BLAST-like Local Alignments with RazerS [View Experiment]
    • Thesis: WS-Mediator for Improving Dependability of Service Composition [View Experiment]
    BLAST Background

    Definition

    BLAST or Basic Local Alignment Search Tool is an algorithm for comparing primary biological sequence information, such as the amino-acid sequences of different proteins or the nucleotides of DNA sequences.

    Introduction

    A BLAST search enables a researcher to compare a query sequence with a library or database of sequences, and identify library sequences that resemble the query sequence above a certain threshold. For example, following the discovery of a previously unknown gene in the mouse, a scientist will typically perform a BLAST search of the human genome to see if humans carry a similar gene; BLAST will identify sequences in the human genome that resemble the mouse gene based on similarity of sequence. The BLAST program was designed by Eugene Myers, Stephen Altschul, Warren Gish, David J. Lipman and Webb Miller at the NIH and was published in J. Mol. Biol. in 1990.

    BLAST is one of the most widely used bioinformatics programs, because it addresses a fundamental problem and the algorithm emphasizes speed over sensitivity. This emphasis on speed is vital to making the algorithm practical on the huge genome databases currently available, although subsequent algorithms can be even faster.

    Before the fast algorithm such as BLAST and FASTA were developed, doing database searches for the protein or nucleic sequences was very time consuming by using a full alignment program like dynamic programming. BLAST is about 50 times faster than the dynamic programming; however, it can not guarantee the optimal alignments of the query and database sequences as in the dynamic programming, but just work to find the related sequences in a database search. BLAST is more time efficient than FASTA by searching only for the more significant patterns in the sequences, but with comparative sensitivity. This could be further realized by knowing the algorithm of BLAST introduced below.

    Examples of other questions that researchers use BLAST to answer are:

    • Which bacterial species have a protein that is related in lineage to a certain protein with known amino-acid sequence?
    • Where does a certain sequence of DNA originate?
    • What other genes encode proteins that exhibit structures or motifs such as ones that have just been determined?

    BLAST is also often used as part of other algorithms that require approximate sequence matching.

    The BLAST algorithm and the computer program that implements it were developed by Stephen Altschul, Warren Gish, David Lipman at the U.S. National Center for Biotechnology Information (NCBI), Webb Miller at the Pennsylvania State University, and Gene Myers at the University of Arizona. It is available on the web on the NCBI website.

    The original paper by Altschul, et al. was the most highly cited paper published in the 1990s. (Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ (1990). "Basic local alignment search tool". J Mol Biol 215 (3): 403–410. doi:10.1006/jmbi.1990.9999.)

    Uses of BLAST

    BLAST can be used for several purposes. These include identifying species, locating domains, establishing phylogeny, DNA mapping, and comparison.

    Identifying species
    With the use of BLAST, you can possibly correctly identify a species and/or find homologous species. This can be useful, for example, when you are working with a DNA sequence from an unknown species.

    Locating domains
    When working with a protein sequence you can input it into BLAST, to locate known domains within the sequence of interest.

    Establishing phylogeny
    Using the results received through BLAST you can create a phylogenetic tree using the BLAST web-page. It should be noted that phylogenies based on BLAST alone are less reliable than other purpose-built computational phylogenetic methods, so should only be relied upon for "first pass" phylogenetic analyses.

    DNA mapping
    When working with a known species, and looking to sequence a gene at an unknown location, BLAST can compare the chromosomal position of the sequence of interest, to relevant sequences in the database(s).

    Comparison
    When working with genes, BLAST can locate common genes in two related species, and can be used to map annotations from one organism to another.

    Process

    Input sequences are in FASTA format or Genbank format.

    BLAST output can be delivered in a variety of formats. These formats include HTML, plain text, and XML formatting. For NCBI’s web-page, the default format for output is HTML. When performing a BLAST on NCBI, the results are given in a graphical format showing the hits found, a table showing sequence identifiers for the hits with scoring related data, as well as alignments for the sequence of interest and the hits received with corresponding BLAST scores for these. The easiest to read and most informative of these is probably the table.

    Using a heuristic method, BLAST finds homologous sequences, not by comparing either sequence in its entirety, but rather by locating short matches between the two sequences. This process of finding initial words is called seeding. It is after this first match that BLAST begins to make local alignments. While attempting to find homology in sequences, sets of common letters, known as words, are very important. For example, suppose that the sequence contains the following stretch of letters, GLKFA. If a BLASTp was being conducted under default conditions, the word size would be 3 letters. In this case, using the given stretch of letters, the searched words would be GLK, LKF, KFA. The heuristic algorithm of BLAST locates all common three-letter words between the sequence of interest and the hit sequence, or sequences, from the database. These results will then be used to build an alignment. After making words for the sequence of interest, neighborhood words are also assembled. These words must satisfy a requirement of having a score of at least the threshold, T, when compared by using a scoring matrix. Along the lines of terms stated above, if a BLASTp were being conducted, the scoring matrix that would be used would most likely be BLOSUM62. Once both words and neighborhood words are assembled and compiled, they are compared to the sequences in the database in order to find matches. The threshold score T, determines whether a particular word will be included in the alignment or not. Once seeding has been conducted, the alignment, which is only 3 residues long, is extended in both directions by the algorithm used by BLAST. Each extension impacts the score of the alignment by either increasing or decreasing it. Should this score be higher than a pre-determined T, the alignment will be included in the results given by BLAST. However, should this score be lower than this pre-determined T, the alignment will cease to extend, preventing areas of poor alignment to be included in the BLAST results. Note, that increasing the T score limits the amount of space available to search, decreasing the number of neighborhood words, while at the same time speeding up the process of BLAST.

    To run, BLAST requires a query sequence to search for, and a sequence to search against (also called the target sequence) or a sequence database containing multiple such sequences. BLAST will find subsequences in the database which are similar to subsequences in the query. In typical usage, the query sequence is much smaller than the database, e.g., the query may be one thousand nucleotides while the database is several billion nucleotides.

    The main idea of BLAST is that there are often high-scoring segment pairs (HSP) contained in a statistically significant alignment. BLAST searches for high scoring sequence alignments between the query sequence and sequences in the database using a heuristic approach that approximates the Smith-Waterman algorithm. The exhaustive Smith-Waterman approach is too slow for searching large genomic databases such as GenBank. Therefore, the BLAST algorithm uses a heuristic approach that is less accurate than the Smith-Waterman algorithm but over 50 times faster. The speed and relatively good accuracy of BLAST are among the key technical innovations of the BLAST programs.

    For more information:
    http://en.wikipedia.org/wiki/BLAST
    http://blast.ncbi.nlm.nih.gov/Blast.cgi

    Source: Wikipedia (All text is available under the terms of the GNU Free Documentation License and Creative Commons Attribution-ShareAlike License.)

    Useful Links
    Bioinformatics Science Fair Projects and Experiments
    General Science Fair Projects Resources
    Biology / Biochemistry Science Fair Projects Books

                  





    My Dog Kelly

    Follow Us On:
           

    Privacy Policy - Site Map - About Us - Letters to the Editor

    Comments and inquiries could be addressed to:
    webmaster@julianTrubin.com


    Last updated: June 2013
    Copyright © 2003-2013 Julian Rubin