of sequenced DNA. One way to find the source of a fragment is to search for it against a reference DNA sequence. A small number of mismatches (due to differences between the sequenced DNA and reference DNA, or errors) can be accounted for by dividing the fragment into smaller fragments—at least one subfragment is likely to match the reference DNA sequence. The matching requires constructing an inverted index of all substrings of a certain length from the reference DNA sequence. Since the human DNA contains more than 3 billion base pairs, and we need to store a DNA substring for every index and a 32-bit integer for index itself, the storage requirement for such an inverted index would probably be in the tens of gigabytes. Compression For historical reasons, inverted list compression and bitmap compression were developed as separate lines of research, and only later were recognized as solving essentially the same problem. See also Index (search engine) Reverse index Vector space model Bibliography References External links NIST's Dictionary of Algorithms and Data Structures: inverted index Managing Gigabytes for Java a free full-text search engine for large document collections written in Java. Lucene - Apache Lucene is a full-featured text search engine library written in Java. Sphinx Search - Open source high-performance, full-featured text search engine library used by craigslist and others employing an inverted index. Example implementations on Rosetta Code Caltech Large Scale Image Search Toolbox: a Matlab toolbox implementing Inverted File Bag-of-Words image search. Data management Search algorithms Database index techniques Substring indices