A sequence similarity search algorithm based on a probabilistic interpretation of an alignment scoring system.
We present a probabilistic interpretation of local sequence alignment methods where the alignment scoring system (ASS) plays the role of a stochastic process defining a probability distribution over all sequence pairs. An explicit algorithms is given to compute the probability of two sequences given and ASS. Based on this definition, a modified version of the Smith-Waterman local similarity search algorithm has been devised, which assesses sequence relationships by log likelihood ratios. When tested on classical examples such as globins or G-protein-coupled receptors, the new method proved to be up to an order of magnitude more sensitive than the native Smith-Waterman algorithm.
Bucher
P
P
Swiss Institute for Experimental Cancer Research (ISREC), Epalinges, Switzerland. pbucxher@isrec-sun 1.unil.ch
Hofmann
K
K
D000465:Algorithms; D003574:Cytochrome c Group / Q000737:chemistry; D019204:GTP-Binding Proteins / Q000378:metabolism; D005914:Globins / Q000737:chemistry; D008958:Models, Molecular; D011956:Receptors, Cell Surface / Q000737:chemistry; D016415:Sequence Alignment / Q000379:methods*; D012984:Software; D018909:src Homology Domains
D003574:Cytochrome c Group; D011956:Receptors, Cell Surface; D005914:Globins; D019204:GTP-Binding Proteins