GBrowse ではフィーチャーの検索に R-Tree をつかって高速化

論文レビュー

ゲノムブラウザの一つ GBrowse ではフィーチャー（＝ゲノム配列中の部分配列につけられるアノテーション）の検索に特別なデータ構造をつかっているという話を聞いたので，論文を読んでみた．


フィーチャーの検索については GBrowse Internals セクションの Bio::DB::GFF Database に記述がある．以下引用：

The Bio::DB::GFF schema is optimized for queries that retrieve features by ID, by their type, or by the region of the genome they overlap. The last query is a challenge, because conventional relational database indexes do not handle positional range queries well. In SQL, the query to find all features that overlap the region on Chromosome 1 between bases 12,010,000 and 12,020,000 looks like this:

１番染色体の 12,010,000 塩基から 12,020,000 塩基の範囲に重なる全てのフィーチャーを取り出すには，以下のような SQL 文が想定できる．

 SELECT ref,start,end WHERE ref="Chr1" AND start <= 12020000 AND end >= 1201000;

If ref, start, and stop are indexed, an SQL optimizer will be able to eliminate half the rows in the feature table, on average, by eliminating all those rows that do not satisfy the criteria for start or end. However, the remainder of the table must then be inspected by a linear search, something that is particularly inefficient when searching for a small feature in the middle of a large chromosome or contig.

しかし，この SQL 文の WHERE 節では，短いフィーチャーが長いゲノムの中程にある場合の検索に非効率である，という．

The solution that we use is a special case of the R-tree algorithm (Guttman 1984) and was inspired by discussions with Richard Durbin (The Wellcome Trust Sanger Institute). In this optimization, the genome is divided into a hierarchical set of bins. At the top level are bins of size 10 Mb. This is followed by a tier of 1-Mb bins, another of 100 kb, and so on down to 1000 bp. The bins are assigned identifiers using floating point numbers in such a way that adjacent bins in the same tier have adjacent IDs, but bin IDs from different tiers do not overlap. As features are entered into the database, they are assigned to the smallest bin that will entirely contain them. A few very large features, such as entire chromosomes, end up in the large bins, but most features are allocated to the smaller ones.

この問題は Guttman の R-tree アルゴリズムの特別な場合をつかうことによって解決できる．

情報系の方に会う機会があったので，「R-tree アルゴリズムってどんなもの？」と聞いてみると，図形のなどで矩形範囲を指定して検索するときに使うという．一辺の長さがゼロの矩形とみてゲノムアノテーションを検索するのにつかっているということ．

R-tree アルゴリズムによるインデクスを GBrowse では，フィーチャーに bin という Float 値のカラムの追加で実現している．bin にはフィーチャーがちょうど収まる幅の bin の 値が格納される．bin の幅は 100 Mb，10 Mb，1 Mb，100 kb，10 kb，1 kb であり，ゲノムの端から番号がつけられる．幅と番号の組みを Float の整数部と少数部に埋め込む．例えば，長さが 1 kb 未満のフィーチャーは，bin = 1000.012010 というような値をもつ．ただし，二つの 1000 幅の bin に重なっているフィーチャーは bin = 10000.001201 のような値をもつ．すると，

The Bio::DB::GFF module automatically takes advantage of this binning scheme to optimize the queries. The example positional query given earlier now becomes the following:

 SELECT ref,start,end 
 WHERE ref = "Chrl" 
  AND (bin = 100000000.000000 
    OR bin = 10000000.000001 
    OR bin = 1000000.000012 
    OR bin = 100000.000120 
    OR bin between 10000.001201 and 10000.001202 
    OR bin between 1000.012010 and 1000.012020) 
  AND start <= 12010000 AND end >= 12020000;

このような bin の条件によって start <= 12010000 AND end >= 12020000 で評価されるデータの範囲が非常に限定される．

Although this query is more complex than the previous one, it executes much faster. On a 700-MHz Pentium III laptop, searching a 6-million-feature database took 17.4 sec with the unoptimized query, and 0.4 sec using the bin optimization, a performance increase of >400-fold. A version of this indexing scheme has also been adopted for use with the Human Genome Browser at UCSC (Kent et al. 2002).

一例として，600万レコードのフィーチャーのデータベースの問い合わせでは，400 倍以上の高速化の効果があったという．フィーチャーはとても簡単なデータ構造で表現できるが，ゲノムブラウザの表示という用途ですら，このような高速化をしないと実用に堪えられないということといえる．
同様なインデクス化は UCSC ゲノムブラウザーでも用いられているそうだ．

ちなみに，PostgreSQL ではインデクスのアクセスメソッドとして R-tree が選択できる．

また，1994 年に R-tree の改善版として Hilbert R-tree というアルゴリズムが提案されている．