Gapped Local Similarity Search with Provable Guarantees
作者： Manikandan Narayanan , Richard M. Karp
DOI: 10.1007/978-3-540-30219-3_7
关键词:
摘要: We present a program qhash, based on q-gram filtration and high-dimensional search, to find gapped local similarities between two sequences. Our approach differs from past q-gram-based approaches in main aspects. step uses algorithms for sparse all-pairs problem, while studies use suffix-tree-like structures counters. works sequence-sequence mode, most ones (except QUASAR) work pattern-database mode.
springer.com
sci-hub.se 参考文章(36)
Piotr Indyk, Nearest Neighbors in High-Dimensional Spaces Handbook of Discrete and Computational Geometry, Second Edition. pp. 877- 892 ,(2004) , 10.1201/9781420035315.CH39
Piotr Indyk, Taher H. Haveliwala, Aristides Gionis, Scalable Techniques for Clustering the Web. WebDB (Informal Proceedings). pp. 129- 134 ,(2000)
Dan Gusfield, Algorithms on Strings, Trees, and Sequences: Suffix Trees and Their Uses ,(1997) , 10.1017/CBO9780511574931
Martin Tompa, Jeremy Daniel Buhler, Search algorithms for biosequences using random projection University of Washington. ,(2001)
Broňa Brejová, Daniel G. Brown, Tomáš Vinař, Vector Seeds: An Extension to Spaced Seeds Allows Substantial Improvements in Sensitivity and Specificity Lecture Notes in Computer Science. pp. 39- 54 ,(2003) , 10.1007/978-3-540-39763-2_4
S. Muthu Muthukrishnan, S. Cenk Ṣahinalp, Simple and Practical Sequence Nearest Neighbors with Block Operations combinatorial pattern matching. pp. 262- 278 ,(2002) , 10.1007/3-540-45452-7_22
Stefan Burkhardt, Juha Kärkkäinen, Better filtering with gapped q-grams combinatorial pattern matching. ,vol. 56, pp. 51- 70 ,(2001) , 10.1007/3-540-48194-X_6
Erkki Sutinen, Jorma Tarhio, On Using q-Gram Locations in Approximate String Matching european symposium on algorithms. pp. 327- 340 ,(1995) , 10.1007/3-540-60313-1_153
Edith Cohen, Size-Estimation Framework with Applications to Transitive Closure and Reachability Journal of Computer and System Sciences. ,vol. 55, pp. 441- 453 ,(1997) , 10.1006/JCSS.1997.1534
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher, Min-wise independent permutations (extended abstract) symposium on the theory of computing. pp. 327- 336 ,(1998) , 10.1145/276698.276781