(57)【特許請求の範囲】
【請求項１】
分離されたサンプルの複数の異なるレーンの位置を決定する方法であって、分離されたサンプルの各レーンが、媒質を通して流すことにより分離されたサンプルに対応するものであり、
コンピューター実行可能なロジックに複数の異なるレーンのデジタル画像を取得させることであって、前記デジタル画像が複数の異なるレーンに対応する複数の異なるレーン画像を含む画像であり、曲線の組中の複数の曲線の各々を前記複数の異なるレーン画像に適合させることであって、前記曲線の組中の各曲線が前記分離された各サンプルの流路に一致すること、
を含む前記方法。
【請求項２】
レーン画像の組中の各レーン画像が対応するバンド画像の組を含み、対応するバンド画像の組中の各バンドが分離されたサンプルにおけるバンドに対応し、曲線の組を適合させることがコンピューター実行可能なロジックに前記バンド画像の組から曲線の初期の組を生成させることを含み、前記曲線の初期の組は前記曲線の組に対応するものである、請求項１に記載の方法。
【請求項３】
曲線の組をレーン画像に適合させることが、コンピューター実行可能なロジックにバンド画像の組の各バンド画像について中心付近を同定させることを含む、請求項２に記載の方法。
【請求項４】
更に、各バンド画像の中心付近を同定する前にコンピューター実行可能なロジックにデジタル画像を圧縮させることを含み、前記画像圧縮がデジタル画像の非線形圧縮を実行することを含み、前記非線形圧縮は少なくとも部分的にはレーン画像の組の少なくとも幾つかのレーン画像の傾斜によって決定される、請求項３に記載の方法。
【請求項５】
曲線の組を適合させることが、コンピューター実行可能なロジックに、バンド画像の組の各バンドについての中心付近から間隔地図を決定させることを含み、前記間隔地図がデジタル画像の与えられた領域についての２つのレーン画像間の概算距離を示すものである、請求項３に記載の方法。
【請求項６】
曲線の初期の組を生成することが、
コンピューター実行可能なロジックに、デジタル画像の対応する領域について隣接するレーン画像間の概算距離に従って離間した、曲線の第1の組を同定させること；
コンピューター実行可能なロジックに前記曲線の第1の組をデジタル画像の中心部分に適合させること；および、
コンピューター実行可能なロジックに、前記デジタル画像の中心部分におけるレーン画像に充分に対応しない、前記曲線の第1の組中の一切の曲線を除去することにより、初期の曲線の組を生成させること、
を含む、請求項２に記載の方法。
【請求項７】
曲線の組が第1の曲線を含み、異なるレーン画像が第1のレーン画像を含み、前記第1の曲線は前記第１のレーン画像に適合されるべきものとして同定されたものであり、前記曲線の組を適合させることがコンピューター実行可能なロジックに前記第1の曲線を前記第1のレーン画像に適合させるための局所的最適化を行なわせることを含む、請求項１に記載の方法。
【請求項８】
レーン画像の組における各レーン画像が、対応するバンド画像の組を含み、曲線の組を適合させることが、コンピューター実行可能なロジックにデジタル画像中の領域についてバンド画像方向へ移動するための移動量を決定させることを含み、第1の曲線がコントロール点の組を含み、局所的最適化がコンピューター実行可能なロジックに前記コントロール点の組を前記第1の曲線に対応する前記デジタル画像の領域についての移動量に従って移動させることを含む、請求項７に記載の方法。
【請求項９】
曲線の組を適合させることが、コンピューター実行可能なロジックにデジタル画像の領域について隣接するレーン間の概算距離を決定させることを含み、局所的最適化がコンピューター実行可能なロジックに第1の曲線に対応する領域について決定された概算距離に従って、前記第1の曲線を移動させることを含む、請求項７に記載の方法。
【請求項１０】
第1の曲線を適合させることがコンピューター実行可能なロジックに、第1の曲線の部分における曲率限界の組に従って前記第1の曲線を移動させることを含む、請求項７に記載の方法。
【請求項１１】
第1の曲線を適合させることが、コンピューター実行可能なロジックに、局所的な最適化の際に第1の曲線の一部をランダムに摂動させることを含む、請求項７に記載の方法。
【請求項１２】
第1の曲線を適合させることが、コンピューター実行可能なロジックに、第1の曲線が曲線の組の隣接する曲線と交叉しないことを保証させるものである、請求項７に記載の方法。
【請求項１３】
曲線の組を適合させることが、コンピューター実行可能なロジックにグローバルな最適化を実行させて、曲線の組を対応するレーン画像に適合させることを含む、請求項１に記載の方法。
【請求項１４】
グローバルな最適化が、コンピューター実行可能なロジックに正規化則の組を用いて曲線の組を対応するレーン画像に適合させることを含む、請求項１３に記載の方法。
【請求項１５】
正規化則の組が、曲線の組の曲線間の正規化された間隔を規定するものである、請求項１４に記載の方法。
【請求項１６】
レーン画像の組が媒質中の対応するサンプルの流れに対応した流れ方向を有し、正規化則の組が第1の曲線を第1のレーン画像近くの領域におけるレーン画像の流れ方向に適合させることを含む、請求項１４に記載の方法。
【請求項１７】
グローバルな最適化が、コンピューター実行可能なロジックに、曲線の組を対応する種々のレーン画像に適合させるための所定の規則の組を使用させることを含む、請求項１３に記載の方法。
【請求項１８】
所定の規則の組が一般的に穏やかに湾曲した形状を得るために曲線の組を必要とする規則を含むものである、請求項１７に記載の方法。
【請求項１９】
サンプルの組中の各サンプルが、分離されたサンプル材料のバーコード様の外観を生じさせるサンプル材料を含み、所定の規則の組が、曲線の組の各曲線が単一のレーン画像に対応することを要求する規則を含むものである、請求項１７に記載の方法。
【請求項２０】
グローバルな最適化が、コンピューター実行可能なロジックに、曲線の組の対応する種々のレーン画像への一致誤差を低減させることを含む、請求項 １７に記載の方法。
【請求項２１】
一致誤差を低減させることが、
曲線の組中の少なくとも第1の曲線について、新たな暫定位置を生成すること；
前記新たな暫定位置を用いて、前記曲線の組の対応するレーン画像の組への一致が改善されたかどうかを決定すること；
一致が改善されたならば、前記第1の曲線の前記位置を前記新たな暫定位置に等しくすること；および、
一致が改善されなければ、「シミュレートされた動的アニーリング」によって修正されるある確率で変化を受け入れること、
を含む、請求項２０に記載の方法。
【請求項２２】
サンプルがDNAサンプル材料および蛍光色素を含み、媒質がゲルを含み、分離されたサンプルがバンドに分離されたDNAサンプル材料および蛍光色素を含む、請求項１に記載の方法。
【請求項２３】
サンプルがDNAサンプル材料および放射性物質を含み、媒質がゲルを含み、分離されたサンプルがバンドに分離されたDNAサンプル材料および放射性物質を含む、請求項１に記載の方法。
【請求項２４】
分離されたサンプルのレーンの組が薄層クロマトグラフィー工程に由来するものである、請求項１に記載の方法。
【請求項２５】
分離されたサンプルのレーンの組が、前記サンプルをサンプルの特性の組のうちの少なくとも一つの特性に基づいて分離することによって形成され、前記特性の組が分子サイズ、電荷、疎水性、親水性、および構造的剛性を含む、請求項１に記載の方法。
【請求項２６】
曲線の組における各曲線がスプライン曲線である、請求項１に記載の方法。
【請求項２７】
コンピューターにデジタル画像中の種々のレーン画像を同定させるためのコンピューター読取可能なプログラムコードを組み込んだコピューター利用可能な媒体であって、
前記各レーン画像が対応するバンド画像の組を含むものであり、前記コンピューター読取可能なプログラムコードが、
前記バンド画像の組の少なくともあるバンド画像の中心付近を同定するためのプログラムコード、
前記中心付近を用いて種々のレーン画像間の隣接レーン画像間の概算距離を決定するためのプログラムコード、
前記概算距離および、中心付近を用いて曲線の初期の組を決定するためのプログラムコードであって、前記曲線の初期の組が前記デジタル画像中の前記種々のレーン画像を位置決めする初期の試行を代表するものである、前記プログラムコード、および、
前記曲線の初期の組を前記種々のレーン画像に適合させて曲線の最終的な組を生成するためのプログラムコードであって、前記曲線の最終的な組が前記デジタル画像中の前記種々のレーン画像の位置を同定するものである、前記プログラムコード、
を含むプログラムコードである、前記コンピューター利用可能な媒体。
【請求項２８】
中心付近を使用するプログラムコードが更にニューラルネットワークのコンピュータープログラム実装を含み、前記ニューラルネットワークが入力デジタル画像に対して少なくともあるバンド画像の中心付近を同定するように調整されており、前記入力デジタル画像はバンド画像を含むものである、請求項２７に記載のコンピューター利用可能な媒体。
【請求項２９】
曲線の初期の組を適合させるプログラムコードがセル自動化プロセスおよびグローバルな最適化プロセスを実行するためのプログラムコードを含む、請求項２７に記載のコンピューター利用可能な媒体。
【請求項３０】
デジタル画像中で種々のレーン画像を追跡する方法であって、
コンピューター実行可能なロジックに少なくとも一つのサンプル画像を使用してパターン認識システムを調整することであって、前記サンプル画像が同定的特徴に対応するサンプル特徴を含む種々のレーン画像を含むものであること；
コンピューター実行可能なロジックに前記パターン認識システムを利用して種々のレーン画像中の同定的特徴を明らかにさせること；
コンピューター実行可能なロジックに前記同定的特徴を使用して前記種々のレーン画像に適合する近似的な曲線の組を決定させること；
コンピューター実行可能なロジックに、前記近似的な曲線の組を種々のレーン画像に適合させることにより前記近似的な曲線の組から曲線の組を生成させることであって、前記曲線の組が種々のレーン画像を追跡するものであること、
を含む、前記方法。
【請求項３１】
パターン認識システムが有限インパルス応答フィルターを含むニューラルネットワークを含み、前記有限インパルス応答フィルターが有限インパルス応答フィルターの応答係数の組を有しており、前記パターン認識システムを調整するために少なくとも一つのサンプル画像を使用することが、前記係数の組を設定することを含む、請求項３０に記載の方法。
【請求項３２】
同定的特徴がバンドの組を含み、レーン画像の組の各レーン画像が対応するバンドの組を含む、請求項３０に記載の方法。
【請求項３３】
サンプルの特徴がサンプルバンドの組を含み、各サンプルレーン画像が対応するサンプルバンドの組を含み、少なくとも前記サンプル画像を使用してパターン認識システムを調整することが前記サンプルバンドの組の少なくとも一つのサブセットの近似中心を同定することを含む、請求項３２に記載の方法。
【請求項３４】
曲線の組を生成することが近似的な曲線の組における各曲線についてセル自動化プロセスを実行することを含む、請求項３０に記載の方法。
【請求項３５】
曲線の組を生成することが一組の近似的な曲線の組における各曲線について局所的最適化を実行することを含む、請求項３０に記載の方法。
【請求項３６】
分離されたサンプルの種々のレーンを同定するためのシステムであって、
サンプルの組を分離されたサンプルの種々のレーンに分離させる装置；
分離されたサンプルの前記種々のレーンのデジタル画像を生成するための画像取込装置であって、前記デジタル画像がレーン画像の組を含み、レーン画像の組の各レーン画像が種々のレーンの一つに対応する前記装置；
前記デジタル画像を受け取り、曲線の組を種々のレーン画像に適合させるコンピューター実行可能ロジックを含むコンピューターシステム。
【請求項３７】
サンプルの組がDNA材料および蛍光色素を含む請求項３６に記載のシステム。
【請求項３８】
装置がゲル電気泳動DNAシーケンサーを含む、請求項３６に記載のシステム。
【発明の詳細な説明】
【０００１】
（発明の背景）
＜ａ．発明の分野＞
本発明は、材料を処理してそれらの構成成分を決定する分野に関する。特に、本発明は分離されたサンプル材料のレーンを自動的に同定することに関する。
【０００２】
＜ｂ．背景情報＞
ゲル電気泳動および他の分子的分離技術は、科学者が生物学的材料の分子配列を決定することを可能にする。例えば、ゲル電気泳動は所定の生物学的サンプルのＤＮＡ配列を決定するために使用される。ＤＮＡシーケンシングには、ＤＮＡを形成するヌクレオチドの配列決定が含まれる。
一般に、ゲル電気泳動には、ゲル材料をガラスプレート上に配置することが含まれる。このゲルは、プレートの一端に多くのウエルを有している。これらのウエルには、生物学的材料のサンプルおよび多くの色素が満たされる。光で励起されると、これらの色素は蛍光を発する。サンプルは色素と反応して、サンプルの部分コピーを形成する。夫々の部分コピーは、当該サンプルのＤＮＡ配列に由来する１−Ｎヌクレオチド（Ｎはサンプル中のヌクレオチドの数である）を含んでいる。従って、夫々の部分コピーは、当該コピーにおけるヌクレオチドの数に比例した質量を有する。ゲル電気泳動の目的は、部分コピーをそれらの質量の順序で分離することである。各部分コピーの末端における色素の種類は、当該部分コピーにおける最後のヌクレオチドの種類を指示する。色素の種類は、該色素の蛍光色から決定することができる。このガラスプレートを、電界の二つの極の間に配置する。磁界の影響下で、部分コピーはゲルを通して移動する。部分コピーはそれらの質量に応じた速度で移動する。従って、長い部分コピーは短い部分コピーよりも遅く移動する。部分コピーはそれらの質量、即ち長さに従って分離する。分離した部分コピーはバンドのレーンに分かれ、夫々のバンドは部分コピーの異なった長さに対応する。バンドの色を順に読取ることによって、ＤＮＡ配列を決定することができる。
【０００３】
上記レーンの位置を自動的に検出し、最終的にはゲルの画像におけるバンドの位置を検出する自動化されたコンピュータシステムが開発されている。このバンド情報は、学者にとって重要なものである。しかし、そのバンドを同定するために、レーンは正確に同定されなければならない。アルファ／ベータ追跡を用いるシステムの一例は、ＰＥアプライドバイオシステムズ社から入手可能なシーケンスアナリシスＴＭシステムである。しかし、これらシステムの多くは、幾つかのゲル画像についてはうまく働かない。この問題は該ゲルに生じたレーンの一貫しない形状から生じるものである。例えば、バンドのレーンは必ずしも直線的ではない。それらは、ゲルの一方の側または他方の側に向きを変える。
従来のシステムの一例は、アルファ／ベータ追跡と呼ばれる技術を用いていた。アルファ／ベータ追跡では、一つのレーンに二つのバンドがあると考えて、プログラムが開始するであろう。次いで該プログラムは、これら二つのバンド間の流れ方向を見出す。次に、該プログラムは、当該レーンにおける後続のバンドが存在する可能性のあるフィールドを予測する。次いで、ゲル画像の対応する領域が、バンドについてサーチされる。該プログラムは、その領域において、該レーンにおける次のバンドである可能性が最も高いバンドを選択する。当該レーンの末端に達するまで、このプロセスが繰り返される。一定の環境において、アルファ／ベータ追跡は間違ったバンドを選択するであろう。一度間違ったバンドが選択されると、正しいレーンは同定されないであろう。
【０００４】
アルファ／ベータ追跡は、遺伝子走査（例えばＳＴＲ分析）のようなゲル電気泳動の幾つかの応用で特に性能が劣る。遺伝子走査では、レーンはバンド間に大きなギャップを有しているかもしれない。（これに対して、ＤＮＡシーケンシングでは長いバンド列がレーン中に現れる。一般に、ＤＮＡ材料の部分コピーの可能な長さの夫々について、レーンの中にバンドが存在する）。遺伝子走査の適用においては、一つのレーン中のバンド間に多くの大きなギャップが存在する可能性がある。比較的少ない数のバンドはレーンの自動追跡を困難にするので、従来のシステムでは、レーンを同定するために人間の介入を必要とすることが多い。
レーン同定のために人間の介入を必要とする問題は、それがゲルを処理するコストを増大することであり、また当該システムのスループットが低下することである。人間の介在の必要性は、幾つかの状況においてネックになる可能性がある。また、ゲル当たりのレーン数が増大し、１日当たりのラン数が増大するに伴って問題は倍化する。
従って、ゲル中においてサンプルのレーンが存在する場所を決定するための、改善された自動化プロセスを得ることが望まれる。このプロセスは、現在入手可能なシステムよりも、より高いパーセンテージのレーンを認識すべきである。加えて、レーンを同定するために未だ人間が必要とされる場合には、該システムは、必要とされる介入が少なくなるように、改善されたインターフェースを提供すべきである。
【０００５】
（発明の概要）
ＤＮＡシーケンシングおよび断片解析から生じる画像中において、レーンを同定するためのシステムおよび方法が記載される。
本発明の一つの実施態様は、分離されたサンプルのレーン位置を決定するためのコンピュータで実行される方法を含む。各レーンは、媒質を通してサンプルを流すことにより分離されたサンプルに対応する。この方法は以下の要素を含む。幾つかのサンプルを媒質上に配置する。レーン中にサンプルを分離させる。レーンのデジタル画像を作成する。該レーン画像に幾つかの曲線を適合させる。各曲線は、分離されたサンプルから形成されたレーンに対応する。
レーンは分離されたサンプルのバンドを有する。これらバンドの画像を使用してレーンを同定することができる。例えば、幾つかの実施態様では、パターン認識システムがバンドの中心を見付ける。次いで、この中心情報を使用して、隣接するレーン間の概略距離およびレーンの流れの一般的方向を決定することができ、これは曲線をレーン画像に適合するために使用することができる。パターン認識システムを使用することは、それがレーン内のバンド位置のより良好な同定を助けるので、当該システム全体の特性を改善する補助となる。
【０００６】
幾つかの実施態様において、初期化プロセスは、コンピュータがレーンの数および位置について最初の推測を行うことを含んでいる。次いで、この最初の推測は、充分に良好なマッチングが得られるまで繰り返されて正確にされる。
幾つかの実施態様では、曲線をレーンに適合させるために、ローカルおよび／またはグローバルな最適化プロセスが使用される。局所的な最適化では、適切な移動量の定義を使用して、個々の曲線が繰返し調整される。この定義は、バンドの中心に対する当該曲線の相対的位置のような情報を使用することができる。該局所的な最適化は、コンピュータに良好な概略的適合性を迅速に与えることによって、レーン追跡システムの速度の改善を補助する。グローバルな最適化プロセスは、全てのレーンに対する全ての曲線の適合性を最大限にするように試みる。この適合性は、所定の領域に如何に近接したレーンが存在すべきか、およびレーンの一般的形状は何であるべきか等のルールによって決定される。このグローバルな最適化は、全ての曲線の良好な適合性を与えるのを補助する。重要なこととして、グローバルな最適化は（或る程度では局所的な最適化も）、媒質中のレーンの総合的な外観に関する情報を使用する。この総合的な情報は、他のシステムに比較してレーン追跡の結果を著しく改善する。
ここでの説明および図面には多くの詳細が含まれるが、本発明は請求項の範囲によって定義される。これらの請求項に見られる限定のみが本発明に適用される。
【０００７】
（発明の説明）
＜ａ．説明の概略＞
以下に、説明の仕方を記述する。最初に、定義の節では、この説明で使用する用語についての定義を提供する。次に、多くの節は本発明の種々の実施態様を記述する。一般に、或る節がフローチャート以外の図を説明する場合、該節は以下のフォーマットを有する。第一に、図の全ての要素が列記される。次に、これら要素のつながりを説明する。最後に、それらの相互作用および動作を説明する。幾つかの場合には、変形例または追加の実施態様を記載する。加えて、また別の節にも実施態様は記載される。最後の節は結論である。
【０００８】
＜ｂ．定義＞
この節では、ここでの記述に使用される幾つかの用語を説明する。
サンプル：  多くの分離技術を使用して分離され得る何等かののバイオ分子。
バイオ分子：  ＤＮＡ、ＲＮＡ、タンパク質などのような多くの生物学的分子の何れか。
曲線、スプライン関数（ｓｐｌｉｎｅ）、モデルレーン：  全て、ゲル中のレーンを同定および追跡するために使用するデータ構造を意味する。
レーン：  サンプルの分離によってゲル中に形成されたレーンを意味する。しかし、レーンは、レーンを同定および追跡するために使用されるデータ構造をも意味する。使用される文脈によって、この言葉がデータ構造またはゲル中の実際のレーンの何れを意味するかが明瞭になるであろう。
【０００９】
＜ｃ．発明の実施態様の概略＞
この節では、発明の実施態様の一例を説明する．一つの実施態様において、コンピュータはゲルのデジタル画像を調べ、ゲル中の分離されたＤＮＡのレーンを同定する。各レーンは、ＤＮＡの特定のフラグメントに対応する蛍光バンドを有している。コンピューターは最初にこのデジタル画像を解析し、バンドの中心を見つけ出す。これらのバンドの中心は、コンピュータがレーンを追跡するのを補助する。次いで、コンピュータは、レーンがどのように見えるかに関する一般的情報、およびレーン間の概略間隔および方向に関する情報を使用して、デジタル画像中のレーン画像に対して一組のスプライン関数を適合させる。
この実施態様を開発する上での一つの洞察は、従来のシステムでは使用されなかったレーンのグローバルな概観の中にかなりの量の情報が存在するということである。人間がゲル画像を試験するとき、人間は全てのレーンの一般的概観を使用して、特定のレーンを同定する。例えば、ゲルの一方の側における一群のレーンが一般的に左の方に向きを変えていれば、人間はこれを見てその情報を使用することにより、ゲルの当該領域におけるレーンを同定することができる。本発明のこの実施態様では、このタイプの全体の概観情報が使用される。
【００１０】
＜ｄ．システム図＞
この節では、本発明の一実施態様で使用し得るように、ゲルにおけるレーンを追跡するために使用できる図１のシステムを説明する。
図１には、シーケンシングシステム１９０が含まれている。このシーケンシングシステム１９０は、ゲル１００、スキャナー１１０、コンピュータ１２０、およびディスプレー装置１３０が含まれている。ゲル１００は、多くのサンプルウエル１０２、幾つかのレーン１０４、およびバンド１０６を含んでいる。コンピュータ１２０は、イメージングプログラム１２２および多くの他のプログラムを含んでいる。これら他のプログラムには、レーン追跡プログラム１２４が含まれる。ディスプレー装置１３０は、画像表示１３２を表示する。画像表示１２３には、レーン画像１３４、バンド画像１３６、スプライン関数１３８、およびコントロール点１３９が含まれる。
以下、図１の要素の間の相互接続を説明する。ゲル１００は、データ１０８をスキャナー１１０に与える。スキャナー１１０は、デジタル画像データ１１８をコンピュータ１２０に与える。イメージングプログラム１２２は、デジタル画像データ１１８の処理に使用される種々のプログラムを制御する。これらプログラムの一つには、レーン追跡プログラム１２４が含まれる。コンピュータは、ディスプレー装置１３０上での画像表示１３２のためのデータを生成する。
【００１１】
以下、これらの要素およびそれらの相互作用を更に詳細に説明する。ゲル１００は、ゲル材料でコートされたガラスプレートを表している。このゲル材料は、サンプルウエル１０２中のサンプル材料が移動する媒質を提供する。該サンプル材料は、ゲル１００を横切って印加される電界の結果として、ゲル１００を通って移動する。サンプル移動の結果として、レーン１０４のような多くの分離されたレーンが生じる。各レーンは、異なったサンプルウエル１０２に対応する。このレーンは、バンド１０６のような多くのバンドからなっている。
重要なこととして、サンプルウエル１０２の全てにサンプル材料がロードされるわけではない。また、分離の際に、全てのレーン１０４が直線になるわけではない。これは、レーンの自動検出を困難にする。
【００１２】
スキャナー１１０はゲル１００を走査して、ゲル１００の画像を捕捉する。スキャナーはこのアナログ画像データ１０８をデジタル画像データ１１８に変換する。デジタル画像データ１１８は、ゲル１００のデジタル画像を表す。
コンピュータ１２０は、多くのコンピュータシステムの何れかを代表する。コンピュータシステムの例には、アップルコンピュータ社から入手可能なＭａｃ ＯＳＴＭコンピュータシステム、ＰＣコンパチブルシステム、ユニックスワークステーションが含まれ、また一以上のコンピュータ（例えばコンピュータのネットワーク）を含むこともできる。重要なことは、コンピュータ１２０が画像を処理する能力を有することである。画像を処理するために、コンピュータはメモリーおよびプロセッサを含んでいる。
コンピュータ１２０により実行されるイメージングプログラム１２２は、典型的にはスキャナー１１０を制御して、スキャナー１１０にデジタル画像データを提供させる。コンピュータ１２０はまた、ゲル１００を横切って印加される電場を制御する。しかし、重要なことは、デジタル画像がイメージングプログラム１２２によって受けとられることである。このデジタル画像データ１１８は、バンドを伴ったレーンの画像を含んでいる。例えば、デジタル画像データ１１８は、レーン画像１３４を含んでいる。該レーン画像１３４は、バンド画像１３６を含む多くのバンドを含んでいる。
【００１３】
本発明の幾つかの実施態様において、イメージングプログラム１２２および／またはレーン追跡プログラム１２４は、コンピュータプログラム製品の中に含められてもよい。コンピュータプログラム製品は、フロッピーディスク、ＣＤ ＲＯＭ、ＤＶＤディスク、ｚｉｐディスク、ハードディスクまたは幾つかの他のコンピュータプログラム製品であることができる。
イメージングプログラム１２２は、レーン追跡プログラム１２４を制御する。レーン追跡プログラム１２４は、デジタル画像データ１１８中のレーン画像を追跡する。この例において、レーン追跡プログラム１２４は、多くのスプライン関数を種々のレーン画像に適合させている。画像表示１３２から分かるように、一般に、スプライン関数はレーン画像の中心を通って走る。例えば、スプライン関数１３８はレーン画像１３４の略中央を通って走る。これは、レーン画像が直線的なレーンでなくてもそうである。レーン画像は、画像表示１３２の底部において著しく左側に向かって曲がっている。重要なことに、レーン追跡プログラム１２４は、レーン画像が異常な形状であっても、レーン画像１３４に対してスプライン関数１３８を適合させることができた。
【００１４】
本発明の幾つかの実施態様において、イメージングプログラム１２２は、ユーザーがレーンの何等かの追跡を変更することを可能にするユーザーインターフェースを提供する。これは、ＤＮＡ配列の自動抽出がイメージングプログラム１２２中の他のプログラムによって達成される場合に有用である。ユーザーインターフェースはユーザーに対して、コントロール点１３９のような、レーン毎に多くのコントロール点を提示する。ユーザーは、このコントロール点の位置を変えることができる。これらのコントロール点は、対応するスプライン関数の形状を変化させる。例えば、コントロール点１３９の変更は、スプライン関数１３８の形状を変更するであろう。加えて、幾つかの実施態様において、コントロール点の位置の変化は、隣接するスプライン関数の形状に対応する変化を生じさせるであろう。これは、以下で説明するグローバル最適化プロセスを用いて行われる。このように、ユーザーは多くのスプライン関数の形状を自動的に変えることができる。
【００１５】
この説明の目的のために、幾つかの座標軸が定義される。図１は、操作方向およびレーンの流れ方向を示している。走査方向は、レーンの流れ方向に対して直交する。また、走査方向およびレーンの流れ方向によって定義される軸も定義される。走査方向は、走査方向に対して直交するものとして走査軸を定義する。同様に、レーン軸（またはチャンネル軸）は、レーンの流れ方向に対して直交するように定義される。
以下の節では、レーン画像を追跡するためのレーン追跡プログラムの使用を説明する。
【００１６】
＜ｅ．レーン追跡方法の例＞
図２は、図１のシステムにおいて使用できる、ゲル中のレーンを追跡する方法の一実施態様を示している。以下では、ゲル１００の中のＤＮＡ配列の読取りに関連して、レーン追跡プログラム１２４の使用を説明する。
ブロック２１０において、科学者はサンプルをウエル１０２に添加する。このサンプルはＤＮＡ材料および幾つかの蛍光色素を含んでいる。１９９６年５月３日に出願され、本発明の譲受人に譲渡された、発明者Ｌｉｎｄａ Ｇ． Ｌｅｅ、Ｓａｎｄｒａ Ｌ． Ｓｐｕｒｇｅｏｎ およびＢａｒｎｅｔｔ Ｒｏｓｅｎｂｌｕｍの「高い蛍光を伴うエネルギー移動色素」（Ｅｎｅｒｇｙ Ｔｒａｎｓｆｅｒ Ｄｙｅｓ Ｗｉｔｈ Ｅｎｈａｎｃｅｄ Ｆｌｕｏｒｅｓｃｅｎｃｅ）という名称の米国特許出願０８／６４２，３３０号は、他の用途の中でも特に、ゲル電気泳動に使用するための高い蛍光を伴う多くのエネルギー移動色素を記載している。ＤＮＡサンプル中の色素は、該色素がＤＮＡサンプルの部分コピーを作るように反応する。
ブロック２２０では、ゲル１００を横切って電場がかけられる。これは、サンプル（特にサンプルの部分コピー）を分離させる。これらサンプルはゲル１００を通って移動し、各レーンについて種々のバンドに分離する。幾つかの実施態様において、コンピュータ１２０は電場のかけ方を制御することができる。
【００１７】
ブロック２３０において、スキャナーはゲル１００の画像を捕捉する。これは、幾つかの方法で達成することができる。例えば、スキャナー１１０はレーンを励起させ、次いで前記色素からの何等かの蛍光を検知することができる。次いで、蛍光強度値および色がデジタル画像データ１１８として記録される。
イメージングプログラム１２２は、レーン追跡プログラム１２４を呼び出す。このレーン追跡プログラムは二つの主要な相を有する。第一の相は、デジタル画像データ１１８におけるバンドに対応した点を同定する。次の相は、スプライン関数適合技術を使用してバンドを結びつける。
ブロック２４０は、第一相を表している。ブロック２４０では、点の同定によって、デジタル画像データ１１８におけるバンドに対応した点が同定される。
「ドット連結」と称する第二の相は、ブロック２５０〜ブロック２７０を含んでいる。その仕事はレーンを追跡すること、即ち、第一の相で見つかった点に指示される通りにスプライン関数を適合させることである。これらのスプライン関数は、スプライン関数をレーンに対応するように動かす最適化プロセスによって、データ点に適合される。
【００１８】
ブロック２５０において、幾つかの初期化工程がとられる。最も注目に値するのは、走査軸に沿った画像の圧縮である。次にブロック２６０において、画像の中心部分（即ち中心走査）が追跡される。これは、ローカル最適化プロセスの連続的呼出しを用いたブートストラッププロセスを使用して達成される。ブートストラッププロセスについては以下で詳述する。局所的な最適化の夫々の呼出しによって、追加のレーンが追跡される。使用される局所的な最適化の一例は、以下で詳述する「セル自動化（ｃｅｌｌ ａｕｔｏｍａｔａ）」である。
中心走査が局所的な最適化によって追跡された後に、ブロック２７０でのグローバルな最適化によって全体の画像が追跡される。このグローバルな最適化は、メトロポリス・シミュレーテッド・アニーリング・アルゴリズム（Ｍｅｔｒｏｐｏｌｉｓ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ）の改変版である。このグローバルな最適化は２回呼び出される。それは、エポック当たり２４バッチで二つのエポックについて実行される。エポックおよびバッチは、グローバルな最適化によって使用されるシミュレートされたアニーリングプロセスに関連する。このプロセスについては、以下でさらに詳細に説明する。最初の実行の結果が特に良好であると評価されたら、次いで、非常に低いエネルギーで、１０バッチの一つのエポックについてグローバルな最適化が実行される。或いは、高い開始温度で三つのエポックが実施される。
このグローバルな最適化の後、スプライン関数適合の結果をディスプレー装置１３０上に表示することができる。
【００１９】
＜ｆ．バンド中心を同定する方法の例＞
図３は、バンドの概略中心を同定する方法の一つの実施態様を示している。この例示方法の最終目的は、レーン追跡プログラム１２４に対して、デジタル画像データ１１８におけるバンド中心の位置を与えることである。加えて、この技術により同定された何れかのバンドに関連した信頼性値が生成される。
点同定プロセスは、全体の曲線適合プロセスにおいて重要である。その理由は、点同定プロセスが、デジタル画像データ１１８におけるバンド中心位置の優れた指標を提供するからである。これは、曲線適合プロセスの信頼性を改善する。
従来のシステムは、バンドの中心として、単純にバンドの最も高い強度値を採っていた。このアプローチに伴う問題は、近隣バンドの最高点が隣接バンドの中に滲み出すことである。アルファ／ベータ追跡技術の使用は、隣接レーンの追跡を開始させる。図３の技術を使用することにより、当該システムは、隣接バンドが特定のバンドの中に滲み出しているバンドを含む、多くの異なったタイプのバンドの中心を同定することができる。
【００２０】
一般に、図３の技術は、パターン認識システムの使用を含んでいる。このパターン認識システムは、サンプル映像におけるバンド中心を同定するように調整されて（ｔｒａｉｎｅｄ）いる。この調整技術は、デジタル画像データ１１８と共に逆伝播プロセスに供給される。その結果は、バンドの中心が存在すると思われる位置に非ゼロ強度値を伴っている画像である。夫々の非ゼロ点値の強度値は、特定の点がバンドの中心を表すことの信頼性のレベルを示す。
次に、図３の実施態様について更に詳細に説明する。
ブロック３３０において、プログラマーは、一位以上のサンプル画像におけるバンドの中心を同定する。これは、多くのサンプルゲル画像を撮り且つバンドの中心をこれら画像の中に位置付ける人間によって行われる。レーン追跡プログラム１２４は、この調整情報の足蹠を維持する。
【００２１】
ブロック３４０において、レーン追跡プログラム１２４は、デジタル画像データ１１８から局在した十字線ベクトルを発生させる。局在した十字線ベクトルを発生させることは公知の技術である。一般に、それは強度値を伴う二次元画像を、強度値を伴う一次元画像に変換することを含んでいる。
ブロック３５０では、ブロック３３０で発生したサンプル同定データと共に、十字線ベクトルが逆伝播プログラム（ｂａｃｋ ｐｒｏｐａｇａｔｉｏｎ ｐｒｏｇｒａｍ）に提供される。逆伝播は、上記で述べたように、画像認識に使用される公知の技術である。
【００２２】
逆伝播プログラム３６０の一部として、有限のインパルス応答フィルターが使用される。この有限インパルス応答フィルターの係数は、サンプル同定データから誘導される。十字線ベクトルは、有限インパルス応答フィルターへの入力として使用される。
ブロック３７０において、有限インパルス応答フィルターの出力は、デジタル画像データ１１８と同じサイズの画像である。この新たな画像は、逆伝播プロセスによってバンド中心が存在すると決定された場所の強度値を含んでいる。これらピクセルの強度値は、バンド中心が所定の位置に存在することの信頼性レベルを示している。図４は、バンド中心を同定するように調整された逆伝播プロセスの出力を示している。図４は、図１のそれと同様の画像表示４３２を含んでいる。図４において、画像は反時計方向に９０°回転されている。この画像表示４３２は、レーン画像１３４に対応するレーン画像４３４を含んでいる。バンド中心指標４３６は、画像表示４３２における画素に対応する。この画素の強度は、バンド中心がバンド中心指標４３６の位置に存在する可能性に対応する。
【００２３】
なお、このシステムの幾つかの実施態様では、調整データは更新されない。即ち、ニューラルネットは調整情報を永続的にプログラムされている。しかし、他の実施態様では、ユーザーは調整情報を置き換えることができ、或いは調整情報を追加することができる。これは、幾つかの実施態様が特定のマシンの特異的な側面を補償することを可能にする。
以下の節では、バンドの中心が連結されるレーン追跡プロセスの第二の相について説明する。この相への入力は、ピーク点座標および点同定相によって発生された信頼性値である。第二の相は、レーンに対してスプライン関数が適合される多段階プロセスを使用して、デジタル画像データ１１８におけるレーンを追跡する。
【００２４】
＜ｇ．ドットの連結＞
先に説明した通り、点同定相によって作成された点をスプライン関数が追跡するこの相は、「ドット連結」と称される。このドットは、点、従ってバンド中心を意味する。幾つかの実施態様において、このドット連結相は、キャットマルスプライン（Ｃａｔｍｕｌｌ ｓｐｌｉｎｅｓ）を用いてレーンを特異的にモデル化する。モデル化されたレーンは、ゲル中のレーン１０４を追跡する。このモデルレーンは、スプラインまたは追跡レーンとも称される。
全てのスプライン関数と同様に、キャットマルスプラインは、連結点（コントロール点とも称する）について規定される。キャットマルスプラインの連結点は、均一に離間している。キャットマルスプラインのスプライン断片は、該断片の点に近接した四つの連続した連結点によって定義される。即ち、四つの連続した一組の連結点は、必然的に、四つの連結点の間の三つのスペースを示唆し、また、キャットマルスプラインの定義によって、四つの連結点は中間スペースについてのスプライン断片を特異的に定義する。
夫々のモデルレーンは一組のキャットマルスプライン点によって定義され、ここでは、四つの連結点の異なる各連続群が、上記で説明したようにしてもう一つのキャットマルスプラインの断片を定義する。全てのモデルレーンは、同じ走査位置にそれらの連結点を有する。レーン追跡プログラム１２４は、チャンネル軸におけるスプライン関数の連結点を操作してスプライン関数を移動させる。
【００２５】
＜ｈ．レーンの初期化方法の例＞
図５は、初期化ブロック２５０の実施態様を示している。この初期化ブロックは、スプライン関数適合を実行するためにシステムを初期化する。
ｉ）圧縮
ブロック５１０において、デジタル画像データ１１８は圧縮される。この圧縮された画像は、下記で説明するように、走査軸に沿って圧縮されるデジタル画像データ１１８に対応する。走査軸は、走査の方向に対して直交する方向である（即ち、チャンネルの方向、従ってレーンの方向に沿っている）。チャンネル（またはレーン）軸は、レーン１０４の流れに対して直交する方向に対応した軸である。デジタル画像データ１１８は非常に大きい可能性があるので、この圧縮プロセスは重要である。ブロック５１０の出力は、元の３０００〜４０００走査に比較して、６０から９０走査に過ぎない画像である。圧縮は、圧縮画像における各画素を、一つのチャンネル内における多数の走査の全体に亘る最大値に設定することにより得られる。これは、点画像に固有の過剰解像度を利用し、また圧縮された解像度においてさえ、レーンの傾斜が小さいという事実を利用する。圧縮は、同時にコンピュータに対する時間および費用の要件を低減しながら、標準の画像処理走査（例えば、流れフィールドを計算するのに使用する小さなコンボリューション）に適した、遥かに小さく且つ密な画像を生じる。以下、このプロセスを更に詳細に説明する。
【００２６】
圧縮は、ゲル１００が使用されるプロセスの種類に応じて異なった方法で行われる。シーケンシング画像については、得られた画像におけるレーンがバンド中心間の所定の最大傾斜を超えないように、動的に確認された圧縮比で画像の一部が圧縮される。遺伝子走査については、デジタル画像データ１１８は、画像の異なった部分についてのアプリオリな知識によって決定された所定の圧縮比率に関して圧縮される。動的に圧縮された画像は、元のデジタル画像データ１１８より２００倍も小さいことが多い一方、同時に傾斜の緩いレーンを有する。また、ピーク密度は大きく増大する。非動的に圧縮された画像は、典型的には、デジタル画像データ１１８よりも１００倍小さいであろう。この増大したピーク密度は、コンピュータ１２０の遥かに少ないメモリーを使用して、レーン追跡プログラム１２４の効果および速度を大きく高める。
【００２７】
動的に圧縮された画像は、ゲル１００の底部に対応する領域を除いて、デジタル画像データ１１８の何処ででも顕著に圧縮されている。この底部領域は「プライマーピーク」に対応する。該プライマーピークは、サンプル材料の非常に短いコピーに対応する。
上記で述べたように、遺伝子走査については所定の圧縮比が使用される。幾つかの実施態様において、遺伝子走査はおよそ１００：１の圧縮比を有する。最初の４００走査線（プライマーピークの近傍）については、２０：１の圧縮比が用いられる。次の４００走査線については５０：１の圧縮比が用いられる。残りの走査線については、１３０：１の圧縮比が用いられる。遺伝子走査画像が５０００の走査線を有するならば、圧縮された画像はおよそ６１の圧縮カラムを有するであろう（８２：１の圧縮比）。
【００２８】
以下、動的圧縮技術について説明する。
デジタル画像データ１１８に対してどの程度の圧縮を行うことができるかを決定するために、２段階の最小圧縮が実行される。最初に、点座標の走査軸部分が１０倍で圧縮され、整数画素座標に切り捨てされる。対応する二値画像は、更なる圧縮がレーンを合体させないように、垂直方向（即ち走査の方向）に細められる。次いで、この画像からの点が再度圧縮され、倍率は４倍である。これは全体で４０倍の圧縮を与える。
４０倍に圧縮された画像の各１２．５走査長の断片（断片は全てのレーンを横切って伸びる）について、該断片における何れかのレーン断面の最大傾斜が決定される。
【００２９】
傾斜の決定は以下の工程を含んでいる。
最初に、現在の１２．５（圧縮）走査断片に対応した、全体の４０倍圧縮画像のサブ画像を抽出することにより、断片画像を作成する。この新しい断片は、コンピュータ処理のために少数の走査パディングを含んでいる。
次に、この断片画像にラベルを付す。ラベリングは、非常に接近しているがバラバラであるレーン断片を一緒に結合するための、閉鎖操作および細線化操作の組合せを含んでいる。また、これには、レーンが一つの画素の太さ未満であることを確認することが含まれる。次に、標準の二値画像ラベリングアルゴリズムの単純化された変形を使用することにより、画像の各断片は分離した実体として容易に同定することができる。この単純化されたラベリングアルゴリズムは、一般的なラベリングのために一般的に充分ではないであろうが、画像は分岐のない単純な一画素の太さの線を含むように処理されているので、ここでの目的のためには充分である。
【００３０】
ラベルされた画像は、各レーンの画素に対して下記のことを示す値を割当てることにより作成される。第一は、当該画素が、その断片におけるレーン断片について最初のものであるかどうかである。第二に、該レーン断片上にある次の画素（もしあれば）がどこに存在するかである。得られたラベルされた断片における各レーン断片は、その傾斜を生じるようにトラバースされ、これは終点座標を用いてコンピュータ処理される。
最大レーン傾斜は、６走査長を越えるレーン断片のみを考慮し、次いで残りのレーン断片の傾斜の９５％をとることによって得られる。非常に短い断片は、本来的に信頼できないので考慮されない。９５％傾斜 ｖｓ．最大傾斜を使用して、可能な逸脱を回避する。
こうして、最大傾斜が決定される。
【００３１】
次に、夫々の断片について、レーン追跡プログラム１２４は最大許容圧縮を計算する。これは、４０倍圧縮因子に対する現在の傾斜の差因子 ｖｓ． 所定の最大許容傾斜を計算することによって行われる。次いで、この因子に４０を乗じて、該断片についての最大許容圧縮を得る。例えば、最大許容可能傾斜は１であり、断片は０．１の関連傾斜を有すると仮定する。元の圧縮は４０倍であるから、最大許容傾斜は４０倍圧縮された傾斜よりも１０倍大きく、計算された許容圧縮は１０の４０倍で４００に等しい。
最後に、ブロック５１０の最後で次のことが行われる。元の画像における夫々の断片について、レーン追跡プログラム１２４は画素の圧縮された座標を計算する。これは、画素の対応する断片の圧縮因子で座標を除算し、次いで切り捨てることにより行われる。圧縮された画像は、圧縮座標に対応する二値画像によって形成される。
図６は、圧縮ブロック５１０の出力の例を示している。バンド中心指標６８６は、バンド中心指標６３６を有するレーン画像６３４の一部に対応している。画像表示４３２は、点同定プロセスの出力を示している。画像表示６３２は、圧縮プロセスの出力を示している。
【００３２】
ｉｉ）間隔地図（ｓｐａｃｅ ｍａｐ）の生成
ブロック５２０において、間隔地図が生成される。この間隔地図は画像中のあらゆるところにおいて隣接するレーン間の距離を示す。この間隔地図は、レーンが実際に存在する場所ではなく可能なレーンが存在し得る場所を示すから、これら隣接レーンは実際には仮想の隣接レーンである。従って、間隔地図は、画像の如何なる領域についても、レーンが隣接レーンからどれだけ離間しているかについての一般的なアイデアを、レーン追跡プログラムに提供する。
以下、間隔地図を生成するプロセスを説明する。先ず、圧縮された画像が縦方向に細線化される。画像が圧縮された後、該画像は典型的には、ピーク点を表す画素の小さな縦線（即ち、１走査内）を含んでいる。この小さな縦線の中心は、元の走査における対応のバンド中心の良好な推定値であり、縦線の圧縮された走査に位置する。縦方向の細線化は、画素のブロックを一つの中心画素で置き換える。
【００３３】
次に、夫々の走査内におけるレーンを横切って各ピークから次のピークまでの距離を決定することにより、差分画像が作成される。この差分画像から、全体の画像のレーン間隔のための公称値として一つの数が計算される。これは、次の技術を用いて行われる。差分画像における合理的な値のヒストグラム内で、最初の顕著なピーク、即ち第一モードが見出される。該画像におけるピークは、ヒストグラムの一次微分および二次微分を分析することによって見出される。このアルゴリズムは、ガウスフィルターのガウシアンおよびラプラシアンを用いて一次微分および二次微分をそれぞれ決定することにより、ノイズ耐性にされる。
次いで、差分画像の次の領域を分析して、各領域の特異的距離を決定する。また、各領域の間隔についての信頼性も計算される。この信頼性は、差分画像によって、画像領域の間隔がグローバルな公称値またはグローバルな公称値の２倍に近いことが示されるときにのみ確実である。当該領域における点の数もまた、各信頼性値における要因である。信頼性値および間隔値は、全体として、信頼性地図（ｃｏｎｆｉｄｅｎｃｅ ｍａｐ）および間隔地図にそれぞれ対応する。
間隔地図および信頼性地図は、反復成長プロセスを使用することにより、可能な範囲で間隔地図を完成するために使用される。以下、反復成長プロセスの一例を説明する。間隔地図には、入力間隔地図の高い信頼性値のみに対応する値が記入される。これら画素のエッジ部に接する画素は、高い信頼性で、それらの近隣と一致した間隔値を有するかどうかを見るために分析される。これらの境界画素がこのような間隔値を有していれば、これらの画素は、間隔地図においてそれらの対応する値に設定される。このプロセスは、新たな一致した画素が見出されるまで反復される。
反復成長プロセスは、間隔地図を完成させないかもしれない。その場合には、この画像から局所的な間隔を推定するための充分な情報が存在しない間隔マップ領域が存在する。これらの孔は、計算された間隔値の間を補間することによって埋められる。これは三段階プロセスとして行うことができ、夫々の段階は一次元補間である。第一段階は一つの軸に沿って補間する。第二段階は、もう一つの軸と共に第一段階の結果に沿って補間する。第三段階は、第一の軸と共に第二段階の結果を補間する。
【００３４】
間隔地図には、埋められていない追加の領域（例えば、埋められた領域の縁に沿って）が存在することがある。これらの領域は補外によって埋められる。先ず、間隔地図は一つの方向に補外され、次いで得られた結果は他の方向に補外される。一つの実施態様では、補外の軸に沿ってエッジ部の値をコピーすることにより補外が行われる。
最後に、間隔地図は画像サイズに補間され、または元に引き伸ばされる。
【００３５】
ｉｉｉ）中心の初期化
次に、初期化プロセスのサブ相には、レーン追跡プログラム１２４の中心初期化が含まれる。この中心初期化は二つの目的を達成する。第一の目的は、追跡すべきレーン１０４を見つけることである。第二の目的は、デジタル画像データ１１８の中心について、これらレーン１０４を追跡することである。レーン１０４は、ゲル１００の中央部分では直線であるが、両端に向かって湾曲する傾向がある。中心初期化はこの情報を用いて、レーン１０４が何処にあるかを同定し、これらレーに対する一次近似を行う。
【００３６】
一般に、中心初期化相は間隔地図を使用して、デジタル画像データ１１８における可能な各レーンのためのモデルレーン（スプライン関数）を作成する。なお、如何なるピークも示さない領域であってもモデルレーンを有することができ、その位置は存在するピークおよび間隔地図に対して決定される。
次いで、中心初期化相は局所的な最適化プロセスの多重呼出しを使用する。この局所的な最適化は、画像の中心におけるレーンの追跡を補助する。局所的な最適化はレーンを追跡して、ピーク、間隔地図および多くの正規化制約を適合させる。次いで、多重ローカル最適化呼出しの出力を分析して、どのモデルレーンが如何なる点にも対応しないように見えるかを決定する。次いで、これらの「幽霊レーン」は更なる考察から除外される。得られたレーンは、サンプル材料を含んだサンプルウエル１０２から生じたレーンに対応するように思える。
【００３７】
今度は、中心初期化について更に詳細に説明する。中心初期化はブートストラッププロセスである。第一のステップは、最も密度の高い走査、即ち、細線化された圧縮画像の中心部分に殆どのピークを有する走査を決定することである。この点において、走査の各ピークでロードされたレーンが存在すると仮定される。細線化された圧縮画像における一つの画素は、元の画像の３０〜２００画素に対応し得ることを想起されたい。従って、このブートストラッププロセスは典型的には殆どのレーンを見つけ出す。
【００３８】
ｉｖ）流れ地図（Ｆｌｏｗ Ｍａｐ）
中心初期化の第一のステップの一つは、流れ地図または流れフィールドを生成することである。レーン追跡プログラム１２４は、この流れ地図を使用して、画像の中心部分における残りの走査のたの初期モデルレーンを補外する。流れフィールドはブロック５３０において生成される。流れフィールドは、圧縮画像における何れかの点で発生するトラックの予想軌跡の地図または画像である。
以下、流れフィールドが如何にして計算されるかを説明する。画像の各画素において、レーン追跡プログラム１２４は、当該画素における最大応答を与える指向性フィルターを見出す。最大応答値および方向は、初期流れフィールド地図における複素数としてコード化される。次に、このサブステップについて更に詳細に説明する。
【００３９】
指向性フィルターは、その主要な軸がフィルターの方向（または方位）にある楕円ガウシアンである。指向性フィルターで画像をフィルターすると一つの画像が生じ、その画素は、入力された画像が当該特定のフィルターの「方向に進行している」量に対応する。不連続な増分において、入力された画像を或る範囲の方位に関してフィルターすると、全ての個々の方位に対する各ピクセルの応答である一連の画像を生じる。最大画像は、夫々の画素について、方位付けされた一連の画像において位置画素の値が最大である画像を見付けることによって形成することができる。各画素について、それが由来する一連の画像の方位に関する最大値は、初期流れフィールド地図における複素数としてコードすることができる。これは、以下に述べるステップを使用して実行することができる：先ず、次の方位のための入力画像をフィルターする。次いで、全ての先に計算されたフィルターの蓄積された最大結果の画像を用いて、次の最大画像の結果を、新たな結果の画像の要素的最大として計算する。
【００４０】
次に、当該プロセスの頑強性を増大させるために、画像はその核を用いて巻き付けることにより平滑化され、圧縮される。この圧縮は、或る範囲の画素について、夫々の軸に沿って最大値をとることにより行われる。次いで、該画像は拡大されてそのオリジナルサイズ双線形補間に戻され、最終の流れフィールド地図を生じる。
次に、ブロック５４０において、スプライン関数の初期セットが配置される。次いで、下記で説明するように、これらのスプライン関数は局所的な最適化プロセスに提供される。なお、これらの初期スプライン関数は如何なるアンカーレーンも含んでいない。アンカーレーンが導入されれば、典型的には、局所的な最適化プロセスは遥かに効果的である。しかし、この初期セットの曲線について、局所的な最適化プロセスはアンカーレーンなしで開始するように変更される。アンカーレーンは、適正に配置されたモデルレーン（良好に適合するスプライン関数）と仮定されるモデルレーンである。アンカーレーンは、明らかに、局所的な最適化処理の際の移動から防止される。他のレーンの移動はアンカーレーンに対するものである。ブロック５４０については、以下で更に詳細に説明する。
【００４１】
ブロック５５０では、全ての良好に適合するスプライン関数を固定するために、初期セットのスプライン関数に対して局所的な最適化プロセスが反復して行われる。ブロック５５０は次のようにして実行される。
何れのスプライン関数がそれに近接した点と良く適合するかを見るために、スプライン関数が分析される。次いで、「良好に適合するスプライン関数」は、連像的な良好に適合するスプライン関数のブロックにグループ化される。良好に適合するスプライン関数のブロックは、トラップされた仮想スプライン関数を含むことができる。仮想スプライン関数は、間隔地図によって示唆された存在しないモデルレーンである。これらの良好に適合するスプライン関数の連続的ブロックの最大のものは、次の局所的な最適化に対するアンカーとして使用される。この局所的な最適化は、次いで、アンカースプライン関数であるその所定のスプライン関数のみについて実行される。残りのスプライン関数は、間隔地図を使用してアンカースプライン関数から補外することにより、局所的な最適化にって初期化される。
【００４２】
この局所的な最適化により出力されたスプライン関数は、良好に適合するスプライン関数を見付けるために再度分析される。これらの良好に適合するスプライン関数は、第一の最適化から出力された良好に適合するスプライン関数と併合される。如何なる重複も除去される。次に、併合された良好に適合するスプライン関数の組は、良好に適合するスプライン関数の新しい最大の連続した組を見付けるために分析される。次いで、これらの連続した組の良好に適合するスプライン関数は、次の局所的な最適化ステップへの入力として使用される。次に、これらのステップは、該スプライン関数の全てがアンカースプライン関数の一部になるまで繰り返される。
最後に、非連続的なアンカースプライン関数が局所的な最適化プロセスに与えられるように、局所的な最適化が実施される。
ブロック５６０では、画像中の点に良く適合しない如何なるスプライン関数も除去される。即ち、何れかの点に最も近接したスプライン関数でない如何なるスプライン関数も除去される。ブロック５１０〜ブロック５６０の結果は、対応する画像レーンに関連した一組のスプライン関数である。
【００４３】
＜ｉ．局所的な最適化方法の例＞
図７は、レーン画像に対する第一の組のスプライン関数の局所的な最適化を行なう方法の一実施態様を示している。局所的な最適化は、レーン１０４に対するスプライン関数の初期適合を行う。グローバルな最適化に伴う問題は、それは非常に良く働くが、集中的なコンピュータ処理であることにある。局所的な最適化は、グローバルな最適化のような多くの処理を必要としないが、グローバルな最適化のための良好な出発点を提供する。
局所的な最適化において、レーン追跡プログラム１２４はそれ自身の動作を制御する各スプライン関数を有する。一般に、これらのスプライン関数はレーン間の間隔がほぼ同じのままであるように、それら自身を移動させようとする。スプライン関数は、スプライン関数がバンド中心に対応するデータ点上にあり、且つ二つのデータ点の間にはないように移動しようとする。これらのスプライン関数はまた、それらが流れ地図に従うように移動しようとする。以下では、局所的な最適化プロセスについて、セル自動化プロセスの説明と共に更に詳細に説明する。
【００４４】
一般に、セル自動化は、対応するスプライン関数が構造的制約および正規化制約に指令された安定なパターンに収斂し易いように、スプライン関数結合点を整列させるための反復的な自己組織化アルゴリズムである。レーン追跡プログラム１２４のために、構造的制約はピーク点（圧縮画像に含まれている）および間隔地図を含んでいる。正規化制約は、レーン曲率および連続的なレーン形状間の相違の最小化を含んでいる。夫々の反復において、夫々の結合スプライン関数について凝集値が決定される。この凝集値は、夫々の制約の移動値によって与えられる全ての制約を満たすために、結合点が移動すべき場所に対応する。一般に、これらの制約は全部が完全に同時に満たされるものではないから、最終的な凝集移動値は制約を解除しないであろう。しかし、夫々の結合点を移動させることにより、凝集移動値の小さな画分は、一般にその次の移動が更に小さくなる（幾つかの合計の大きさの意味で）システムを形成し易い。このプロセスの反復適用を通して、当該プロセスは、或る任意の大きい反復回数で最早移動しないシステムに収斂する傾向がある。
【００４５】
レーン追跡プログラム１２４において、この結合点はキャットマル結合点（Ｃａｔｍｕｌｌ ｔｉｅ ｐｏｉｎｔ）であり、従って定義により均一に離間される。これはコンピュータ処理を更に効率的にするが、必要とされるものではない。更に、結合点の移動はチャンネル軸に限定される。これはアルゴリズムを大幅に単純化するが、これもまた必要とされるものではない。
次に、以下の段落では図７の実施態様を詳細に説明する。セル自動化は、その入力として、幾つかの数のアンカーレーンおよび圧縮画像を有している。この出力はアンカーレーンのより大きな組である。
ブロック７１０において、レーン追跡プログラム１２４は、アンカーレーン間にモデルレーンの開始組を生成する。これは、アンカーレーンの回りに「完全櫛歯モデル」を作成することによって行われる。完全櫛歯モデルは、ゲル１００においてアンカーレーンの間にロードされた全てのレーンに対応する。
【００４６】
ブロック７１０における第一のステップは、アンカーレーンの間で、間隔地図を使用して「（モデル）レーン距離」を計算することである。レーン距離は、完全櫛歯モデルを仮定して、一つの与えられたレーンが次の所定のレーンからどれだけ多くのレーンだけ離れているかの目安である。例えば、これらアンカーレーン間のレーンにサンプルがロードされなければ、二以上の対応するレーン距離は、これら二つのアンカーレーン間に少なくとも一つの「幽霊（ｐｈａｎｔｏｍ）」（即ち未ロードの）レーンを示すことが期待されるであろう。この距離は中心走査について採用される。
【００４７】
次に、レーン追跡プログラム１２４は、必要に応じ線形補間によって、何れか二つのアンカーレーン間の幽霊レーンについてモデルレーンを作成する。
次に、レーン追跡プログラム１２３は、潜在的なレーン、幽霊レーン等についての追加のモデルレーンを補外によって作成する。これらの追加のモデルレーンは、必要に応じてアンカーレーンの前または後にくる。この新たなレーンは、最も近接したアンカーレーンがシフトされた複製である。モデルレーンは、これらが圧縮画像における全てのピークを結合するまで追加される。
ブロック７２０では、重力地図（ｇｒａｖｉｔｙ ｍａｐ）が作成される。重力地図は、走査に対して、何れかのピーク（バンドの中心）に向けてスプライン関数を移動させる基本移動を与える。
重力地図は、エッジ検出カーネルを用いて圧縮画像をコンボリューションすることにより形成される。即ち、このカーネルは一次元ガウスフィルターである。該フィルターはチャンネル軸に沿って適用される。ガウスフィルターの半分は打消され、中心値は０である。この結果は、ピークの正の側に負の値をもった重力地図およびその逆である。これらの移動値は、ピークの何れの側でもピークに向かってスプライン関数を描く。
【００４８】
次に、ブロック７３０からブロック７９０は局所的な最適化が達成されるまで繰り返される。
ライン追跡プログラム１２４は、重力地図から基本スプライン関数結合点移動を決定する。この基本スプライン関数結合点移動は、ブロック７３０〜ブロック７５０およびブロック７６０の一部を含む。
ブロック７３０において、ライン追跡プログラム１２４は、点適合制約による移動部分を決定する。次に、これを詳細に説明する。先ず、スプライン地図（ｓｐｌｉｎｅ ｍａｐ）が生成される。このスプライン地図は、各走査でのモデルレーンの位置を含む。次に、レーン追跡プログラム１２４は点適合移動値を生成する。この点適合移動値は、先の結合点と次の結合点との間にある点のレーン上での各走査について、重力移動の加重合計をとることによって、夫々の結合点について決定される。重みはガウス関数によって与えられる。このガウス関数は、次の結合点までの距離である標準偏差を有し、結合点上に中心を有し、またその範囲はモデルレーン上での先の結合点から次の結合点までである。このようにして、一定の走査上の点適合移動は、走査を制限する結合点の両方に影響する。
【００４９】
次に、ブロック７４０において、レーン追跡プログラム１２４は間隔制約による移動部分を決定する。今度はこれについて説明する。レーン追跡プログラム１２３は、先ず間隔地図により与えられるモデルレーン間の予想距離と、実際の距離との間の不一致を決定する。この不一致を決定するために、結合点地図（ｖｓ． 他の実施例で使用されるスプライン関数の或る分析形態、またはより微細なサンプリング）が用いられる。実際の距離は、結合点のチャンネル座標とその一つ上との単純な差を取ることにより計算される。これは、一つ少ない列をもった差行列、次いで結合点行列を生じる（Ｎレーンの間にはＮ−１の間隔があるから）。この間隔地図の距離は、該第一のＮ−１レーンにおける各結合点について、間隔地図の中にインデックスすることによって計算される。従って、この行列は実際の差行列と同じサイズである。他の与えられた間隔不一致行列から１を差し引く。間隔地図における固有の不正確さを考慮して、不一致行列における夫々の間隔移動の大きさは１だけ減少される。従って、１以下の不一致は不一致がないとみなす。
【００５０】
間隔不一致行列が計算されたら、それを結合点のための基本間隔制約移動に翻訳することが必要とされる。夫々の間隔不一致要素は、隣接するレーン上での結合点の対に対応する。不一致を減少するために、頂部または底部の何れの結合点を移動させるかの決定は、種々の因子および内容に依存する。セル自動化が所定のアンカーレーンを伴わずに（固定されたレーンなしで）呼び出されると、選択は２０反復毎に変化する。セル自動化がアンカーレーンと共に呼び出されて、頂部の結合点がアンカーレーンの上のレーンについて移動されると、底部の結合点は底部アンカーレーンについて移動し、またアンカーレーンの間の何れかのレーンについて、選択は２０反復毎に交互になるであろう。
次に、ブロック７５０において、レーン追跡プログラム１２４は、曲率制約に関する移動の一部を決定する。これは以下のようにして行われる。先ず、レーン追跡プログラム１２４は、レーン上の結合点の位置を、それ自身および該結合点の二つの隣接点の平均として計算することにより、理想的な正規化された軌道を決定する。再度、これは幾つかの実施態様における結合点行列を使用して行われるのに対して、他の実施態様においては、分析形態またはより精細なサンプリングのスプライン関数が用いられる。次に、レーン追跡プログラム１２４は、理想的な正規化された軌道から現在の位置を差し引くことにより、曲率制約移動を決定する。
【００５１】
次に、正規化および間隔地図制約に起因する移動は、点（ピーク）に近接しない結合点に対して低い重要度を与えるように調節される。これは、ピーク点制約に起因した正規化された移動を用い、それらの移動の一部を減衰することにより達成される。
ブロック７６０では、ブロック７３０〜ブロック７５０において発生された部分移動の加重合計から、基本スプライン関数結合移動が決定される。加えて、結合点が間隔地図によって与えられる移動になるように、レーン追跡プログラム１２４は極端に近接した結合点に対応する移動部分をオーバーライドする。また、ブロック７６０において、新たな一組の結合点座標を発生させるために、０．２の合計移動が加えられる。
ブロック７７０において、時折、レーン追跡プログラムは幾つかのランダムノイズで結合点座標を摂動する。これは、悪いコンフィギュレーションでの「膠着（スタック）」になり得る場合に、レーン追跡プログラム１２４を補助する。
ブロック７８０では、何れかのスプライン関数が交差するときには元の組の結合点座標が使用される。そうでなければ、新たな移動座標が使用される。
ブロック７９０では、ブロック７２０からブロック７８０の充分な反復が行われたかどうかを決定するために試験が行われる。幾つかの実施態様では、この繰返しの際に１０００回の反復が行われ、或いは６００回の反復が行われる。
上記プロセスの４回の反復の後に、グローバルな最適化が行われる。
【００５２】
＜ｊ．グローバルな最適化の例＞
図８は、一組のスプライン関数のレーン画像への適合のグローバルな最適化を行う方法の実施態様を示している。
グローバルな最適化プロセスは、入力として、セル自動化からの一組のスプライン関数を取り、次いでこれらをレーン画像に適合させる。スプライン関数の入力組に関して、スプライン関数の組は全て現存のレーン画像を追跡すると仮定する。グローバルな最適化は、セル自動化適合、並びに先に追跡されなかった画像の領域（例えばレーンの頂部および底部）の適合性を更に精密にする。
グローバルな最適化は、トライアル状態を生じさせるために、一以上のスプライン関数の一部を揺動する（ｓｈａｋｉｎｇ）プロセスとして考えることができる。スプライン関数の揺動された部分の結果は、当該適合の良好さを決定するためにコスト関数によって評価される。適合の良好さは、スプライン関数がより良くレーン画像に適合する場所に対応する。この適合がより良好（即ち、より低エネルギー／より低コスト）であれば、該グローバルな最適化プロセスは常にトライアル状態を（標準のシミュレートされたアニーリングとして）許容するであろう。適合が悪く、シミュレートされた動的アニーリングプロセスが画像の揺動された部分について乏しい適合性を示すときは、時折、シミュレートされたアニーリング許容関数によって与えられるように、トライアル状態はとにかく許容される。
【００５３】
グローバルな最適化のコストは、構造的コストならびに正規化コストの組合せとして計算される。構造的コストは、ピーク点に対するモデルレーンの適合（圧縮ゲル画像に含まれるものとして）および間隔地図（これは、圧縮画像において、次のレーンがもう一つのレーンから何れか所定の点にあるべき距離の誘導された見積もりを含む）を含む。正規化コストは、レーン曲率、レーン類似性およびレーン傾斜変化を含む。
グローバルな最適化は、シミュレートされたアニーリングと称するアルゴリズムに基づいている。即ち、幾つかの実施態様は「メトロポリスアルゴリズム」の変形を用いる。シミュレートされたアニーリングは、グローバルな最適化の一つの方法である。所定の組のパラメータ（例えばキャットマルスプライン結合点によって定義されるモデルレーン）、および該パラメータ値に関連した誤差を測定するコスト（誤差）関数によって定義されるシステムが与えられると、誤差表面（ｅｒｒｏｒ ｓｕｒｆａｃｅ）が定義される（誤差関数のサポートの上に）。この誤差表面は多くの局所的な極小値を含む可能性があるが、当該表面の何処かに最小値が存在する。この最小値を持った誤差表面上の点は、グローバルな最小値と称する。殆どの最適化アルゴリズムは局所的な最小化を行う。即ち、幾つかの初期誤差を定義するパラメータの幾つかの初期組が与えられると、局所的な最小化アルゴリズムは常に、その対応する誤差が単調に減少するシーケンスを形成する一連のパラメータ変化を生じるであろう。それは、誤差表面上の現在の位置から、丁度小さな近くの丘を超えたところにある更に良好なまたはグローバルな最小値を得る能力を有していない。（これは、丘を昇ることはより高い誤差への移行であり、単調に減少する誤差シーケンスに違反するからである）。グローバルな最小値を見出す試みとは異なり、最も近い局所的な最小値を見出すことは、迅速且つ決定論的なプロセスである。不運なことに、局所的な最小値の誤差は、グローバルな最小値よりも遥かに大きい。従って、グローバルな最小値がより望ましい。
【００５４】
基本的なシミュレートされたアニーリングプロセスは次の通りである。この説明は、基本的なシミュレートされたアニーリングプロセスと、本発明の幾つかの実施態様に使用されるプロセスとの間の相違の決定を補助するために提供される。
・システムの状態を初期化する。これは、最適化すべきパラメータに幾つかの開始値を割当てることに対応する。
・温度パラメータを比較的高い値に初期化する。
・該システムの初期の（現在の）コスト（または誤差）を決定する。
このシステムのコストはコスト関数によって与えられる。このコスト関数は、該システムの何等かの可能な配置に対して数字を割当てることによって、適合性の良好さを定量化する。
【００５５】
・温度が上記の或る値より高い間に下記を実行する。
・何回かの繰返しについて：
・システムの次のトライアル状態を決定する。これは、幾つかの発生確率関数に一致した発生関数の使用を含む。次のトライアル状態の発生確立は、現在の状態からの距離と共に減少し、温度と共に増大する。
・トライアル状態のコストを計算する。
・トライアルコストが現在のコストより少なければ、またはトライアルコストは高いが許容度確立関数により許容されるときは現在の状態をトライアル状態にセットする。
・時折、アニーリングスケジュールに従って温度を減少させる。
【００５６】
この段落は、グローバルな最適化プロセスの概略を提供する。中心初期化の後に、得られたスプライン関数は単純な線形補外を使用して全体に拡張される。次いで、この完全長のスプライン関数は、グローバルな最適化アルゴリズムの２回のパスに入力される。グローバルな最適化は、シミュレートされたアニーリングの修飾バージョンを使用して、スプライン関数の結合点を移動させる。その達成目標は、点適合、間隔地図および正規化制約に関して適切に追跡された画像である。グローバルな最適化の最初の呼出しの結果は、第二の呼出しへ回される。第二の呼出しの振舞は一組の制御パラメータによって指令されるので、第一の呼出しとは異なるであろう。これらの制御パラメータは、第一のグローバルな最適化呼出しの後に、追跡は典型的には完全に良好であることを考慮に入れる。また、該システムは、第一のグローバルな最適化呼出しの出力を分析する。この分析によって追跡が非常に良好であることが示されれば、グローバルな最適化は、最小の精細化のみが行われるように、第二のグローバルな最適化の呼出しをパラメータ化する。他方、この分析により追跡が劣悪であることが示されれば、グローバルな最適化は、スプライン関数の大きな移動のために第二の呼出しをパラメータ化する。これによって、より良好な適合を行うための第二の機会がレーン追跡プログラム１２４に与えられる。このプロセスについて以下に詳細に説明する。
【００５７】
以下の段落では、シミュレートされた基本的なアニーリングプロセスと、グローバルな最適化に用いられるプロセスとの間の幾つかの重要な相違を説明する。  グローバルな最適化は、その仕事を、乏しい適合性を有することが確認された画像領域に動的に集中する。これは「動的な注意」と称する。これは、トライアル状態の形成において、移動すべき結合点を、それに伴う比較的局所的な誤差（即ち、悪い適合性）に比例して選択することにより達成される。レーン追跡プログラム１２４は、モデルレーンが如何に良好にこれらの点に適合するかを見るために、正規の間隔でチェックする。局所的なレベルにおいて、これは、どのモデルレーンスプライン断片が夫々の点（ピーク）を結合するかを確認し、これらのスプライン断片に影響する結合点に或る誤差測定を割当てることによって達成される。その結果は、全てのモデルレーンの全ての結合点についての誤差地図である。該システムは、モンテカルロ法を使用することにより、何れの結合点が、結合点の相対誤差に比例して移動すべきかを選択するであろう。
【００５８】
選択された結合点に加えて、その隣接する結合点の選択された群は選択された結合点に沿って移動し、次のトライアル状態を生じるであろう。これは「隣接テンション移動」と称する。隣接する結合点が移動する量は、選択された結合点からのそれらの距離および現在の温度を計算に入れた確率論的プロセスである。
また、グローバルな最適化は「シミュレートされた動的アニーリング」を使用する。シミュレートされた動的アニーリングにおいて、グローバルな最適化は、どの結合点が、これらの点に対するモデルレーンの適合性が乏しい領域にあるかを見るために周期的にチェックする。グローバルな最適化は、対応する選択された結合点が、モデルレーンがこれらの点にあまり適合しない領域に位置するときに、この情報に基づいてより高いコストのトライアル状態の許容を可能にするのみである。そうでなければ、より低いコストのトライアル状態が許容される。
【００５９】
標準のシミュレートされたアニーリングにおいては、上記のように、より大きなコストを有するトライアル状態を許容することが可能である（これはシミュレートされたアニーリングが局所的な最小から逃れる仕方である）。しかし、幾つかの局所的な領域が非常に良好に適合するように見えるときは、より高いエネルギージャンプは一般に更に遅い収斂を生じる。また場合によっては、稀ではあるが非常に悪い状態へのジャンプが行われ、これについて該システムには、修復のための充分な反復が残されていないかもしれない。従って、非常に良好に適合する場合には、高いエネルギーへのジャンプを許容しないことが一般には有益であるように思える。なお、理論的には、何れの関数も局所的な適合性に関してシステムの最適性を適切に判断できる限界があるので、これは最適な追跡よりも低い結果を与えることがある。一般に、より良好な局所的なコンフィギュレーションは、より劣るグローバルな最適化を生じることになることがある。幸運なことに、この応用についての経験的証拠は、合理的な量の結合点を考慮に入れた局所的な適合性の測定が非常に効果的な長所を生じることを示している。本発明の他の実施態様では、より遅い収斂が用いられる。
【００６０】
グローバルな最適化において、「良好レーン則」もまた、最適化の速度増大を補助する。この良好レーン則は、もう一つの局所的な基準である。グローバルな最適化は、どのレーンがその全体において適合性に優れているように見えるかを定期的に決定し、非常に悪い適合性を有するように見えるレーンが適合性の優れたレーンの近くに存在するかどうかを調べるためにチェックする。良好レーン則は、これらの劣悪なレーンの形状を、最も近接した良好なレーンの形状に変更する。この良好レーン則は、広範に広がっている悪いコンフィギュレーション（ｃｏｎｆｉｇｕｒａｔｉｏｎ）からシステムを移動させるのに有効である。
次に、良好レーン則について更に詳細に説明する。システムコンフィギュレーションを変化させる通常のグローバルな最適化方法は、結合点を選択し、該結合点およびその隣接点の幾つかを或る量だけ移動させる。或る場合（通常は初期化時）には、或るアニーリングスケジュールに関してシステムが少数の結合点を移動させても、その状態が充分に改善されない悪い状態にあるであろう。これは、例えば、多くの連続したレーンが誤って追跡しているが、それ自身類似しているときに生じる。そのような領域において、結合点の局所的な領域を移動させることは規則的制約を乱し、コストの大きな増大を生じるので、この移動は許容されないであろう。
非常に劣悪なレーンが二つの良好なレーンの間にあるならば、新たなレーンの形状は、三つのレーンの加重平均である。この重み付けは、三つのレーンの適合性の良好さ、および二つの良好なレーンから劣悪なレーンまでの距離を考慮する。非常に劣悪なレーンが一つの非常に良好なレーンの合理的な距離内にあるときは、重み付けは、この二つのレーンの適合基準の良好さおよびこれら二つのレーン間の距離を考慮する。
【００６１】
上記で述べたように、当該システムは良好レーン則の適用を周期的にチェックする。しかし、良好レーン則によってレーンが再整形されたら、別の二つの期間については、良好レーン則の適用が禁止される。
次に、図８に関連して、グローバルな最適化を説明する。
ブロック８１０では、初期温度が設定される。
ブロック８２０において、該システムの状態が初期化される。これには、当該システムの初期コストの決定、および初期パラメータ値の設定が含まれる。コスト関数については下記で説明する。
次に、ブロック８３０〜ブロック８９５が、一回の反復毎に３５バッチで二回繰り返される。
ブロック８３０では、５バッチ毎に、更なるバッチが必要とされないほど適合性が充分であるかどうかを決定するための試験が行なわれる。
【００６２】
ブロック８４０では、移動する一組のコントロール点が決定される。これは、先ず特定のバッチ数毎に誤差の局所的な評価を使用して、その誤差が充分に大きく、より高いコストにジャンプする能力から利益を得るであろうことが示唆されれば、夫々の結合点についてフラグを１に設定し、そうでなければゼロに設定する。特定のバッチ数毎に良好レーン則を使用して、適合性の悪いレーンを隣接する良好なレーン（もし存在すれば）のように変化させる。特定のバッチ数毎に誤差の局所的な評価を使用して、シミュレートされた動的なアニーリングデータを作成する。これは、トライアル状態のための結合点の選択に用いたモンテカルロ確立データを使用する。このデータは、より高い誤差を伴って画像領域中の点を選択するようにシステムをバイアスするであろう。
【００６３】
結合点の数に等しいバッチ毎の反復回数だけ、ブロック８５０〜ブロック８８０が繰り返される。
レーン追跡プログラム１２４は移動すべき結合点を選択する。おそらく、シミュレートされた動的なアニーリングのモンテカルロデータに指示されるように、幾つかの隣接点もまた選択されるであろう。
ブロック８５０において、選択された結合点を移動させる距離が決定される。レーン追跡プログラム１２４はコーシー母関数を使用して、選択された結合点を移動させるための指令された距離を計算する。レーン追跡プログラム１２４はまた、移動させる選択された結合点の周囲における結合点の近傍「半径」をも選択する。この近傍はゼロ〜２（両端を含む）である。半径の語は、移動すべき選択された結合点の周囲における結合点の近傍が、レーンの半径数および該レーンに沿った結合点の半径数内の近傍であることを意味する。これは、２−ｄ空間近傍である。近傍が選択されたら、それを移動させる距離もまた計算される。
ブロック８６０では、選択された結合点が移動されて、新たなトライアル状態が発生される。
【００６４】
ブロック８７０では、該トライアル状態についてのコスト変化が決定される。なお、このコスト変化は、該トライアル状態について位置が変化した結合点に対するコストを決定するだけで効率的に計算される。次に、このコストの計算について説明する。レーン追跡プログラムは以下のステップを実行する。
・夫々の点のコストを、該点の二つの境界モデルレーン（ｂｏｕｎｄｉｎｇ ｍｏｄｅｌ ｒａｎｅｓ）について計算する。この計算は、該点から該レーンの一つまでの非指向性距離であり、該点から他のレーンまでの非指向性距離の倍数である。次いで、この数字は１０の標準レーン間隔に正規化される。正規化されない計算は、実際には、夫々のレーンから当該点までの間の距離を重み付けする「レーン所有確率」である。「レーン所有確率」は、レーンまで点の距離の、二つのレーン間の距離に対する比率である。最初のレーンの前または最後のレーンの後にあるエッジ点に付いては、特別の計算が行なわれる。境界モデルレーンコストは、結合点の数（ｖｓ．ピーク点の数）に比例配分された点誤差の合計である。この比例配分は、ピーク点の数 ｖｓ． 結合点の数の間の差が、画像から画像への他のコストに対する点コストの相対的重要度を変化させないように行なわれる（これらは全て、結合点の数に対するものである）。
【００６５】
・間隔コストを計算する。これは、結合点行列（ｖｓ． 他の実施態様に使用される、或る分析形態またはスプライン関数のより精細なサンプリング）を使用して行なわれる。この基本間隔コスト行列は、間隔地図によって予想される間隔から現在の間隔を差し引くことによって得られる。セル自動化とは異なり、間隔地図は全てのレーン（装荷されていてもいなくても）についての間隔であるから、グローバルな最適化は、発見されたロードされたレーンのためのモデルレーンを有するに過ぎない。グローバルな最適化は、一つのグローバルな最適化モデルレーンから次へと間隔地図を「ウオーク」し、幽霊（ｐｈａｎｔｏｍ）（装荷されていない）レーンを推論し、モデルレーン間の予想間隔を蓄積する。間隔コスト行列は、１５％の公称許容差を使用して減衰される。その値は外側のレーンに向かって、またプライマーピークに向かって増大する。許容差未満の間隔誤差はゼロに設定される。この減衰は、間隔地図の特有の不正確さの経験的証拠を反映する。総計間隔コストは、間隔コスト行列要素の二乗合計である。
【００６６】
・曲率コストを計算する。これは、結合点行列（ｖｓ． 他の実施態様に使用されるような、ある分析形態またはスプライン関数のより精細なサンプリング）を使用して行なわれる。基本曲率コスト行列は、連続的なスプライン断片の傾斜間の差として計算される。この差は、夫々のレーン内の連続的な結合点の位置の単純な差として取られる。全てのレーンについて、結合点は均等に離間した同じチャンネルの中に整列するから、この差の計算においては、結合点の位置のチャンネル軸部分のみが使用される。基本曲率コスト行列の要素は、外側のレーンおよびプライマーピーク近傍に向かって減衰される。合計の曲率コストは、曲率コスト行列要素の二乗合計である。
【００６７】
・レーン類似性コストを計算する。これは、結合点行列（ｖｓ． 他の実施態様に使用されるような或る分析形態またはスプライン関数のより精細なサンプリング）を使用して行なわれる。基本レーン類似性コストは、一つのレーン内の連続的な結合点間の単純な傾斜の交差レーンの差として計算される。この基本レーン類似性コスト行列の要素はプライマーピークの近傍で減衰され、また交差レーン傾斜間のレーン差についても減衰される。交差レーン傾斜の減衰は、幾つかのレーンがロードされなかったために連続的なモデルレーンが実際には相互に複数のレーンであるときは、それらは真に連続的である（またはこの点について近接している）レーンと同じ形状を有するようになることはあまりない。総間隔コストは、レーン類似性行列要素の二乗合計である。
【００６８】
・傾斜変化コストを計算する。ここでは平坦なレーンが好まれる。これは、結合点行列（ｖｓ． 他の実施態様で使用されるような、或る分析形態またはスプライン関数のより精細なサンプリング）だけを使用して行なわれる。この傾斜変化ベクトルは、レーンの結合点毎の二乗重み付け平均中央チャンネル軸座標の平均として計算される。この重み付けは、プライマーピーク付近での平均からの差を減衰させる。総傾斜変化コストは、傾斜変化ベクトルの合計である。
【００６９】
・トライアル状態の総コストを、全ての別々のコストの重み付け合計として計算する。
ブロック８８０において、トライアル状態を維持する決定がなされる。トライアル状態のコストが現在の状態よりも低ければ、そのトライアル状態が許容される（即ち、それは現在の状態になる）。トライアル状態のコストが現在の状態よりも大きく、且つシミュレートされた動的アニーリングプロセスが選択された結合点について更に高いコストジャンプを許容するときは、トライアル状態の許容度は（シミュレートされたアニーリングの）許容度関数によって決定される。トライアル状態が許容されなかった場合、レーン追跡プログラム１２４は、トライアル状態を試みるために行なわれたシステムへの如何なる変更をも元に戻す。
ブロック８９０において、温度が、入力された減衰因子（典型的には０．８５の値）によって、現在の温度から低下される。
ブロック８９５において、必要な数のエポックおよびバッチが実行されれば、当該プロセスは完了する。
【００７０】
＜ｋ．ユーザーインターフェース例＞
図９は、図１のシステムに使用されるユーザーインターフェースを例示している。図９には、ＤＮＡシーケンシングプロセスの結果が、追跡されるレーンと共に示されている。画像表示１３２は、スプライン指標９１０および位置指標９２０を含んでいる。スプライン指標９１０は、与えられたレーン画像に関連したスプライン関数を指示する。この位置指標９１０はバンドの相対的位置である。画像表示１３２は、ユーザーが結合点（例えばコントロール点１３９）を走査して、対応するスプライン関数の追跡を変化させることを可能にする。しかし、幾つかの実施例では、ユーザーに指令された動きが与えられたときに、隣接するスプライン関数の形状を滑らかにするために平滑化プロセスが用いられる。幾つかの実施例において、これはグローバルな最適化を実施することによって行なわれる。
【００７１】
図１０は、図９のＤＮＡシーケンシング画像の拡大図である。なお、この画像では特定のバンドを見ることができる。
図１１は、遺伝子走査プロセスのレーンを追跡した結果を示している。このバンドは、図９におけるバンドよりも遥かに離間して広がっている。これは、レーン追跡を更に困難にする。なお、レーン追跡プログラム１２４によって適合されるスプライン関数は、レーンの中心を辿る。
図１２は、遺伝子走査プロセスのレーンを追跡する異なる図を示している。
【００７２】
＜ｌ．追加の実施態様＞
上記で述べたように、本発明の多くの異なる実施態様が存在する。このセクションでは幾つかの追加の実施態様を説明する。
本発明の幾つかの実施態様では、使用する最初のスプライン関数の組を決定することを除いて、局所的な最適化は使用されない。これらの実施態様では、グローバルな最適化プロセスを用いて、スプライン関数をレーン画像に適合させる。  本発明の幾つかの実施態様では、幾つかのプロセスステップが平行して、または異なった順序で実行される。例えば、セル自動化において、ベーススプライン関数結合点移動の成分移動値の生成は、異なった順序でまたは平行して実施することができる。
【００７３】
加えて、コンピュータ１２０が増加したメモリーおよび処理能力を有する本発明の幾つかの実施態様において、幾つかのステップは使用されない。例えば、幾つかの圧縮ステップは使用されない。
当該システムの幾つかの実施態様では、レーンを作製する他のプロセスが使用される。例えば、薄層クロマトグラフィーにおいては、他のゲル、プレート、およびサンプルが使用される。更に、走査される情報のタイプは異なり得る。例えば、蛍光ではなく放射線の検出を実行することもできる。重要なことは、本発明は如何なるレーン追跡プログラムにも適用できることである。
本発明の幾つかの実施態様において、サンプルウエル１０２に特別なバーコードサンプルが加えられる。これは、特定のバーコードに対応するレーンの区画を生じる。このバーコード情報もまた、アプリオリな要件として、追跡プロセスで使用することができる。
【００７４】
＜ｍ．結論＞
画像におけるレーンを同定するためのシステムおよび方法を説明してきた。一つの例示的方法は、分離されたサンプルのレーン位置を決定するためのコンピュータで実行される方法を含む。夫々のレーンは、媒質を通してサンプルを流すことにより分離されたサンプルに対応する。該方法は以下の要素を含む。幾つかのサンプルを媒質上に配置する。該サンプルをレーン中に分離させる。これらレーンのデジタル画像を作製する。幾つかの曲線をレーン画像に適合させる。夫々の曲線は、分離されたサンプルから形成されたレーンに対応する。
このシステムは、多くの如何なる応用についても、レーンを追跡するために使用することができる。特定の例を提供してきたが、本発明には多くの変形例が存在する。本発明の範囲は請求項によって決定されるものであり、ここで説明した特定の実施態様に限定されるべきではない。
【図面の簡単な説明】
【図１】図１は本発明の一つの実施態様において使用されることのある、ゲルにおけるレーンを追跡するためのシステムを示している。
【図２】図２は、図１のシステムに使用し得るゲル中のレーンを追跡する方法の一実施態様を示している。
【図３】図３は、バンドの中心を同定する方法の一実施態様を示している。
【図４】図４は、バンドの中心が同定された場合の出力の例を示している。
【図５】図５は、システムを初期化する方法の一実施態様を示している。
【図６】図６は、初期評価の一部の際における出力の例を示している。
【図７】図７は、一組のスプライン関数のレーン画像への適合について局所的な最適化を行う方法の一実施態様を示している。
【図８】図８は、一組のスプライン関数のレーン画像への適合についてグローバルな最適化を行う方法の一実施態様を示している。
【図９】図９は、図１のシステムに使用するユーザーインターフェースを示している。図９には、ＤＮＡシーケンシングプロセスの結果が、追跡されたレーンと共に示されている。
【図１０】図１０は、図９のＤＮＡシーケンシング画像の拡大した図を示している。
【図１１】図１１は、遺伝子走査プロセスにおけるレーン追跡の結果を示している。
【図１２】図１２は、遺伝子走査プロセスにおけるレーン追跡の異なった図を示している。
【図１】
0003585440.tif 000002
【図２】
0003585440.tif 000003
【図３】
0003585440.tif 000004
【図４】
0003585440.tif 000005
【図５】
0003585440.tif 000006
【図６】
0003585440.tif 000007
【図７】
0003585440.tif 000008
【図８】
0003585440.tif 000009
【図９】
0003585440.tif 000010
【図１０】
0003585440.tif 000011
【図１１】
0003585440.tif 000012
【図１２】
0003585440.tif 000013