(57)【要約】      （修正有）【課題】処理時間が大幅に改善されるアラインメントツールを提供する。【解決手段】アルゴリズムは低コストワークステーションを利用する従来の方法よりも１桁以上高速化される。このような結果は、シード化をベースとした方法のアルゴリズムを慎重に調整することで得られる。ハッシュされていないシードを利用し、検索エンジンランキングの技術を利用してハッシュされていないシードを組み合わせて、高速且つキャッシュ効率の高い処理を実現する。アルゴリズムはさらに、良好に並列化することができる。インメモリデータベースインフラストラクチャ（ＩＭＤＢ）に組み込むことで、データ管理およびさらなる解析のオーバーヘッドが少なくなる。【選択図】図６
2014146319.tif 000002
【特許請求の範囲】
【請求項１】
複数のリードとして提供されるヌクレオチドシーケンスデータを処理するコンピュータベースのシステムであって、
前記システムは、シークエンサマシンから前記ヌクレオチドシーケンスデータをインポートするインターフェースを備え、
前記ヌクレオチドシーケンスデータを処理するべく処理ロジックおよびインメモリデータベースを保持するプラットフォーム層を備え、
前記プラットフォーム層は、複数のワーカー、および、アラインメント調整部を含むワーカーフレームワークを有し、
前記複数のワーカーはそれぞれ、クラスタのノードで実行され、
前記複数のワーカーは、並列に処理を行い、
全ての結果および中間結果は、前記インメモリデータベースに格納され、
前記アラインメント調整部は、前記インメモリデータベースに修正されたアラインメント機能を提供するシステム。
【請求項２】
外部ソースから前記インメモリデータベースへとアノテーションアップデートのダウンロードおよびインポートを自動的に行うアップデートフレームワークをさらに備える請求項１に記載のシステム。
【請求項３】
少なくとも一のゲノムブラウザを有するユーザインターフェースをさらに備え、
前記ユーザインターフェースは、
前記ヌクレオチドシーケンスデータと、複数の参照されたセルライン／ゲノムおよび基準シーケンスの少なくとも一方とを比較して表示するセクションと、
複数の外部データベースからの解析情報を結合して表示するセクションと、
特にゲノムシーケンスデータのアラインメントのための特定のパイプライン構成のためのデータ処理の命令を選択するセクションと
を有する請求項１または２に記載のシステム。
【請求項４】
インメモリデータベースにおいて人間または人間以外のヌクレオチドシーケンスデータを処理するためのコンピュータで実行される方法であって、
複数のＣＰＵコアを含むコンピューティングノード群を含むクラスタを提供する段階と、
複数のリードとしてヌクレオチドシーケンスデータを前記インメモリデータベース内に提供し、同時に処理データをシークエンシングする段階と
を備え、
並列データ処理のために、各コンピューティングノードが一のワーカーを実装し、
データ処理は、
前記コンピューティングノード群において並列に前記複数のリードのそれぞれのチャンクをアラインメントし、前記インメモリデータベースに格納するべく複数の部分的アラインメント結果を一のアラインメント結果に統合することを含むコンピュータで実行される方法。
【請求項５】
前記コンピューティングノード群において並列にバリアントコールを実行し、複数の部分的バリアントコール結果を一のバリアントコール結果に統合する段階と、
前記インメモリデータベースにおいてアップデートフレームワークにアクセスすることで前記一のバリアントコール結果を自動的に解析する段階と
をさらに備え、
前記アップデートフレームワークは、定期的および自動的に、アップデートがあるか否か複数の異なる外部アノテーションソースを確認して、前記アップデートを前記インメモリデータベースに自動的にダウンロードおよびインポートする請求項４に記載の方法。
【請求項６】
アラインメントは、前記インメモリデータベースで直接実行される請求項４または５に記載の方法。
【請求項７】
アラインメントはシードに基づいて行われ、早期終了条件についてヒューリスティックスを適用するべく前のマッチングを評価することを目的として、検索ストラテジを利用する請求項４から６のいずれか一項に記載の方法。
【請求項８】
前記アラインメントは、高効率アルゴリズムを前記複数のリードのうち大きい割合に適用するべく、そして、複雑なアラインメントアルゴリズムを、必要であれば、前記複数のリードのうち少ない割合にのみ適用するべく、ヒューリスティックス手段に基づいて行われる請求項４から７のいずれか一項に記載の方法。
【請求項９】
長いヒットリストは、特別に取り扱われ、特に前に発見されたマッチングおよびヒットの少なくとも一方にスコアをつけるべく利用される請求項４から８のいずれか一項に記載の方法。
【請求項１０】
短いヒットリストは、長いヒットリストとは別個に取り扱われ、前に発見されたマッチングにスコアをつけること、そして、新しい位置を発見することの両方を目的として用いられる請求項４から９のいずれか一項に記載の方法。
【請求項１１】
アラインメントは、ダブルインデキシングに基づいて行われ、基準ゲノムにおける２つの後続のシードにおいてシードマッチングについての設定可能なしきい値を超えると、前記基準ゲノムにおける前記２つの後続のシードのそれぞれからのヒットを組み合わせて、別箇のより小さいインデックス構造に格納する請求項４から１０のいずれか一項に記載の方法。
【請求項１２】
アラインメントは、分散型システムにおいて、コンピュータノードまたはプロセッサの境界を越えて、複数の異なる処理ノードで並列に複数のワーカー上で実行される請求項４から１１のいずれか一項に記載の方法。
【請求項１３】
アラインメントのために、各リードは複数の重複しないシードに分割される請求項４から１２のいずれか一項に記載の方法。
【請求項１４】
シングルアレイ型またはダブルアレイ型のインデックスデータ構造を生成して前記インメモリデータベースに格納する請求項４から１３のいずれか一項に記載の方法。
【請求項１５】
インデックスデータ構造は、巨大並列マシンにおいてオンザフライでリードのアラインメントを可能とするべく、複数のプロセッサソケットのローカルメモリに、または、前記クラスタの複数のノードに複製される請求項４から１４のいずれか一項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、インメモリ技術を適用することによりゲノムシーケンスデータのアラインメントを行うコンピュータベースのシステムに関する。
【背景技術】
【０００２】
次世代シークエンシングは、発展の結果信頼性の高い診断ツールへと成長し、幅広く利用されている。シークエンシング技術は、シークエンシングの高速化および低コスト化を推し進め、ワークフローは明確に定義されるようになった。これから数年以内には、数千から数百万ものヒトゲノムは完全にシークエンシングされ、解析が急務になるであろう。
【０００３】
研究所側としては、このような発展が可能になったのは、これまでになく高速且つ低コストでシークエンシングデータを出力するシークエンシングマシンのスループットが劇的に改善されたためである。近年では、シークエンシングされた塩基対当たりのコストは６ヶ月未満の期間で半減し続けている。
【０００４】
このような進歩は、計算能力のコストに関し１８か月ごとに半減すると述べているムーアの法則よりもはるかに高速である。この結果、計算は深刻なボトルネックになり得ることに注目が集まった。シークエンシングのうち計算コストが最も高くデータ量の多いのは、短く不完全なリード（長さが約１００個の塩基対程度のゲノム断片）を基準ゲノム（約３×１０９個の塩基対）にアラインメントする処理である。つまり、一のリードを考えると、基準ゲノムで当該リードが最も良好に適合する箇所を特定して、読出エラーおよび突然変異の原因となる編集回数を少なくしつつどのように当該リードをアラインメントすることができるかを特定する（アラインメントではギャップを特定してスコア付与する）必要がある。これは、正しい位置に関して予め情報を得ることが出来ないので、困難な課題である。また、計算について、並列処理およびメモリヒエラルキーを活用できなければ、完全にムーアの法則の恩恵を受けることができないことに留意されたい。特に、接尾辞配列および接尾辞木等の高度なインデックスデータ構造は、並列に構築することが難しく、このようなインデックスデータ構造に対するクエリは多くのキャッシュ障害を発生させてしまう。本来は、この特定の問題点を解決するべく、並列処理およびこのようなデータ構造のメモリヒエラルキー認識構成を利用することが提案されてきた。しかし、当該問題点を詳細に解析すると、はるかに単純な技術で大きな高速化が見込めることが分かった。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
このため、本発明は、処理時間が大幅に改善されるアラインメントツールを提供することを目的にする。
【０００６】
このため、本発明は、高品質な処理結果をできる限り高速に提供すること、および、複数の異なるデータベーストランザクションのクエリ結果を自動的に統合することを目的とする。
【課題を解決するための手段】
【０００７】
上記の目的は、特許請求の範囲に記載する独立請求項、特に、インメモリデータベースシステムを用いてゲノムシーケンスデータを処理（アラインメント）するコンピュータベースのシステムおよび方法によって実現される。
【０００８】
複数のリードとして提供される人間または人間以外のヌクレオチドシーケンスデータを処理する本発明に係るコンピュータベースのシステムであって、ヌクレオチドシーケンスデータを処理するべく処理ロジックおよびインメモリデータベースシステムを保持するプラットフォーム層を備え、プラットフォーム層は、プロセスとして実現される複数のワーカーを含むワーカーフレームワークと、インメモリデータベースシステムに修正されたアラインメント機能を提供するアラインメント調整部とを有し、複数のワーカーはそれぞれ、複数のコアで構成されるクラスタのコンピューティングノードで実行され、複数のワーカーは、並列に処理を行い、全ての結果および中間結果は、インメモリデータベースに格納される。
【０００９】
本発明の好ましい実施形態によると、アラインメント調整部はワーカーフレームワーク内に組み込まれるとしてよい。
【００１０】
好ましい実施形態によると、システムはさらに、少なくとも一のゲノムブラウザを有するユーザインターフェースを備える。ユーザインターフェースは、ヌクレオチドシーケンスデータと、複数の参照されたセルライン／ゲノムおよび／または基準シーケンスとを比較して表示するセクションと、複数の外部データベースからの解析情報を結合して表示するセクションと、特別にゲノムシーケンスデータのアラインメントのための特定のパイプライン構成のためのデータ処理の命令を選択するセクションとを有する。
【００１１】
別の好ましい実施形態によると、システムはさらに、外部ソースからインメモリデータベースへとアノテーションアップデート（関連検索文献を含む可能性がある）のダウンロードおよびインポートを自動的に行うアップデートフレームワークを備える。
【００１２】
本発明の別の側面によると、インメモリデータベースにおいて人間または人間以外のヌクレオチドシーケンスデータを処理するためのコンピュータで実行される方法が提供される。当該方法は、複数のコアを含むコンピューティングノード群を含むクラスタを提供する段階であって、複数のコアはそれぞれ、並列データ処理のために、ワーカーを実装する段階と、リードとしてヌクレオチドシーケンスデータをインメモリデータベース内に提供し、同時に処理データをシークエンシングする段階とを備え、データ処理は、コンピューティングノード群において並列にリードのチャンクをアラインメントし、インメモリデータベースシステムに格納するべく複数の部分的アラインメント結果を一のアラインメント結果に統合することを含む。
【００１３】
好ましい実施形態によると、当該方法はさらに、以下に記載する段階のうち１つを備える。
コンピューティングノード群において並列にバリアントコールを実行し、複数の部分的バリアントコール結果を一のバリアントコール結果に統合する段階、および／または
インメモリデータベースにおいてアップデートフレームワークにアクセスすることでバリアントコール結果を自動的に解析する段階、アップデートフレームワークは、定期的および自動的に、アップデートがあるか否か複数の異なる外部アノテーションソースを確認して、アップデートをインメモリデータベースに自動的にダウンロードおよびインポート
【００１４】
以下では、本願で用いられる用語の定義を簡単に説明する。
【００１５】
「チャンク」は、リードの一部と解釈されたい。コンピューティングノードの量およびチャンクのサイズは変更可能である。
【００１６】
「ヌクレオチドシーケンスデータ」は、人体または人体以外のデータであってよく、ＤＮＡシーケンスデータまたはＲＮＡシーケンスデータであってよい。本発明の別の実施形態によると、上記のシステムはさらに、例えば、アミノ酸シーケンス等の他のゲノムシーケンスデータを処理するように構成されるとしてもよい。しかし、ゲノムシーケンスは主に、主な核酸塩基はシトシン、グアニン、アデニン（ＤＮＡおよびＲＮＡ）、チミン（ＤＮＡ）およびウラシル（ＲＮＡ）であり、それぞれＣ、Ｇ、Ａ、ＴおよびＵと省略されるので、アルファベットＣ、Ｇ、Ａ、ＴおよびＵを含む文字にマッピングされ得るシーケンスを意味する。以下では、簡単に塩基と呼ぶことが多い（遺伝学での慣用に応じたもの）。
【００１７】
シークエンサマシンは、ＤＮＡ分子におけるヌクレオチドの正確な順序を自動的に決定する研究デバイスである。これは、次世代シークエンシング（ＮＧＳ）デバイスであることが好ましい。シークエンシングマシンはリードを提供し、リードはシステムにインポートされる。ＮＧＳマシンは通常、システムの一部ではない。ＮＧＳマシンは、ＤＮＡ鎖における４つの塩基、アデニン、グアニン、シトシンおよびチミンの順序を決定するために用いられる任意の方法または技術を含む。一般的に、ＤＮＡシークエンシングは、複数の個別の遺伝子で構成されるシーケンス、より大きな遺伝領域（つまり、一の制御信号またはプロモータの制御下で複数の遺伝子で形成されるクラスタを含むゲノムＤＮＡの機能単位として、遺伝子クラスタまたはいわゆるオペロン）、全染色体または全ゲノムを決定するために用いられるとしてよい。結果として得られるシーケンスは、さらなる科学の進歩のために分子生物学または遺伝学の研究者によって用いられるとしてよく、または、薬物を個人向けにカスタマイズするために用いられるとしてよい。例えば、がんゲノムシークエンシングは、一の均質または異質がん細胞群の全ゲノムシークエンシングである。これは、がん細胞のＤＮＡシーケンスまたはＲＮＡシーケンスの特徴付けおよび特定のための生化学研究方法である。通常は血球、唾液、上皮細胞または骨から行われる全ゲノム（ＷＧ）シークエンシングとは異なり、がんゲノムシークエンシングは、原発腫瘍組織、隣接または離れた位置にある正常組織、線維芽細胞／間質細胞等の腫瘍微小環境、または、転移腫瘍部位の直接シークエンシングを行う。全ゲノムシークエンシングと同様に、この方法で生成される情報は、ヌクレオチド塩基の識別情報（ＤＮＡまたはＲＮＡ）、複製番号およびシーケンスバリアント、突然変異状態、および、染色体の転座および融合遺伝子等の構造変化を含む。がんゲノムシークエンシングは、ＷＧシークエンシングに限定されず、エキソームシークエンシング、トランスクリプトームシークエンシング、および、ミクロノーム（ｍｉｃｒｏｎｏｍｅ）シークエンシングを含むとしてよい。これらの方法は、遺伝子発現、ｍｉＲＮＡ発現を定量化し、シーケンスデータに加えて代替的なスプライシングイベントを特定するために用いられるとしてよい。本発明において処理すべき入力データは、ＦＡＳＴＱ形式ファイルとして提供されるとしてよい。
【００１８】
「修正されたアラインメント機能」という表現は、インメモリデータベースに組み込まれている複数の異なるアラインメントアルゴリズムのうち少なくとも１つとして解釈されたい。このため、特定のアラインメントアルゴリズム、理想的には当該アルゴリズム用に追加パイプライン構成を含むものを適用するとしてよい。「修正されたアラインメント機能」の別の側面としては、アラインメントアルゴリズムはインメモリデータベースでの利用のために最適化されるという事実が挙げられる。ファイルシステム内の入出力ファイルにアクセスする従来のアルゴリズムとは対照的に、修正後のアラインメントアルゴリズムは、インメモリデータベースシステムに直接格納されているデータまたは格納される予定のデータを利用するとしてよい。この結果、媒体損傷（ｍｅｄｉａ  ｂｒｅａｋ）が減少し、スループットが上昇し、現在の専用ＯＬＡＰシステムに対して抽出、変換加工およびロード（ｅｘｔｒａｃｔｉｏｎ，ｔｒａｎｓｆｏｒｍａｔｉｏｎ，  ａｎｄ  ｌｏａｄｉｎｇ）を行うことなく、インメモリデータベースに格納されている全データに加えて解析クエリを実行することができる。
【００１９】
「ＣＰＵ」という用語は、コンピュータまたはコンピュータ群の中央演算処理装置を意味する。一般的に、一のコンピュータは複数のＣＰＵを備えるとしてよい。この場合、コンピューティングシステムはマルチプロセッシング型であるという。一部のマイクロプロセッサは、一のチップに複数のＣＰＵを含んでおり、この場合はマルチコアプロセッサと呼ばれる。また、分散させた複数のプロセッサを相互接続して一のプロセッサ群を形成することも可能である。
【００２０】
「プラットフォーム層」は、ゲノムシークエンシングデータの処理をインメモリデータベースに組み込むためのコンピュータベースアーキテクチャを意味する。本発明によると、全ての処理結果および中間結果はファイルシステムにファイルとして格納されるのではなく、インメモリデータベースシステムに提供されることに留意されたい。このように、全ての処理、例えば、ソート、マージング等は、専用ツールによってファイルに対して実行され、演算（ＯＬＴＰシステム）トランザクションおよび解析（ＯＬＡＰシステム）トランザクションを用いることで、ネイティブインメモリデータベーストランザクションに置換される。
【００２１】
インメモリデータベースは、メインメモリ技術を利用すると共に列指向データ構造を利用し、列および行の格納を組み合わせてデータ群に対して実行する。このように、インメモリ技術は、もはやディスク格納メカニズムを利用しない。解析システムおよびトランザクションシステムを統合し、組み合わせる。本発明の一の側面によると、ＯＬＴＰクエリは入力データに対して実行することができる。入力データは、特に、シークエンシングデータ（ＮＧＳマシンが提供）およびアノテーションデータ（アップデートフレームワークが提供、外部の分散している登録アノテーションソースまたはデータベース全てからのデータを統合）および他のゲノムデータを含むとしてよい。本発明に係る処理結果は、中間結果および最終結果を含み、インメモリデータベースシステムにおいて行指向または列指向のデータベース形式で格納されるとしてよい。列型のデータベース方式は、ＯＬＡＰクエリをサポートするので、ＯＬＡＰ処理はインタラクティブ応答時間挙動から恩恵を受ける。列指向型のデータベース形式で格納されているデータは、入力データおよび結果の両方によって定期的にアップデートされるとしてよく、この特徴は、インメモリデータベースは、列指向データ形式でレイテンシ無し（つまり、リアルタイム）でＯＬＡＰクエリの実行を可能とするという利点と組み合わせられる。本発明の基礎となるインメモリデータベースの特徴および利点に関して、インメモリデータベースの詳細な内容を説明する特許出願ＥＰ２  ０４０  １８０を参照されたい。
【００２２】
ワーカーフレームワークは、インメモリデータベース（以下ではＩＭＤＢと省略する）とやり取りを行い、複数の異なるアプリケーション（アプリケーション層）とデータ（データ層）との間の中間役である。ワーカーフレームワークは、関連技術分野で公知であるマップリデュース（ＭａｐＲｅｄｕｃｅ）方式と同様に、入力されるシークエンシング要求について、必要なタスクおよびサブタスク、ならびに、その順序を指定する。また、これらのタスクをコンピューティングリソース、例えば、コンピューティングノードに振り分けて、それらのステータスを観察し、部分的結果群を組み合わせて最終結果群を得る。
【００２３】
アップデートフレームワークもまた、インメモリデータベースとやり取りを行い、複数の異なるアプリケーション（アプリケーション層）とデータ（データ層）との間の中間役である。アップデートフレームワークは、国際検索結果を組み合わせるための基礎的役割を果たす。アップデートフレームワークは、アップデートされたアノテーションおよび新しく追加されたアノテーションがあるかどうか、例えば、データベースエクスポートまたはＣＳＶ、ＴＳＶ、ＶＣＦ等の特徴的なファイル形式があるかどうか、インターネットソース、例えば、公開されているＦＴＰサーバまたはウェブページを定期的に確認する。新しいデータは、自動的にダウンロードされ、ＩＭＤＢにインポートされ、知識ベースを拡張する。また、関連する文献ソース、例えば、ＰｕｂＭｅｄをパーシングして、データベース内の関連文献をアップデートする。任意で、確認すべき外部データベース群を選択するとしてもよく、および／または、結果を選択して関連する発見結果のみをインメモリデータベースにインポートするとしてもよい。新しいデータがインポートされると、レイテンシを発生させること無くゲノムデータをリアルタイムで解析するために利用可能である。例えば、アップデートフレームワークが処理するべく選択された研究データベースは、国立バイオテクノロジー情報センター（Ｎａｔｉｏｎａｌ  Ｃｅｎｔｅｒ  ｆｏｒ  Ｂｉｏｔｅｃｈｎｏｌｏｇｙ  Ｉｎｆｏｒｍａｔｉｏｎ：ＮＣＢＩ）、サンガー、カリフォルニア大学サンタクルーズ校（Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃａｌｉｆｏｒｎｉａ  Ｓａｎｔａ  Ｃｒｕｚ：ＵＣＳＣ）等である。具体的な利用事例について関連研究文献を選択するべく選択プロセスが実行されることが好ましい（例えば、特別なデータベースを含めて、他のものは無視するとしてよい）。
【００２４】
処理パイプラインは、固定的にプログラミングされず、本発明の一側面によると、例えば、ビジネス・プロセス・モデル・アンド・ノーテーション（ＢＰＭＮ）等の一般的な表記法を利用して、グラフィカルにモデリングされる。このため、例えば、異なるアラインメントアルゴリズムを実装する異なるパイプラインも設定されるとしてよい。これらのパイプラインは、並列に処理されるとしてよい。これは、並列データ処理に起因する、性能の大きな改善である。さらに、個別のパイプライン構成は、複数の異なる研究グループが取得する結果が比較可能になることを保証する。
【００２５】
アラインメント処理ステップは、リード自体は変更せず各リードについて数個の追加属性を生成するのみであるので、インメモリ列格納データベースが持つ、単一行の追加または修正は残りの行にアクセスすることなく超高速で実行可能であるという特性は、全ての情報を、大半が入力情報の複製から形成される単純なテキストファイルに格納する現在の実施例に比べて大きな利点となる。
【００２６】
アラインメントは通常、各リードを互いに重複しない複数のシードに分割することに基づいて行われる。しかし、互いに重複するシードを利用することも可能である。
【００２７】
本発明の側面によると、アラインメントは、今後のアラインメントプロセスをゲノムデータの一部に限定するべく、アーリーアウトヒューリスティックを利用する。
【００２８】
本発明の一側面によると、アラインメントアルゴリズムを適合させてギャップをヒューリスティック方式で埋めるべくシードを利用する。これには、Ｎｅｅｄｌｅｍａｎ  Ｗｕｎｓｃｈ等の時間およびリソースが大量に必要なアラインメントアルゴリズムはほとんど適用する必要がなく、データのうちわずかな部分にのみ適用されるという技術的効果がある。
【００２９】
本発明の一側面によると、アラインメントはダブルインデキシングに基づいて行われ、基準ゲノムにおける２つの後続のシードにおいてシードマッチングについての設定可能なしきい値を超えると、基準ゲノムにおける２つの後続のシードのそれぞれからのヒットを組み合わせて、別箇のより小さいインデックス構造に格納する。言い換えると、（ゲノムシーケンスと比較されアラインメントされる）基準ゲノムにおける２つの後続のシードがヒットが多過ぎる場合、これら２つの後続のシードは組み合わせて別箇のインデックス構造に格納される。この別箇のインデックス構造は、言うまでもなく、他の（第１の）インデックス構造よりもはるかに小さい。２つの長いヒットリストが連続して発見されると、はるかに短いヒットリストを得るべく、この（第２の）インデックス構造で検索することが可能になる。これは、シードが長くなるほど選択が厳しくなるためである。利点として、処理時間およびリソースを低減させることができるとしてよい。
【００３０】
別の側面は、所定の一群の静的なパイプライン構成の代わりに、パイプライン構成を動的にモデリングする際の柔軟性に見られる。例えば、一または複数のアラインメントアルゴリズムを一群のアラインメントアルゴリズムから選択して組み合わせ、特に、ほとんど知られていないゲノム上の差について、結果の精度を高めるとしてよい。さらに、特定のパイプライン構成を選択して適用し、例えば、同質の基礎の複数の異なるゲノムデータ群を比較するための基準としてよい。
【００３１】
本発明の一側面によると、シングルアレイまたはダブルアレイ型のインデックスデータ構造を生成してインメモリデータベースに格納する。
【００３２】
本発明の一側面によると、インデックスデータ構造は、巨大並列マシンにおいてオンザフライでリードのアラインメントを可能とするべく、複数のプロセッサソケットのローカルメモリに、または、クラスタの複数のノードに複製される。
【００３３】
本発明の主要な側面は、インデックス構造およびアラインメントアルゴリズムはキャッシュミスに関して最適化されるという点にある。
【００３４】
本発明に係る方法およびシステムの好ましい実施形態は、従属請求項に定義されている。この点について、一般的に、本発明はさらにハードウェアまたはソフトウェアモジュールと組み合わせたハードウェアモジュールにおいて実現されることに留意されたい。そして、ハードウェアモジュールは、上述した方法の段階の機能を実行するように構成されている。したがって、ハードウェアモジュールおよびソフトウェアモジュールの組み合わせを備えることも可能である。ハードウェアモジュールおよびソフトウェアモジュールは、既存のバイオ科学環境または医学環境、例えば、シークエンシング環境に組み込まれることが好ましい。当該方法に関して上述または後述する特徴、別の実施形態および利点は、対応する段階の機能を実行するように構成されているハードウェアモジュールを用いて、システムにも同様に適用されるとしてよく、逆もまた然りである。
【図面の簡単な説明】
【００３５】
本発明をより完全に理解していただくべく、以下の詳細な説明を参照されたい。以下の詳細な説明は、添付図面と共に参照されたい。
【図１】本発明の好ましい実施形態に係るシードスコアを説明する図である。
【図２】新たなヒットを含む複数のマッチングリストをマージングする例を説明する図である。
【図３】本発明の好ましい実施形態に係るシード拡張を説明する図である。
【図４】Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈアラインメントアルゴリズムへの拡張を示す。
【図５】本発明の好ましい実施形態に係るシステムパイプラインを示す概略図である。
【図６】システムアーキテクチャを示す概略図である。
【図７】本発明の好ましい実施形態に係る処理ノードを示す図である。
【発明を実施するための形態】
【００３６】
図６は、ＦＭＣ（Ｆｕｎｄａｍｅｎｔａｌ  Ｍｏｄｅｌｉｎｇ  Ｃｏｎｃｅｐｔｓ）ブロック図としてモデリングされている、リアルタイム解析を可能とする重要部分としてＩＭＤＢを備えるシステムアーキテクチャのデータ層、プラットフォーム層およびアプリケーション層を示す。プラットフォーム層において、インメモリデータベース（ＩＭＤＢ）は、複数の国際研究データベースからのデータを組み合わせて、クラウドアプリケーションに対してリアルタイム解析機能を持つ。図６から分かるように、コアコンピュータ内のインメモリデータベースＩＭＤＢは、データ処理のため、外部データベース（例えば、アノテーションデータベース）とやり取りを行い、ワーカーフレームワークおよびアップデートフレームワークとやり取りを行う。より高いレベルには、リアルタイム解析およびゲノムブラウジングのために、ならびに、アラインメント調整部を利用したアラインメントのために、複数の異なるアプリケーションが配置されている。
【００３７】
図５は、ＢＰＭＮ（Ｂｕｓｉｎｅｓｓ  Ｐｒｏｃｅｓｓ  Ｍｏｄｅｌｉｎｇ  ａｎｄ  Ｎｏｔａｔｉｏｎ）としてモデリングされている現在の典型的なゲノム処理パイプラインを示す図である。図５は、ＢＰＭＮでモデリングされているこの研究用試作品に組み込まれているゲノムデータ処理パイプラインを示す図である。入力ＦＡＳＴＱファイルは、１０００個のコアを持つクラスタにおいて並列データ処理を行うべく最大２５個のチャンクに分割される。第一に、特定のアラインメントアルゴリズム、ここではＢＷＡは並列に呼び出され、複合ＢＡＭファイルが作成されるまで変換ステップを実行する。第二に、ＢＡＭファイルは、染色体毎に１つのチャンクになるよう、複数の別箇のチャンクに分割され、バリアントコールは並列に処理される。結果をＩＭＤＢにインポートして、結果をリアルタイムで解析できるようにする。
【００３８】
図７は、ゲノムデータ処理を実行するべく、ＯＬＡＰトランザクションおよびＯＬＴＰトランザクションで構成されるインメモリベースアーキテクチャ全体を示す図である。図７から分かるように、ヌクレオチドシーケンスは、シークエンサマシンＭから提供される。シークエンサマシンＭは、図７では左側に図示されている。当該パイプラインによると、一群のリードが提供される。各リードは、変更可能なチャンク数で分割され、具体的には、２５個のチャンクに分割される。各チャンクは、ノードクラスタの一のワーカーに対応付けられているか、または、割り当てられている。図７から分かるように、処理デバイスとしてチャンクにワーカーを割り当てることも、動的に設定可能であるので、本例では、チャンク１はワーカー２に割り当てられ、チャンク２はワーカー１に割り当てられる。これは、チャンク１は処理能力の要求が最も厳しく、ワーカー２はこの時点において余剰リソースが最も多いためである。こうして各ワーカーは、ＩＭＤＢデータベースに格納されている変更可能なアラインメントアルゴリズムを実行することで、部分的アラインメント結果ＡＲ１、ＡＲ２、・・・、ＡＲｎを提供する。各チャンクを処理するアラインメントアルゴリズムは異なる場合がある（ユーザが希望する場合）ことに留意されたい。したがって、リード毎に利用するアラインメントアルゴリズムを変更することも可能である。主要な特徴として、シークエンシングの算出または処理が終了する前にアラインメントが開始される点も挙げられる。このため、この方法は最初のシーケンス結果が得られるとすぐに実施されるとしてよい。全ての部分的アラインメント結果ＡＲｉを統合した後、部分的アラインメント結果ＡＲｉおよび統合結果をＩＭＤＢデータベースに格納する。
【００３９】
これらのデータベーストランザクションが実行され統合アラインメント結果が得られると、パイプラインの対応する利用事例のために設定され得るバリアントコールアルゴリズムを利用して、統合アラインメント結果を再度、並列処理用に複数のアイテムに分割する。各ワーカーは、バリアントコールの中間結果ＶＣＲ１、ＶＣＲ２、・・・、ＶＣＲｎを提供する。これらの部分的結果ＶＣＲｉはＩＭＤＢデータベースに格納され、統合して統合結果を作成し、統合結果をＩＭＤＢデータベースに格納する。同時に、結果をユーザインターフェースＵＩで表示するとしてよい。
【００４０】
薬物を個人向けにカスタマイズする際にＤＮＡを組み込むためには、ＤＮＡシークエンシングおよびゲノムデータの解析という２つの重要なステップを実行する。ＤＮＡシークエンシングは、例えば、血液または組織等の生体サンプルを用意し、ＮＧＳデバイスを用いてシークエンシングを行う。ゲノムデータの解析は、ＩＴを利用したステップであり、ＮＧＳデバイスから得られたＦＡＳＴＱファイルを処理する。アラインメント、バリアントコールおよび結果の解析を含む。
【００４１】
アラインメントは、選択した基準ゲノムで、取得したリードシーケンスを組み合わせて、特定の全ゲノムを再構築することである。
【００４２】
バリアントコールは、再構築したゲノムで異常を検出し、バリアントの可能性があるか否か、例えば、特定の対立遺伝子の発現であるか否かを確認する。バリアントコールで得られた全ての結果の解析および世界中のアノテーションデータベースを用いたその解釈は、最後且つ最も時間のかかるステップである。本願に係るゲノムブラウザは、時間をかけて手動でインターネット検索を行う必要なく、これらの結果のアドホックに解析する。
【００４３】
＜並列データ処理＞
本願は、Ｐｙｔｈｏｎで記述され、一群のワーカーを提供する専用データ処理フレームワークを開示する。各コンピューティングノードは、専用ワーカーを備える。専用ワーカーは、複雑なタスク、つまり、複数のジョブまたは長時間かかる非インタラクティブ型のバッチ処理の一方で構成されるタスク、例えば、全ゲノムについてのリードのシーケンスアラインメントを処理する。複雑でないインタラクティブ型のタスクは、ウェブサービスによって直接実行され、ワーカーフレームワークは関係しない。複雑なタスクは、並列データ処理を行うべく、ワーカーフレームワークによってワークのアトミック部分単位で分割される。アトミックジョブは、分散方式で実行するとしてよい。ワーカーが利用可能になれば、ジョブ待ち行列から次のジョブをフェッチして、自動的に実行する。
【００４４】
ジョブおよびワーカーの同期は、ジョブデータベーステーブルを介して実行される。ジョブデータベーステーブルは、新規ジョブ、現在処理されているジョブ、および、完了したジョブ、ならびに、それらのステータス、例えば、新規、処理中、完了、失敗等を含む。全てのワーカーは、自分のローカルデータベースインスタンスを介してジョブテーブルに直接アクセスし、次の適切なタスクを自己割り当てする。同時性制御は、ＩＭＤＢによって保証される。つまり、属性ＴＡＳＫ−ＩＤ、ＪＯＢ−ＩＤおよびＳＴＡＴＵＳに対する主キーは、一のワーカーのみがタスクのＳＴＡＴＵＳ属性をＮＥＷ（新規）からＩＮ  ＰＲＯＧＲＥＳＳ（処理中）に変更できるように保証する。アップデートされたステータスがデータベースシステムで確認された直後、ワーカーはジョブの処理を開始する。
【００４５】
ジョブの実行は、要求に応じてワーカーフレームワークにロードされるモジュラーＰｙｔｈｏｎスクリプトを用いて処理される。ワーカーモジュールは、待ち行列から、まだ割り当てられていないジョブを選択する。ジョブのうち特定のサブ群の依存関係および同期は、ジョブデータベーステーブルの内容を評価する専用ジョブによって自己調整される。
【００４６】
全てのＰｙｔｈｏｎジョブモジュールはスーパーモジュールジョブから継承する。スーパーモジュールジョブは、ステータスアップデートまたはエラーロギング等の一般的な方法を提供する。ジョブが実行するコード、例えば、未処理のＤＮＡリードのアラインメント、または、ＣＳＶファイルのデータベースへのインポートは、対応するジョブモジュール内に配置されている。
【００４７】
本発明によれば、ジョブ毎に個別のツールおよびスクリプトを利用することができる。この結果、既存のツール、例えば、ｓａｍｔｏｏｌｓ、ｂｃｆｔｏｏｌｓ、ｖｃｆｔｏｏｌｓ、および、高度に最適化されたインメモリ型のツールをパイプラインに組み込むことが可能である。本願は、さまざまな事実上の標準規格であるアラインメントアルゴリズム、例えば、Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ  Ａｌｉｇｎｅｒ（ＢＷＡ）、Ｂｏｗｔｉｅ、Ｂｏｗｔｉｅ２、ＳＮＡＰ等をパイプラインに組み込むことに成功した。
【００４８】
＜シーケンスアラインメントおよびバリアントコール＞
アラインメントタスク用の入力は、数千または数百万の未処理のＤＮＡリードまたはＤＮＡ断片を含むＦＡＳＴＱファイルである。ＦＡＳＴＱファイルは、ＮＧＳデバイスによって時間のかかる処理を実行して生成される。一の大きなＦＡＳＴＱファイルを待つ代わりに、処理はできる限り早く開始される。つまり、ファイルサイズが、例えば、２５６ＭＢであるＦＡＳＴＱチャンクがＮＧＳデバイスで生成されると、開始される。この結果、シークエンシングのランがいまだ進行中である間に、データ処理は既に開始している。バリアントコールの結果は、バリアントコール形式（ＶＣＦ）に準拠するタスク特有データベーステーブルに格納される。
【００４９】
図５は、ＢＰＭＮでモデリングされるＢＷＡアラインメントアルゴリズムを含むゲノムデータ処理パイプラインを示す。図示しているステップは先行技術に係るパイプラインと全体的に同様の機能を持つが、全ての処理ステップおよび処理ツールがＩＭＤＢに移動されている。このように、全ての中間結果はデータベースに格納され、選択された処理はＩＭＤＢの固有のデータベース処理で置換される。このため、本願に係るシステムは、既存のツールおよびパイプラインのための統合プラットフォーム、および、高度に最適化されたアルゴリズム、例えば、ＨＡＮＡ  Ａｌｉｇｎｍｅｎｔのための開発プラットフォームを意味する。以下のＦＭＣ図では、シーケンスアラインメントの一般的な手順を示す。ステップ２−４は、複数のノードにおいてＦＡＳＴＱファイルの全ての分割部分に対して行われる。ステップ５−８は、一のノードでのみ実行され得る。一方、分割後、ステップ９−１０は再度、最多で２４個の異なるノードで実行される。
１．ＦＡＳＴＱファイルは、複数のチャンクに分割され、複数のノードでの並列処理を可能とする。
２．特定のアラインメントアルゴリズムはＳＡＭ形式でゲノムを再構築する。アラインメントアルゴリズムは、選択または選定されるとしてよい（ＢＷＡ、Ｂｏｗｔｉｅ等）。
３．ＳＡＭファイルは、続いてバリアントコールを行うべく、バイナリ表現、つまり、ＢＡＭ形式に変換される。
４．ＢＡＭファイルをステップ５のための準備ステップとして（マージングのため）ソートする。
５．複数のＢＡＭファイルを一のＢＡＭファイルにマージングする。
６．蓄積したＢＡＭファイルをインデキシングのためにソートする。
７．ＢＡＭファイルをインデキシングする。
８．ＢＡＭファイルを、並列処理のために、染色体毎に個別のチャンクに分割する（２４分割）。
９．ｓａｍｔｏｏｌｓ等のバリアントコールを実行して、ＶＣＦファイルを作成する
１０．複数のＶＣＦファイルをマージングして、蓄積した結果群をリアルタイム解析のためにデータベースＩＭＤＢにインポートする。
【００５０】
ＩＭＤＢ技術のために最適化されたパイプラインでは、ソート、マージングおよびインデキシングの処理ステップは、特定のツールで実行されるのではない。これらの処理ステップは、ファイルシステムに中間ファイルを形成することなく、ＩＭＤＢによって直接実行される。
【００５１】
本発明の主要な利点としては、慎重にアルゴリズム変更を行うことで、多くの障害にもかかわらず、中程度の機能を持つワークステーションにおいて数分でアラインメント問題の解を求めることが可能であることが挙げられる。これは、略無視可能な計算コストといえる。このように驚くべき結果が得られる理由は、３つある。一方では、本発明はムーアの法則に比べて発展度合が倍増している。アルゴリズムは並列化が容易であるので、最新のマルチコアプロセッサを利用することができる。さらに、ＲＡＭ価格が下落していることも有利に働き、高速かつ単純だがメモリ集約的なデータ構造を利用できるようになる。他方では、数多く列挙される単純だが効果的なアルゴリズム技術をまとめて、性能を改善する。恐らく、ここで最も基本的な側面は、リードにおけるエラーレートが十分に低く、本願は多くの「近道（ショートカット）」を辿り得る点を利用していることにある。大半のリードについて、重複しないサブストリング（シード）と基準ゲノムとが正確にマッチングするかどうかを確認するだけで十分であり、このような正確なマッチングのうち幾つかが見られる候補位置のみをより詳細に検査するだけでよい。本願は、基準ゲノムにおいて頻度が高過ぎるサブストリングを無視するとしてよい。残りのアラインメントされていないリードは少数であり、より（計算コストが）高価な検索を行う余裕がある。候補位置における実際のアラインメントも、エラーレートが低いことの恩恵を受け、非常に単純な形式のビット並列マッチングが実用可能となる。
【００５２】
アラインメント問題が程度の差こそあれ解決されたので、大きな課題は、シークエンシング、アーカイビングおよび大量のシークエンシングされたゲノムに対する処理で構成されるワークフロー全体となる。ＨＡＮＡ技術に基づき、一部の特別な高性能アルゴリズムを、データベースサーバに実装するとしてよい。データベースサーバでは、カスタマイズされたアルゴリズムがデータと直接やり取りを行う。データ転送およびデータ変換が必要ないので、この方法はデータベースでアルゴリズムを実行する方法よりも優れている。アラインメントアルゴリズムは、このような実施例の良い例である。アラインメントアルゴリズムは、一連のリードをオンザフライで処理するので、ほぼ基準ゲノム上でのインデックスだけにメインメモリを必要とするので、このアーキテクチャから既に恩恵を受けている。基準ゲノムは、データリードの総量よりはるかに少ない。
【００５３】
＜これまでの研究＞
基準ゲノムに対するショートヌクレオチドシーケンス（リード）のアラインメントは、多大な研究努力が費やされている。さまざまなアルゴリズムが存在し、最も一般的なものを幾つか挙げると、ＢＷＡ−ＳＷ（Ｌｉ，Ｈ．，Ｄｕｒｂｉｎ，Ｒ．：Ｆａｓｔ  ａｎｄ  ａｃｃｕｒａｔｅ  ｌｏｎｇ−ｒｅａｄ  ａｌｉｇｎｍｅｎｔ  ｗｉｔｈ  Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ  ｔｒａｎｓｆｏｒｍ．  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  （Ｏｘ−ｆｏｒｄ，  Ｅｎｇｌａｎｄ）  ２６（５），５８９−９５（２０１０年３月）を参照のこと）、ＳＯＡＰ２（Ｌｉ，Ｒ．，Ｙｕ，Ｃ．，Ｌｉ，Ｙ．，Ｌａｍ，Ｔ．Ｗ．，Ｙｉｕ，Ｓ．Ｍ．，Ｋｒｉｓｔｉａｎｓｅｎ，Ｋ．，Ｗａｎｇ，Ｊ．：ＳＯＡＰ２：ａｎ  ｉｍｐｒｏｖｅｄ  ｕｌｔｒａｆａｓｔ  ｔｏｏｌ  ｆｏｒ  ｓｈｏｒｔ  ｒｅａｄ  ａｌｉｇｎｍｅｎｔ．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ（Ｏｘｆｏｒｄ，  Ｅｎｇｌａｎｄ）  ２５（１５），１９６６−７（２００９年８月）を参照のこと）、Ｂｏｗｔｉｅ２（Ｌａｎｇｍｅａｄ，Ｂ．，Ｓａｌｚｂｅｒｇ，Ｓ．Ｌ．：Ｆａｓｔ  ｇａｐｐｅｄ−ｒｅａｄ  ａｌｉｇｎｍｅｎｔ  ｗｉｔｈ  Ｂｏｗｔｉｅ  ２．  Ｎａｔｕｒｅ  ｍｅｔｈｏｄｓ  ９（４），３５７−９（２０１２年４月）を参照のこと）、ＳＮＡＰ（Ｚａｈａｒｉａ，Ｍ．，Ｂｏｌｏｓｋｙ，Ｗ．Ｊ．，Ｃｕｒｔｉｓ，Ｋ．，Ｆｏｘ，Ａ．，Ｐａｔｔｅｒｓｏｎ，Ｄ．，Ｓｈｅｎｋｅｒ，Ｓ．，Ｓｔｏｉｃａ，Ｉ．，Ｋａｒｐ，Ｒ．Ｍ．，Ｓｉｔｔｌｅｒ，Ｔ．：Ｆａｓｔｅｒ  ａｎｄ  Ｍｏｒｅ  Ａｃｃｕｒａｔｅ  Ｓｅｑｕｅｎｃｅ  Ａｌｉｇｎｍｅｎｔ  ｗｉｔｈ  ＳＮＡＰ  （２０１１年１１月）を参照のこと）、ＳＭＡＬＴおよびＭａｓａｉ（Ｓｉｒａｇｕｓａ，Ｅ．，Ｗｅｅｓｅ，Ｄ．，Ｒｅｉｎｅｒｔ，Ｋ．：Ｆａｓｔ  ａｎｄ  ｓｅｎｓｉｔｉｖｅ  ｒｅａｄ  ｍａｐｐｉｎｇ  ｗｉｔｈ  ａｐｐｒｏｘｉｍａｔｅ  ｓｅｅｄｓ  ａｎｄ  ｍｕｌｔｉｐｌｅ  ｂａｃｋｔｒａｃｋｉｎｇ．  ＣｏＲＲ  ａｂｓ／１２０８．４２３８（２０１２）を参照のこと）がある。最新の概論は、（Ｌｉ，Ｈ．，Ｈｏｍｅｒ，Ｎ．：Ａ  ｓｕｒｖｅｙ  ｏｆ  ｓｅｑｕｅｎｃｅ  ａｌｉｇｎｍｅｎｔ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｎｅｘｔ−ｇｅｎｅｒａｔｉｏｎ  ｓｅｑｕｅｎｃｉｎｇ．  Ｂｒｉｅｆｉｎｇｓ  ｉｎ  Ｂｉｏｉｎ−ｆｏｒｍａｔｉｃｓ  １１（５），４７３−４８３  （２０１０））に記載されている。
【００５４】
リードは基準ゲノムに対してわずかに異なりシークエンシングエラーも含むので、各アラインメントアルゴリズムはこのような相違を許容する必要がある。基準ゲノムにおいてリードの最良マッチング位置を発見するために一般的に用いられる基本方式として、バックトラッキング方式およびシード化方式の２つがある。バックトラッキング方式では、入力されたリードを何回か変更して、この変更が基準ゲノムに発見されるか否かを常に確認する。可能な変更の数が非常に多く、リードの長さに応じて増加するので、可能な検索空間は、大き過ぎて、アルゴリズムで全てカバーすることはできない。このため、最有力経路を辿ろうとするインテリジェントヒューリスティックスおよび変更の回数または種類に対する制限が適用されることが多い。シード化方式のアルゴリズムは、エラーを許容することなく、基準ゲノム内にリードのショートサブシーケンス（シード）を発見しようとする。このようなサブシーケンスが存在する場合、エラー許容拡張アルゴリズムがリードの残りを基準ゲノムにマッチングさせようと試みる。
【００５５】
ＢＷＡ−ＳＷ、ＳＯＡＰ２およびＢｏｗｔｉｅ２は、ＦＭインデックスを利用している（Ｆｅｒｒａｇｉｎａ，Ｐ．，Ｍａｎｚｉｎｉ，Ｇ．：  Ｏｐｐｏｒｔｕｎｉｓｔｉｃ  ｄａｔａ  ｓｔｒｕｃｔｕｒｅｓ  ｗｉｔｈ  ａｐｐｌｉｃａｔｉｏｎｓ．  Ｉｎ：  Ｐｒｏｃｅｅｄｉｎｇｓ  ４１ｓｔ  Ａｎｎｕａｌ  Ｓｙｍｐｏ−ｓｉｕｍ  ｏｎ  Ｆｏｕｎｄａｔｉｏｎｓ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ．ｐｐ．３９０−３９８．ＩＥＥＥ  Ｃｏｍｐｕｔ．Ｓｏｃ（２０００））。一方、ＳＮＡＰおよびＳＭＡＬＴはハッシュテーブルベースのインデックスを利用する。
【００５６】
ＦＭインデックスベースのアルゴリズムは、インデックスは圧縮されていないが、ハッシュテーブルベースのアルゴリズムに比べてメモリ効率が非常に高い。しかし、ＦＭインデックスベースのアルゴリズムは、ランダムなメモリ位置に対して多数の検索を実行する必要があるので、キャッシュミスが発生し易い。特に、エラー許容アラインメントについてバックトラッキング方式を利用するアルゴリズム（例えば、ＢＷＡ−ＳＷおよびＳＯＡＰ２）は、エラーを含む複数の代替案を考慮しなければいけないので、多くのキャッシュミスを発生させる。これは、ハッシュが長い場合には性能に関する大きなボトルネックになり得る。ハッシュ長が長いハッシュテーブルベースの実施例は、多くのメモリを必要とする傾向があるが（ＳＮＡＰの場合は３９ＧＢ）、キャッシュミスははるかに少なくなるので、通常は高速化される。
【００５７】
Ｍａｓａｉ（Ｓｉｒａｇｕｓａ，Ｅ．，Ｗｅｅｓｅ，Ｄ．，Ｒｅｉｎｅｒｔ，Ｋ．：Ｆａｓｔ  ａｎｄ  ｓｅｎｓｉｔｉｖｅ  ｒｅａｄ  ｍａｐｐｉｎｇ  ｗｉｔｈ  ａｐｐｒｏｘｉｍａｔｅ  ｓｅｅｄｓ  ａｎｄ  ｍｕｌｔｉｐｌｅ  ｂａｃｋｔｒａｃｋｉｎｇ．ＣｏＲＲ  ａｂｓ／１２０８．４２３８  （２０１２））は、少数のエラーが許容されるシードにバックトラッキングを利用することで、両方の方式を組み合わせる。これによって、精度および速度の両方が実現される。しかし、Ｍａｓａｉは、基準ゲノムのために改善された接尾辞配列が必要になり、シードのために基数木データ構造が必要になるので、大量のメモリが必要になる。
【００５８】
本発明に係るアラインメントアルゴリズムは、非常に一般的な基礎概念に基づいて、インデックスデータ構造を構築するので、長さがＳ＝１６（シード長）である全てのサブストリングを基準ゲノム内で高速に発見することができる。データ構造は、ほとんど当惑するほど単純である。長さが１６の全ての２３２個のサブストリングについて、基準ゲノム内の当該サブストリングが現れる位置の全てが列挙されているリストを格納する。ハッシュ構造も接尾辞配列も無い。
【００５９】
ハードウェアの観点からみると、この方式が上手くいくのは、このようなリストの処理は、より高度なデータ構造で処理する場合よりキャッシュ効率がはるかに高いアレイを走査するだけで実行可能なためである。また、これは、情報検索で利用される逆インデックスデータ構造に類似していることに留意されたい。
【００６０】
リードは独立して処理されるので、当惑するほど並列に処理される。唯一注意すべき点は、データの並列読み書きのための同期オーバーヘッドがボトルネックにならないようにすることである。これは、リードのブロック全体を一度で処理することで容易に実現される。本願では、アラインメントのための有力候補位置を短時間で発見するべく、検索エンジン由来の技術を利用する。
【００６１】
＜インデックス構造＞
インデックスは、４１６個のエントリポイントで構成されるアレイｅと、基準ゲノム内のマッチング位置（基準位置）で構成されるアレイｍという２つの部分から構成される。ｍ［ｅ［ｓ］，...，ｅ［ｓ＋１］−１］は、基準ゲノム内のシードｓにマッチングする位置を格納する。
【００６２】
この構造は、全ての基準ゲノム位置に対して繰り返し行い、各シードが登場した回数をカウントすることによって、線形時間で算出され得る。この情報は、さらなるメモリを必要とすることなく、直接ｅに格納することができる。次のステップでは、相対的に小さい全てのシードのカウントを加算することでこれらのカウントを統合する。これによって既に、マッチング位置リストに対して正しいエントリポイントが提供され、マッチング位置リストはこの後単純に、基準ゲノム全体にわたって再度繰り返して、この場合の値を格納することで、書き込む。このステップはさらに、メモリオーバーヘッドを発生させることなく算出することができる。これは、エントリポイントインデックスを用いて各シードの次の書込位置を格納できるためである。この目的のため、シードが発見される度に、そのエントリポイントを１増加させて、次回の書込オフセットとして利用できるようにする。全ゲノムを処理した後、各シードエントリポイントは、次のシードの値を含み、データ構造は本来の値を回復するためには１シード戻るだけでよい。
【００６３】
このため、インデックス構成は単に、カウンティングソート型のメモリ効率の高い実施例である。カウントが多数になるので、アルゴリズムは多くのキャッシュミスを発生させ、並列化はそれほど容易ではない。直接並列化は、いくらか単純化したものであるが、コアの数が中程度である場合には非常に効果的である。各コアは、カウントの部分区間についてのみ責任を持つ。全基準ゲノムを走査するが、割り当てられているカウントのみをインクリメントする。
【００６４】
空間消費を増やすという犠牲を払うことによって同時に、並列キャッシュ最適化ソートアルゴリズムを利用して、よりスケーラブルな並列化およびキャッシュ障害の大幅な低減を実現することができる。本発明は、「Ｓａｎｄｅｒｓ，Ｐ．，Ｗａｓｓｅｎｂｅｒｇ，Ｊ．：Ｅｎｇｉｎｅｅｒｉｎｇ  ａ  ｍｕｌｔｉ−ｃｏｒｅ  ｒａｄｉｘ  ｓｏｒｔ．Ｉｎ：Ｅｕｒｏ−Ｐａｒ．ＬＮＣＳ，ｖｏｌ．６８５３，ｐｐ．１６０−１６９」に説明されている高度にチューニングされた基数ソートに基づいている。尚、位置は既に構造によってソートされており、当該ソートは安定しているので、シードをソートすることで十分である。
【００６５】
インデックスにおける位置は、性能および簡素化のために、基準ゲノムにおける全ての染色体を連結させたバージョンを意味する。これによって、全ての関連する位置を一回のコールで得ることが可能となり、キャッシュミスの回数を低く抑え、複数のリストをマージングしなくても済む。非常に高速化されたインデックス構造のおかげで、基本的にオーバーヘッドは発生しない。マッチングのための対応する基準染色体は、別のインデックス構造を用いて非常に効率的に発見することができる。この染色体インデックスは、単純なビットシフトおよび整数の比較に基づいている。第一に、全ての染色体を連結し、各染色体のためのオフセットｏｊ（染色体ｊについて）を保存して、後に減算できるようにする。ここで、最上位ビットの最小数ｋを算出して、２つの染色体の開始部分が、ｋ個の最上位ビットについて、決して同じ値にならないようにする。サイズが２ｋのルックアップテーブルビンを作成する。ビンｉは、基準ゲノムにおいて最上位ビットｉを持つ全ての位置を表し、ビンｉに重複する最も右の染色体のｉｄを格納する。位置ｘの検索は、ｊ＝ビン［ｘ：１≫（３２−ｋ）］を算出し、ｏｊ≦ｘであるか否かを確認する。ｏｊ≦ｘである場合、ｊは正しい染色体ｉｄである。ｏｊ＞ｘである場合、正しいｉｄはｊ−１である。
【００６６】
ヒトゲノムの場合、必要なビットは７ビットに過ぎず、この場合には１２８個のビンが得られる。６４ビット長のポインタであり、当該構造の大きさは１キロバイトに過ぎず、Ｌ１キャッシュに十分入る。
【００６７】
＜マッチング候補の発見＞
各リードは、Ｒがリード長でＳがシード長である場合、Ｒ／Ｓ個の重複しないシードに分割される。尚、この方法ではアラインメントされないサイズＳのマッチングを幾つか見逃すが、総当たり方式における実行時間に比べて１／Ｓに短縮する。シードインデックスにおいて各シードをクエリすることによって、当該シードがマッチング（ヒット）する位置のソート済みリストを取得する。大半のシードは複数回ヒットするので、リードのシード毎に検索空間は大きくなる。一部の非常に一般的なシードは数千回から数十万回ヒットする可能性があるので、さらに大きな問題になる。この問題を回避するべく、本願は、各シードのヒットを組み合わせ（マッチングを形成し）、ヒット数が最多のマッチングのみを利用するように試みている。これは、ヒット数が最多のマッチングが、基準ゲノムに重複している度合が最も高い可能性が高いからである。
【００６８】
ヒットを組み合わせてマッチングを形成し、最も有力なマッチングを発見するべく、全てのシードにわたって繰り返す。過去のマッチングは、基準位置に応じて整列させたリストに格納し、現在のシードのヒットのリストと組み合わせる。どちらのリストもソートされているので、この組み合わせ処理は基本的に、一般化されたマージング方式であり、複数のキーワードのヒットリストを組み合わせる場合にサーチエンジンで実行される処理と密に関係している。
【００６９】
判断は、このようなマッチングが実現するのが理想的なスコアを楽観的計算で算出した結果に基づいて行われる。この点については、図１を参照されたい。スコアについて、ミスマッチングについてはｐ≠＝２のペナルティを利用し、挿入／欠失についてはｐ±＝３を利用し、マッチングについてはｐ＝＝０とペナルティを付けない。ペナルティは、負の対数確率に基づいて決まる。これは、合計ペナルティを得るべく単に加算することが可能で、これは全ての確率の積に等しくなるためである。ペナルティ「２」は、確率が１０−２＝１％であることを意味し、ペナルティ「３」は１０−３＝０．１％であることを意味する。ペナルティスコアが高くなるほど、マッチングは悪くなる。１６回を超えるヒットのシードは無視するが、検索空間が妥当なサイズ以上に大きくならないように、マッチングと楽観的にカウントして、ミスマッチングペナルティを付与しない。最初のマッチングのシードのスコアは、以下の通りである。
ｓ←ｉ・ｐ≠
ｉは、０から始まるリードにおけるシードのインデックスである。これは単に、先行するｉ個のシードはマッチングしなかったが、インデックスｉを持つ現在のシードはマッチングすることを意味する。さらに、最初のマッチングは、マッチングの基準位置を決める。
ｒ←ｒｉ−ｉ・Ｓ
【００７０】
続くスコアは、最後のヒットｒｉの位置、ならびに、現在のヒットｒｊおよびリード上の塩基対におけるそれらの距離ｄ：＝（ｊ−ｉ−１）・Ｓのうちの一方に基づいて決まる。
ｓ←ｓ＋｜ｒｊ−ｒｉ−ｄ｜・ｐ±＋（ｊ−ｉ−１−｜ｒｊ−ｒｉ｜）・ｐ≠
これは、予測された位置ｒｉ＋ｄからのｒｊのずれと挿入／欠失のペナルティとを乗算した結果に、その間でミスしたシードの数を説明するために必要なミスマッチングの最小数とミスマッチングペナルティとを乗算した結果を加算して得られる。後者の項は、単純な例で説明することができる。シードｊの予測位置からのずれが２である場合、少なくとも２個の挿入または欠失があるはずである。しかし、その間でミスしたシードが３個である場合、３個のシードがミスした理由を説明するべく、少なくとも別の１個のミスマッチングが必要になるはずである。
【００７１】
図１は、シードスコアを示す図である。同図では、ａからｆの数字が以下のシナリオ／イベントを表している。
（ａ）マッチングが発見されないため、更に情報が利用可能になるまでこのシードを無視。
（ｂ）最初のマッチングを発見。それ以前のマッチングを、結果が多過ぎるために無視されていない限り、全てミスマッチングとしてカウント。仮定された開始部分に基準位置（点線）を割り当てる。
（ｃ）結果が多過ぎるので、シードは楽観的に正しい位置でマッチングしていると仮定。
（ｄ）マッチングは発見されない。
（ｅ）挿入を行って後続のシードを「１」シフト。
（ｆ）マッチングを発見。２個のシードをミスしたので、少なくとも２個のミスマッチングが必要。シフトさせることは、少なくとも１回の挿入があることを意味する。挿入は、ミスマッチングよりも重みが大きい。このため、１回のミスマッチングおよび１回の欠失があったと楽観的に仮定。
【００７２】
図２は、新しいヒットを含むマッチングリストをマージングする様子を示す。現在のシード（本例では、リード内の最後のシード）についての全てのヒット（基準シーケンス内の小文字）を、前のマッチングのそれぞれの領域と比較すると、所定のしきい値未満のスコアが得られる。両者が重複する場合、組み合わせたマッチングを追加する。いずれの場合も、楽観的スコアが依然としてしきい値未満でありミスマッチングがあると仮定すると、前のマッチングが複製される。同様に、先行する全てのシードがミスマッチングであったと仮定して、新しいヒットを追加する。前に無視したリストは基準ゲノムマッチングに格納されているので、これらのシードはスコア算出から排除する。リストは常に基準位置に応じてソートされるので、マッチングリストは空間的に近いので、大きな労力を払うことなく比較することができる。
【００７３】
原則的には、全てのマッチング／ヒットの組み合わせについてスコアを算出する必要があり、所定のスコアしきい値未満の組み合わせは全て保持すべきである一方、残りは破棄する。本願では、これらの組み合わせの大半を、基準位置が離れ過ぎており、両方のリストの順序が整理されているという事実に基づき、排除することが可能であるので、本発明は、両方のリストにわたって同時に繰り返すことが可能であり、小さいウィンドウ内でスコアを算出するのみである。これは、より離れたマッチングは全て、挿入／欠失のペナルティが大きくなるために、確実にスコアが悪くなるためである（図２を参照のこと）。両方のリストを走査するのは１回のみであり、ウィンドウが非常に小さいので、アクセスはランダムではなく局所的であり、この方法はキャッシュ効率が非常に高い。基本的に、全てのリストアクセスはＬ１キャッシュ内で行われるべきであり、プリフェッチは最適に適用され得る。
【００７４】
最終的に、最良のスコアのマッチングを決定して、最高スコアの半分未満のマッチングは全て除外する。マッチングするシードが最多で１個の場合には、更に処理を実行して、その中から最良候補を特定する（以下を参照のこと）。
【００７５】
＜シード拡張＞
図３は、シード拡張を説明するための図である。マッチングから開始して、シードをできる限り拡張することを試みて、最終的に２個のギャップが残る。
【００７６】
最初のシード化の後、リード毎にスコアに関して最も有力な候補をさらに処理する。本願に係るシステムおよび方法はさらに、マッチングに対して最初にある程度のフィルタリングを行い、可能なスコアおよびマッチングするシードの最小数を限定する。
【００７７】
最初の段階では、６４ビットのアーキテクチャでは最高で３２個の塩基対をＸＯＲを利用する一回の処理で比較することが可能であるので、ビットの平行性を利用してシードをできる限り拡張する。そして、最新型のＣＰＵにおいて先行／後置ゼロカウント処理を利用して、マッチングする位置をカウントするとしてよい。結果を２で除算すると、すぐに塩基対の数が得られる。塩基対の数だけマッチングを拡張することができる。
【００７８】
＜単純なギャップ＞
基準シーケンスからの相違点を含むアラインメント情報は、最も左の基準位置から開始して拡張したシードにわたって繰り返すことで、再構築することができる。これによって、マッチング領域（拡張したシード）、および、その間のギャップが交互に出現する複数のセグメントのリストが作成される。拡張したシードは、容易に処理することができる完全にマッチングする領域を表すが、ギャップは、基準シーケンスからの相違点が複雑である。
【００７９】
エラーレートが低いおかげで、大半のギャップは以下に示す４つの分類のうち一つに分類される。
１．空のギャップ
リードおよび基準ゲノムのどちらにおいてもギャップの長さがゼロ個の塩基に等しい。マッチング位置の数が多いために無視されたシードでギャップが構成されている場合に見られる。
２．一回の置換
リードおよび基準ゲノムのどちらにおいてもギャップの長さが１個の塩基に等しい。このため、ギャップは１個の塩基の置換を表す。
３．挿入
基準ゲノムにおけるギャップのサイズがゼロであるが、リードにおけるギャップのサイズはゼロでない。これは、リードの全ての塩基は挿入されたことを意味する。
４．欠失
基準ゲノムのギャップのサイズはゼロでないが、リードにおけるギャップのサイズはゼロである。これは、全ての塩基は基準ゲノムから欠失したことを意味する。
【００８０】
これらの単純なギャップのアラインメントは、算出が容易であり、追加のロジックは必要ない。
【００８１】
＜複雑なギャップおよび未結合端部＞
マッチングがリードの端部まで拡張されない場合、未結合端部は特別な方法で取り扱う必要がある。これは、上記の基準にマッチングしなかったギャップであって、マッチング、置換、挿入および欠失を複雑に組み合わせる必要があるギャップにも当てはまる。
【００８２】
このような問題について、２つのアルゴリズムが確立されている。Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈアルゴリズム「Ｎｅｅｄｌｅｍａｎ，Ｓ．Ｂ．，Ｗｕｎｓｃｈ，Ｃ．Ｄ．：Ａ  ｇｅｎｅｒａｌ  ｍｅｔｈｏｄ  ａｐｐｌｉｃａｂｌｅ  ｔｏ  ｔｈｅ  ｓｅａｒｃｈ  ｆｏｒ  ｓｉｍｉｌａｒｉｔｉｅｓ  ｉｎ  ｔｈｅ  ａｍｉｎｏ  ａｃｉｄ  ｓｅｑｕｅｎｃｅ  ｏｆ  ｔｗｏ  ｐｒｏｔｅｉｎｓ．Ｊｏｕｒｎａｌ  ｏｆ  ｍｏｌｅｃｕｌａｒ  ｂｉｏｌｏｇｙ  ４８（３），４４３−５３（Ｍａｒ  １９７０）」およびＳｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズム「Ｓｍｉｔｈ，Ｔ．Ｆ．，Ｗａｔｅｒｍａｎ，Ｍ．Ｓ．：Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｏｆ  ｃｏｍｍｏｎ  ｍｏｌｅｃｕｌａｒ  ｓｕｂｓｅｑｕｅｎｃｅｓ．Ｊｏｕｒｎａｌ  ｏｆ  ｍｏｌｅｃｕｌａｒ  ｂｉｏｌｏｇｙ」である。前者はグローバルアラインメント用に設計されているのでギャップに完璧に適用されるが、後者はローカルアラインメント用に設計されている。未結合端部は一端ではある程度の柔軟性が必要であるが他方ではそうでなく、本願は、この目的のために、修正したＳｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムを利用する。
【００８３】
Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈアルゴリズムに比べて、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムは、図４に列挙している幾つかの修正を適用する。これらの修正を行った結果、ローカルアラインメントが検出される。これらは、２つのヌクレオチドシーケンスに含まれるショートマッチングサブシーケンスである。しかし、場合によっては、一端にのみこの柔軟性を適用することを希望し、リードのクリッピングは許可せず、基準ゲノムのみクリッピングを行う。場合によってはリードをクリッピングすることが望ましいが、一般的なケースではないので、オプションとする。境界の状況に応じて、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムの修正の一部を可能とする必要がある（図４のテーブルを参照のこと）。当該テーブルにおいて、行はリード内の各塩基に対応しているが、列は基準内の塩基を表している。
【００８４】
図４のテーブルは、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈアルゴリズムへの拡張を説明する。ギャップ／端の種類および設定に応じて、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈアルゴリズムを修正する。行はリードの塩基に対応し、列は基準の塩基に対応する。クリッピングによってより多くの特徴が明らかになり、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムに近くなる。どの端部もオープンでなく、クリッピング無しの極端なケースは、通常のＮｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈアルゴリズムとなるが、逆（両端でオープンであり、クリッピングあり）は、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムとなる。
【００８５】
＜マッチングしなかったリードの処理＞
基準ゲノムにマッチングさせた大半のリードは、上述した高速処理でマッチングさせることができる。これは、「一般的なケースを高速化する」という処理の基本の応用である。数少ない残りのリードについて、本願はより高コストの方法を実行することができる。特に、ここでは長さがＳの全てのサブストリングをシードとして利用する。残るのは大抵、エラーレートが非常に高いので他よりも有用性が低いリード、および、基準ゲノムに全く由来しないリードである。このため、現在の実施例ではここで終わる。
【００８６】
しかし、前者のリードはある程度の有用性を持つ場合がある。このようなリードをマッチングさせるためには、より短い正確なマッチングに基づく方法が必要になる。十分な空間がありインデックス構築時間を気にしない場合、本願は、既存のバックトラッキング型のリードアラインメントを利用することができる。本願では、この高コストの方法はリードのうちわずかな割合にのみ適用されるので、速度に関する利点をほぼ維持する。しかし、本願に係る方法の応用例には、マッチングしていないリードから最も有用な情報を抽出する低コストの方法もある。大半の場合、既に他のリードで良好にカバーしているゲノム部分にマッピングされる追加リードについては考慮しない。しかし、ゲノムのうちわずかな一部分は良好にカバーされないことが常であり、この場合、残りのリードの幾つかをマッピングすることは非常に効果的である。これは、カバーが不十分な領域が偶然その箇所にあるのではなく、生物学的に非常に関連性が高い大規模な変異のためである箇所について特に重要である。この目的のため、本願に係る方法およびシステムは、基準ゲノムのうちカバーが不十分である部分を抽出し（ウィンドウサイズはＲ）、これらの部分についてシード長ＳＩ＜Ｓの新しいインデックス構造を構築する。ここで、本願はマッピングされていないリード（そして、おそらく過去のマッピングスコアが低いもの）について本願に係るアルゴリズムを繰り返す。基準ゲノムを短くすると、ヒットリストは遥かに短いので、これもまた高速である。
【００８７】
上記のアルゴリズムの性能を他の従来技術のアラインメントアルゴリズムと比較するべく、本発明は、ＢＷＡ−ＳＷおよびＢｏｗｔｉｅ２を同じデータに対して実行し、ミリ秒当たりのリードのスループットおよびアラインメントレートを比較した。
【００８８】
一実施形態によると、全ての測定は２．６７ＧＨｚのクロックを持つ４個のＩｎｔｅｌ  Ｘｅｏｎ  Ｅ−７５６０ヘキサコアプロセッサを備える機械で実行される。当該機械は、５０４ギガバイトのＲＡＭを備える。尚、全てのコードは６４ギガバイトでも動作する。本願は、Ｉ／Ｏハードウェアの詳細ではなく、アルゴリズムの性能のみを測定するべく、残りのメモリを利用してＲＡＭディスクとの間の全てのＩ／Ｏを実行する。
【００８９】
＜考察＞
リードアラインメントアルゴリズムは、非常に高速であるので、発生し得る計算コストは数セントに過ぎず、無視できる値である。これは、シークエンシングのための研究所技術がムーアの法則よりも早い速度で低コスト化したとしても、リードアラインメントはボトルネックにならないことを意味する。本願では、現在重要な事例である長さが約１００であるリードという事例について実験を行っているが、非常に短いリードの場合のみに上手く適用されるバックトラッキング型の方法とは対照的に、リード長とはほとんど関係がないように思われる。さらに、本発明に係る方法は、多くのシークエンシング技術について同様であると思われるが、リードの開始部分のエラーレートが低い限りにおいて良好に適用される。
【００９０】
さらに、本願に係る方法のインデックス構築時間およびメモリフットプリントは、過去の方法、特に、接尾辞配列／Ｂｕｒｒｏｗｓ−Ｗｈｅｅｌｅｒ変換等の高度なデータ構造に基づく方法よりもはるかに高速である。これによって、基準ゲノムを変更することがはるかに容易になる。これは、人間以外のゲノムについて、または、基準ゲノムとして類縁のゲノムを利用することを希望する場合に重要であるとしてよい。
【００９１】
所望される場合、アラインメントアルゴリズムの性能はさらに、ＲＡＭ、並列化およびアルゴリズム改善の３つの方法を全て利用して、改善することができる。例えば、更に多くのＲＡＭを利用して、本発明は、ダブルアレイインデックスデータ構造の代わりに、サイズがＢ個のバケツで構成されるシングルアレイを利用することができる。尚、Ｂは少なくとも一のキャッシュラインに適応する十分な大きさである。ここで、シードｉの最初のＢ−１個のヒットをバケツｉに格納する。Ｂ番目のエントリは、オーバーフロー領域または空のバケツを指定するために用いられるとしてよい。この方法の場合、最初のＢ−１個のヒットにアクセス可能となる前に発生するキャッシュミスは１回のみである。
【００９２】
よりスケーラブルな並列化を可能とするべく、本願は再度、複数のプロセッサソケットのローカルメモリまたはクラスタの複数のノードにわたってインデックスデータ構造を複製することによって、より多くのＲＡＭを利用することができる。原則的には、これによって巨大並列マシンにおいてリードアラインメントを瞬間的に行うことができるようになる。このため、同等に高速の研究設備が存在し、さらに処理すると仮定すると、例えば、手術中に、腫瘍の組織サンプルを即座に解析してその対処法を決定することができるようになる。
【００９３】
アルゴリズムを改善する機会としては、長いヒットリストに加えてインデックスデータ構造を構築し、長いヒットリストと短いリストとを、短いリストの長さに時間比例してマージングすることを含む。
【００９４】
最後に、実施形態例の説明は、原則的に、本発明の特定の物理的な実施例について限定的に理解されるべきではないことに留意されたい。特に、当業者には、本発明の実施形態は一部分または全てをソフトウェアで実現可能であり、特にコンピュータプログラム製品等の複数の物理的製品で分散して実現可能であることは明らかである。
【００９５】
さらに、上述した方法はいずれもプログラムとして具現化され得る。プログラムは、コンピュータ可読媒体に格納されるとしてよく、コンピュータデバイス（少なくとも１つのプロセッサコアを含むデバイス、ノード、ワーカー、または、ワーカーネットワーク）で実行されると上述した方法のいずれか１つを実行するように構成される。このように、格納媒体またはコンピュータ可読媒体は、情報を格納するように構成されており、データ処理設備またはコンピュータデバイスとやり取りを行って上述した実施形態のいずれか１つに係る方法を実行するように構成されている。
【００９６】
このように実施形態例を説明したが、多くの点で変更し得ることは明らかである。このような変更は本発明の意図および範囲から逸脱するものとみなされるのではなく、このような変形は全て当業者には明らかであり特許請求の範囲に含まれるものとする。
【図１】
2014146319.tif 000003
【図２】
2014146319.tif 000004
【図３】
2014146319.tif 000005
【図４】
2014146319.tif 000006
【図５】
2014146319.tif 000007
【図６】
2014146319.tif 000008
【図７】
2014146319.tif 000009
【外国語明細書】
2014146319000001.pdf