区間に関するクエリ

published: 2022/6/4 update: 2022/6/12

Table of Contents

TL;DR

Genomicなデータを扱っていると、区間に対するクエリを扱いたいことがよくある。

例えば、遺伝子領域と重複するピークやSNVを探したり、Open Chromatin Regionにあるヒストンマークを探したりするような利用方法が考えられる。

こういったクエリは、ナイーブに投げると になってしまう。 現実問題として、この計算量はあまりよろしくない。

解決策

CLI

CLIであるbedtoolsなどを使えばこういったクエリをある程度効率的に処理することができる。基本的には くらいになる。速度面で問題なければこういったツールを活用するのが良いと考えられる。

テスト済みのツールが使えるので定型的な処理をする分には安心感がある。また、bedなどのパーサーを書かなくていいので嬉しい。 一番メジャーかつできる処理が多いのはbedtools、高速なのはbedtkかなという感じを受ける。

自作

CLIで解決できない問題の場合は自分でコードを書くことになる。その場合に使えるようなデータ構造は当然ながら古くから研究されている。計算量のオーダーとしてはそこまで変化はないっぽいが、ベンチマークとか見るとだいぶ違うので最適化はされていっているらしい。

基本的なアイデアとしては、Interval TreeR-treeなどが使われている。

このあたりの基本的なデータ構造の実装としては、色々あるがrust-bioのデータ構造だったり、python実装だったりがある。 ALV木として実装されているので、自分で実装するよりこういったものを利用すると苦労は少なそう。

最近開発されているより高速・省メモリなデータ構造としては、以下のような物がある。ctrangesはbedtkで使用されているデータ構造。

NameLanguageGithub
Augmented Interval List (AIList)C, Pythonhttps://github.com/databio/AIList
cgrangesC, C++https://github.com/lh3/cgranges
Cache Oblivious Interval Trees (COITree)Rusthttps://github.com/dcjones/coitrees

Githubで公開されているベンチマーク的にはCOITreeが一番早い。個人的にはCほとんどわからないので普通にCOITree使いそう。

記事に間違い等ありましたら、お気軽に以下までご連絡ください

E-mail: illumination.k.27|gmail.com ("|" replaced to "@")

Twitter: @illuminationK

当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

Ofuse

Other Articles

Site Map

Table of Contents

    TL;DR

    解決策

      CLI

      自作


当HPを応援してくれる方は下のリンクからお布施をいただけると非常に励みになります。

Ofuse
Privacy Policy

Copyright © illumination-k 2020-2022.