PubMed · 1591607
Statistical distance between texts and filtration methods in sequence comparison.
Abstract
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.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
P A Pevzner. 1992. Statistical distance between texts and filtration methods in sequence comparison.. https://doi.org/10.1093/bioinformatics%2F8.2.121. https://pubmed.health/record/pubmed%3A1591607/statistical-distance-between-texts-and-filtration-methods-in-sequence-comparison
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite PubMed Health by Indiciae: BibTeX · RIS.