Alai

Figure 11.2。 単純なDPアルゴリズムに対応する有限状態オートマトン。

このような定式化の利点は、最大スコア（または最小ペナルティ）を求めるための動的計画法がより一般的なタイプであり、したがって新しい状態や新しい遷移を加えることが容易であることである。 例えば、任意の数の遺伝子や部分的な遺伝子も許容する、より一般的な動的計画法のアルゴリズムの状態図を描くのは簡単であるが（図11.3）、書き下すのは大変である。 同様に上でスケッチしたフレームを考慮したアルゴリズムの状態図を図11.4に示す。

図11.3 図11.2のモデルに、配列がエクソンまたはイントロンの途中で開始または終了する任意の数の遺伝子および部分遺伝子を予測することを可能にする遷移を追加したものである。 遺伝子全体のフレームの一貫性を確保するモデル。 前の2つの図と同様に、点線は遺伝子間領域、破線はイントロン、全線はコーディング領域（エクソン）に対応する。

使用するスコアがログ確率またはログオッズであれば、有限状態オートマトンは本質的に隠れマルコフモデル（HMM）となり、これらは最近いくつかのグループにより遺伝子探索に導入されてきている。 前述した動的計画法との根本的な違いは、これらのモデルが完全な確率的モデルであることであり、これにはある種の利点がある。 その利点の1つは重み付け問題が容易なことである。

VEIL (Henderson et al., 1997) は遺伝子探索問題へのHMMの応用である。 このモデルではすべてのセンサーがHMMである。 エキソンモジュールは基本的に上述した一次非一様マルコフ連鎖である。 これは HMM に実装するには自然な順序である。なぜなら、そのとき非一様マルコフ連鎖の各条件付確率は、HMM のある状態から次の状態への遷移の確率に対応する。 一次モデルでは読み枠内のストップコドンを回避することはできないが、VEILでは巧妙な方法でいくつかの状態を追加し、ストップコドンの確率をゼロにすることができる。 スプライスサイトのセンサーも同様の方法で作られている。 次に、個々のモジュールは基本的に図11.2のように結合される（すなわち、フレームの一貫性は強制されない）。 結合されたモデルは一つの大きなHMMであり、すべての遷移は関連する確率を持つ。 これらの確率は最尤法によって学習データのセットから推定することができる。 モデルを結合する場合、これは本質的にデータセット内の異なるタイプの遷移の発生を数えることに帰着する。 そのため、個々のセンサーの暗黙の重み付けはあまり問題にならない。

最適な遺伝子構造を見つける方法は、上記のダイナミックプログラミングと精神的には似ているが、実際にはかなり違って見える。 これは動的計画法がすべてのサブモデルにおける個々の状態のレベルで行われるからで、VEILにはそのような状態が200以上ある。 このモデルは完全に確率的であるため、与えられたDNA配列に対して、任意の状態配列の確率を計算することができる。 この状態配列（パスと呼ばれる）がエクソンとイントロンの割り当てを決定する。 パスがエクソンモデルを通過すれば、その部分はエクソンとラベル付けされ、イントロンモデルを通過すればイントロンとラベル付けされ、といった具合である。 ビタビアルゴリズムと呼ばれる動的計画法では、与えられた配列に対してモデルを通る最も確率の高い経路を見つけ、そこから予測される遺伝子構造を導き出す（HMMの一般的な紹介はRabiner（1989）参照）。 十分な学習データがあり、遺伝子の統計的性質がこのようなモデルで記述できれば、パラメータの最尤推定は最適であることを示すことができる。 VEILの弱点は1次のエクソンモデルであり、おそらくコーディング領域の統計量をとらえることができず、他のほとんどの手法は4次か5次のモデルを使っている。

現在HMMgeneというHMMベースの遺伝子検出器が開発されている。 基本的な方法はVEILと同じであるが、標準的なHMMの方法論にいくつかの拡張を加えたもので、Krogh(1997)に記載されている。 最も重要なものの1つは、コーディング領域を1次鎖の代わりに4次非均質マルコフ鎖でモデル化することである。 これは、標準的なHMMが4つの基底（0次に対応）上の単純な無条件確率分布を持っているのに対し、モデルの状態における任意の次数のマルコフ連鎖を可能にする、標準HMM形式主義のほとんど自明な拡張によって行われます。 このモデルはフレームを考慮し、任意の数の遺伝子や部分遺伝子を予測できるので、モデルの全体構造は図11.4のようになり、図11.3のようにイントロンの開始と終了を可能にする遷移が追加されます。

すでに述べたように、最尤推定法はモデル構造が遺伝子の真の統計を記述できる場合によく働きます。 これは非常に理想的な仮定なので、HMMgeneでは条件付き最尤法という別の方法でパラメータを推定しています(Juang and Rabiner, 1991; Krogh, 1994)。 条件付き最大尤度は、学習セットに含まれるDNA配列の確率を最大化するのに対し、我々が関心を持つのはこれらの配列の遺伝子構造の確率を最大化することである。 このような最適化は、予測精度を最適化するGeneParserで用いられているものと概念的に類似しています。 また、HMMgene では遺伝子構造の予測にビタビアルゴリズムとは異なる動的計画法アルゴリズムを使用している。 これらの手法によりHMMgeneは高い性能を発揮している。

Genieも一般化HMMと呼ばれる確率的状態モデルの一例である（Kulp et al.） 図11.4は実際にGenieの状態構造であり、この図と図11.2は本質的にKulpら(1996)からコピーされたものである。 Genieでは、シグナルセンサー（スプライスサイト）とコンテンツセンサー（コーディングポテンシャル）はニューラルネットワークであり、これらのネットワークの出力は確率として解釈される。 この解釈には、センサーの重みのように働く確率パラメータを追加で推定する必要がある。 つまり、確率モデルとして定式化されてはいるが、重み付け問題はまだ偽装して現れているのである。 予測のためのアルゴリズムは前節の動的計画法とほぼ同じである。 Genieのバージョンでは、データベースの類似性もエクソンセンサーの一部として含まれている（Kulp et al.、1997）＜1888＞＜986＞標準HMMと比較して、一般化HMMの主な利点が2つある。 まず、個々のセンサーは、標準的なHMMではHMMのフレームワークによって制限されるのに対し、ニューラルネットワークなど、どのようなタイプでも良いということである。 第二に、（例えば符号化領域の）長さ分布を明示的に考慮できる。一方、HMMの自然な長さ分布は幾何分布であり、長さに応じて指数関数的に減衰する。 しかし、いくつかの状態を使用すれば、HMMでかなり高度な長さモデリングを行うことが可能である（Durbin et al.） 一方、HMMgeneのようなシステムの利点は、それが一つの統合されたモデルであり、最大の予測精度のために一度に最適化できることである。

一般化HMMに基づくもう一つの遺伝子探索機はGENSCAN(Burge and Karlin, 1997)である。 GENSCAN の状態構造と Genie や HMMgene の状態構造の主な違いは、GENSCAN が配列を両方向に同時にモデル化することである。 上述したような多くの遺伝子探索ツールでは、まず片方の鎖で遺伝子を予測し、次にもう片方の鎖で予測する。 両鎖を同時にモデル化することは GeneMark で非常にうまくいったが、GENSCAN でも同様の方法が実装されている。 この方法の利点は、おそらくヒトゲノムでは非常に稀である、2本の鎖に重複する遺伝子の予測を避けることができることである。 GENSCAN は HMMgene のように任意の数の遺伝子や部分遺伝子をモデル化することができる。 GENSCAN のセンサーは HMMgene で使用されているものと類似している。 例えば、coding センサーは 5 次非均質マルコフ連鎖である。 シグナルセンサーは基本的に位置依存の重み行列なので、これも HMMgene のものと非常に似ていますが、スプライスサイトモデルにはより高度な機能があります。 GENSCANはプロモーターや5’および3’UTRもモデル化しています

。