Nested containment list (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases
Nested containment list (NCList): a new algorithm for accelerating interval query of genome alignment and interval databases
复制标题
DOI：
10.1093/bioinformatics/btl647
复制
发表时间：
2007-06-01
期刊：
影响因子：
5.8
通讯作者：
Lee, Christopher J.
中科院分区：
文献类型：
--
作者：
Alekseyenko, Alexander V.;Lee, Christopher J.
动机：序列数据库的指数增长对用于查询比对和注释数据库的生物信息学工具提出了重大挑战。迫切需要找到对数据库大小、查询间隔大小、结果大小以及间隔数据库的构建/更新高度可扩展的重叠序列间隔的方法。结果：我们开发了一种新的间隔数据库表示形式，即嵌套包含列表（NCList），其查询时间为 O(n + log N)，其中 N 是数据库大小，n 是结果集的大小。在所有测试的情况下，该查询算法比本研究中测试的其他索引方法（例如 MySQL 多列索引、MySQL binning 和 R-Tree 索引）快 5-500 倍。我们提供模拟数据集和真实世界基因组比对数据库中的性能比较，涵盖各种数据库大小和查询间隔宽度。我们还提出了一种就地 NCList 构建算法，其数据库构建时间比其他可用方法快 100 倍。 NCList 数据结构似乎为高度可扩展的区间数据库应用程序提供了有用的基础。
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.