The Bit Vector Intersection Problem (Preliminary Version)

This paper introduces the bit vector intersection problem: given a large collection of sparse bit vectors, find all the pairs with at least t ones in common for a given input parameter t. The assumption is that the number of ones common to any two vectors is significantly less than t, except for an unknown set of O(n) pairs. This problem has important applications in DNA physical mapping, clustering, and searching for approximate dictionary matches. We present two randomized algorithms that solve this problem with high probability and in sub-quadratic expected time. One of these algorithms is based on a recursive tree-searching procedure, and the other on hashing. We analyze the tree scheme in terms of branching processes, while our analysis of the hashing scheme is based on Markov chains. Since both algorithms have similar asymptotic performance, we also examine experimentally their relative merits in practical situations. We conclude by showing that a fundamental problem arising in the Human Genome Project is captured by the bit vector intersection problem described above and hence can be solved by our algorithms.

Authors

• Richard M. Karp
• Orli Waarts
• Geoffrey Zweig

Keywords

• Cloning
• DNA
• Dictionaries
• Biological cells
• Fingerprint recognition
• Clustering algorithms
• Humans
• Genomics
• Bioinformatics
• Electronic mail
• High Probability
• Practical Situations
• Human Genome Project
• Relative Merits
• Branching Process
• Sufficiently Large
• Amount Of Work
• Error Probability
• Coordination Number
• Interval Length
• Hash Function
• Poisson Process
• Problem Of Finding
• Leaf Node
• High Overlap
• Small Constant
• Multiple Representations
• Pair Of Vectors
• Variant Of Problem
• Small Positive Value