US 2014/0274752 A1 · SET MEMBERSHIP TESTERS FOR ALIGNING NUCLEIC ACID SAMPLES

Abstract

Disclosed are methods and tools for rapidly aligning reads to a reference sequence. These methods and tools employ Bloom filters or similar set membership testers to perform the alignment. The reads may be short sequences of nucleic acids or other biological molecules and the reference sequences may be sequences of genomes, chromosomes, etc. The Bloom filters include a collection of hash functions, a bit array, and associated logic for applying reads to the filter. Each filter, and there may be multiple of these used in a particular application, is used to determine whether an applied read is present in a reference sequence. Each Bloom filter is associated with a single reference sequence such as the sequence of a particular chromosome. In one example, chromosomal abundance is determined by aligning reads from a sequencer to multiple chromosomes, each having an associated Bloom filter or other set membership tester.

Claims27

Dependent claims

A method of aligning nucleic acid sequence reads to a reference sequence, the method comprising:

(a) receiving a first read comprising the sequence of a first nucleic acid segment from a sample;
(b) applying the first read to a Bloom filter to determine whether the first nucleic acid segment is found in a first reference sequence represented by the Bloom filter;
(c) receiving a second read comprising the sequence of a second nucleic acid segment from the sample;
and
(d) applying the second read to the Bloom filter to determine whether the second nucleic acid segment is found in the first reference sequence represented by the Bloom filter.

2 more elements

Dependencies are inferred from the claim text.

Set membership testers for aligning nucleic acid samples

Life of this patent

Set membership testers for aligning nucleic acid samples

Life of this patent

Abstract

Claims27