Paper Info
Title
Nested Containment List (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases.
Abstract
Motivation: 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 similar to 100-fold faster than other methods available. The NCList data structure appears to provide a useful foundation for highly scalable interval database applications.
Year
DOI
Venue
2007
10.1093/bioinformatics/btl647
BIOINFORMATICS
Keywords
Field
DocType
data structure,exponential growth,indexation
Data structure,Data mining,Graph database,Database tuning,Result set,Computer science,View,Database design,Online aggregation,Bioinformatics,Scalability
Journal
Volume
Issue
ISSN
23
11
1367-4803
Citations 
PageRank 
References 
15
5.06
6
Authors
2
Name
Order
Citations
PageRank
Alexander V. Alekseyenko1379.10
Christopher Lee237540.57