View source for CS-BLAST

{{Infobox software
| name                   = CS-BLAST
| developer              = Angermueller C, Biegert A, and Soeding J
| latest_release_version = 2.2.3
| latest_release_date    = {{release date|2013|12|07}}
| latest preview version = 1.1
| latest preview date    = {{Start date and age|2009|04|14}}
| programming language   = [[C++]]
| language               = English
| genre                  = [[Bioinformatics]] tool
| license                = [[GNU GPL| GNU GPL v3]]
| website                = http://wwwuser.gwdg.de/~compbiol/data/csblast/releases/, https://github.com/soedinglab/csblast
}}

'''CS-BLAST'''
<ref name="csdis">{{Cite journal  
| last1 = Angermüller 
| first1 = C. 
| last2 = Biegert 
| first2 = A. 
| last3 = Söding 
| first3 = J. 
| title = Discriminative modelling of context-specific amino acid substitution probabilities. 
| journal = Bioinformatics 
| volume = 28 
| issue = 24 
| pages = 3240–7
|date=Dec 2012 
| doi = 10.1093/bioinformatics/bts622 
| pmid = 23080114 | doi-access = free 
| hdl = 11858/00-001M-0000-0015-8D22-F 
| hdl-access = free 
}}</ref>
<ref name="csgen">{{Cite journal  
| last1 = Biegert 
| first1 = A. 
| last2 = Söding 
| first2 = J. 
| title = Sequence context-specific profiles for homology searching. 
| journal = Proc Natl Acad Sci U S A 
| volume = 106 
| issue = 10 
| pages = 3770–5 
|date=Mar 2009 
| doi = 10.1073/pnas.0810767106 
| pmid = 19234132
| pmc=2645910| bibcode = 2009PNAS..106.3770B 
| url = http://pubman.mpdl.mpg.de/pubman/item/escidoc:1944232/component/escidoc:1949958/1944232.pdf 
| doi-access = free 
}}</ref> 
<ref name="betterseqSD">{{cite web
|url=https://www.sciencedaily.com/releases/2009/02/090223131125.htm
|title=Better Sequence Searches Of Genes And Proteins Devised|date=Mar 7, 2009
|publisher=ScienceDaily 
|accessdate=2009-08-14}}
</ref> 
(Context-Specific BLAST) is a tool that searches a [[protein]] sequence that extends [[BLAST (biotechnology)|BLAST (Basic Local Alignment Search Tool)]],<ref>{{ cite journal
  |vauthors=Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ | title = Basic local alignment search tool.
  | journal = J Mol Biol
  | year =  1990 
  | volume = 215
  | issue = 3
  | pages = 403–410
  | pmid = 2231712
  | doi = 10.1016/S0022-2836(05)80360-2}}
</ref> using context-specific mutation probabilities. More specifically, CS-BLAST derives context-specific [[amino-acid]] similarities on each query sequence from short windows on the query sequences. Using CS-BLAST doubles sensitivity and significantly improves alignment quality without a loss of speed in comparison to BLAST. '''CSI-BLAST''' (Context-Specific Iterated BLAST) is the context-specific analog of [[PSI-BLAST]]<ref>{{cite journal
  |author1=Altschul SF |author2=Madden TL |author3=Schäffer AA |author4=Zhang J |author5=Zhang Z |author6=Miller W |author7=Lipman DJ. | title = Gapped BLAST and PSI-BLAST: a new generation of protein database search programs.
  | journal = Nucleic Acids Res
  | year = 1997
  | volume = 25
  | issue = 17
  | pages = 3389–3402
  | pmid = 9254694
  | doi = 10.1093/nar/25.17.3389
  | pmc = 146917
}}
</ref> (Position-Specific Iterated BLAST), which computes the mutation profile with substitution probabilities and mixes it with the query profile. CSI-BLAST (Context-Specific Iterated BLAST) is the context specific analog of PSI-BLAST (Position-Specific Iterated BLAST). Both of these programs are available as web-server and are available for free download.

== Background ==
Homology is the relationship between biological structures or sequences derived from a common ancestor. Homologous proteins (proteins who have common ancestry) are inferred from their sequence similarity. Inferring homologous relationships involves calculating scores of aligned pairs minus penalties for gaps. Aligning pairs of proteins identify regions of similarity indicating a relationship between the two, or more, proteins. In order to have a homologous relationship, the sum of scores over all the aligned pairs of amino acids or nucleotides must be sufficiently high [2]. Standard methods of sequence comparisons use a [[substitution matrix]] to accomplish this [4]. Similarities between amino acids or nucleotides are quantified in these substitution matrices. The substitution score (<math>S</math>) of amino acids <math>a</math> and <math>b</math> can we written as follows:

<math>S(a,b) = const \times \log \left ( \frac{P(a|b)}{P(a)} \right )</math>

where <math>P(a|b)</math> denotes the probability of amino acid <math>a</math> mutating into amino acid <math>b</math> [2]. In a large set of sequence alignments, counting the number of amino acids  as well as the number of aligned pairs <math>(a, b)</math> will allow you to derive the probabilities <math>P(a|b)</math> and <math>P(a)</math>.

Since protein sequences need to maintain a stable structure, a residue’s substitution probabilities are largely determined by the structural context of where it is found. As a result, substitution matrices are trained for structural contexts. Since context information is encoded in transition probabilities between states, mixing mutation probabilities from substitution matrices weighted for corresponding states achieves improved alignment qualities when compared to standard substitution matrices. CS-BLAST improves further upon this concept. The figure illustrates the sequence to sequence and profile to sequence equivalence with the alignment matrix. The query profile results from the artificial mutations in which the bar heights are proportional to the corresponding amino acid probabilities.

(A FIGURE NEEDS TO GO HERE THIS IS THE CAPTION) “Sequence search/alignment algorithms find the path that maximizes the sum of similarity scores (color-coded blue to red). Substitution matrix scores are equivalent to profile scores if the sequence profile (colored histogram) is generated from the query sequence by adding artificial  mutations with the substitution matrix pseudocount scheme. Histogram bar heights represent the fraction of amino acids in profile columns”.

== Performance ==
CS-BLAST greatly improves alignment quality over the entire range of sequence identities and especially for difficult alignments in comparison to regular BLAST and PSI-BLAST. PSI-BLAST (Position-Specific Iterated BLAST) runs at about the same speed per iteration as regular BLAST, but is able to detect weaker sequence similarities that are still biologically relevant. Alignment quality is based on alignment sensitivity and alignment precision.

=== Alignment Quality ===
Alignment sensitivity is measured by correctly comparing predicted alignments of residue pairs to the total number of possible alignable pairs. This is calculated with the fraction: (pairs correctly aligned)/(pairs structurally alignable)

Alignment precision is measured by the correctness of aligned residue pairs. This is calculated with the fraction: (pairs correctly aligned)/(pairs aligned)

=== Search Performance ===
The graph is the benchmark Biegert and Söding used to evaluate homology detection. The benchmark compares CS-BLAST to BLAST using true positives from the same superfamily versus false positive of pairs from different folds. (A GRAPH NEEDS TO GO HERE)

The other graph uses detects true positives (with a different scale than the previous graph) and false positives of PSI-BLAST and CSI-BLAST and compares the two for one to five iterations. (A DIFFERENT GRAPH NEEDS TO GO HERE)

CS-BLAST offers improved sensitivity and alignment quality in sequence comparison. Sequence searches with CS-BLAST are more than twice as sensitive as BLAST. It produces higher quality alignments and generates reliable E-values without a loss of speed. CS-BLAST detects 139% more homologous proteins at a cumulative error rate of 20%. At a 10% error rate, 138% more homologs are detected, and for the easiest cases at a 1% error rate, CS-BLAST was still 96% more effective than BLAST. Additionally, CS-BLAST in 2 iterations is more sensitive than 5 iterations of PSI-BLAST. About 15% more homologs were detected in comparison.

== Method ==
The CS-BLAST method derives similarities between sequence context-specific amino acids for 13 residue windows centered on each residue. CS-BLAST works by generating a sequence profile for a query sequence by using context-specific mutations and then jumpstarting a profile-to-sequence search method.

CS-BLAST starts by predicting the expected mutation probabilities for each position. For a certain residue, a sequence window of ten total surrounding residues is selected as seen in the image. Then, Biegert and Söding compared the sequence window to a library with thousands of context profiles. The library is generated by clustering a representative set of sequence profile windows. The actual predicting of mutation probabilities is achieved by weighted mixing of the central columns of the most similar context profiles. This aligns short profiles that are nonhomologous and ungapped which gives higher weight to better matching profiles, making them easier to detect. A sequence profile represents a multiple alignment of homologous sequences and describes what amino acids are likely to occur at each position in related sequences. With this method substitution matrices are unnecessary. In addition, there is no need for transition probabilities as a result of the fact that context information is encoded within the context profiles. This makes computation simpler and allows for runtime to be scaled linearly instead of quadratically.

The context specific mutation probability, the probability of observing a specific amino acid in a homologous sequence given a context, is calculated by a weighted mixing of the amino acids in the central columns of the most similar context profiles. The image illustrates the calculation of expected mutation probabilities for a specific residue at a certain position. As seen in the image, the library of context profiles all contribute based on similarity to the context specific sequence profile for the query sequence.

== Models  ==
In predicting substitution probabilities using only the amino acid’s local sequence context, you gain the advantage of not needing to know the structure of the query protein while still allowing for the detection of more homologous proteins than standard substitution matrices [4]. Bigert and Söding’s approach to predicting substitution probabilities was based on a generative model. In another paper in collaboration with Angermüller, they develop a discriminative machine learning method that improves prediction accuracy [2].

=== Generative Model ===
Given an observed variable <math>x</math> and a target variable <math>y</math>, a generative model defines the probabilities <math>P(x, y)</math> and <math> P(y)</math> separately. In order to predict the unobserved target variable, <math>y</math>,  Bayes’ theorem, <math>P(y|x) = \left ( \frac{P(x|y)P(y)}{[\textstyle \sum_{y}P(x|y)P(y) \displaystyle]} \right )</math>

is used. A generative model, as the name suggests, allows one to generate new data points <math>(x, y)</math>. The joint distribution is described as <math>P(x,y) = P(x|y)P(y)</math>. To train a generative model, the following equation is used to maximize the joint probability <math>\prod\left ( \frac{P(x_n,y_n)}{trainingData(x_n,y_n)} \right )</math>.

=== Discriminative Model ===
The discriminative model is a logistic regression maximum entropy classifier. With the discriminative model, the goal is to predict a context specific substitution probability given a query sequence. The discriminative approach for modeling substitution probabilities,<math>P(a|C_l)</math> where <math>C_l</math> describes a sequence of amino acids around position <math>l</math> of a sequence, is based on <math>K</math> context states. Context states are characterized by parameters emission weight (<math>v_k(a)</math>), bias weight (<math>\pi_k</math>), and context weight (<math>\lambda_k(j,a)</math>) [2]. Emission probabilities from a context state are given by the emission weights as follows for <math>d=1</math> to <math>20</math>: <math>P(a|k) = \left ( \frac{exp(v_k(a))}{\sum exp(v_k(a'))} \right )</math>

where <math>P(a|k)</math> is the emission probability and  is the context state. In the discriminative approach, probability for a context state <math>k</math> given context <math>C_l</math> is modeled directly by the exponential of an affine function of the context account profile where <math>C_l(j,a)</math> is the context count profile with a normalization constant <math>Z(C_l)</math> normalizes the probability to 1. This equation is as follows where the first summation takes <math>j=-d</math> to <math>d</math> and the second summation takes <math>a=1</math> to <math>20</math>: <math>P(k|C_l) = \left ( \frac{1}{Z(C_l)}exp(\pi_k + \pi\sum\sum \lambda_k(j,a)(C_l(j,a)) \right)</math>.

As with the generative model, target distribution is obtained by mixing the emission probabilities of each context state weighted by the similarity.

== Using CS-BLAST ==
The MPI Bioinformatics toolkit in an interactive website and service that allows anyone to do comprehensive and collaborative protein analysis with a variety of different tools including CS-BLAST as well as PSI-BLAST [1]. This tool allows for input of a protein and select options for you to customize your analysis. It also can forward the output to other tools as well.

==See also==
*[[Sequence alignment software]]
*[[Multiple sequence alignment]]
*[[Position-specific scoring matrix]]
*[[BLAST (biotechnology)| BLAST (Basic Local Alignment Search Tool)]]
*[[HH-suite|HH-suite software package]]

==References==
{{reflist}}[1] Alva, Vikram, Seung-Zin Nam, Johannes Söding, and Andrei N. Lupas. “The MPI Bioinformatics Toolkit as an Integrative Platform for Advanced Protein Sequence and Structure Analysis.” ''Nucleic Acids Research'' 44.Web server Issue (2016): W410-415. ''NCBI''. Web. 2 Nov. 2016.

[2] Angermüller, Christof, Andreas Biegert, and Johannes Söding. “Discriminative Modelling of Context-specific Amino Acid Substitution Properties” ''BIOINFORMATICS'' 28.24 (2012): 3240-247. ''Oxford Journals''. Web. 2 Nov. 2016.

[3] Astschul, Stephen F., et al. “Gapped BLAST and PSI-BLAST: A New Generation of Protein Database Search Programs.” ''Nucleic Acids Research'' 25.17 (1997): 3389-402. ''Oxford University Press.'' Print

[4] Bigert, A., and J. Söding. “Sequence Context-specific Profiles for Homology Searching.” ''Proceedings of the National Academy of Sciences'' 106.10 (2009): 3770-3775. PNAS. Web. 23 Oct. 2016.

==External links==
*[https://web.archive.org/web/20120804155807/http://toolkit.lmb.uni-muenchen.de/cs_blast CS-BLAST] &mdash; free server at University of Munich (LMU)
*[https://web.archive.org/web/20120628204442/http://toolkit.tuebingen.mpg.de/cs_blast CS-BLAST] &mdash; free server at Max-Planck Institute in Tuebingen
*[https://github.com/soedinglab/csblast CS-BLAST source code]

[[Category:Bioinformatics software]]
[[Category:Computational science]]