Nested Containment List (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases.
BACKGROUND
The exponential growth of sequence databases poses a major challenge to bioinformatics tools for querying alignment and annotation databases. There is a pressing need for methods for finding overlapping sequence intervals that are highly scalable to database size, query interval size, result size and construction/updating of the interval database.


RESULTS
We have developed a new interval database representation, the Nested Containment List (NCList), whose query time is O(n + log N), where N is the database size and n is the size of the result set. In all cases tested, this query algorithm is 5-500-fold faster than other indexing methods tested in this study, such as MySQL multi-column indexing, MySQL binning and R-Tree indexing. We provide performance comparisons both in simulated datasets and real-world genome alignment databases, across a wide range of database sizes and query interval widths. We also present an in-place NCList construction algorithm that yields database construction times that are approximately 100-fold faster than other methods available. The NCList data structure appears to provide a useful foundation for highly scalable interval database applications.


BACKGROUND
NCList data structure is part of Pygr, a bioinformatics graph database library, available at http://sourceforge.net/projects/pygr
Alekseyenko
Alexander V
AV
Department of Biomathematics, David Geffen School of Medicine, University of California Los Angeles, Los Angeles, CA 90095-1570, USA.
Lee
Christopher J
CJ
D000465:Algorithms; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D003628:Database Management Systems; D030541:Databases, Genetic; D016247:Information Storage and Retrieval / Q000379:methods*; D008969:Molecular Sequence Data; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software