.png){kind=icon}
返回
Efficient Genomic Interval Queries Using Augmented Range Trees
.png){kind=icon}
OA
AI
DOI：10.1038/s41598-019-41451-3.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Efficient large-scale annotation of genomic intervals is essential for personal genome interpretation in the realm of precision medicine. There are 13 possible relations between two intervals according to Allen's interval algebra. Conventional interval trees are routinely used to identify the genomic intervals satisfying a coarse relation with a query interval, but cannot support efficient query for more refined relations such as all Allen's relations. We design and implement a novel approach to address this unmet need. Through rewriting Allen's interval relations, we transform an interval query to a range query, then adapt and utilize the range trees for querying. We implement two types of range trees: a basic 2-dimensional range tree (2D-RT) and an augmented range tree with fractional cascading (RTFC) and compare them with the conventional interval tree (IT). Theoretical analysis shows that RTFC can achieve the best time complexity for interval queries regarding all Allen's relations among the three trees. We also perform comparative experiments on the efficiency of RTFC, 2D-RT and IT in querying noncoding element annotations in a large collection of personal genomes. Our experimental results show that 2D-RT is more efficient than IT for interval queries regarding most of Allen's relations, RTFC is even more efficient than 2D-RT. The results demonstrate that RTFC is an efficient data structure for querying large-scale datasets regarding Allen's relations between genomic intervals, such as those required by interpreting genome-wide variation in large populations.
Keyword:
ALGORITHM
ALIGNMENT
SEARCH
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.9
论文数:
28.2W
被引数:
83.5W
机构
引用论文
Defective number module or impaired access? Numerical magnitude processing in first graders with mathematical difficulties有缺陷的号码模块或受损的访问？数学困难的一年级学生的数值大小处理OAAI
OAAI分享收藏
Cation ordering and structural variations with temperature in MgAl2O4spinel: An X-ray single-crystal studyMgAl2O4 尖晶石中阳离子有序性和结构随温度的变化: x射线单晶研究
PREAI
分享收藏Holmium Laser Enucleation of Prostate: Outcome and Complications of Self-taught Learning Curve.png)
Urology
UrologyIF0
PREAI
分享收藏
查看更多内容