Efficient Genomic Interval Queries Using Augmented Range Trees

Abstract 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 t...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Chengsheng Mao, Alal Eran, Yuan Luo
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2019
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/534112f11b594c28b1ca2a7fbe538624
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:534112f11b594c28b1ca2a7fbe538624
record_format	dspace
spelling	oai:doaj.org-article:534112f11b594c28b1ca2a7fbe5386242021-12-02T15:09:28ZEfficient Genomic Interval Queries Using Augmented Range Trees10.1038/s41598-019-41451-32045-2322https://doaj.org/article/534112f11b594c28b1ca2a7fbe5386242019-03-01T00:00:00Zhttps://doi.org/10.1038/s41598-019-41451-3https://doaj.org/toc/2045-2322Abstract 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.Chengsheng MaoAlal EranYuan LuoNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 9, Iss 1, Pp 1-12 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Chengsheng Mao Alal Eran Yuan Luo Efficient Genomic Interval Queries Using Augmented Range Trees
description	Abstract 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.
format	article
author	Chengsheng Mao Alal Eran Yuan Luo
author_facet	Chengsheng Mao Alal Eran Yuan Luo
author_sort	Chengsheng Mao
title	Efficient Genomic Interval Queries Using Augmented Range Trees
title_short	Efficient Genomic Interval Queries Using Augmented Range Trees
title_full	Efficient Genomic Interval Queries Using Augmented Range Trees
title_fullStr	Efficient Genomic Interval Queries Using Augmented Range Trees
title_full_unstemmed	Efficient Genomic Interval Queries Using Augmented Range Trees
title_sort	efficient genomic interval queries using augmented range trees
publisher	Nature Portfolio
publishDate	2019
url	https://doaj.org/article/534112f11b594c28b1ca2a7fbe538624
work_keys_str_mv	AT chengshengmao efficientgenomicintervalqueriesusingaugmentedrangetrees AT alaleran efficientgenomicintervalqueriesusingaugmentedrangetrees AT yuanluo efficientgenomicintervalqueriesusingaugmentedrangetrees
_version_	1718387814594248704

Efficient Genomic Interval Queries Using Augmented Range Trees

Ejemplares similares