View source for BLAST (biotechnology)

{{Short description|Bioinformatics search algorithm}}
{{More citations needed|date=April 2024}}
{{Infobox software
| name = BLAST
| author = [[Stephen Altschul]], [[Warren Gish]], [[Webb Miller]], [[Eugene Myers]], and [[David Lipman]]
| developer = [[National Center for Biotechnology Information|NCBI]]
| programming language = [[C (programming language)|C]] and [[C++]]<ref>{{cite web |title= BLAST Developer Information |url = https://blast.ncbi.nlm.nih.gov/Blast.cgi?CMD%20=%20Web&PAGE_TYPE%20=%20BlastDocs&DOC_TYPE%20=%20DeveloperInfo |website = blast.ncbi.nlm.nih.gov}}</ref>
| latest release version = 2.16.0+<ref>{{cite book |title= BLAST Release Notes | date=24 June 2024 | publisher=National Center for Biotechnology Information (US) |url = https://www.ncbi.nlm.nih.gov/books/NBK131777/}}</ref>
| latest release date = {{release date and age|2024|06|25|df=yes}}
| operating_system = [[UNIX]], [[Linux]], [[Apple Macintosh|Mac]], [[MS-Windows]]
| genre = [[Bioinformatics]] tool
| license = [[Public domain]]
| website = {{URL|http://blast.ncbi.nlm.nih.gov/Blast.cgi}}
}}

In [[bioinformatics]], '''BLAST''' ('''basic local alignment search tool''')<ref name=KarlinObit.NYT>{{cite news  
   |newspaper=[[The New York Times]]
   |url=https://www.nytimes.com/2008/02/21/us/21karlin.html
   |title=Samuel Karlin, Versatile Mathematician, Dies at 83
   |author=Douglas Martin |date=21 February 2008}}</ref> is an [[algorithm]] and program for comparing [[Primary structure|primary]] biological sequence information, such as the [[amino acid|amino-acid]] sequences of [[protein]]s or the [[nucleotide]]s of [[DNA sequence|DNA]] and/or [[RNA]] sequences. A BLAST search enables a researcher to compare a subject protein or nucleotide sequence (called a query) with a library or [[database]] of sequences, and identify database sequences that resemble the query sequence above a certain threshold. For example, following the discovery of a previously unknown gene in the [[Mus musculus|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.

== Background ==
BLAST is one of the most widely used bioinformatics programs for sequence searching.<ref>{{cite web 
   |author=R. M. Casey |year=2005 
   |title=BLAST Sequences Aid in Genomics and Proteomics 
   |publisher=Business Intelligence Network 
   |url=http://www.b-eye-network.com/view/1730}}</ref> It addresses a fundamental problem in bioinformatics research. The [[heuristic]] algorithm it uses is much faster than other approaches, such as calculating an optimal alignment. 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.

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 extended the alignment work of a previously developed program for protein and DNA sequence similarity searches, [[FASTA]], by adding a novel stochastic model developed by [[Samuel Karlin]] and [[Stephen Altschul]].<ref name="FASTA.NIH">{{cite web
   |url=https://www.ncbi.nlm.nih.gov/BLAST/fasta.shtml
   |title=BLAST topics}}</ref> They proposed "a method for estimating similarities between the known DNA sequence of one organism with that of another",<ref name="KarlinObit.NYT" /> and their work has been described as "the statistical foundation for BLAST."<ref name="Stanford8">{{cite web
   |website=Stanford.edu
   |url=https://news.stanford.edu/pr/2008/pr-karlin_obit-012308.html
   |title=Sam Karlin, mathematician who improved DNA analysis, dead at 83
   |author=Dan Stober
   |date=January 16, 2008
   |access-date=July 16, 2019
   |archive-date=June 12, 2016
   |archive-url=https://web.archive.org/web/20160612093401/http://news.stanford.edu/pr/2008/pr-karlin_obit-012308.html
   |url-status=dead
   }}</ref> Subsequently, Altschul, Gish, Miller, Myers, and Lipman designed and implemented the BLAST program, which was published in the ''[[Journal of Molecular Biology]]'' in 1990 and has been cited over 100,000 times since.<ref name="Altschul1990">{{Cite journal 
   |author1=Stephen Altschul |author-link1=Stephen Altschul  |author2=Warren Gish |author-link2=Warren Gish
   |author3=Webb Miller |author-link3=Webb Miller |author4=Eugene Myers |author-link4=Eugene Myers
   |author5=David J. Lipman |author-link5=David J. Lipman
   |title=Basic local alignment search tool |doi = 10.1016/S0022-2836(05)80360-2 
   |journal=Journal of Molecular Biology |volume=215 |issue=3 |pages=403–410 |year=1990 |pmid=2231712
   |s2cid=14441902 |url= http://www.blastalgorithm.com}}</ref>

While BLAST is faster than any [[Smith–Waterman algorithm|Smith-Waterman]] implementation for most cases, it cannot "guarantee the optimal alignments of the query and database sequences" as Smith-Waterman algorithm does. The Smith-Waterman algorithm was an extension of a previous optimal method, the [[Needleman–Wunsch algorithm]], which was the first sequence alignment algorithm that was guaranteed to find the best possible alignment. However, the time and space requirements of these optimal algorithms far exceed the requirements of BLAST.

BLAST is more time-efficient than FASTA by searching only for the more significant patterns in the sequences, yet with comparative sensitivity. This could be further realized by understanding the algorithm of BLAST introduced below.

Examples of other questions that researchers use BLAST to answer are:
* Which [[bacteria]]l [[species]] have a protein that is related in lineage to a certain protein with known [[primary structure|amino-acid sequence]]
* What other genes encode proteins that exhibit structures or [[structural motif|motifs]] such as ones that have just been determined
BLAST is also often used as part of other algorithms that require [[approximate string matching|approximate sequence matching]].

BLAST is available on the web on the NCBI website. Different types of BLASTs are available according to the query sequences and the target databases. Alternative implementations include AB-BLAST (formerly known as WU-BLAST), FSA-BLAST (last updated in 2006), and ScalaBLAST.<ref>{{Cite journal | last1 = Oehmen | first1 = C. | last2 = Nieplocha | first2 = J. | doi = 10.1109/TPDS.2006.112 | title = ScalaBLAST: A Scalable Implementation of BLAST for High-Performance Data-Intensive Bioinformatics Analysis | journal = IEEE Transactions on Parallel and Distributed Systems | volume = 17 | issue = 8 | pages = 740 | year = 2006 | s2cid = 11122366 | url = https://zenodo.org/record/1232261 }}</ref><ref>{{Cite journal | last1 = Oehmen | first1 = C. S. | last2 = Baxter | first2 = D. J. | doi = 10.1093/bioinformatics/btt013 | title = ScalaBLAST 2.0: Rapid and robust BLAST calculations on multiprocessor systems | journal = Bioinformatics | volume = 29 | issue = 6 | pages = 797–798 | year = 2013 | pmid =  23361326| pmc =3597145 }}</ref>

The original paper by Altschul, ''et al.''<ref name="Altschul1990" /> was the most highly cited paper published in the 1990s.<ref>{{cite web|title=Sense from Sequences: Stephen F. Altschul on Bettering BLAST |publisher=ScienceWatch |date=July–August 2000 |url=http://www.sciencewatch.com/july-aug2000/sw_july-aug2000_page3.htm |url-status=dead |archive-url=https://web.archive.org/web/20071007132448/http://www.sciencewatch.com/july-aug2000/sw_july-aug2000_page3.htm |archive-date=7 October 2007 }}</ref>

=== Input ===
Input sequences (in [[FASTA format|FASTA]] or [[Genbank]] format), database to search and other optional parameters such as scoring matrix.{{clarification|date=July 2024}}<ref>{{Cite journal |last1=Penumarthi |first1=Lasya R. |last2=Baptista |first2=Rodrigo P. |last3=Beaudry |first3=Megan S. |last4=Glenn |first4=Travis C. |last5=Kissinger |first5=Jessica C. |date=2024-12-18 |title=A new chromosome-level genome assembly and annotation of Cryptosporidium meleagridis |journal=Scientific Data |language=en |volume=11 |issue=1 |pages=1388 |doi=10.1038/s41597-024-04235-7 |pmid=39695163 |issn=2052-4463|pmc=11655656 |bibcode=2024NatSD..11.1388P }}</ref>

=== Output ===
BLAST output can be delivered in a variety of formats. These formats include [[HTML]], [[plain text]], and [[XML]] formatting. For NCBI's webpage, 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.

If one is attempting to search for a proprietary sequence or simply one that is unavailable in databases available to the general public through sources such as NCBI, there is a BLAST program available for download to any computer, at no cost. This can be found at BLAST+ executables. There are also commercial programs available for purchase. Databases can be found on the NCBI site, as well as on the Index of BLAST databases (FTP).

== Process ==
Using a [[heuristic]] method, BLAST finds similar sequences,  by locating short matches between the two sequences. This process of finding similar sequences is called seeding. It is after this first match that BLAST begins to make local alignments. While attempting to find similarity 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 [[Sequence alignment#Pairwise alignment|BLAST]] was being conducted under normal conditions, the word size would be 3 letters. In this case, using the given stretch of letters, the searched words would be GLK, LKF, and 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. This result will then be used to build an alignment. After making words for the sequence of interest, the rest of the 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.

One commonly used scoring matrix for BLAST searches is [[BLOSUM62]],<ref>{{cite journal  
   |author1=Steven Henikoff  |author2=Jorja Henikoff
   |year=1992| journal=PNAS |volume=89 |pages=10915–10919
   |pmid=1438297 |title=Amino Acid Substitution Matrices from Protein Blocks 
   |doi=10.1073/pnas.89.22.10915  |issue=22 |pmc=50453|bibcode=1992PNAS...8910915H
 |author1-link=Steven Henikoff
 |doi-access=free
 }}</ref> although the optimal scoring matrix depends on sequence similarity. 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 or not a particular word will be included in the alignment. 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. If this score is higher than a pre-determined ''T'', the alignment will be included in the results given by BLAST. However, if this score is lower than this pre-determined ''T'', the alignment will cease to extend, preventing the areas of poor alignment from being 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

== Algorithm ==
To run the software, 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 sub-sequences 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 alignment]]s between the query sequence and the existing sequences in the database using a heuristic approach that approximates the [[Smith-Waterman algorithm]]. However, the exhaustive Smith-Waterman approach is too slow for searching large genomic databases such as [[GenBank]]. Therefore, the BLAST algorithm uses a [[Heuristic algorithm|heuristic]] approach that is less accurate than the Smith-Waterman algorithm but over 50 times faster. <ref name="Sequence&GenomeAnalysis">{{cite book |last=Mount |first=D. W. |title=Bioinformatics: Sequence and Genome Analysis |year=2004 |url=http://www.bioinformaticsonline.org/ |publisher=Cold Spring Harbor Press |isbn=978-0-87969-712-9 |edition=2nd}}</ref> The speed and relatively good accuracy of BLAST are among the key technical innovations of the BLAST programs.

An overview of the BLAST algorithm (a protein to protein search) is as follows:<ref name="Sequence&GenomeAnalysis"/>

# ''Remove low-complexity region or sequence repeats in the query sequence.''
#: "Low-complexity region" means a region of a sequence composed of few kinds of elements. These regions might give high scores that confuse the program to find the actual significant sequences in the database, so they should be filtered out. The regions will be marked with an X (protein sequences) or N (nucleic acid sequences) and then be ignored by the BLAST program. To filter out the low-complexity regions, the SEG program is used for protein sequences and the program DUST is used for DNA sequences. On the other hand, the program XNU is used to mask off the tandem repeats in protein sequences.
# ''Make a ''k''-letter word list of the query sequence.''
#: Take ''k''=3 for example, we list the words of length 3 in the query protein sequence (''k'' is usually 11 for a DNA sequence) "sequentially", until the last letter of the query sequence is included. The method is illustrated in figure 1.[[File:Query words.svg|frame|Fig. 1 The method to establish the ''k''-letter query word list.<ref>Adapted from Biological Sequence Analysis I, Current Topics in Genome Analysis [https://www.youtube.com/watch?v=SAweFv8I8ow].</ref> ]]
# ''List the possible matching words.''
#: This step is one of the main differences between BLAST and FASTA. FASTA cares about all of the common words in the database and query sequences that are listed in step 2; however, BLAST only cares about the high-scoring words. The scores are created by comparing the word in the list in step 2 with all the 3-letter words. By using the scoring matrix ([[substitution matrix]]) to score the comparison of each residue pair, there are 20^3 possible match scores for a 3-letter word. For example, the score obtained by comparing PQG with PEG and PQA is respectively 15 and 12 with the [[BLOSUM62]] weighting scheme. For DNA words, a match is scored as +5 and a mismatch as -4, or as +2 and -3. After that, a neighborhood word score threshold ''T'' is used to reduce the number of possible matching words. The words whose scores are greater than the threshold ''T'' will remain in the possible matching words list, while those with lower scores will be discarded. For example, PEG is kept, but PQA is abandoned when T is 13.
# ''Organize the remaining high-scoring words into an efficient search tree.''
#: This allows the program to rapidly compare the high-scoring words to the database sequences.
# ''Repeat step 3 to 4 for each ''k''-letter word in the query sequence.''
# ''Scan the database sequences for exact matches with the remaining high-scoring words.''
#: The BLAST program scans the database sequences for the remaining high-scoring word, such as PEG, of each position. If an exact match is found, this match is used to seed a possible un-gapped alignment between the query and database sequences.
# ''Extend the exact matches to high-scoring segment pair (HSP).''
#* The original version of BLAST stretches a longer alignment between the query and the database sequence in the left and right directions, from the position where the exact match occurred. The extension does not stop until the accumulated total score of the HSP begins to decrease. A simplified example is presented in figure 2.[[File:extension process.jpg|frame|Fig. 2 The process to extend the exact match. Adapted from Biological Sequence Analysis I, Current Topics in Genome Analysis [https://www.youtube.com/watch?v=SAweFv8I8ow]. ]] [[File:neighbor HSP.jpg|frame|Fig. 3 The positions of the exact matches.]]
#* To save more time, a newer version of BLAST, called BLAST2 or gapped BLAST, has been developed. BLAST2 adopts a lower neighborhood word score threshold to maintain the same level of sensitivity for detecting sequence similarity. Therefore, the list of possible matching words list in step 3 becomes longer. Next, the exact matched regions, within distance A from each other on the same diagonal in figure 3, will be joined as a longer new region. Finally, the new regions are then extended by the same method as in the original version of BLAST, and the HSPs' (High-scoring segment pair) scores of the extended regions are then created by using a substitution matrix as before.
# ''List all of the HSPs in the database whose score is high enough to be considered.''
#: We list the HSPs whose scores are greater than the empirically determined cutoff score ''S''. By examining the distribution of the alignment scores modeled by comparing random sequences, a cutoff score ''S'' can be determined such that its value is large enough to guarantee the significance of the remaining HSPs.
# ''Evaluate the significance of the HSP score.''
#: BLAST next assesses the statistical significance of each HSP score by exploiting the Gumbel extreme value distribution (EVD). (It is proved that the distribution of Smith-Waterman local alignment scores between two random sequences follows the Gumbel EVD. For local alignments containing gaps it is not proved.). In accordance with the Gumbel EVD, the probability ''p'' of observing a score ''S'' equal to or greater than x is given by the equation
#::<math>p\left( S\ge x \right) =1-\exp \left( -e^{-\lambda \left( x-\mu \right) } \right) </math>
#: where
#:: <math>\mu = \frac{ \log \left( Km'n' \right) }{\lambda }\;</math>
#: The statistical parameters <math>\lambda</math> and <math>\mathrm{K}</math> are estimated by fitting the distribution of the un-gapped local alignment scores, of the query sequence and a lot of shuffled versions (Global or local shuffling) of a database sequence, to the Gumbel extreme value distribution. Note that <math>\lambda</math> and <math>\mathrm{K}</math> depend upon the substitution matrix, gap penalties, and sequence composition (the letter frequencies). <math>m'</math> and <math>n'</math> are the effective lengths of the query and database sequences, respectively. The original sequence length is shortened to the effective length to compensate for the edge effect (an alignment start near the end of one of the query or database sequence is likely not to have enough sequence to build an optimal alignment). They can be calculated as
#:: <math>m'\approx m-\frac{ \ln Kmn }{H}\;</math>
#:: <math>n'\approx n-\frac{ \ln Kmn }{H}\;</math>
#: where <math>\mathrm{H}</math> is the average expected score per aligned pair of residues in an alignment of two random sequences. Altschul and Gish gave the typical values, <math>\lambda = 0.318</math>, <math> \mathrm{K} = 0.13</math>, and <math>\mathrm{H} = 0.40</math>, for un-gapped local alignment using BLOSUM62 as the substitution matrix. Using the typical values for assessing the significance is called the lookup table method; it is not accurate. The expect score ''E'' of a database match is the number of times that an unrelated database sequence would obtain a score ''S'' higher than ''x'' by chance. The expectation ''E'' obtained in a search for a database of ''D'' sequences is given by
#::<math>E\approx 1-e^{-p\left( s>x \right) D}</math>
#: Furthermore, when <math>p<0.1</math>, E could be approximated by the Poisson distribution as
#:: <math>E\approx pD</math>
#: This expectation or expect value "E" (often called an ''E'' score or ''E''-value or ''e''-value) assessing the significance of the HSP score for un-gapped local alignment is reported in the BLAST results. The calculation shown here is modified if individual HSPs are combined, such as when producing gapped alignments (described below), due to the variation of the statistical parameters.
# ''Make two or more HSP regions into a longer alignment.''
#: Sometimes, we find two or more HSP regions in one database sequence that can be made into a longer alignment. This provides additional evidence of the relation between the query and database sequence. There are two methods, the Poisson method and the sum-of-scores method, to compare the significance of the newly combined HSP regions. Suppose that there are two combined HSP regions with the pairs of scores (65, 40) and (52, 45), respectively. The Poisson method gives more significance to the set with the maximal lower score (45>40). However, the sum-of-scores method prefers the first set, because 65+40 (105) is greater than 52+45(97). The original BLAST uses the Poisson method; gapped BLAST and the WU-BLAST uses the sum-of scores method.
# ''Show the gapped Smith-Waterman local alignments of the query and each of the matched database sequences.''
#* The original BLAST only generates un-gapped alignments including the initially found HSPs individually, even when there is more than one HSP found in one database sequence.
#* BLAST2 produces a single alignment with gaps that can include all of the initially found HSP regions. Note that the computation of the score and its corresponding ''E''-value involves use of adequate gap penalties.
# ''Report every match whose expect score is lower than a threshold parameter ''E''.''

===Types of BLAST===
;BLASTn (Nucleotide BLAST):
BLASTn compares one or more nucleotide sequence to a database or another sequence. This is useful when trying to identify evolutionary relationships between organisms. <ref>{{cite web | url=https://guides.lib.berkeley.edu/ncbi/blast#:~:text=Basic%20Local%20Alignment%20Search%20Tool%20(BLAST)&text=The%20program%20compares%20nucleotide%20or,identify%20members%20of%20gene%20families | title=Library Guides: NCBI Bioinformatics Resources: An Introduction: BLAST: Compare & identify sequences }}</ref>
;tBLASTn:
tBLASTn used to search for proteins in sequences that haven't been translated into proteins yet. It takes a protein sequence and compares it to all possible translations of a DNA sequence. This is useful when looking for similar protein-coding regions in DNA sequences that haven't been fully annotated, like ESTs (short, single-read cDNA sequences) and HTGs (draft genome sequences). Since these sequences don't have known protein translations, we can only search for them using tBLASTn.<ref>{{cite web | url=https://guides.lib.berkeley.edu/ncbi/blast#:~:text=Basic%20Local%20Alignment%20Search%20Tool%20(BLAST)&text=The%20program%20compares%20nucleotide%20or,identify%20members%20of%20gene%20families | title=Library Guides: NCBI Bioinformatics Resources: An Introduction: BLAST: Compare & identify sequences }}</ref>
;BLASTx:
BLASTx compares a nucleotide query sequence, which can be translated into six different protein sequences, against a database of known protein sequences. This tool is useful when the reading frame of the DNA sequence is uncertain or contains errors that might cause mistakes in protein-coding. BLASTx provides combined statistics for hits across all frames, making it helpful for the initial analysis of new DNA sequences.<ref>{{cite web | url=https://guides.lib.berkeley.edu/ncbi/blast#:~:text=Basic%20Local%20Alignment%20Search%20Tool%20(BLAST)&text=The%20program%20compares%20nucleotide%20or,identify%20members%20of%20gene%20families | title=Library Guides: NCBI Bioinformatics Resources: An Introduction: BLAST: Compare & identify sequences }}</ref>
;BLASTp:
[[File:Blastp.png|thumb|Protein sequence being compared against nr database using BLASTp.]]
BLASTp, or Protein BLAST, is used to compare protein sequences. You can input one or more protein sequences that you want to compare against a single protein sequence or a database of protein sequences. This is useful when you're trying to identify a protein by finding similar sequences in existing protein databases.<ref>{{cite web | url=https://guides.lib.berkeley.edu/ncbi/blast#:~:text=Basic%20Local%20Alignment%20Search%20Tool%20(BLAST)&text=The%20program%20compares%20nucleotide%20or,identify%20members%20of%20gene%20families | title=Library Guides: NCBI Bioinformatics Resources: An Introduction: BLAST: Compare & identify sequences }}</ref>

=== Parallel BLAST ===

Parallel BLAST versions of split databases are implemented using [[Message Passing Interface|MPI]] and [[Pthreads]], and have been ported to various platforms including [[Microsoft Windows|Windows]], [[Linux]], [[Solaris (operating system)|Solaris]], [[Mac OS X]], and [[AIX operating system|AIX]]. Popular approaches to parallelize BLAST include query distribution, hash table segmentation, computation parallelization, and database segmentation (partition). Databases are split into equal sized pieces and stored locally on each node. Each query is run on all nodes in parallel and the resultant BLAST output files from all nodes merged to yield the final output. Specific implementations include MPIblast, ScalaBLAST, DCBLAST and so on.<ref>{{cite journal |last1=Yim |first1=WC |last2=Cushman |first2=JC |title=Divide and Conquer (DC) BLAST: fast and easy BLAST execution within HPC environments |journal=PeerJ |date=2017 |volume=5 |pages=e3486 |doi=10.7717/peerj.3486 |pmid=28652936 |pmc=5483034 |doi-access=free }}</ref>

MPIblast makes use of a database segmentation technique to parallelize the computation process.<ref>{{cite web |last1=Darling |first1=Ace |last2=Carey |first2=Lewis |last3=Feng |first3=Wei-Chun |title=The design, implementation, and evaluation of mpiBLAST |url=https://pages.cs.wisc.edu/~darling/mpiblast-cwce2003.pdf |website=University of Wisconsin-Madison |date=2003 |access-date=2023-04-17 }}</ref> This allows for significant performance improvements when conducting BLAST searches across a set of nodes in a cluster. In some scenarios a superlinear speedup is achievable. This makes MPIblast suitable for the extensive genomic datasets that are typically used in bioinformatics.

BLAST generally runs at a speed of [[Big O notation|O(n)]], where n is the size of the database.<ref>{{cite web |last1=Kellis |first1=Manolis |title=The Blast Algorithm (Basic Alignment Search Tool |url=https://bio.libretexts.org/Bookshelves/Computational_Biology/Book%3A_Computational_Biology_-_Genomes_Networks_and_Evolution_(Kellis_et_al.)/03%3A_Rapid_Sequence_Alignment_and_Database_Search/3.05%3A_The_BLAST_algorithm_(Basic_Local_Alignment_Search_Tool) |website=LibreTexts |date=5 October 2020 | access-date=2023-04-17 }}</ref> The time to complete the search increases linearly as the size of the database increases. MPIblast utilizes [[Parallel computing|parallel processing]] to speed up the search. The ideal speed for any [[parallel computation]] is a complexity of O(n/p), with n being the size of the database and p being the number of processors. This would indicate that the job is evenly distributed among the p number of processors. This is visualized in the included graph. The superlinear speedup that can sometimes occur with MPIblast can have a complexity better than O(n/p). This occurs because the cache memory can be used to decrease the run time.<ref>{{cite web |last1=Darling |first1=Ace |last2=Carey |first2=Lewis |last3=Feng |first3=Wei-Chun |title=The design, implementation, and evaluation of mpiBLAST |url=https://pages.cs.wisc.edu/~darling/mpiblast-cwce2003.pdf |website=University of Wisconsin-Madison |date=2003 |access-date=2023-04-17 }}</ref>

== Alternatives to BLAST ==

The predecessor to BLAST, [[FASTA]], can also be used for protein and DNA similarity searching.  [[FASTA]] provides a similar set of programs for comparing proteins to protein and DNA databases, DNA to DNA and protein databases, and includes additional programs for working with unordered short peptides and DNA sequences.  In addition, the [[FASTA]] package provides SSEARCH, a vectorized implementation of the rigorous [[Smith-Waterman]] algorithm.  FASTA is slower than BLAST, but provides a much wider range of scoring matrices, making it easier to tailor a search to a specific evolutionary distance.

An extremely fast but considerably less sensitive alternative to BLAST is [[BLAT (bioinformatics)|BLAT]] (''B''last ''L''ike ''A''lignment ''T''ool). While BLAST does a linear search, BLAT relies on [[k-mer]] indexing the database, and can thus often find seeds faster.<ref>{{Cite journal|last=Kent|first=W. James|date=2002-04-01|title=BLAT—The BLAST-Like Alignment Tool|journal=Genome Research|language=en|volume=12|issue=4|pages=656–664|doi=10.1101/gr.229202|issn=1088-9051|pmc=187518|pmid=11932250}}</ref> Another software alternative similar to BLAT is [[PatternHunter]].

Advances in sequencing technology in the late 2000s has made searching for very similar nucleotide matches an important problem. New alignment programs tailored for this use typically use [[Burrows–Wheeler transform|BWT]]-indexing of the target database (typically a genome). Input sequences can then be mapped very quickly, and output is typically in the form of a BAM file. Example alignment programs are [[Burrows-Wheeler Aligner|BWA]], [[Short Oligonucleotide Analysis Package|SOAP]], and [[Burrows-Wheeler Aligner#Short-Read Sequence Alignment|Bowtie]].

For protein identification, searching for known domains (for instance from [[Pfam]]) by matching with [[Hidden Markov Models]] is a popular alternative, such as [[HMMER]].

An alternative to BLAST for comparing two banks of sequences is PLAST. PLAST provides a high-performance general purpose bank to bank sequence similarity search tool relying on the PLAST<ref>{{cite journal |last1=Lavenier |first1=D. |year=2009|doi=10.1186/1471-2105-10-329 |pmid=19821978 |title=PLAST: parallel local alignment search tool for database comparison |journal=BMC Bioinformatics |volume=10 |pages=329 |last2=Lavenier |first2=Dominique |pmc=2770072 |doi-access=free }}</ref> and ORIS<ref>{{cite book|doi=10.1109/IPDPS.2008.4536172 |citeseerx=10.1.1.155.3633 |last=Lavenier |first=D. |year=2009 |chapter-url=http://www.hicomb.org/papers/HICOMB2008-01.pdf|chapter=Ordered index seed algorithm for intensive DNA sequence comparison |title=2008 IEEE International Symposium on Parallel and Distributed Processing |isbn=978-1-4244-1693-6 |pages=1–8 |s2cid=10804289 |url=https://hal.archives-ouvertes.fr/hal-00322696/file/lavenier_1569087275.pdf }}</ref> algorithms. Results of PLAST are very similar to BLAST, but PLAST is significantly faster and capable of comparing large sets of sequences with a small memory (i.e. RAM) footprint.

For applications in metagenomics, where the task is to compare billions of short DNA reads against tens of millions of protein references, DIAMOND<ref>{{Cite journal |author=Buchfink, Xie and Huson |title=Fast and sensitive protein alignment using DIAMOND |journal=Nature Methods |volume=12  |issue=1 |pages=59–60 |date= 2015 |doi=10.1038/nmeth.3176|pmid=25402007 |s2cid=5346781 }}</ref> runs at up to 20,000 times as fast as BLASTX, while maintaining a high level of sensitivity.

The open-source software MMseqs is an alternative to BLAST/PSI-BLAST, which improves on current search tools over the full range of speed-sensitivity trade-off, achieving sensitivities better than PSI-BLAST at more than 400 times its speed.<ref>{{Cite journal|last1=Steinegger|first1=Martin|last2=Soeding|first2=Johannes|date=2017-10-16|journal=Nature Biotechnology|volume=35|issue=11|pages=1026–1028|title=MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets|doi=10.1038/nbt.3988|pmid=29035372|hdl=11858/00-001M-0000-002E-1967-3|s2cid=402352|hdl-access=free}}</ref>

[[Optical computing]] approaches have been suggested as promising alternatives to the current electrical implementations. OptCAM is an example of such approaches and is shown to be faster than BLAST.<ref>{{Cite journal | doi=10.1002/jbio.201900227 |pmid = 31397961|title = OptCAM: An ultra-fast all-optical architecture for DNA variant discovery|journal = Journal of Biophotonics|pages = e201900227|year = 2020|last1 = Maleki|first1 = Ehsan|last2 = Koohi|first2 = Somayyeh|last3 = Kavehvash|first3 = Zahra|last4 = Mashaghi|first4 = Alireza|volume = 13|issue = 1|doi-access = free}}</ref>

=== Comparing BLAST and the Smith-Waterman Process ===
{{tone|date=December 2023}}
While both [[Smith–Waterman algorithm|Smith-Waterman]] and BLAST are used to find homologous sequences by searching and comparing a query sequence with those in the databases, they do have their differences.

Due to the fact that BLAST is based on a heuristic algorithm, the results received through BLAST will not include all the possible hits within the database. BLAST misses hard to find matches.

An alternative in order to find all the possible hits would be to use the Smith-Waterman algorithm. This method varies from the BLAST method in two areas, accuracy and speed. The Smith-Waterman option provides better accuracy, in that it finds matches that BLAST cannot, because it does not exclude any information. Therefore, it is necessary for remote homology. However, when compared to BLAST, it is more time consuming and requires large amounts of computing power and memory. However, advances have been made to speed up the Smith-Waterman search process dramatically. These advances include [[FPGA]] chips and [[SIMD]] technology.

For more complete results from BLAST, the settings can be changed from their default settings. The optimal settings for a given sequence, however, may vary. The settings one can change are E-Value, gap costs, filters, word size, and substitution matrix. 

Note, the algorithm used for BLAST was developed from the algorithm used for Smith-Waterman. BLAST employs an alignment which finds "local alignments between sequences by finding short matches and from these initial matches (local) alignments are created".<ref>{{cite web
   |url=http://www.montefiore.ulg.ac.be/~kvansteen/GBIO0009-1/ac20092010/Class4/BE-smith-waterman_versus_blast.pdf
   |title=Bioinformatics Explained: BLAST versus Smith-Waterman
   |date=4 July 2007}}</ref>

== BLAST output visualization ==

To help users interpreting BLAST results, different software is available. According to installation and use, analysis features and technology, here are some available tools:<ref>{{Cite journal |author=Neumann, Kumar and Shalchian-Tabrizi |title=BLAST output visualization in the new sequencing era|journal=Briefings in Bioinformatics|volume=15|issue=4|pages=484–503 |date=2014|doi=10.1093/bib/bbt009|pmid=23603091|doi-access=free}}</ref>

* NCBI BLAST service
* general BLAST output interpreters, GUI-based: JAMBLAST, Blast Viewer, BLASTGrabber
* integrated BLAST environments: PLAN, BlastStation-Free, [https://SequenceServer.com SequenceServer]
* BLAST output parsers: MuSeqBox, Zerg, BioParser, BLAST-Explorer, [https://SequenceServer.com SequenceServer]
* specialized BLAST-related tools: [https://www.wsi.uni-tuebingen.de/lehrstuehle/algorithms-in-bioinformatics/software/megan6/ MEGAN], BLAST2GENE, BOV, [http://tools.bat.infspire.org/circoletto/ Circoletto]

Example visualizations of BLAST results are shown in Figure 4 and 5. [[File:Seqserv-circos.png|thumb|Fig. 4 Circos-style visualization of BLAST results generated using [https://SequenceServer.com SequenceServer] software.]] [[File:Seqserv-length-dist.png|thumb|Fig. 5 Length distribution of BLAST hits generated using [https://SequenceServer.com SequenceServer] software showing that the query (a predicted gene product) is longer compared to similar database sequences.]]

== 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 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 [[Protein domain|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. Phylogenies based on BLAST alone are less reliable than other purpose-built [[Computational phylogenetics|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). NCBI has a "Magic-BLAST" tool built around BLAST for this purpose.<ref>{{cite web |title=NCBI Magic-BLAST |url=https://ncbi.github.io/magicblast/ |website=ncbi.github.io |access-date=16 May 2019}}</ref>

;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.

; Classifying taxonomy
: BLAST can use genetic sequences to compare multiple taxa against known taxonomical data. By doing this, it can provide a picture of the evolutionary relationships between various species (Fig.6). This is a useful way to identify [[Orphan gene|orphan genes]], since if the gene shows up in an organism outside of the ancestral lineage, then it wouldn't be classified as an orphan gene.[[File:Fig._6.png|thumb|Fig. 6 Output of a BLASTP search showing that a gene found in ''Bufo japonicus'' is also found in many other species of the frog (''Anura'') lineage. ]]
: Although this method is helpful, some more accurate options to find homologs would be through pairwise sequence alignment and [[multiple sequence alignment]].

== See also ==
{{Div col|colwidth=22em}}
* [[PSI Protein Classifier]]
* [[Needleman-Wunsch algorithm]]
* [[Smith-Waterman algorithm]]
* [[Sequence alignment]]
* [[Sequence alignment software]]
* [[Sequerome]]
* [[eTBLAST]]
{{div col end}}

== References ==
{{Reflist|2}}

== External links ==
{{Library resources box
 |onlinebooks=no
 |by=no
 |wikititle=Sequence alignment
 |label=Sequence alignment}}
* {{Official website|http://blast.ncbi.nlm.nih.gov/}}
* [https://ftp.ncbi.nlm.nih.gov/blast/executables/blast+/LATEST/ BLAST+ executables] — free source downloads

{{Bioinformatics}}
{{Authority control}}

[[Category:Bioinformatics algorithms]]
[[Category:Phylogenetics software]]
[[Category:Laboratory software]]
[[Category:Public-domain software]]
[[Category:Free bioinformatics software]]