Statistical distance between texts and filtration methods in sequence comparison

Upon searching local similarities in long sequences, the necessity of a ‘rapid’ similarity search becomes acute. Quadratic complexity of dynamic programming algorithms forces the employment of filtration methods that allow elimination of the sequences with a low similarity level. The paper is devote...

Full description

Saved in:
Bibliographic Details
Published in:Bioinformatics 1992-04, Vol.8 (2), p.121-127
Main Author: PEVZNER, P. A
Format: Article
Language:English
Subjects:
Amino Acid Sequence
Base Sequence
Biological and medical sciences
DNA - genetics
Fundamental and applied biological sciences. Psychology
General aspects
Mathematics in biology. Statistical analysis. Models. Metrology. Data processing in biology (general aspects)
Models, Statistical
Proteins - genetics
Sequence Alignment - methods
Sequence Alignment - statistics & numerical data
Software
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Upon searching local similarities in long sequences, the necessity of a ‘rapid’ similarity search becomes acute. Quadratic complexity of dynamic programming algorithms forces the employment of filtration methods that allow elimination of the sequences with a low similarity level. The paper is devoted to the theoretical substantiations of the filtration method based on the statistical distance between texts. The notion of the filtration efficiency is introduced and the efficiency of several filters is estimated. It is shown that the efficiency of the statistical l-tuple filtration upon DNA database search is associated with a potential extension of the original four–letter alphabet and grows exponentially with increasing l. The formula that allows one to estimate the filtration parameters is presented.
ISSN:1367-4803
0266-7061
1460-2059
DOI:10.1093/bioinformatics/8.2.121