(57)【要約】本発明は、全般的には、ゲノム研究に関し、特に、公知の位置における同定されたヌクレオチドを使用した、リードマッピングのための改善された方法に関する。本発明は、同定されたヌクレオチドと一致していない潜在的マッピングまたはアセンブリを除外することにより、ゲノム内の公知の場所において同定されたヌクレオチドを使用して、ゲノム由来の配列リードの解析をガイドする方法を提供する。被験体のゲノムにおける複数のＳＮＰに関する情報を使用して、ゲノム有向非巡回グラフ（ＤＡＧ）を通る候補パスを同定する。配列リードは、候補パスにマッピングされる。
2017510871.tif 000002
【特許請求の範囲】
【請求項１】
ゲノム配列を決定するためのシステムであって、
メモリにカップリングされたプロセッサを含むコンピュータシステム
を含み、
被験体のゲノム上の公知の位置における複数のヌクレオチドの同一性を受け取り、
複数のゲノム配列から１または複数のゲノム配列を選択し、ここで該選択された配列が該公知の位置に該ヌクレオチドを含み、
該被験体由来の試料から配列リードを受け取り、
該配列リードを該１または複数の選択されたゲノム配列にマッピングし、これにより該ゲノムの少なくとも一部の配列を同定する
ように操作可能である、システム。
【請求項２】
前記複数のゲノム配列を表すデータが、ヌクレオチド配列を表すノードおよび該ノードの対を接続するエッジを含み、該ノードおよびエッジが、有向非巡回グラフを定義し、さらに、前記選択されたゲノム配列のそれぞれが、該有向非巡回グラフを通る選択されたパスを定義する、請求項１に記載のシステム。
【請求項３】
前記有向非巡回グラフが、複数のポジションにおいてポジション当たり少なくとも２種の代替配列を表す、請求項２に記載のシステム。
【請求項４】
前記配列リードのマッピングが、各配列リードおよび各選択されたパスの間に最適なアライメントを見出すことを含む、請求項３に記載のシステム。
【請求項５】
最適なアライメントを見出すことが、多次元マトリックスを通る最高スコアリングトレースを見出すことを含む、請求項４に記載のシステム。
【請求項６】
前記公知の位置における前記複数のヌクレオチドの前記同一性に基づき追加のヌクレオチドの同一性の確率を得て、
前記最適なアライメントを見出すことにおいて該得られた確率を使用する
ようにさらに操作可能な、請求項４に記載のシステム。
【請求項７】
前記確率が、前記追加のヌクレオチドのうち１種と、前記公知の位置における前記複数のヌクレオチドのうち１種との間の連鎖不平衡の尺度から得られる、請求項６に記載のシステム。
【請求項８】
前記複数のゲノム配列が、ノードおよびエッジオブジェクトのうち隣接するもののメモリにおける位置に対するポインタのリストをそれぞれ記憶する複数のノードおよびエッジオブジェクトを含むＤＡＧとしてメモリに記憶され、ここで、前記選択されたゲノム配列のそれぞれが、該ＤＡＧを通る選択されたパスを定義し、前記システムが、前記配列リードおよび該選択されたパスの間に最適なアライメントを見出すことにより、該配列リードをマッピングするように操作可能である、請求項４に記載のシステム。
【請求項９】
最適なアライメントを見出すことが、
前記リードと、前記ＤＡＧにおける前記ノードおよびエッジオブジェクトの少なくとも一部との間のマッチスコアを計算し、
メモリにおけるそれらの参照される位置から、該ＤＡＧにおけるリード先行処理オブジェクトへと前記ポインタの少なくとも一部を逆参照することにより、該ＤＡＧを通る最高スコアリングトレースを見出すことを含み、ここで、マッチスコアの最大和で先行処理オブジェクトを通るパスが、該ＤＡＧを通る該最高スコアリングトレースである、請求項８に記載のシステム。
【請求項１０】
前記複数のゲノム配列が、複数のノードおよびエッジオブジェクトを含むＤＡＧとして前記メモリに記憶され、ここで、複数のヌクレオチドの前記同一性が、前記被験体のゲノムにおける複数のＳＮＰを含み、前記システムが、該複数のＳＮＰを含む該ＤＡＧを通る候補パスを同定することにより該ＳＮＰを含む前記１または複数のゲノム配列を選択する、請求項１に記載のシステム。
【請求項１１】
前記ＤＡＧが、対立遺伝子毎に単一のオブジェクトにより、複数のゲノムにわたって相同の少なくとも１種の遺伝子座を表す、請求項１０に記載のシステム。
【請求項１２】
前記ＤＡＧが、共存できないノード対のリストを作るためにアノテートされ、前記システムが、
前記複数のＳＮＰのうち１種から共存できないノード対の該リストにおけるノードを同定し、
共存できないノード対の該リストにおける該同定されたノードと対形成した第２のノードを同定し、
前記配列リードをマッピングする際に、該第２のノードを含有するパスを除外する
ようにさらに操作可能である、請求項１０に記載のシステム。
【請求項１３】
被験体の遺伝情報を決定するための方法であって、
該被験体のゲノムにおける複数のＳＮＰに関する情報を得るステップと、
遺伝子配列を表すノードおよび該ノードの対を接続するエッジを含む有向非巡回データ構造内で、該複数のＳＮＰを含む候補パスを同定するステップと、
該被験体のゲノムから配列リードを得るステップと、
該配列リードを該候補パスにマッピングするステップと
を含む方法。
【請求項１４】
前記有向非巡回データ構造が、対立遺伝子毎に単一のノードにより、複数のゲノムにわたって相同の少なくとも１種の遺伝子座を表す、請求項１３に記載の方法。
【請求項１５】
前記有向非巡回データ構造が、共存できないノード対のリストを作るためにアノテートされる、請求項１３に記載の方法であって、
前記複数のＳＮＰのうち１種から共存できないノード対の前記リストにおけるノードを同定するステップと、
共存できないノード対の該リストにおける該同定されたノードと対形成する第２のノードを同定するステップと、
前記マッピングするステップから該第２のノードを含有するパスを除外するステップと
をさらに含む、方法。
【請求項１６】
ゲノム配列を決定するための方法であって、
コンピュータシステムにおいて、被験体のゲノム上の公知の位置における複数のヌクレオチドの同一性を受け取るステップと、
該コンピュータシステムに記憶された複数のゲノム配列から１または複数のゲノム配列を選択するステップであって、該選択された配列が、該公知の位置に該ヌクレオチドを含むステップと、
該被験体由来の試料から配列リードを受け取るステップと、
該配列リードを該選択されたゲノム配列にマッピングし、これにより、該ゲノムの少なくとも一部の配列を決定するステップと
を含む方法。
【請求項１７】
前記複数のゲノム配列を表す前記データが、それが隣接するオブジェクトのリストをそれぞれ記憶する複数のノードおよびエッジオブジェクトを含むＤＡＧであり、ここで、前記選択されたゲノム配列のそれぞれが、該ＤＡＧを通る選択されたパスを定義する、請求項１６に記載の方法。
【請求項１８】
各ノードおよびエッジオブジェクトが、１または複数の隣接するオブジェクトのリストを記憶し、ここで、前記配列リードのマッピングが、前記配列リードおよび前記選択されたパスの間に最適なアライメントを見出すことを含む、請求項１６に記載の方法。
【請求項１９】
各リストが、前記隣接するオブジェクトのメモリにおける位置に対するポインタを含み、ここで、最適なアライメントを見出すことが、多次元マトリックスを通る最高スコアリングトレースを見出すことを含む、請求項１８に記載の方法。
【請求項２０】
前記最高スコアリングトレースを見出すことが、前記コンピュータシステムを使用して、前記リードと、前記ＤＡＧにおける前記ノードおよびエッジオブジェクトの少なくとも一部との間のマッチスコアを計算し、該ＤＡＧにおける先行処理オブジェクトの後方に注目して、最適スコアを有するバックトレースを同定することを含む、請求項１９に記載の方法。
【請求項２１】
前記公知の位置における前記複数のヌクレオチドの前記同一性に基づき追加のヌクレオチドの同一性の確率を得るステップであって、該確率が、該追加のヌクレオチドのうち１種と、該公知の位置における該複数のヌクレオチドのうち１種との間の連鎖不平衡の尺度から得られるステップと、
前記最適なアライメントを見出すことにおいて該得られた確率を使用するステップと
をさらに含む、請求項１８に記載の方法。
【請求項２２】
前記有向非巡回グラフを通る少なくとも１種のパスが、少なくとも１本のヒト染色体の実質的に配列全体をもたらす、請求項１７に記載の方法。
【請求項２３】
前記有向非巡回グラフが、複数のポジションにおいてポジション当たり少なくとも２種の代替配列を表す、請求項１７に記載の方法。
【請求項２４】
前記マッピングされた配列リードをアセンブルするステップをさらに含む、請求項１１に記載の方法。
【請求項２５】
前記公知の位置における前記複数のヌクレオチドの前記同一性が、マイクロアレイアッセイの結果として受け取られる、請求項１６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願との相互参照
本出願は、２０１４年１月１０日に出願された米国仮特許出願第６１／９２５，８９２号に対する優先権の利益を主張し、この内容は参考として援用される。
【０００２】
配列表
本願は、ＥＦＳ−Ｗｅｂを介してＡＳＣＩＩフォーマットで提出された、参照によりその全体において本明細書に組み込まれる配列表を含有する。２０１５年１月８日に作成されたＡＳＣＩＩフォーマットの配列表は、ＳＢＧ−０１０−０１ＷＯ−ｓｅｑ＿ＳＴ２５と命名され、２，０３１バイトのサイズである。
【０００３】
本発明は、全般的には、ゲノム研究に関し、特に、公知の位置で同定されたヌクレオチドを使用したリードマッピングのための改善された方法に関する。
【背景技術】
【０００４】
個人の遺伝情報は、その健康および生命に関して多くを明らかにする潜在力を有する。個人の遺伝子の配列によって、がんまたは遺伝性疾患のリスク、同様にその子供が遺伝性障害を受け継ぐ可能性が明らかになる可能性がある。多数の技術が、大量の個人の遺伝データをもたらすことができるが、ヘルスケアのためにそのデータを使用することに対しては障壁がある。
【０００５】
例えば、様々な形態のＳＮＰチップ、遺伝子チップまたはマイクロアレイとしても公知の一塩基多型（ＳＮＰ）アレイは、個人のゲノム内の多数の異なる遺伝子における数多くの異なるヌクレオチド塩基の同一性をもたらすことができる。このようなアレイは、疾患関連ＳＮＰを同定し、がん細胞におけるヘテロ接合性の損失および他の体細胞変化を検出し、ハプロタイプを相決定することができる。例えば、ＬａＦｒａｍｂｏｉｓｅ、２００９年、Ｓｉｎｇｌｅ  ｎｕｃｌｅｏｔｉｄｅ  ｐｏｌｙｍｏｒｐｈｉｓｍ  ａｒｒａｙｓ：  ａ  ｄｅｃａｄｅ  ｏｆ  ｂｉｏｌｏｇｉｃａｌ，  ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｎｄ  ｔｅｃｈｎｏｌｏｇｉｃａｌ  ａｄｖａｎｃｅ、Ｎｕｃｌｅｉｃ  Ａｃｉｄｓ  Ｒｅｓ  ３７巻（１３号）：４１８１〜４１９３頁を参照されたい。しかし、ＳＮＰチップには限界がある。それらは、常には新規変異の発見に適正なツールであるとは限らず、ゲノムにおける関係を欠いている。ＳＮＰチップからの結果は、本の各頁に現れる最初の文字を伝えられることに近く、すなわちデータ点は、ある特定の誤りまたはパターンを明らかにすることができるが、ストーリー全体を提供することはできない。
ゲノムの相当な部分を次世代配列決定（ＮＧＳ）技術により配列決定して、非常に多数の短い配列リードを生成することができる。このようなリードの解析は、相当に困難な課題である。現存する方法は、典型的には、参照ゲノムへのリードのマッピングまたはｄｅ  ｎｏｖｏアセンブリの実行に関与する。データの容量のために、アライメントおよびアセンブリは、ジョブを行うために数学的ショートカットを採用する必要のあるヒューリスティックアルゴリズムによって行われる。しかし、数学的に完璧なアルゴリズムは、計算的に禁制的であるため、このような不完全は許容される。ＮＧＳリードの解析において数学的精度が犠牲になるだけでなく、現在の方法は、利用できる情報の活用が限定されている。ＮＧＳリードは多くの場合、幾分任意の参照にマッピングされ、該参照にマッチするまたはマッチしないと呼ばれ、すなわち参照が有用な標準であるという問題を全体的に提起する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】ＬａＦｒａｍｂｏｉｓｅ、２００９年、Ｓｉｎｇｌｅ  ｎｕｃｌｅｏｔｉｄｅ  ｐｏｌｙｍｏｒｐｈｉｓｍ  ａｒｒａｙｓ：  ａ  ｄｅｃａｄｅ  ｏｆ  ｂｉｏｌｏｇｉｃａｌ，  ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｎｄ  ｔｅｃｈｎｏｌｏｇｉｃａｌ  ａｄｖａｎｃｅ、Ｎｕｃｌｅｉｃ  Ａｃｉｄｓ  Ｒｅｓ  ３７巻（１３号）：４１８１〜４１９３頁
【発明の概要】
【課題を解決するための手段】
【０００７】
本発明は、同定されたヌクレオチドと一致していない潜在的マッピングまたはアセンブリを除外することにより、ゲノム内の公知の場所において同定されたヌクレオチドを使用して、該ゲノム由来の配列リードの解析をガイドする方法を提供する。リードが、複数のポジションにおいてポジション毎の複数の代替配列を表す有向非巡回グラフ（ＤＡＧ）にマッピングされる場合、同定されたヌクレオチドを含まないＤＡＧを通るパスは、リードマッピングから除外することができ、その結果、コンピュータ処理時間は、参照の無関係領域へのリードを比較して無益に費やされる必要がなくなる。計算資源におけるこのような節約は、例えば、リードが、最良のアライメントを見出すＳｍｉｔｈ−Ｗａｔｅｒｍａｎに基づくアライメントアルゴリズム等の、数学的に強固なアルゴリズムを使用して、ＤＡＧにおけるパスにアラインされることを可能にするマッピングおよびアセンブリアルゴリズムに適用することができる。ゲノム配列決定プロジェクトが、以前には不可能であったペース、適用範囲の深さおよび処理量で進むことができるように、提供される方法は、非常に多数のＮＧＳリードがマッピングまたはアセンブルされることを可能にする。
【０００８】
参照ＤＡＧは、複数の遺伝子座におけるいずれかまたはあらゆる公知のまたは推測される遺伝子型を表すことができる。結果として、配列リードは、単に限定された線形参照超のものと比較される。配列リードは、種々の公知バリアントと比較され、単一の参照へのアライメントによって生じる誤解を招く推測を回避する。複数の公知バリアントをＤＡＧ内で実証することができ、リードマッピングは、他の仕方では不可能なやり方で、公知バリアントに対するマッチの発見を含むことができる。ＤＡＧは、同じ集団または民族的帰属（ｅｔｈｎｉｃｉｔｙ）の他のメンバー由来の配列等の、特定の被験体のための天然に妥当な参照であるパスを含むことができる。ＤＡＧを通るパスは線形参照よりも良く適合するため、ＤＡＧへのマッピングは、リードアセンブリを成功させ、被験体のゲノムはそれが集団の数多くの他のメンバーに関係すると理解することができるため、結果をより有意義なものにもする。
【０００９】
例えば、ＳＮＰチップによってもたらされる被験体のゲノムにおける同定されたヌクレオチドを使用した、ＤＡＧ検索空間の限定、すなわち、ＤＡＧのフィルタリングは、より優れた結果および高速処理により、リードマッピングを迅速かつ完璧なものとする。結果として、個人のゲノム研究がよりアクセス可能なものとなり、このような研究が明らかにすることができる医学的に有意な情報は、人々の生活の改善をもたらす。
【００１０】
その上、同定されたヌクレオチド（例えば、ＳＮＰチップ由来）の使用は、アライメントの結果を改善することができる。同定されたヌクレオチドをゲノム内の他のヌクレオチドに関連付けて、データを得ることができる。例えば、多くの遺伝子座は、互いに連鎖不平衡にある。ゲノムにおける遺伝子座が同定されると（例えば、ＳＮＰチップにより）、同定された遺伝子座と連鎖不平衡にある別の遺伝子座は、該ゲノムにおけるある特定の対立遺伝子のある特定の確率を有することができる。連鎖した遺伝子座へのリードのマッピングは、アライメントアルゴリズムへの確率の取り込みを含むことができ、よって、得られたアライメントが、被験体のゲノムおよびＤＡＧ内で表される他のゲノムの間で天然の関係性を示す確率を増加させることにより、得られたアライメントを改善する。
【００１１】
ある特定の態様において、本発明は、ゲノム配列を決定するためのコンピュータシステムを提供する。本コンピュータシステムは、メモリにカップリングされたプロセッサを使用して、被験体のゲノム上の公知の位置における複数のヌクレオチドの同一性（ｉｄｅｎｔｉｔｙ）を受け取り、複数のゲノム配列から１または複数のゲノム配列を選択し、選択された配列が、公知の位置にヌクレオチドを含み、被験体由来の試料から配列リードを受け取る。本システムは、１または複数の選択されたゲノム配列に配列リードをマッピングし、これにより、ゲノムの少なくとも一部の配列を同定することができる。好ましい実施形態において、複数のゲノム配列は、ノードおよびエッジオブジェクトのうち隣接するもの（ａｄｊａｃｅｎｔ  ｏｎｅｓ  ｏｆ  ｔｈｅ  ｎｏｄｅ  ａｎｄ  ｅｄｇｅ  ｏｂｊｅｃｔｓ）のメモリにおける位置にポインタのリストをそれぞれ記憶する、複数のノードおよびエッジオブジェクトを含むＤＡＧとしてメモリに記憶される。選択されたゲノム配列のそれぞれは、ＤＡＧを通る選択されたパスを定義し、本システムは、配列リードおよび選択されたパスの間に最適なアライメントを見出すことにより、配列リードをマッピングする。最適なアライメントを見出すことは、ＤＡＧを通る最高スコアリングトレースを見出すことにより行うことができる。この最高スコアリングトレースは、リードと、ＤＡＧにおけるノードおよびエッジオブジェクトの少なくとも一部との間のマッチスコアを計算し、メモリにおけるその参照される位置からＤＡＧにおけるリード先行処理オブジェクト（ｒｅａｄ  ｐｒｅｄｅｃｅｓｓｏｒ  ｏｂｊｅｃｔ）にポインタの少なくとも一部を逆参照（ｄｅｒｅｆｅｒｅｎｃｉｎｇ）することにより見出すことができる。マッチスコアの最大和で先行処理オブジェクトを通るパスは、ＤＡＧを通る最高スコアリングトレースである。
【００１２】
一部の実施形態において、本システムは、各配列リードおよび各選択されたパスの間に最適なアライメントを見出すことにより、配列リードをマッピングする。最適なアライメントを見出すことは、多次元マトリックスを通る最高スコアリングトレースを見出すことを含むことができる。本システムを操作して、公知の位置における複数のヌクレオチドの同一性に基づき、追加のヌクレオチドの同一性の確率を得ることができ、得られた確率を最適なアライメントを見出すことにおいて使用することができる。確率は、追加のヌクレオチドのうち１種（ｏｎｅｓ  ｏｆ  ｔｈｅ  ａｄｄｉｔｉｏｎａｌ  ｎｕｃｌｅｏｔｉｄｅｓ）と、公知の位置における複数のヌクレオチドのうち１種（ｏｎｅｓ  ｏｆ  ｔｈｅ  ｐｌｕｒａｌｉｔｙ  ｏｆ  ｎｕｃｌｅｏｔｉｄｅｓ）との間の連鎖不平衡の尺度から得ることができる。
【００１３】
ある特定の実施形態において、複数のゲノム配列は、ノードおよびエッジオブジェクトのうち隣接するもののメモリにおける位置に対するポインタのリストをそれぞれ記憶する、複数のノードおよびエッジオブジェクトを含むＤＡＧとしてメモリに記憶され、選択されたゲノム配列のそれぞれは、ＤＡＧを通る選択されたパスを定義し、システムは、配列リードおよび選択されたパスの間に最適なアライメントを見出すことにより、配列リードのマッピングに操作可能である。最適なアライメントを見出すことは、リードと、ＤＡＧにおけるノードおよびエッジオブジェクトの少なくとも一部との間のマッチスコアを計算し、メモリにおけるその参照される位置からＤＡＧにおけるリード先行処理オブジェクトにポインタの少なくとも一部を逆参照することにより、ＤＡＧを通る最高スコアリングトレースを見出すことにより行うことができ、マッチスコアの最大和で先行処理オブジェクトを通るパスは、ＤＡＧを通る最高スコアリングトレースである。
【００１４】
ある特定の実施形態において、複数のゲノム配列は、複数のノードおよびエッジオブジェクトを含むＤＡＧとしてメモリに記憶され、複数のヌクレオチドの同一性は、被験体のゲノムにおける複数のＳＮＰを含み、システムは、複数のＳＮＰを含むＤＡＧを通る候補パスを同定することにより、ＳＮＰを含む１または複数のゲノム配列を選択する。一部の実施形態において、ＤＡＧは、対立遺伝子毎に単一のオブジェクトを有する、複数のゲノムにわたって相同の少なくとも１種の遺伝子座を表す。ＤＡＧをアノテートして、共存できないノード対のリストを作ることができ、システムは、複数のＳＮＰのうち１種由来の共存できないノード対のリストにおけるノードの同定、共存できないノード対のリストにおける同定されたノードと対形成する第２のノードの同定、および配列リードをマッピングする際の第２のノードを含有するパスの除外にさらに操作可能である。
【００１５】
本システムにおいて、複数のゲノム配列を表すデータは、ヌクレオチド配列を表すノードおよびノードの対を接続するエッジを含むことができ、ノードおよびエッジが、有向非巡回グラフを定義し、さらに、選択されたゲノム配列のそれぞれが、有向非巡回グラフを通る選択されたパスを定義する。好ましくは、有向非巡回グラフは、複数のポジションにおいてポジション当たり少なくとも２種の代替配列を表す。
【００１６】
一部の態様において、本発明は、被験体のゲノムにおける複数のＳＮＰに関する情報を得て、遺伝子配列を表すノードおよびノードの対を接続するエッジを含む有向非巡回データ構造（またはＤＡＧ）内で、複数のＳＮＰを含む候補パスを同定することにより、被験体の遺伝情報を決定するための方法を提供する。配列リードは、被験体のゲノムから得られ、候補パスにマッピングされる。ＤＡＧは、対立遺伝子毎に単一のノードを有する、複数のゲノムにわたって相同の少なくとも１種の遺伝子座を表すことができる。ＤＡＧをアノテートして、共存できないノード対のリストを作成することができ、本方法は、複数のＳＮＰのうち１種から、共存できないノード対のリストにおけるノードを同定するステップと、共存できないノード対のリストにおける同定されたノードと対形成した第２のノードを同定するステップと、マッピングステップから第２のノードを含有するパスを除外するステップとを含むことができる。
【００１７】
本発明の態様は、コンピュータシステムにおいて、被験体のゲノム上の公知の位置における複数のヌクレオチドの同一性を（例えば、マイクロアレイまたはＳＮＰチップから）受け取り、コンピュータシステムに記憶される複数のゲノム配列から１または複数のゲノム配列を選択することにより、ゲノム配列を決定するための方法を提供し、選択された配列は、公知の位置にヌクレオチドを含む。本方法は、被験体由来の試料から配列リードを受け取るステップと、選択されたゲノム配列に配列リードをマッピングし、これにより、ゲノムの少なくとも一部の配列を決定するステップとを含む。
【００１８】
複数のゲノム配列を表すデータは、ヌクレオチド配列を表すノードおよびノードの対を接続するエッジを有するＤＡＧとなり得る。選択されたゲノム配列のそれぞれは、ＤＡＧを通る選択されたパスを定義する。配列リードのマッピングは、配列リードおよび選択されたパスの間に最適なアライメントを見出すことにより行うことができる。
【００１９】
本方法は、公知の位置における複数のヌクレオチドの同一性に基づき、追加のヌクレオチドの同一性の確率を得るステップと、最適なアライメントを見出すことにおいて得られた確率を使用するステップとをさらに含むことができる。確率は、追加のヌクレオチドのうち１種と、公知の位置における複数のヌクレオチドのうち１種との間の連鎖不平衡の尺度から得ることができる。
【００２０】
ＤＡＧは、ゲノムスケールを含むいずれか適したスケールのものとなり得る、あるいは遺伝子または領域を表すように調整する（ｓｃａｌｅｄ）ことができる。一部の実施形態において、ＤＡＧは、ゲノムスケールＤＡＧとなることができ、少なくとも１本のヒト染色体の実質的に配列全体をもたらすＤＡＧを通る少なくとも１種のパスを含むことができる。ある特定の実施形態において、ＤＡＧは、染色体よりも小さい領域、例えば、遺伝子；遺伝子周囲の領域；オペロン；オルガネラ、細菌、ウイルスまたはプラスミド由来の染色体；大型のＳＶエレメント；等を表すスケールのものである。ＤＡＧは、複数のポジションにおいてポジション当たり少なくとも２種の代替配列を表す。ＤＡＧにマッピングされたら（またはマッピングにより）、リードをアセンブルすることができる。
【００２１】
関連する態様において、本発明は、ゲノム配列を決定するためのシステムを提供する。本システムは、メモリにカップリングされたプロセッサを含み、被験体のゲノム上の公知の位置における複数のヌクレオチドの同一性を受け取り、複数のゲノム配列から１または複数のゲノム配列を選択する（例えば、ＤＡＧ内から）ように操作可能であり、選択された配列は、公知の位置にヌクレオチドを含む。本システムを使用して、被験体由来の試料から配列リードを受け取り、１または複数の選択されたゲノム配列に配列リードをマッピングし、これによりゲノムの少なくとも一部の配列を同定することができる。本システムは、公知の位置における複数のヌクレオチドの同一性に基づき、追加のヌクレオチドの同一性の確率を得て、最適なアライメントを見出すことにおいて得られた確率を使用するようにさらに操作可能となり得る。確率は、追加のヌクレオチドのうち１種と、公知の位置における複数のヌクレオチドのうち１種との間の連鎖不平衡の尺度から得ることができる。
【図面の簡単な説明】
【００２２】
【図１】図１は、ＤＡＧを使用して、バイオインフォマティクスデータを表し操作することを図解する。
【図２】図２は、ゲノムＤＡＧの可能な１つのフォーマットを示す。
【図３】図３は、仮説上のゲノム領域における数個のポジションのＤＡＧを表す。
【図４】図４は、共存可能性（ｃｏｍｐｏｓｓｉｂｉｌｉｔｙ）に関する情報を強化したＤＡＧを示す。
【図５】図５は、ＤＡＧへの配列リードのマッピングを記す。
【図６】図６は、ＤＡＧへの配列のアライメントにおいて使用されるマトリックスを示す。
【図７】図７は、確率的情報を含むために作製したＤＡＧを示す。
【図８】図８は、図７のＤＡＧの低下バージョンを示す。
【図９】図９は、ＤＡＧの低下の結果を図解する。
【図１０】図１０は、本発明の方法を図示する。
【図１１】図１１は、ゲノムスケールＤＡＧのほんのごく一部の例を図解する。
【図１２】図１２は、ヌクレオチド情報を有するＤＡＧを示す。
【図１３】図１３は、フィルタリング後のＤＡＧを示す。
【図１４】図１４は、本発明のシステムを図解する。
【発明を実施するための形態】
【００２３】
一般に、本発明は、被験体の遺伝情報を決定するためのシステムおよび方法を提供する。被験体のゲノムにおける複数の一塩基多型（ＳＮＰ）に関する情報を得て、使用して、該ＳＮＰを含むゲノムＤＡＧを通る候補パスを同定する。次に、ＮＧＳリードを候補パスにマッピングし、相当な計算的節約資源をもたらすことができるが、これは、このような資源が、ＳＮＰ情報と一致しないパスにこのようなリードをアラインしようとする努力に費やされないためである。
【００２４】
ＤＮＡの単一の部位における変種である一塩基多型（ＳＮＰ）は、遺伝的変種の１種である。数百万種のＳＮＰが、ヒトゲノムにおいて同定された。ＳＮＰは、科学、医学および農業において多くの用途を有し、ゲノムワイド関連研究において価値あるマーカーとして機能する。例えば、Ｍａｎｏｌｉｏら、２０１０年、Ｇｅｎｏｍｅ  ｗｉｄｅ  ａｓｓｏｃｉａｔｉｏｎ  ｓｔｕｄｉｅｓ  ａｎｄ  ａｓｓｅｓｓｍｅｎｔ  ｏｆ  ｔｈｅ  ｒｉｓｋ  ｏｆ  ｄｉｓｅａｓｅ、ＮＥＪＭ  ３６３巻（２号）：１６６〜７６頁を参照されたい。とりわけ、ＳＮＰアレイは、疾患感受性を決定するためおよび個体に特異的に設計された薬物療法の有効性を測定するために使用される。各個体は、多くのＳＮＰを有する。ＳＮＰに基づく遺伝子連鎖解析を使用して、疾患遺伝子座をマッピングし、個体における疾患感受性遺伝子を決定することができる。ＳＮＰマップおよび高密度ＳＮＰチップの組合せは、複合形質を有する遺伝性疾患のマーカーとしてのＳＮＰの使用を可能にする。例えば、全ゲノム遺伝子連鎖解析は、関節リウマチ、前立腺がんおよび新生児糖尿病等の、疾患の連鎖を示す。ＳＮＰの重要性のため、国際ハップマップコンソーシアム（Ｉｎｔｅｒｎａｔｉｏｎａｌ  ＨａｐＭａｐ  Ｃｏｎｓｏｒｔｉｕｍ）その他は、ＳＮＰ遺伝子座を同定し、様々な祖先の個体におけるその遺伝子型を決定し、ゲノムにおけるその相関構造を明らかにする進行中の努力の一部である。政府のプロジェクトｄｂＳＮＰは、全ＳＮＰを包括的にカタログ作成することを目的とする公共の努力である。
【００２５】
ＳＮＰチップ（様々な形態で、マイクロアレイ、遺伝子チップ、ＤＮＡチップその他としても公知）は、多数のオリゴ（ｏｌｉｇｏ）が結合した小型のチップである。オリゴは、相補的配列のみに選択的にハイブリダイズする。オリゴは、ＳＮＰを探索するように設計される。
【００２６】
本発明の実施形態の方法は、ＳＮＰチップにより被験体に存在する対立遺伝子を同定するステップを含む。例えば、ＳＮＰチップは、複数の異なる公知の位置におけるヌクレオチドの同一性を決定することができる。いかなる対立遺伝子が被験体に存在するか決定するために、被験体由来のゲノムＤＮＡを単離し、断片化し、蛍光色素をタグ付けし、チップにアプライする。ゲノムＤＮＡ断片は、それと相補的なオリゴのみにアニールする。相補的ＤＮＡが、オリゴプローブに結合すると、蛍光レポーターが、イメージング機器を介して検出可能となる。よって、ＳＮＰチップを使用して、異種性試料における特異的ＤＮＡ配列を同定することができる。例えば、ＳＮＰチップは、被験体のゲノムＤＮＡのバックグラウンドに対し特定の対立遺伝子の存在を検出することができる。コンピュータは、蛍光タグのポジションを読み取り、オリゴによって探索されている特異的な公知の位置におけるヌクレオチドを同定する。
【００２７】
ＳＮＰチップは、数十万種のオリゴを収容することができる。相対的濃度非依存および最小のクロスハイブリダイゼーションを達成するために、複数のデータベースの未加工の配列およびＳＮＰをスキャンして、プローブを設計する。アレイにおける各ＳＮＰを異なるプローブと照合する。
【００２８】
その上、ＳＮＰを使用して、がんにおける遺伝子異常を研究することもできる。例えば、ＳＮＰアレイを使用して、変異が正常に機能している対立遺伝子の損失をもたらす、ヘテロ接合性の損失（ＬＯＨ）を研究することができる。腫瘍サプレッサー遺伝子のＬＯＨは、がんに関連する。
【００２９】
ＳＮＰアレイは、病的コピーニュートラルＬＯＨ（片親性ダイソミーまたは遺伝子変換とも呼ばれる）を検出することができる。コピーニュートラルＬＯＨは、対立遺伝子不均衡の一形態である。コピーニュートラルＬＯＨにおいて、一方の親由来の１個の対立遺伝子または染色体全体が失われる。この問題は、他方の親の対立遺伝子の重複をもたらす。ＬＯＨは、多くのヒトがんにおいて非常に一般的であるため、ＳＮＰチップは、がん診断のために潜在的に価値がある。
【００３０】
高密度ＳＮＰアレイにおいて、数十万種のプローブを小型のチップ上にアレイ形成し、多くのＳＮＰが同時に照合されることを可能にする。現在、市販のアレイプラットフォームは、１回のアッセイで、個体における約百万種のＳＮＰを遺伝子型決定することができる。
【００３１】
ＡｆｆｙｍｅｔｒｉｘおよびＩｌｌｕｍｉｎａ  ＳＮＰアレイ等の製品は、異なる化学を使用して作用するが、典型的には、共通した側面を有する。一般に、高密度ＳＮＰチップは、数十万種の特有のヌクレオチドプローブ配列を含有するアレイへの断片化した一本鎖ＤＮＡのハイブリダイゼーションを活用する。ＡｆｆｙｍｅｔｒｉｘおよびＩｌｌｕｍｉｎａアレイの両方に対し、特殊装置は、ハイブリダイゼーション後に各プローブおよびその標的に関連するシグナル強度を測定する。このような未加工の強度測定値の解析は、ＳＮＰ遺伝子型の推測を生じる。
【００３２】
Ａｆｆｙｍｅｔｒｉｘ  Ｈｕｍａｎ  ＳＮＰ  ５．０  ＧｅｎｅＣｈｉｐは、５００，０００種のヒトＳＮＰにわたって遺伝子型決定することができるゲノムワイドアッセイを行う。それぞれ２５−ｎｔ長のプローブのセットにより、全ＳＮＰ部位を照合する。プローブは、ＳＮＰ部位を有するＤＮＡ配列の部分と相補的または極めてほとんど相補的となるように設計される。Ｈｕｍａｎ  ＳＮＰ  Ａｒｒａｙ  ６．０における各ＳＮＰは、６または８種の完全マッチプローブ  −  ２個の対立遺伝子のそれぞれについての同じプローブの３または４種の複製物によって照合される。したがって、ＳＮＰ毎の強度データは、反復測定値の２セットからなる。さらに、ＳＮＰプローブセットは、ほとんど百万コピー数のプローブにより増大され、これは、ＳＮＰを持たないゲノムの領域を照合することを意味するが、むしろコピー数に関して多型となり得る。
【００３３】
Ａｆｆｙｍｅｔｒｉｘ製の６．０アレイは、Ｂｉｒｄｓｅｅｄと呼ばれるＡｆｆｙｍｅｔｒｉｘ製のアルゴリズムにより解析することができる。未加工の、正規化されたプローブ強度から、Ｂｉｒｄｓｅｅｄは、シグナルの対を得る。Ｂｉｒｄｓｅｅｄは、ＳＮＰ毎に遺伝子型をもたらす期待値最大化（ＥＭ）手順を使用して、被験試料由来のシグナルを二次元ガウス混合モデルに適合させ、そのクラスターへのコールの近接性（ｃａｌｌ’ｓ  ｐｒｏｘｉｍｉｔｙ）に基づき遺伝子型毎の信頼スコアを得る。
【００３４】
その最新バージョンのＩｌｌｕｍｉｎａ  ＢｅａｄＡｒｒａｙは、百万種の遺伝子座を照合する。単一のＨｕｍａｎＨａｐ１Ｍアレイ由来の未加工ファイルは、約２百万個のデータ点、概念的には、約百万対（Ｘ１，Ｙ１）、（Ｘ２，Ｙ２）、・・・、（ＸＮ，ＹＮ）からなる。Ｉｌｌｕｍｉｎａソフトウェアは、複数のアレイに頼ることなく、ＸおよびＹ座標のシフト、スケーリングおよび回転に適切な因数を捕捉するパラメータを使用して、各試料において個々に内部正規化を実行し、外れ値除去後に、対それ自体を使用して推測される。目標は、各ＳＮＰに未加工の対立遺伝子特異的コピー測定値の対を生成することである。また、現在のバージョンのＡｆｆｙｍｅｔｒｉｘアレイと同様に、ＨｕｍａｎＨａｐ１Ｍも、非ＳＮＰヒト遺伝的変種を照合することを意味するコピー数プローブを含む。
【００３５】
一部の実施形態において、本発明の方法は、被験体から試料を収集するステップと、その試料においてＳＮＰチップを使用して、ヌクレオチドを同定するステップとを含む。一般に、ＳＮＰチップは、バリアントまたは変異の発見が重要であり、ＳＮＰチップそれ自体がバリアントに関する情報を生じる文脈において使用することができる。いくつかの点で、ＳＮＰチップは、バリアントに関するいくつかの事実が得られる（複雑で極端な）ブラックボックスのようなものである。これらの事実を考慮すると、存在していてもしていなくてもよい他のバリアントに関する結論を含む、いくつかの結論を導くことができる。本発明の方法は、いずれかの形態の変異検出により一般に操作可能であるが、ＳＮＰチップは、変異情報を得る仕方の１つをもたらす。変異情報を得る他の方法は、制限酵素断片長多型および同様の研究、マルチプレックスライゲーションプローブ依存性増幅、非チップベースのハイブリダイゼーションアッセイその他を含む。ＳＮＰチップおよび他のこのようなアッセイは、変異検出および同定のためのツールをもたらす。これらのアッセイを使用して、ゲノム内の公知ポジションにおけるある特定の対立遺伝子またはヌクレオチドの同一性を決定することができる。本発明は、被験体のゲノム内の公知ポジションにおけるヌクレオチドの同一性を使用して、ＮＧＳリードのマッピング、アセンブリまたは解析を補助する方法を提供する。
【００３６】
ある特定の実施形態において、ＮＧＳリードは、被験体由来の試料において配列決定を行うことにより得られる。配列決定は、当技術分野で公知のいずれかの方法によることができる。全般的には、Ｑｕａｉｌら、２０１２年、Ａ  ｔａｌｅ  ｏｆ  ｔｈｒｅｅ  ｎｅｘｔ  ｇｅｎｅｒａｔｉｏｎ  ｓｅｑｕｅｎｃｉｎｇ  ｐｌａｔｆｏｒｍｓ：  ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｉｏｎ  Ｔｏｒｒｅｎｔ，  Ｐａｃｉｆｉｃ  Ｂｉｏｓｃｉｅｎｃｅｓ  ａｎｄ  Ｉｌｌｕｍｉｎａ  ＭｉＳｅｑ  ｓｅｑｕｅｎｃｅｒｓ、ＢＭＣ  Ｇｅｎｏｍｉｃｓ  １３巻：３４１頁を参照されたい。ＤＮＡ配列決定技法は、標識されたターミネーターまたはプライマーおよびスラブまたはキャピラリーにおけるゲル分離を使用した古典的ジデオキシ配列決定反応（サンガー法）、可逆的に終結された標識ヌクレオチドを使用した合成による配列決定、パイロシーケンシング、４５４シーケンシング、Ｉｌｌｕｍｉｎａ／Ｓｏｌｅｘａシーケンシング、標識オリゴヌクレオチドプローブのライブラリーへの対立遺伝子特異的ハイブリダイゼーション、標識クローンのライブラリーへの対立遺伝子特異的ハイブリダイゼーションと、続くライゲーション、重合ステップにおける標識ヌクレオチドの取り込みのリアルタイムモニタリングを使用した合成による配列決定、ポロニーシーケンシング、ならびにＳＯＬｉＤシーケンシングを含む。分離された分子は、ポリメラーゼまたはリガーゼを使用した連続的または単一の伸長反応と、プローブのライブラリーとの単一または連続的差次的ハイブリダイゼーションにより配列決定することができる。ＮＧＳ技術が、疾患関連ＳＮＰを直接的に検出する際に不十分な仕事しか為さなかったことが見出されたことに留意されたい。例えば、Ｗａｎｇら、２０１１年、Ｎｅｘｔ  ｇｅｎｅｒａｔｉｏｎ  ｓｅｑｕｅｎｃｉｎｇ  ｈａｓ  ｌｏｗｅｒ  ｓｅｑｕｅｎｃｅ  ｃｏｖｅｒａｇｅ  ａｎｄ  ｐｏｏｒｅｒ  ＳＮＰ−ｄｅｔｅｃｔｉｏｎ  ｃａｐａｂｉｌｉｔｙ  ｉｎ  ｔｈｅ  ｒｅｇｕｌａｔｏｒｙ  ｒｅｇｉｏｎｓ、Ｓｃｉｅｎｔｉｆｉｃ  Ｒｅｐｏｒｔｓ  １巻：５５頁を参照されたい。
【００３７】
使用することができる配列決定技法は、例えば、商標ＧＳ  ＪＵＮＩＯＲ、ＧＳ  ＦＬＸ＋で販売される合成による配列決定（ｓｅｑｕｅｎｃｉｎｇ−ｂｙ−ｓｙｎｔｈｅｓｉｓ）システムおよび４５４  Ｌｉｆｅ  Ｓｃｉｅｎｃｅｓ、Ｒｏｃｈｅ社（Ｂｒａｎｆｏｒｄ、ＣＴ）による４５４  ＳＥＱＵＥＮＣＩＮＧの使用を含み、その内容全体が本明細書に参照として援用される、Ｍａｒｇｕｌｉｅｓ，  Ｍ．ら、Ｇｅｎｏｍｅ  ｓｅｑｕｅｎｃｉｎｇ  ｉｎ  ｍｉｃｒｏ−ｆａｂｒｉｃａｔｅｄ  ｈｉｇｈ−ｄｅｎｓｉｔｙ  ｐｉｃｏｔｉｔｅｒ  ｒｅａｃｔｏｒｓ、Ｎａｔｕｒｅ、４３７巻：３７６〜３８０頁（２００５年）；米国特許第５，５８３，０２４号；米国特許第５，６７４，７１３号；および米国特許第５，７００，６７３号によって記載されている。４５４シーケンシングは、２ステップを包含する。このようなシステムの第１のステップにおいて、ＤＮＡは、およそ３００〜８００塩基対の断片へと剪断され、この断片は平滑断端である。次に、オリゴヌクレオチドアダプタをこの断片の末端にライゲーションする。アダプタは、断片の増幅および配列決定のためのプライマーとして機能する。断片は、例えば、５’−ビオチンタグを含有するＡｄａｐｔｏｒ  Ｂを使用して、ＤＮＡ捕捉ビーズ、例えば、ストレプトアビジンコーティングされたビーズへと結合することができる。ビーズに結合した断片は、油−水エマルションの液滴内でＰＣＲ増幅される。結果は、各ビーズにおけるクローン的に増幅されたＤＮＡ断片の複数のコピーである。第２のステップにおいて、ビーズは、ウェル（ピコリットルサイズの）において捕捉される。パイロシーケンシングは、各ＤＮＡ断片において並列して行われる。１または複数のヌクレオチドの付加は、配列決定機器におけるＣＣＤカメラによって記録される光シグナルを生じる。シグナル強度は、取り込まれたヌクレオチドの数に比例する。パイロシーケンシングは、ヌクレオチド付加により放出されるピロホスフェート（ＰＰｉ）を利用する。ＰＰｉは、アデノシン５’ホスホスルフェートの存在下でＡＴＰスルフリラーゼによりＡＴＰへと変換される。ルシフェラーゼは、ＡＴＰを使用して、ルシフェリンをオキシルシフェリンへと変換し、この反応は、検出および解析される光を生じる。
【００３８】
使用することができるＤＮＡ配列決定技法の別の例は、Ｌｉｆｅ  Ｔｅｃｈｎｏｌｏｇｉｅｓ  Ｃｏｒｐｏｒａｔｉｏｎ（Ｃａｒｌｓｂａｄ、ＣＡ）製のＡｐｐｌｉｅｄ  ＢｉｏｓｙｓｔｅｍｓによるＳＯＬｉＤ技術である。ＳＯＬｉＤシーケンシングにおいて、ゲノムＤＮＡを断片へと剪断し、この断片の５’および３’端にアダプタを結合して、断片ライブラリーを作製する。あるいは、断片の５’および３’端にアダプタをライゲーションし、この断片を環状化し、この環状化された断片を消化して、内部アダプタを作製し、得られた断片の５’および３’端にアダプタを結合して、メイトペアライブラリー（ｍａｔｅ−ｐａｉｒｅｄ  ｌｉｂｒａｒｙ）を作製することにより、内部アダプタを導入することができる。次に、クローナルビーズ集団は、ビーズ、プライマー、鋳型およびＰＣＲ構成成分を含有するマイクロリアクタにおいて調製される。ＰＣＲ後に、鋳型を変性し、ビーズを富化して、伸長された鋳型を有するビーズを分離する。選択されたビーズにおける鋳型は、スライドガラスへの結合を可能にする３’修飾に付される。特異的フルオロフォアによって同定される中央決定塩基（ｃｅｎｔｒａｌ  ｄｅｔｅｒｍｉｎｅｄ  ｂａｓｅ）（または塩基の対）による部分的にランダムなオリゴヌクレオチドの連続的ハイブリダイゼーションおよびライゲーションにより、配列を決定することができる。色が記録されたら、ライゲーションされたオリゴヌクレオチドを除去し、次にプロセスを反復する。
【００３９】
使用することができるＤＮＡ配列決定技法の別の例は、例えば、Ｌｉｆｅ  Ｔｅｃｈｎｏｌｏｇｉｅｓ（Ｓｏｕｔｈ  Ｓａｎ  Ｆｒａｎｃｉｓｃｏ、ＣＡ）のＩｏｎ  Ｔｏｒｒｅｎｔにより商標ＩＯＮ  ＴＯＲＲＥＮＴで販売されるシステムを使用したイオン半導体シーケンシングである。イオン半導体シーケンシングは、例えば、これらそれぞれの内容全体が本明細書に参照として援用される、Ｒｏｔｈｂｅｒｇら、Ａｎ  ｉｎｔｅｇｒａｔｅｄ  ｓｅｍｉｃｏｎｄｕｃｔｏｒ  ｄｅｖｉｃｅ  ｅｎａｂｌｉｎｇ  ｎｏｎ−ｏｐｔｉｃａｌ  ｇｅｎｏｍｅ  ｓｅｑｕｅｎｃｉｎｇ、Ｎａｔｕｒｅ  ４７５巻：３４８〜３５２頁（２０１１年）；米国特許出願公開第２００９／００２６０８２号、同第２００９／０１２７５８９号、同第２０１０／００３５２５２号、同第２０１０／０１３７１４３号、同第２０１０／０１８８０７３号、同第２０１０／０１９７５０７号、同第２０１０／０２８２６１７号、同第２０１０／０３００５５９号、同第２０１０／０３００８９５号、同第２０１０／０３０１３９８号および同第２０１０／０３０４９８２号に記載されている。イオン半導体シーケンシングにおいて、ＤＮＡは、およそ３００〜８００塩基対の断片へと剪断され、この断片は平滑断端である。次に、オリゴヌクレオチドアダプタが、この断片の末端にライゲーションされる。アダプタは、断片の増幅および配列決定のためのプライマーとして機能する。断片は、表面に結合することができ、断片を個々に分解できるような分解能で結合する。１または複数のヌクレオチドの付加は、プロトン（Ｈ＋）を放出し、このシグナルは、配列決定機器において検出および記録される。シグナル強度は、取り込まれたヌクレオチドの数に比例する。
【００４０】
使用することができる配列決定技術の別の例は、Ｉｌｌｕｍｉｎａシーケンシングである。Ｉｌｌｕｍｉｎａシーケンシングは、フォールドバック（ｆｏｌｄ−ｂａｃｋ）ＰＣＲおよびアンカープライマーを使用した固体表面におけるＤＮＡの増幅に基づく。ゲノムＤＮＡが断片化され、この断片の５’および３’端にアダプタが付加される。フローセルチャネルの表面に結合したＤＮＡ断片は、伸長およびブリッジ増幅される。断片は二本鎖となり、この二本鎖分子は変性される。複数サイクルの固相増幅と、続く変性は、フローセルの各チャネルにおける同じ鋳型のおよそ１，０００コピーの一本鎖ＤＮＡ分子の数百万個のクラスターを作製することができる。プライマー、ＤＮＡポリメラーゼおよび４種のフルオロフォア標識された可逆的に終結するヌクレオチドを使用して、連続的配列決定を行う。ヌクレオチド取り込み後に、レーザーを使用してフルオロフォアを励起し、画像を捕捉し、第１の塩基の同一性を記録する。３’ターミネーターおよび各取り込まれた塩基由来のフルオロフォアを除去し、取り込み、検出および同定ステップを反復する。この技術に従った配列決定は、これらそれぞれ全体が本明細書に参照として援用される、米国特許出願公開第２０１１／０００９２７８号、米国特許出願公開第２００７／０１１４３６２号、米国特許出願公開第２００６／００２４６８１号、米国特許出願公開第２００６／０２９２６１１号、米国特許第７，９６０，１２０号、米国特許第７，８３５，８７１号、米国特許第７，２３２，６５６号、米国特許第７，５９８，０３５号、米国特許第６，３０６，５９７号、米国特許第６，２１０，８９１号、米国特許第６，８２８，１００号、米国特許第６，８３３，２４６号および米国特許第６，９１１，３４５号に記載されている。
【００４１】
使用することができる配列決定技術の別の例として、Ｐａｃｉｆｉｃ  Ｂｉｏｓｃｉｅｎｃｅｓ（Ｍｅｎｌｏ  Ｐａｒｋ、ＣＡ）の単一分子、リアルタイム（ＳＭＲＴ）技術が挙げられる。ＳＭＲＴにおいて、４種のＤＮＡ塩基のそれぞれは、４種の異なる蛍光色素のうち１種に結合する。これらの色素は、ホスホ結合（ｐｈｏｓｐｈｏｌｉｎｋｅｄ）される。単一のＤＮＡポリメラーゼは、ゼロモード導波路（ＺＭＷ）の底で、鋳型一本鎖ＤＮＡの単一分子により固定化される。ＺＭＷは、ＺＭＷの内外に迅速に拡散する（マイクロ秒単位で）蛍光ヌクレオチドのバックグラウンドに対し、ＤＮＡポリメラーゼによる単一のヌクレオチドの取り込みの観察を可能にする閉じ込め構造である。成長中の鎖へとヌクレオチドを取り込むには、数ミリ秒を要する。この時間内に、蛍光標識が励起され、蛍光シグナルを生成し、蛍光タグが切断除去される。色素の相当する蛍光の検出は、いずれの塩基が取り込まれたかを示す。このプロセスを反復する。
【００４２】
使用することができる配列決定技法の別の例は、ナノポアシーケンシングである。ＳｏｎｉおよびＭｅｌｌｅｒ、２００７年、Ｃｌｉｎ  Ｃｈｅｍ  ５３巻：１９９６〜２００１頁を参照されたい。ナノポアは、１ナノメートルオーダーの直径の小孔である。導電性流体におけるナノポアの浸漬と、これを通した電位の印加は、ナノポアを通るイオンの伝導による僅かな電流を生じる。流れる電流の量は、ナノポアのサイズに対し感受性である。ＤＮＡ分子が、ナノポアを通過する際に、ＤＮＡ分子における各ヌクレオチドが、異なる程度までナノポアを塞ぐ。よって、ＤＮＡ分子がナノポアを通過する際にナノポアを通る電流の変化は、ＤＮＡ配列の読み取りを表す。
【００４３】
配列決定は、複数のリードを作製する。リードは一般に、約６００または７００塩基未満の長さのヌクレオチドデータの配列を含み、本発明の方法は、例えば、＜１５０塩基またはさらには５０未満ならびに、７００超、例えば、数千塩基長のリードを含む、いずれかの長さのリードまたは配列情報に適用できる。典型的には、ＮＧＳリードは、参照にマッピングされる、あるいはｄｅ  ｎｏｖｏアセンブルされ、解析される。本発明の方法は、ゲノム有向非巡回グラフ（ＤＡＧ）または同様のデータ構造である参照にＮＧＳリードをマッピングするステップを含む。ゲノムＤＡＧは、参照データならびに入ってくる配列リードを表すことができる。このようなデータ構造において、ヒトゲノム由来の特色（例えば、配列およびサブシーケンス）は、エッジによって接続されるノードとして表される。
【００４４】
本発明の態様は、１種または複数の公知の参照由来の配列を含むＤＡＧの創出に関する。ＤＡＧは、グラフとして提示することができるデータと、データを提示するグラフを指すものと本技術分野において理解されている。本発明は、バイオインフォマティクス処理またはグラフとしての提示のためのコンピュータシステムにより読み取ることができるデータとしてＤＡＧを保存するための方法を提供する。ＤＡＧは、例えば、グラフのための構文で構築された言語、グラフを目的とした汎用マークアップ言語などにおいて、ノードおよびエッジのリスト、行列もしくは行列を表す表、アレイのアレイまたは行列を表す同様の可変構造を含むいずれか適したフォーマットでセーブすることができる。
【００４５】
一部の実施形態において、ＤＡＧは、ノードおよびエッジのリストとして保存される。かかる方法の１つは、全ノードを含むテキストファイルを作成することであり、各ノードにＩＤを割り当て、全エッジはそれぞれが、開始および終了ノードのノードＩＤを有する。よって、例えば、ＤＡＧが、２つの文（「Ｓｅｅ  Ｊａｎｅ  ｒｕｎ」および「Ｒｕｎ，  Ｊａｎｅ  ｒｕｎ」）について作成される場合、大文字と小文字を区別しない（ｃａｓｅ−ｉｎｓｅｎｓｉｔｉｖｅ）テキストファイルを作成することができる。いずれかの適したフォーマットを使用することができる。例えば、テキストファイルは、カンマ区切り値を含むことができる。このフォーマットにおいて将来の参照のためにこのＤＡＧを「Ｊａｎｅ」と命名すると、ＤＡＧ「Ｊａｎｅ」は、次の通りに読み取ることができる：１  ｓｅｅ，２  ｒｕｎ，３  ｊａｎｅ，４  ｒｕｎ，１−３，２−３，３−４。当業者であれば、この構造が、ゲノム配列に適用できることを容易に認められる。
【００４６】
ある特定の実施形態において、ＤＡＧは、Ｎ×Ｎ行列における（ｉ，ｊ）エントリが、ノードｉおよびノードｊが接続されていることを表示する行列（またはアレイのアレイまたは行列を表す同様の可変構造）を表す表として保存される（Ｎは、ゲノム上の順序でノードを含有するベクトルである）。ＤＡＧが非巡回となるには、あらゆる非ゼロエントリが、対角を上回ることを単純に必要とする（ノードが、ゲノム上の順序で表されていると仮定）。バイナリーの場合、０エントリは、ノードｉからノードｊへのエッジが存在しないことを表し、１エントリは、ｉからｊへのエッジを表す。当業者であれば、行列構造が、０〜１以外の値をエッジに関連付けることが可能であることを認める。例えば、任意のエントリは、世界中の観察されたデータの何らかの天然の品質を反映する重みまたは使用された回数を示す数値であり得る。行列は、表または線形の一連の行（例えば、まず行１、続いてセパレーターなど）としてテキストファイルに書き込むことができ、それによって、単純な直列化構造を提供する。
【００４７】
行列ＤＡＧを直列化する有用な方法の１つは、ノードの定義後に、エントリにカンマ区切り値を使用することである。このフォーマットを使用して、ＤＡＧ「Ｊａｎｅ」は、上述と同じノード定義と、続く行列エントリを含む。このフォーマットは、次の通りに読み取ることができる：
１  ｓｅｅ，２  ｒｕｎ，３  ｊａｎｅ，４  ｒｕｎ
，，１，＼，，１，＼，，，１＼，，，
ゼロ（０）のエントリは単純に省略されており、「＼」は改行文字である。
【００４８】
本発明の実施形態は、グラフのための構文で構築された言語におけるＤＡＧの保存を含む。例えば、Ｇｒａｐｈｖｉｚとして公知のグラフ視覚化ソフトウェアパッケージを備えたＤＯＴ言語は、補助的情報を有するＤＡＧの保存に使用することができ、Ｇｒａｐｈｖｉｚウェブサイトから入手できる多数のツールを使用してグラフィックファイルフォーマットに変換することができるデータ構造を提供する。Ｇｒａｐｈｖｉｚは、オープンソースのグラフ視覚化ソフトウェアである。グラフ視覚化は、アブストラクトグラフおよびネットワークの略図として構造情報を表す方法である。これは、ネットワーク、バイオインフォマティクス、ソフトウェアエンジニアリング、データベースおよびウェブデザイン、機械学習ならびに他の技術領域のための視覚インターフェースにおける用途を有する。Ｇｒａｐｈｖｉｚレイアウトプログラムは、単純なテキスト言語におけるグラフの記述を採用し、ウェブページのための画像およびスケーラブルベクターグラフィックス（ｓｃａｌａｂｌｅ  ｖｅｃｔｏｒ  ｇｒａｐｈｉｃｓ）；他の文書における包含のためのＰＤＦもしくはＰｏｓｔｓｃｒｉｐｔ；または対話型グラフブラウザにおけるディスプレイなど、有用なフォーマットで略図を作成する。
【００４９】
関連する実施形態において、ＤＡＧは、グラフを目的とする汎用マークアップ言語で保存される。上述の線形テキストファイルまたはカンマ区切り行列の記述に従って、当業者であれば、ＸＭＬなどの言語を使用（拡張）して、ノードおよびそのヘッダーまたはＩＤ、エッジ、重みなどを定義する標識（マークアップ）を作成することができることを認識する。しかし、ＤＡＧは、構造化および保存され、本発明の実施形態は、エクソンおよびイントロンなどの特徴を表すためのノードの使用に関与する。これは、ＲＮＡ−Ｓｅｑリードを解析し、アイソフォームを発見、同定および表すための有用なツールを提供する。
【００５０】
好ましい実施形態において、ゲノムグラフ表現のコアエレメントおよび操作ルーチン（ｍａｎｉｐｕｌａｔｉｏｎ  ｒｏｕｔｉｎｅ）をもたらすライブラリーが開発される。例えば、ライブラリーエレメントは、Ｃ＋＋等の、低レベルメモリ操作をもたらす言語で開発し、コンパイルしてバイナリーエレメントをもたらすことができる。ゲノムＤＡＧは、互いにリンクされたエッジオブジェクトおよび頂点オブジェクトのセットとして表すことができる。
【００５１】
グラフを表すために、頂点およびエッジが物理的オブジェクトとして記憶された、隣接リストを使用することができる。頂点またはエッジは、それが隣接するエッジ／頂点のリストを記憶する。ある特定の実施形態において、ヌクレオチド配列およびメタデータは、エッジオブジェクトにおいて記憶される。隣接リストの使用は、ローカルグラフトラバーサル（ｌｏｃａｌ  ｇｒａｐｈ  ｔｒａｖｅｒｓａｌ）を単純化する。隣接リストは、ゲノムＤＡＧを表すために非常に効率的な仕方であると判明する。ゲノムスケール参照ＤＡＧは、コンピュータ実行可能命令を使用して実装されると、効率的隣接リストを作成するために処理するハードウェアメモリの明細を効果的に活用することができる。例えば、ゲノムスケールゲノム参照ＤＡＧ（ｇｅｎｏｍｉｃ−ｓｃａｌｅ  ｇｅｎｏｍｉｃ  ｒｅｆｅｒｅｎｃｅ  ＤＡＧ）の実装は、ハードウェアレベルから隣接するエッジ／頂点オブジェクトにネイティブポインタを実際にコールすることができる。ライブラリーエレメントは、非常に小さいメモリフットプリントを維持しつつ、グラフにおけるｋ−ｍｅｒ（配列断片）の効率的検索のためにハッシュ表および検索アルゴリズムを含むことができる。ハッシュ表の使用により、ルックアップの平均コストは、表において記憶されるエレメントの数とは独立的となるように作製することができる。その上、ハッシュ表を実装して、エントリーの任意挿入または削除を可能にすることができる。ポインタの使用は、ゲノムＤＡＧを通るパスを横断して、配列ストリングを取り出すまたはアライメントを行うための操作（ｏｐｅｒａｔｉｏｎ）を有意に改善する（この横断操作は、共通した特性を有する）。
【００５２】
好ましい実施形態において、ポインタまたはネイティブポインタは、メモリにおける物理的位置を指すが、ポインタアクセス企図データ（ｐｏｉｎｔｅｒ  ａｃｃｅｓｓｅｓ  ｉｎｔｅｎｄｅｄ  ｄａｔａ）も逆参照するという点において、メモリアドレスとして操作可能である。すなわち、ポインタは、メモリ内のどこかで記憶されるデータの参照である；このデータを得ることは、ポインタを逆参照することである。ポインタを他の種類の参照から分離する特色は、ポインタの値が、低レベルまたはハードウェアレベルでメモリアドレスとして解釈されるということである。記載されているグラフゲノムエンジン（ｇｒａｐｈ  ｇｅｎｏｍｅ  ｅｎｇｉｎｅ）のスピードおよび効率は、全ゲノムの短いリードアライメントが、オフザシェルフのデスクトップシステムを使用して、数千種の試料由来のバリアントデータを含有するゲノムスケールゲノム参照ＤＡＧにおいて作製されることを可能にする。このようなグラフ表現は、高速ランダムアクセス、修飾およびデータ検索のための手段を提供する。ライブラリーは、ユニバーサルグラフゲノム座標系（ｕｎｉｖｅｒｓａｌ  ｇｒａｐｈ  ｇｅｎｏｍｅ  ｃｏｏｒｄｉｎａｔｅ  ｓｙｓｔｅｍ）を含み支持することもできる。グラフ表現の緊密さは、全ヒトゲノムが、ｄｂＳＮＰ等の典型的バリアントデータベース由来のバリアントと共に、現代の消費者グレードコンピュータシステムの限定内で保持および使用されることを可能にする。
【００５３】
一部の実施形態において、高速ランダムアクセスが支持され、全エレメントが、その隣接するエレメントに対し直接的ポインタを含有するという点において、インデックス・フリー隣接性においてグラフオブジェクト記憶が実装され（例えば、参照として援用される米国特許出願公開第２０１４／０２８０３６０号および米国特許出願公開第２０１４／０２７８５９０号に記載）、これは、インデックスルックアップを不必要にし、トラバーサル（例えば、本明細書に記載されている修飾されたＳＷアライメントアルゴリズムにおいて為される）を非常に迅速にする。インデックス・フリー隣接性は、データ検索のために参照する低レベルまたはハードウェアレベルのメモリ（アライメントにおいて要求される場合の、特に、本明細書に記載されている修飾された多次元Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアライメントにおけるスピード増加に関して生じる場合の）の別の例である。特に、インデックス・フリー隣接性は、エレメント内に含有されるポインタが、メモリにおける物理的位置の実際の（ｉｎ−ｆａｃｔ）参照となるように実装することができる。
【００５４】
ネイティブポインタ等の、アドレスする物理的メモリを使用する技術的実装は、別々のインデックス表または他の介在するルックアップステップの要件なしで、このような軽量様式でデータにアクセスおよび使用することができるため、所定のコンピュータ、例えば、いずれか現代の消費者グレードのデスクトップコンピュータの性能は、ゲノムスケールＤＡＧ（すなわち、完全ヒトゲノムのみならず、ｄｂＳＮＰ等の、データベースに表される該ゲノムにおけるあらゆる変種または１種もしくは複数種の完全ゲノムの再配列決定によって発見されたあらゆる変種も含む参照構造）の完全操作を可能にするように拡張される。よって、ネイティブポインタまたはインデックス・フリー隣接性をもたらす他の実装によるオブジェクトのライブラリーを使用したグラフエレメント（例えば、ノードおよびエッジ）を記憶すること  −  すなわち、メモリにおける物理的位置にポインタを逆参照することによりデータが取り出される実施形態  −  は、特定の仕方でコンピュータの物理的メモリを使用するため、ゲノム情報の記憶、検索およびアライメントをもたらす技術の能力を実際に改善する。
【００５５】
特異的フォーマットは、ＤＡＧの記憶に必要とされないが、図１および図２は、図解に有用な簡便かつコンパクトな１つのフォーマットを図解するために示されている（好ましい実施形態において、グラフオブジェクトが、トラバーサルおよびアライメントのスピードを上げるために別々に記憶されるメタデータを有するインデックス・フリー隣接性により記憶されることを想起）。下の図解において、例示的ＤＡＧは、グラフとして示され記されているが、グラフとしてのＤＡＧを、コンピュータメモリまたはテキスト文書におけるデータ構造に直接的に翻訳し、戻してよいことが認められよう。
【００５６】
図１は、バイオインフォマティクスデータを表し、操作するためのＤＡＧ  １０１の使用を図解する。配列。ＤＡＧ  １０１の内容を明らかにするために、図１は、仮説上の配列のセットの線形リストも含み、該セットのそれぞれは、ＤＡＧ  １０１を通るパスである。仮説上の公表された参照（これは、例えば、「ヒトゲノム」に寄与した、ニューヨーク州バッファロー（Ｂｕｆｆａｌｏ、ＮＹ）の人物由来の実際のゲノムＤＮＡであり得る）が含まれ、対立遺伝子１を表す：
５’−ＣＣＣＡＧＡＡＣＧＴＴＧＣＡＴＣＧＴＡＧＡＣＧＡＧＴＴＴＣＡＧＣ−３’（配列番号１）
対立遺伝子１から１５ｂｐインデルによって変動する、第２の対立遺伝子が含まれる（対立遺伝子２）：
【化１】
2017510871.tif 000003
（配列番号２）
第３の対立遺伝子（対立遺伝子３）も含まれ、これは、対立遺伝子２由来のＡＣが対立遺伝子３におけるＧＧと推定上相同であるインデルの中央の多型以外は対立遺伝子２にマッチする：
【化２】
2017510871.tif 000004
（配列番号３）
被験体由来の仮説上配列リードが含まれる：
５’−ＴＴＧＣＴＡＴＧＣＡＧＧＡＡＧＧＧＡＣＡＴＣＧ−３’（配列番号４）
【００５７】
描写されているシナリオにおいて、被験体は、ＧＧ多型を有する。配列リードが、公表された参照ゲノムとアラインされる場合、ＧＧ多型が、対立遺伝子２と比べて２個の連続した置換を表したことは発見されないことになる。その代わりに、多くの現存するアライメントまたはアセンブリアルゴリズムは、配列リードおよび公表された参照の間に十分なアライメントを見出さず、さらには、品質判定基準を満たさないとしてこのリードを廃棄し得る。
【００５８】
本発明の方法において、ＤＡＧ  １０１が構築される。ノード１は、５’−ＣＣＣＡＧＡＡＣＧＴＴＧ−３’（配列番号５）として具体化される。ノード２は、５’−ＣＡＴＣＧＴＡＧＡＣＧＡＧＴＴＴＣＡＧＣＡＴＴ−３’（配列番号６）として作成される。ノード３は、ＣＴＡＴＧＣＡである。ノード４は、ＡＡＧＧＧＡである。ノード５は、ＡＣであり、ノード６は、ＧＧである。一部の実施形態において、ＤＡＧへのリードのマッピングが、ＤＡＧに未だ存在しないリードにおけるデータを表す新たなノードの作成に関与することは注目に値する。
【００５９】
例えば、リードマッピングに先立ち、ＤＡＧ  １０１は、ノード６（ＧＧ）を未だ含んでいなくてよい。アライメントアルゴリズム（下に示す）は、配列リードが、図１に描写されている通り、ノード１→３→５→４→２を接続する対立遺伝子２のパスに最も良くマッチすることを見出す。配列リードを正確に表すため、新たなノード６が作成され、これにより、配列リードは、ノード１→３→６→４→２を接続するパスによりＤＡＧ  １０１内で表される。このマッピングに先立ち、ノード３、５および４が、別々のノードとして存在する必要が未だないことが認められよう。リードのマッピングおよび新たなノード６の作成は、先のノード（３＋５＋４）をノード３、５および４へと分割することを含むことができる。これは、参照としてＤＡＧを使用する強力な利益の１つである  −  リードマッピングは、参照との比較における単純な演習ではなく、未だ新たな配列リードによってのみ実証される、新規遺伝子型を含むあらゆる公知の遺伝子型を表す参照の構築を含むことができる。
【００６０】
図２は、計算的記憶および検索に適するＤＡＧ  １０１の可能な１フォーマットを示す。図２に表されるＤＡＧ  １０１は、図１に描写されるグラフィックバージョンと同じトポロジーおよび配列を示す。本図では、ノードが、バイオインフォマティクスの技術分野で馴染みがあるＦＡＳＴＡファイルとして記憶されている（また、まさに容易にＦＡＳＴＱファイルとなり得る）ため、描写されているフォーマットは有用である。エッジは、本図では単純なリストとして、テキストファイルにおいて記憶することができる。
【００６１】
いかなるノードからも、上流ノードが下流ノードと独立的であるという点において、ＤＡＧ  １０１を通るパスは、図１および図２に描写されているマルコフプロセスを表す。しかし、遺伝子保存、連鎖不平衡、不均一ＧＣ含量および他の生物学的現象のため、パスに従って、ノードからノードへと、実際のゲノムを表すゲノムＤＡＧを通ることは、実際には非マルコフプロセスとなり得る。このような生物学的現象を表すため、条件付き情報が含まれ得る。本発明は、被験体のゲノム内の公知ポジションにおけるヌクレオチドの同一性を使用して、ゲノムＤＡＧをフィルタリングする方法を提供する。
【００６２】
本目的のため、特に、ゲノムＤＡＧが、（効率的に表される）配列セットまたはそれとアラインするオブジェクトとしてだけでなく、問題になっているゲノムまたはゲノム領域に関する条件付き情報のリポジトリとしても解釈され得ることに留意されたい。さらに、このような価値ある条件付き情報がＤＡＧそれ自体に存在しない程度まで、本発明者らは、これにこのような情報を補足することができる。
【００６３】
この条件付き情報は、バイナリーまたは確率的のいずれかとなり得る。一部の文脈において、様々なノード対によって表されるいずれの配列が共存できるかを単に把握することで満足がいく。他の文脈において、別の配列が存在することを考慮して、ある１配列の条件付き確率を知ることが有用である。例えば、ある特定のＳＮＰの観察が、他のある特定のＳＮＰが同じゲノムに存在する確率を生じることが公知となり得る。これは、ＳＮＰが連鎖不平衡にある場合に頻繁に起こる。
【００６４】
高密度ＳＮＰチップ（例えば、アッセイ当たり百万種の遺伝子座）は、ヒト疾患に関連する受け継がれたゲノムバリアントを見出すことを目的とする研究に役立った。連鎖不平衡を取り込むことにより、アレイが直接的に決定できるよりも数多くの遺伝子座を研究することができる。
【００６５】
２個またはそれを超える遺伝子座における対立遺伝子が、偶然に予想されるよりも頻繁に同じ個体において共に現れる、連鎖不平衡（ＬＤ）およびフェージング（ｐｈａｓｉｎｇ）ＬＤが生じる。ヒトにおけるＬＤは、同じ染色体上の遺伝子座の間に限定された歴史的組換えを有する、該遺伝子座においてそれ自体、主に顕在化する。数学的には、同じ染色体上の２個のＳＮＰ間のＬＤは、集団染色体にわたる対立遺伝子間の相関として定量することができる。この相関の尺度は、一倍体遺伝子型を表す２個のバイナリーランダム変数の統計的共分散Ｄと、統計的相関係数の二乗ｒ２を含む。２個のＳＮＰが相関し、有意なｒ２を示す場合、ＳＮＰのうち一方の遺伝子型決定は、他方のＳＮＰの遺伝子型に関する情報をもたらす。したがって、百万種のＳＮＰを遺伝子型決定するＳＮＰアレイは、アレイに表されるよりも高い比率のヒト遺伝的変種を効果的にアッセイする。
【００６６】
アレイ製造業者は、ヒトゲノムにおける多数の他のＳＮＰと相関するまたは「タグ付けする」ＳＮＰを問い合わせるためにアレイを設計する。ゲノムにおけるＬＤ構造の有用な知識は、国際ハップマップ計画（Ｉｎｔｅｒｎａｔｉｏｎａｌ  ＨａｐＭａｐ  Ｐｒｏｊｅｃｔ）によって寄与されてきた。例えば、Ｉｎｔｅｒｎａｔｉｏｎａｌ  ＨａｐＭａｐ  Ｃｏｎｓｏｒｔｉｕｍ、２００５年、Ａ  ｈａｐｌｏｔｙｐｅ  ｍａｐ  ｏｆ  ｔｈｅ  ｈｕｍａｎ  ｇｅｎｏｍｅ．、Ｎａｔｕｒｅ  ４３７巻：１２９９〜１３２０頁を参照されたい。ＨａｐＭａｐは、単に多数のＳＮＰの対立遺伝子だけではなく、各染色体に生じる連続したＳＮＰ対立遺伝子の配列も含む。フェージングとは、ゲノムが、２個の連続したＳＮＰにおいてヘテロ接合性である場合、対立遺伝子をそれらそれぞれの染色体に割り当てることである。フェージングは、集団遺伝子型からのＬＤ構造の決定に役立ち、これは続いて、各ＳＮＰによって捕捉されるヒト遺伝的変種の量の推定に必要である。フェージングのための例示的アプローチは、Ｓｔｅｐｈｅｎｓら、２００１年、Ａ  ｎｅｗ  ｓｔａｔｉｓｔｉｃａｌ  ｍｅｔｈｏｄ  ｆｏｒ  ｈａｐｌｏｔｙｐｅ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｆｒｏｍ  ｐｏｐｕｌａｔｉｏｎ  ｄａｔａ、Ａｍ  Ｊ  Ｈｕｍ  Ｇｅｎｅｔ  ６８巻：９７８〜９８９頁に記述されている。フェージングは、ＬＤ構造を提供する。
【００６７】
ＡｆｆｙｍｅｔｒｉｘおよびＩｌｌｕｍｉｎａ等の、製造業者は、チップに表されるＳＮＰに対し信頼できるＬＤを有するＳＮＰを実質的に除外して、チップ設計にＨａｐＭａｐ情報およびＬＤ構造を取り込んだ。よって、例えば、ＬＤ構造に基づき設計されたチップを使用したＳＮＰチップによって公知の位置に同定されるヌクレオチドを使用して、他の位置におけるヌクレオチドの同一性の確率を確立することができる。
【００６８】
一般的なヒト遺伝的変種を捕捉するアレイの能力を測定するための測定基準の１種は、アレイＳＮＰによって固定ｒ２閾値を上回って捕捉された公知ヒトＳＮＰの比率である。研究は、８０％もの多さのヒトＳＮＰが、Ａｆｆｙｍｅｔｒｉｘ  ５００ＫおよびＩｌｌｕｍｉｎａ  ＨｕｍａｎＨａｐ３００アレイによって捕捉されることを示す。例えば、Ｐｅ’ｅｒ．ら、２００６年、Ｅｖａｌｕａｔｉｎｇ  ａｎｄ  ｉｍｐｒｏｖｉｎｇ  ｐｏｗｅｒ  ｉｎ  ｗｈｏｌｅ−ｇｅｎｏｍｅ  ａｓｓｏｃｉａｔｉｏｎ  ｓｔｕｄｉｅｓ  ｕｓｉｎｇ  ｆｉｘｅｄ  ｍａｒｋｅｒ  ｓｅｔｓ．、Ｎａｔ．  Ｇｅｎｅｔ．、３８巻、６６３〜６６７頁を参照されたい。
【００６９】
このような研究は、多数の被験体のＳＮＰチップデータを得るステップと、群の中の対立遺伝子頻度における統計的有意差に関して得られたデータをマイニングするステップとに関与する。ＬＤ構造の大型のセットが利用でき、本発明の方法における使用に適応させることができる。例えば、Ｗｅｌｌｃｏｍｅ  Ｔｒｕｓｔ  Ｃａｓｅ  Ｃｏｎｔｒｏｌ  Ｃｏｎｓｏｒｔｉｕｍ、２００７年、Ｇｅｎｏｍｅ−ｗｉｄｅ  ａｓｓｏｃｉａｔｉｏｎ  ｓｔｕｄｙ  ｏｆ  １４，０００  ｃａｓｅｓ  ｏｆ  ｓｅｖｅｎ  ｃｏｍｍｏｎ  ｄｉｓｅａｓｅｓ  ａｎｄ  ３，０００  ｓｈａｒｅｄ  ｃｏｎｔｒｏｌｓ、Ｎａｔｕｒｅ  ４４７巻：６６１〜６７８頁を参照されたい。
【００７０】
確率的情報または厳密にバイナリー情報が追跡されてもされなくても、この情報は、ＤＡＧ自体においてまたはそれにより記憶することができ、ＤＡＧによる解析において使用することができる。データは、ＤＡＧ内のアノテーションとしてまたは補足情報のファイルとして記憶することができる。
図３は、仮説上のゲノム領域におけるポジション１〜２０に関する仮説上のＤＡＧ  ３０１を示す。ＤＡＧ  ３０１は、次の４種の可能な配列を表す：
５’−ＡＡＴＧＣＡＴＴＧＧＴＣＧＡＴＡＣＣＴＧ−３’（配列番号７）
５’−ＡＡＴＧＣＡＡＡＧＧＴＣＧＡＴＡＣＣＴＧ−３’（配列番号８）
５’−ＡＡＴＧＣＡＴＴＧＧＴＣＣＡＴＡＣＣＴＧ−３’（配列番号９）
５’−ＡＡＴＧＣＡＡＡＧＧＴＣＣＡＴＡＣＣＴＧ−３’（配列番号１０）
【００７１】
配列番号７〜１０のいずれかを、図３に示すＤＡＧ  ３０１から読み取ることができることが認められよう。図３に表されている通り、ＤＡＧ  ３０１を通る全パスは同等であり、マルコフ独立性が想定される。上記の通り、種々の自然かつ統計的な理由により、しかし、ＤＡＧを通る代替パスの全てが、上流または下流ノードから同等に独立的であるとは限らないことが見出され得る。すなわち、ある１種のノードからのパスの選択は、上流（または下流）ノードの特定のパスにおいて条件付きとなり得る。ＤＡＧが自然現象を表す場合、ＤＡＧにおいてこれを表すことは、実際に条件付きの関係性を仮定する。条件付きの関係性は、バイナリー（Ａであれば、Ｂ）または確率的（Ａであれば、Ｂの可能性が高いが、Ｃの可能性もある）となり得る。
【００７２】
条件付きの情報のリポジトリとしてＤＡＧを考慮すると、ＴＴおよびＡＡを含有するノードはそれぞれ、第１のノードから始まる配列の可能な継続である（すなわち、配列ＡＡＴＧＣＡによる）。この情報は価値があり、ＤＡＧから直接的に読み取ることができる。
【００７３】
ポジション７および８にＴＴを有する配列が、ポジション１３にＧを常に有し、Ｃを有することはない一方、ポジション７および８にＡＡを有する例の配列は、ポジション１３にこの２種の代替のそれぞれを有して見出されたことがさらに分かる。この情報は、例えば、ノードＩＤによりＤＡＧ  ３０１を強化し、共存可能性に関する情報をもたらすタブ区切りテキストファイルを作成することにより、いくつもの仕方で記憶することができる：
【００７４】
図４は、共存可能性に関する情報を強化したＤＡＧ  ３０１を示す。ＤＡＧ  ３０１の下は、共存可能性の表である。共存可能性は、次の通り、コンマ区切りの値として表すこともできる：
ノード１，ノード２，共存できる？
２，５，Ｙ
２，６，Ｎ
３，５，Ｙ
３，６，Ｙ
【００７５】
例えば、共存できないノードの対のみを含有し（これにより、第３の列および多くの行を排除する）、「はい（ｙｅｓ）」を暗黙のデフォルト回答とすることによって、上のデータを容易に圧縮することができることに留意する：
［共存できないノードのリスト：］
ノード１，ノード２
２，６
【００７６】
共存可能性データの使用についてより詳細に後述して、ゲノムＤＡＧに配列リードをアラインする際に、このデータがどのように役立つか図解する。
【００７７】
本発明は、ＤＡＧに配列リードをアラインするための方法およびシステムを提供する。本発明のアライメントアルゴリズムを使用して、このような多数にもかかわらず、リードを迅速にマッピングすることができる。多数の利益は、参照としてＤＡＧを使用することにより得られる。例えば、ＤＡＧに対するアラインは、１つの参照に対してアラインし、続いて他の外部情報を踏まえてその結果を調整する試みよりも正確である。これは、主に、後者のアプローチが、初期アライメントにおいて使用した配列と、他の情報との間の不自然な非対称を強制するためである。あらゆる関連する物理的可能性を潜在的に表す対象に対するアラインは、物理的可能性ごとに線形配列に対しアラインする試みよりもはるかに計算的に効率的である（かかる可能性の数は、一般に、接合部の数において指数関数的である）。
【００７８】
本発明の実施形態は、ＤＡＧに対する１または複数のリードのアライメントを含む。
【００７９】
ペアワイズアライメントは、一般に、標的の一部に沿ってある一配列を配置し、アルゴリズムに従ってギャップを導入し、この２配列がどの程度マッチするかスコアリングし、好ましくは、参照に沿った様々な位置に対し反復することに関与する。最良のスコアリングマッチは、アライメントであると思われ、配列データが表すものに関する推測を表す。一部の実施形態において、核酸配列のペアのアライメントのスコアリングは、置換およびインデルの確率の値の設定に関与する。個々の塩基がアラインされると、マッチまたはミスマッチが、置換確率によりアライメントスコアに寄与し、これは、例えば、マッチに対し１およびミスマッチに対し−０．３３であり得る。インデルは、アライメントスコアからギャップペナルティを差し引き、これは、例えば、−１であり得る。ギャップペナルティおよび置換確率は、配列が進化する仕方に関する経験的知識または演繹的仮説に基づくことができる。これらの値は、得られるアライメントに影響を与える。特に、ギャップペナルティと置換確率との間の関係性は、置換またはインデルが、得られるアライメントにおいて好まれるかどうかに影響する。
【００８０】
式に表明される通り、アライメントは、２つの配列ｘとｙの間の推測される関係性を表す。例えば、一部の実施形態において、配列ｘおよびｙのアライメントＡは、（ｉ）｜ｘ’｜＝｜ｙ’｜となる；（ｉｉ）ｘ’およびｙ’からスペースを除去すると、ｘおよびｙにそれぞれ戻るべきである；ならびに（ｉｉｉ）任意のｉについて、ｘ’［ｉ］およびｙ’［ｉ］は、両者共にスペースとなることができないように、スペースを含有し得る別の２つの文字列ｘ’およびｙ’に、ｘおよびｙをそれぞれマップする。
【００８１】
ギャップは、ｘ’またはｙ’のいずれかにおける連続スペースの最大の部分文字列である。アライメントＡは、次の３種類の領域を含むことができる：（ｉ）マッチしたペア（例えば、ｘ’［ｉ］＝ｙ’［ｉ］；（ｉｉ）ミスマッチしたペア（例えば、ｘ’［ｉ］≠ｙ’［ｉ］かつ両者共にスペースではない）；または（ｉｉｉ）ギャップ（例えば、ｘ’［ｉ．．ｊ］またはｙ’［ｉ．．ｊ］のいずれかがギャップである）。ある特定の実施形態において、マッチしたペアのみが、高い正のスコアａを有する。一部の実施形態において、ミスマッチしたペアは、一般に、負のスコアｂを有し、長さｒのギャップも、負のスコアｇ＋ｒｓ（式中、ｇ、ｓ＜０）を有する。ＤＮＡに関して、一般的なスコアリングスキームの１種は（例えば、ＢＬＡＳＴによって使用される）、スコアａ＝１、スコアｂ＝−３、ｇ＝−５およびｓ＝−２を作成する。アライメントＡのスコアは、あらゆるマッチしたペア、ミスマッチしたペアおよびギャップのスコアの和である。ｘおよびｙのアライメントスコアは、ｘおよびｙのあらゆる可能なアライメントの中の最大スコアとして定義することができる。
【００８２】
一部の実施形態において、任意のペアは、置換確率の４×４行列Ｂによって定義されるスコアａを有する。例えば、Ｂ（ｉ，ｉ）＝１および０＜Ｂ（ｉ，ｊ）ｉ＜＞ｊ＜１は、１つの可能なスコアリングシステムである。例えば、転移（ｔｒａｎｓｉｔｉｏｎ）が、トランスバージョンよりも生物学的にあり得ると考えられる場合、行列Ｂは、Ｂ（Ｃ，Ｔ）＝．７およびＢ（Ａ，Ｔ）＝．３または本技術分野において公知の方法によって望まれるもしくは決定される他のいずれかのセットの値を含むことができる。
【００８３】
本発明の一部の実施形態に従ったアライメントは、ペアワイズアライメントを含む。ペアワイズアライメントは、一般に、ｍ個の文字を有する配列Ｑ（クエリー）およびｎ文字の参照ゲノムＴ（標的）に関して、ＱとＴとの間で可能なローカルアライメントを見出し評価することに関与する。任意の１≦ｉ≦ｎおよび１≦ｊ≦ｍに関して、Ｔ［ｈ．．ｉ］およびＱ［ｋ．．ｊ］（式中、ｈ≦ｉおよびｋ≦ｊ）の最大の可能なアライメントスコアが算出される（すなわち、位置ｉで終了するＴの任意の部分文字列および位置ｊで終了するＱの任意の部分文字列の最良のアライメントスコア）。これは、ｃｍ個の文字を有するあらゆる部分文字列の検査を含むことができ、ここでｃは類似性モデルに依存した定数であり、各部分文字列をＱと別々にアラインする。各アライメントはスコア化され、好まれるスコアを有するアライメントがアライメントとして受容される。当業者は、配列アライメントのための正確なアルゴリズムおよび近似的なアルゴリズムが存在することを十分に理解する。正確なアルゴリズムは、最高スコアのアライメントを見出す予想されるが、計算が高価でありうる。２つの周知の正確なアルゴリズムは、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ（Ｊ  Ｍｏｌ  Ｂｉｏｌ、４８巻（３号）：４４３〜４５３頁、１９７０年）およびＳｍｉｔｈ−Ｗａｔｅｒｍａｎ（Ｊ  Ｍｏｌ  Ｂｉｏｌ、１４７巻（１号）：１９５〜１９７頁、１９８１年；Ａｄｖ．  ｉｎ  Ｍａｔｈ．、２０巻（３号）：３６７〜３８７頁、１９７６年）である。Ｇｏｔｏｈ（Ｊ  Ｍｏｌ  Ｂｉｏｌ、１６２巻（３号）：７０５〜７０８頁、１９８２年）による、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎに対するさらなる改善は、計算時間を、Ｏ（ｍ２ｎ）からＯ（ｍｎ）［ここで、ｍおよびｎは、比較される配列サイズであり、並列処理により適する］へと短縮する。バイオインフォマティクスの分野では、Ｇｏｔｏｈの改変アルゴリズムが、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムと称されることが多い。並列計算リソースが、より広くかつ廉価に利用可能となりつつあるので、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ法は、より多くの配列セットをより多くの基準配列に対してアラインするのに使用されている。例えば、Ａｍａｚｏｎのクラウドコンピューティングリソースを参照されたい。本明細書において参照される上記の雑誌論文の全ては、参照によりそれらの全体において組み込まれる。
【００８４】
Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ（ＳＷ）アルゴリズムでは、配列内の塩基間の重複に対して報酬を与え、配列間のギャップに対してペナルティペナルティを課すことにより、直鎖状の配列をアラインする。Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎはまた、ＳＷは、短い配列が、長い配列を記載する文字の文字列にわたることを必要としないという点でも、Ｎｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈと異なる。すなわち、ＳＷは、１つの配列が、他の配列の全体についてのリードであることを仮定しない。さらに、ＳＷは、文字列の全長にわたり伸長するアライメントを見出さなくてもよいため、局所的アライメントは、２つの配列内のどこでも開始および終結させることが可能である。
【００８５】
一部の実施形態において、ペアワイズアライメントは、ドットマトリクス方法、ダイナミックプログラミング方法またはワード（ｗｏｒｄ）方法に従って進む。ダイナミックプログラミング方法は、一般に、Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ（ＳＷ）アルゴリズムまたはＮｅｅｄｌｅｍａｎ−Ｗｕｎｓｃｈ（ＮＷ）アルゴリズムを実行する。ＮＷアルゴリズムに従ったアライメントは、一般に、線形ギャップペナルティｄによる相似行列Ｓ（ａ，ｂ）（例えば、上述の行列Ｂなど）に従ってアラインされた文字をスコア化する。行列Ｓ（ａ，ｂ）は、一般に、置換確率を与える。ＳＷアルゴリズムは、ＮＷアルゴリズムと同様であるが、いずれの負のスコアリング行列セルも、ゼロに設定される。ＳＷおよびＮＷアルゴリズムならびにそれらの実行は、両者共に参照によりその全体が本明細書に組み込まれる、米国特許第５，７０１，２５６号および米国特許出願公開第２００９／０１１９３１３号により詳細に記載されている。
【００８６】
Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎアルゴリズムのバージョンを実行するアライメントプログラムは、Ｇｅｅｋｎｅｔ（Ｆａｉｒｆａｘ、ＶＡ）によって維持されるＳｏｕｒｃｅＦｏｒｇｅウェブサイトから入手できるＭＵＭｍｅｒである。ＭＵＭｍｅｒは、ゲノムスケールの配列を迅速にアラインするためのシステムである（Ｋｕｒｔｚ，  Ｓ．ら、Ｇｅｎｏｍｅ  Ｂｉｏｌｏｇｙ、５巻：Ｒ１２頁（２００４年）；Ｄｅｌｃｈｅｒ，  Ａ．Ｌ．ら、Ｎｕｃｌ．  Ａｃｉｄｓ  Ｒｅｓ．、２７巻：１１頁（１９９９年））。例えば、ＭＵＭｍｅｒ  ３．０は、１３．７秒間で、７８ＭＢのメモリを使用して、２．４ＧＨｚのＬｉｎｕｘ（登録商標）デスクトップコンピュータにおいて、５メガベースゲノムのペア間のあらゆる２０塩基対またはそれより長い正確なマッチを見出すことができる。ＭＵＭｍｅｒは、ショットガンシーケンシングプロジェクト由来の１００個または１０００個のコンティグを取り扱うことができ、システムにより含まれるＮＵＣｍｅｒプログラムを使用して、これらを別のセットのコンティグまたは参照にアラインする。種が、ＤＮＡ配列アライメントにとって多岐にわたり過ぎて類似性を検出できない場合、ＰＲＯｍｅｒプログラムは、両方のインプット配列の６フレーム翻訳に基づきアライメントを作成することができる。
【００８７】
他の例示的なアライメントプログラムは、次のものを含む：ヌクレオチドデータベースの効率的大規模アライメント（ＥＬＡＮＤ：Ｅｆｆｉｃｉｅｎｔ  Ｌａｒｇｅ−Ｓｃａｌｅ  Ａｌｉｇｎｍｅｎｔ  ｏｆ  Ｎｕｃｌｅｏｔｉｄｅ  Ｄａｔａｂａｓｅｓ）または配列およびバリエーションのコンセンサス評価（ＣＡＳＡＶＡ：Ｃｏｎｓｅｎｓｕｓ  Ａｓｓｅｓｓｍｅｎｔ  ｏｆ  Ｓｅｑｕｅｎｃｅ  ａｎｄ  Ｖａｒｉａｔｉｏｎ）ソフトウェア（Ｉｌｌｕｍｉｎａ、Ｓａｎ  Ｄｉｅｇｏ、ＣＡ）のＥＬＡＮＤｖ２コンポーネント；Ｒｅａｌ  Ｔｉｍｅ  Ｇｅｎｏｍｉｃｓ，Ｉｎｃ．（Ｓａｎ  Ｆｒａｎｃｉｓｃｏ、ＣＡ）製のＲＴＧ  Ｉｎｖｅｓｔｉｇａｔｏｒ；Ｎｏｖｏｃｒａｆｔ（Ｓｅｌａｎｇｏｒ、Ｍａｌａｙｓｉａ）製のＮｏｖｏａｌｉｇｎ；Ｅｘｏｎｅｒａｔｅ、Ｅｕｒｏｐｅａｎ  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  Ｉｎｓｔｉｔｕｔｅ（Ｈｉｎｘｔｏｎ、ＵＫ）（Ｓｌａｔｅｒ，  Ｇ．およびＢｉｒｎｅｙ，  Ｅ．、ＢＭＣ  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ６巻：３１頁（２００５年））、Ｕｎｉｖｅｒｓｉｔｙ  Ｃｏｌｌｅｇｅ  Ｄｕｂｌｉｎ（Ｄｕｂｌｉｎ、Ｉｒｅｌａｎｄ）製のＣｌｕｓｔａｌ  Ｏｍｅｇａ（Ｓｉｅｖｅｒｓ  Ｆ．ら、Ｍｏｌ  Ｓｙｓｔ  Ｂｉｏｌ  ７巻、ａｒｔｉｃｌｅ  ５３９（２０１１年））；Ｕｎｉｖｅｒｓｉｔｙ  Ｃｏｌｌｅｇｅ  Ｄｕｂｌｉｎ（Ｄｕｂｌｉｎ、Ｉｒｅｌａｎｄ）製のＣｌｕｓｔａｌＷまたはＣｌｕｓｔａｌＸ（Ｌａｒｋｉｎ  Ｍ．Ａ．ら、Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ、２３巻、２９４７〜２９４８頁（２００７年））；ならびにＦＡＳＴＡ、Ｅｕｒｏｐｅａｎ  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  Ｉｎｓｔｉｔｕｔｅ（Ｈｉｎｘｔｏｎ、ＵＫ）（Ｐｅａｒｓｏｎ  Ｗ．Ｒ．ら、ＰＮＡＳ  ８５巻（８号）：２４４４〜８頁（１９８８年）；Ｌｉｐｍａｎ，  Ｄ．Ｊ．、Ｓｃｉｅｎｃｅ  ２２７巻（４６９３号）：１４３５〜４１頁（１９８５年））。
【００８８】
上述の通り、配列を有向非巡回アノテートされた参照ゲノムにアラインする際に、ＳＷアライメントアルゴリズムまたはその修正バージョン（さらに詳細に後述する）を実行することが好ましくまたは望ましくあり得る。
【００８９】
下記の等式（１）：
【数１】
2017510871.tif 000005
との関連で、ＳＷアルゴリズムは、長さｎおよびｍの２つの文字列を表示する、ｎ×ｍ行列Ｈで容易に表示される。
【００９０】
上記の等式では、ｓ（ａｉ，ｂｊ）は、マッチボーナス（ａｉ＝ｂｊである場合）またはミスマッチペナルティ（ａｉ≠ｂｊである場合）を表し、挿入および欠失には、それぞれ、ペナルティＷｉｎおよびＷｄｅｌが課される。大半の場合、結果として得られる行列は、ゼロである多くの成分を有する。この表示は、行列内の上行〜下行、右列〜左列のバックトレースを容易とし、これにより、アライメントの同定を容易とする。
【００９１】
行列にスコアを完全に追加したら、ＳＷアルゴリズムにより、バックトラックを実施して、アライメントを決定する。アルゴリズムは、行列内の最大値から始めて、各セルの最終的な最大値を計算するのに３つの値（Ｈｉ−１，ｊ−１、Ｈｉ−１，ｊ、またはＨｉ，ｊ−１）のうちのいずれを使用したのかに基づき、バックトラックする。バックトラッキングは、ゼロに達すると停止する。最適スコアリングアライメントは、挿入および欠失の最小可能な数を超えて含有することができるが、置換の最大可能な数よりもはるかに少なく含有する。
【００９２】
ＳＷまたはＳＷ−Ｇｏｔｏｈとして適用する場合、技法では、動的計画法アルゴリズムを使用して、それぞれ、サイズをｍおよびｎとする、２つの文字列ＳおよびＡの局所的配列アライメントを実施する。この動的計画法では、表または行列を援用して、マッチスコアを保存し、一連のセルについての再計算を回避する。文字列の各成分は、配列の文字に関するインデックスが付されていてもよく、すなわち、Ｓが文字列ＡＴＣＧＡＡであれば、Ｓ［１］＝Ａである。最適のアライメントをＨｉ，ｊ（上記）と表す代わりに、最適のアライメントは、下記の等式（２）：
【数２】
2017510871.tif 000006
のＢ［ｊ，ｋ］と表すことができる。
【００９３】
最大値関数であるＢ［ｊ，ｋ］の引数を、下記の等式（３）〜（５）［ここで、ＭＩＳＭＡＴＣＨ＿ＰＥＮ、ＭＡＴＣＨ＿ＢＯＮＵＳ、ＩＮＳＥＲＴＩＯＮ＿ＰＥＮ、ＤＥＬＥＴＩＯＮ＿ＰＥＮ、およびＯＰＥＮＩＮＧ＿ＰＥＮは、全て定数であり、ＭＡＴＣＨ＿ＢＯＮＵＳを除き、全て負である］に概括する（ＰＥＮはＰＥＮＡＬＴＹの短縮型）。マッチの引数であるｐ［ｊ，ｋ］は、下記の等式（３）：
【数３】
2017510871.tif 000007
で与えられ、挿入の引数であるｉ［ｊ，ｋ］は、下記の等式（４）：
【数４】
2017510871.tif 000008
で与えられ、欠失の引数であるｄ［ｊ，ｋ］は、下記の等式（５）：
【数５】
2017510871.tif 000009
で与えられる。
【００９４】
３つの引数全てについて、［０，０］成分は、ゼロと置いて、バックトラックの完了を確認する、すなわち、ｐ［０，０］＝ｉ［０，０］＝ｄ［０，０］＝０とする。
【００９５】
スコア付けパラメータは、ある程度任意のものであり、計算の挙動を達成するように調整することができる。ＤＮＡのためのスコア付けパラメータ設定の一例（Ｈｕａｎｇ、３章：Ｂｉｏ−Ｓｅｑｕｅｎｃｅ  Ｃｏｍｐａｒｉｓｏｎ  ａｎｄ  Ａｌｉｇｎｍｅｎｔ、Ｃｕｒｒ  Ｔｏｐ  Ｃｏｍｐ  Ｍｏｌ  Ｂｉｏｌシリーズ、Ｃａｍｂｒｉｄｇｅ、Ｍａｓｓ．：  Ｔｈｅ  ＭＩＴ  Ｐｒｅｓｓ、２００２年）であれば、
ＭＡＴＣＨ＿ＢＯＮＵＳ：１０
ＭＩＳＭＡＴＣＨ＿ＰＥＮ：−２０
ＩＮＳＥＲＴＩＯＮ＿ＰＥＮ：−４０
ＯＰＥＮＩＮＧ＿ＰＥＮ：−１０
ＤＥＬＥＴＩＯＮ＿ＰＥＮ：−５
である。
【００９６】
上記のギャップペナルティ（ＩＮＳＥＲＴＩＯＮ＿ＰＥＮ、ＯＰＥＮＩＮＧ＿ＰＥＮ）の間の関係は、ギャップ挿入ペナルティを、ギャップオープニングコストより大きく設定することにより、ギャップオープニングの数を制限する助けとなる、すなわち、ギャップをまとめてグループ化することを支援する。当然ながら、ＭＩＳＭＡＴＣＨ＿ＰＥＮ、ＭＡＴＣＨ＿ＢＯＮＵＳ、ＩＮＳＥＲＴＩＯＮ＿ＰＥＮ、ＯＰＥＮＩＮＧ＿ＰＥＮ、およびＤＥＬＥＴＩＯＮ＿ＰＥＮの間の代替的な関係も可能である。
【００９７】
一部の実施形態において、本発明の方法およびシステムは、多次元アライメントアルゴリズムを組み入れる。本発明の多次元アルゴリズムは、配列情報の「遡及（ｌｏｏｋ−ｂａｃｋ）」型解析を提供し（Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎと同様に）、この遡及は、複数の経路および複数のノードを含む多次元空間により行われる。多次元アルゴリズムを使用して、ＤＡＧ型参照に対してＲＮＡ−Ｓｅｑリードをアラインすることができる。「背景技術（Ｂａｃｋｇｒｏｕｎｄ）」で表されたアルゴリズムと異なり、アライメントアルゴリズムでは、ＤＡＧ（例えば、基準配列構築物）上の位置において含有される各配列に対する最大スコアを同定することにより、Ｃｉｊの最大値を同定する。実際、先行する位置を「後ろ向きに（ｂａｃｋｗａｒｄｓ）」見ることにより、複数の可能な経路にわたり最適のアライメントを同定することが可能である。
【００９８】
本明細書に記載されている修飾されたＳｍｉｔｈ−Ｗａｔｅｒｍａｎアライメントは、多次元アライメントとも称され、物理的メモリアドレス化（例えば、上記のネイティブポインタまたはインデックス・フリー隣接性の使用による）を用いるゲノムＤＡＧシステムにおいて実行される場合、例外的なスピードを提供する。参照ゲノムＤＡＧにおけるオブジェクト由来のデータを取り出すための空間的メモリアドレス（例えば、ネイティブポインタまたはインデックス・フリー隣接性）の使用と、参照ゲノムＤＡＧに対する多次元アライメントとの組合せにより、コンピュータシステムが、全ゲノムスケール解析およびリードアセンブリが本明細書に記載されている公知対立遺伝子を使用して容易に実行されることが可能となるよう改善される。
【００９９】
本発明のアルゴリズムは、上記で論じた通り、リード（別名「文字）および有向非巡回グラフ（ＤＡＧ）上で実行される。アルゴリズムを規定する目的で、Ｓを、アラインされる文字列とし、Ｄを、Ｓがアラインされる有向非巡回グラフとする。文字列Ｓの成分において、１で始まるインデックスがカッコ内に示される。したがって、Ｓが文字列ＡＴＣＧＡＡであれば、Ｓ［１］＝Ａ、Ｓ［４］＝Ｇなどである。
【０１００】
ＤＡＧについてのある特定の実施形態では、ノードの配列の各文字は、別個の成分であるｄとして表示される。ｄの先行成分（ｐｒｅｄｅｃｅｓｓｏｒ）は、以下のように定義される。
（ｉ）ｄが、そのノードの配列の第１の文字でなければ、そのノード内のｄに先行する文字が、その（唯一の）先行成分であり、
（ｉｉ）ｄが、そのノードの配列の第１の文字であれば、任意のノードの配列（例えば、ゲノムにおける全てのエクソンの上流）の最後の文字であって、ｄのノードの親である文字が、ｄの先行成分である。
【０１０１】
全ての先行成分のセットは、Ｐ［ｄ］として表示する。
「最良の」アライメントを見出すために、アルゴリズムでは、Ｓの最初のｊ個の成分の、ｄに先行する（およびｄを含む）ＤＡＧの部分による最適のアライメントについてのスコアである、Ｍ［ｊ，ｄ］の値を求める。このステップは、上記の等式１内のＨｉｊを見出すステップと同様である。具体的に、Ｍ［ｊ，ｄ］を決定するステップは、下記：
【数６】
2017510871.tif 000010
で規定される通り、ａ、ｉ、ｅ、および０のうちの最大値を見出すことを伴う。
【０１０２】
上記で記載した通り、ｅとは、Ｓの最初のｊ個の文字の、ＤＡＧの部分であって、ｄまでであるが、ｄを含まない部分によるアライメントのうちの最高のアライメントに、追加のＤＥＬＥＴＥ＿ＰＥＮを加えた値である。したがって、ｄが、ノードの配列の第１の文字でなければ、唯一の先行成分ｐが存在し、Ｓの最初のｊ個の文字の、ＤＡＧ（ｐまでであり、ｐを含む）によるアライメントスコアは、Ｍ［ｊ，ｐ］＋ＤＥＬＥＴＥ＿ＰＥＮＹと等しい。ｄが、そのノードの配列の第１の文字である場合、複数の可能な先行成分が存在することが可能であり、ＤＥＬＥＴＥ＿ＰＥＮは定数であるため、［Ｍ［ｊ，ｐ＊］＋ＤＥＬＥＴＥ＿ＰＥＮ］を最大化することは、先行成分を、Ｓの最初のｊ個の文字による最高のアライメントスコアと共に選択することと同じである。
【０１０３】
等式（６）では、ｉとは、文字列Ｓの最初のｊ−１個の文字の、ｄまでであり、ｄを含むＤＡＧによるアライメントに、ＳＷにおける挿入引数の定義（等式１を参照されたい）と同様のＩＮＳＥＲＴ＿ＰＥＮを加えた値である。
【０１０４】
加えて、ａとは、Ｓの最初のｊ個の文字の、ＤＡＧの部分であって、ｄまでであるが、ｄを含まない部分によるアライメントのうちの最高のアライメントに、ＭＡＴＣＨ＿ＳＣＯＲＥ（Ｓのｊ番目の文字が、文字ｄと同じである場合）またはＭＩＳＭＡＴＣＨ＿ＰＥＮ（Ｓのｊ番目の文字が、文字ｄと同じでない場合）を加えた値である。ｅと同様に、これは、ｄが、そのノードの配列の第１の文字でなければ、唯一の先行成分、すなわち、ｐが存在することを意味する。これは、ａが、Ｓの最初のｊ−１個の文字の、ＤＡＧ（ｐまでであり、ｐを含む）によるアライメントスコア、すなわち、ｄとＳのｊ番目の文字とがマッチするのかどうかに応じて、ＭＩＳＭＡＴＣＨ＿ＰＥＮまたはＭＡＴＣＨ＿ＳＣＯＲＥを加えたＭ［ｊ−１，ｐ］であることを意味する。ｄが、そのノードの配列の第１の文字である場合、複数の可能な先行成分が存在しうる。この場合、｛Ｍ［ｊ，ｐ＊］＋ＭＩＳＭＡＴＣＨ＿ＰＥＮまたはＭＡＴＣＨ＿ＳＣＯＲＥ｝を最大化することは、先行成分を、Ｓの最初のｊ−１個の文字による最高のアライメントスコア（すなわち、Ｍ［ｊ−１，ｐ＊］の候補引数の最高値）と共に選択し、ｄとＳのｊ番目の文字とがマッチするのかどうかに応じて、ＭＩＳＭＡＴＣＨ＿ＰＥＮまたはＭＡＴＣＨ＿ＳＣＯＲＥを加えることと同じである。
【０１０５】
ここでもまた、ＳＷアルゴリズムの場合と同様に、ペナルティ、例えば、ＤＥＬＥＴＥ＿ＰＥＮ、ＩＮＳＥＲＴ＿ＰＥＮ、ＭＡＴＣＨ＿ＳＣＯＲＥ、およびＭＩＳＭＡＴＣＨ＿ＰＥＮは、少数のギャップを伴うアライメントを促すなどのように調整することができる。
【０１０６】
上記の等式で記載されている通り、アルゴリズムでは、各リードについて、その成分についての挿入スコア、欠失スコア、およびマッチスコアを計算するだけでなく、ＤＡＧ上の任意の先行ノードを後ろ向きに見て（ＤＡＧの方向と反対方向に）、最適の（すなわち、最大の）スコアを見出すことにより、最大値を見出す。こうして、アルゴリズムは、ＤＡＧを通る異なる経路であって、公知の変異を含有する経路を横断することが可能である。グラフは、有向性であるため、グラフの方向と反対に移動するバックトラックは、グラフの起点に向けて好まれるアイソフォームに従い、最適アライメントスコアは、高度な確実性の最も可能性の高いアライメントを同定する。
【０１０７】
図５は、ＤＡＧ  ５０１への配列リードのマッピングについて説明し、ＤＡＧへの配列のアライメントの図解に役立つ。図５の上部分において、仮説上の配列リード「ＡＴＣＧＡＡ」が、次の２種の仮説上の配列と共に示されている：
ＴＴＧＧＡＴＡＴＧＧＧ（配列番号１１）
ＴＴＧＧＡＴＣＧＡＡＴＴＡＴＧＧＧ（配列番号１２）
【０１０８】
図５の中央部分は、配列番号１１および１２が、６文字インデルによって関係することを図解するために描かれており、仮説上のリードが、配列番号１２とアラインし、インデルへと伸長するという予備知識が存在するように装われている。図５の中央部分において、描写は、直線化および単純化されて、可視化に役立つ。
【０１０９】
図５の下部分は、仮説上の配列リードがアラインされるＤＡＧ  ５０１の作成を図解する。描写されているＤＡＧ５０１において、異なるパスに沿っているにもかかわらず、ＤＡＧ５０１の５’末端からこのＤＡＧの３’末端へと読み取ることにより、配列番号１１および１２は両者共に読み取ることができる。描写されている通り、上のパスとアラインするものとして配列リードを示す。
【０１１０】
図６は、比較に対応する実際の行列を示す。Ｓｍｉｔｈ−Ｗａｔｅｒｍａｎ技法と同様に、本発明の図示されているアルゴリズムは、最高スコアを同定し、バックトラックを実行して、リードの適切な場所を同定する。図５および図６は、本発明が、構築物に対する文字列の実際のマッチを産生することも強調する。配列リードが、ＤＡＧに含まれていない変異体を含む事例において、アラインされた配列は、ギャップ、挿入などとともに報告される。
【０１１１】
上記の通り、確率的情報は、アライメントに対し利益を有し得るＤＡＧにおいて表すことができる。これは、先ず与えられる第２のノードの確率を示す「重み（ｗｅｉｇｈｔ）」を各エッジと関連させることにより行うことができる。
【０１１２】
図７は、確率的情報を含むために作製されるＤＡＧ  ３０１を示す。ＤＡＧ  ３０１のエッジに沿った数は、ＤＡＧ  ３０１によって表される配列の６０％が、ノード２を含有し、４０％がノード３を含有することを示す。また、配列の７０％は、ノード５を含有し、表される配列の３０％は、ノード６を含有する。他の情報が存在しない場合、多くの場合、このような推移確率が独立的である（例えば、マルコフ）と想定することが自然である。すなわち、ノード４からノード５への推移は、配列がノード２またはノード３のどちらかを含む場合の回数の７０％で起こる。しかし、ＤＡＧ  ３０１は、ノード間の依存性に関する情報を補足することができる。例えば、図７の参照を続けると、ノード２を通る配列の全てを検査し、これらの配列の９０％がノード５を通ることが判明した場合、この情報は、例えば次の通り、ＤＡＧ  ３０１により記憶することができる：
ノード１，ノード２，ノード３，確率
２，４，５，０．９
２，４，６，０．１
【０１１３】
再度これは、例えば第１の行から推定することができる第２の行を排除することにより、いくつもの仕方で圧縮することができる。
【０１１４】
本発明の実施形態は、候補配列リードがマッピングされようとするゲノムＤＡＧを通る多数のパスを低下させるために、公知の位置における同定されたヌクレオチドまたは他のいずれかの遺伝子型情報の使用を含む。例えば、被験体についてのＳＮＰチップの結果は、ＤＡＧをフィルタリングすることができ、ＳＮＰチップと一致していないＤＡＧを通るパスは、該被験体由来の配列リードのアセンブリにおける考慮から除外することができる。
【０１１５】
ゲノムにおけるあらゆる公知の変種を表すＤＡＧは、大型になり、ＤＡＧを通る数多くの異なるパスを含むことができる。
【０１１６】
本発明は、この状況に関連する、より大型のＤＡＧをより小型のＤＡＧに低下させるための方法を提供する。ＳＮＰチップおよび条件付き情報の組合せは、このような低下を行う自然な仕方をもたらす。ＳＮＰチップの結果は、ＤＡＧにおけるいずれのノードが、所定の配列によって横断されるかに関する情報をもたらし、続いて条件付き情報を使用して、横断されるノードを仮定して他のノードの関連性に関する事実を推定することができる。
【０１１７】
例えば、非確率的に取り組んでいると仮定し、ＳＮＰチップにより、被験体の配列が、図７のＤＡＧ  ３０１のノード２を通ることを学習する。ＤＡＧにおける情報単独から、グラフのサイズの僅かな低下を達成することができる。
【０１１８】
図８は、低下したバージョンのＤＡＧ  ３０１を示す。図８に示すＤＡＧ  ３０１は、公知ポジションにおける少なくとも１個のヌクレオチドの同一性を得ることに基づく可能なパスの低下を表す。すなわち、ポジション７またはポジション８のいずれかが、チミンであると決定される。次に、ノードｉｄ＝３は、さらなる考慮から除外することができる。上記のとおりの条件付き情報を使用することにより、さらなる利益を得ることができる。上に収載する単純なテキストファイルを参考にして、ノード２および６が共存できず、よって、グラフをさらに低下させると知ることができる。
【０１１９】
図９は、フィルタリングされ（例えば、ＳＮＰチップデータにより）、条件付き情報（例えば、ノード２および６の共存不可能性）によってさらに低下された、ＤＡＧ  ３０１のこのようなさらなる低下の結果を図解する。これらの２ステップ（公知の位置におけるヌクレオチドによるフィルタリング、ヌクレオチドが連鎖する確率によるフィルタリング）から、ＤＡＧ  ３０１を通る候補パスは、１個のパスへと低下された。実際のゲノムデータにより、このような低下は、１個のみのパスを有するＤＡＧをもたらすことはできないが、パスの数の低下（フィルタリングされていないＤＡＧと比較して）は、例えば、修飾された多次元Ｓｍｉｔｈ  Ｗａｔｅｒｍａｎによる、これらのパスに対するリードの包括的アライメントを可能にする。
【０１２０】
このような低下が多くの場合重要でありえることに留意する。ノード２を通らないノード１からノード４まで多くのパスが存在することができ、これらのパスは、任意に長く複雑で、入れ子状態となり得る。このようなパスはいずれも、このステップで排除することができる。
【０１２１】
図１０は、ある特定の実施形態に係る方法１００１のダイヤグラムを示す。一般に、本発明は、公知の位置におけるヌクレオチドの同一性を受け取るステップ１００５（例えば、ＳＮＰチップから）を含む方法１００１を提供する。この情報は、ＤＡＧに適用１００９され、使用されて、公知の位置におけるヌクレオチドを含むＤＡＧにおけるパスを選択１０１５する。その上、ＮＧＳリードを受け取り１０１９、選択されたパスにマッピング１０２３することができる。マッピングから、遺伝子型決定または同様の解析を行うことができる１０２９。
【０１２２】
当技術分野で公知のいかなる開発環境、データベースまたは言語を使用して、本発明の実施形態を実装することもできる。例示的な言語、システムおよび開発環境は、Ｐｅｒｌ、Ｃ＋＋、Ｐｙｔｈｏｎ、Ｒｕｂｙ  ｏｎ  Ｒａｉｌｓ、ＪＡＶＡ（登録商標）、Ｇｒｏｏｖｙ、Ｇｒａｉｌｓ、Ｖｉｓｕａｌ  Ｂａｓｉｃ．ＮＥＴを含む。本発明において有用な資源の概要は、Ｂａｒｎｅｓ（編）、Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ｆｏｒ  Ｇｅｎｅｔｉｃｉｓｔｓ：  Ａ  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  Ｐｒｉｍｅｒ  ｆｏｒ  ｔｈｅ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｇｅｎｅｔｉｃ  Ｄａｔａ、Ｗｉｌｅｙ、Ｃｈｉｃｈｅｓｔｅｒ、Ｗｅｓｔ  Ｓｕｓｓｅｘ、Ｅｎｇｌａｎｄ（２００７年）ならびにＤｕｄｌｅｙおよびＢｕｔｔｅ、Ａ  ｑｕｉｃｋ  ｇｕｉｄｅ  ｆｏｒ  ｄｅｖｅｌｏｐｉｎｇ  ｅｆｆｅｃｔｉｖｅ  ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ｐｒｏｇｒａｍｍｉｎｇ  ｓｋｉｌｌｓ、ＰＬｏＳ  Ｃｏｍｐｕｔ  Ｂｉｏｌ  ５巻（１２号）：ｅ１０００５８９頁（２００９年）に示されている。
【０１２３】
一部の実施形態において、方法は、Ｐｅｒｌにおいて開発されたコンピュータアプリケーションによって実装される（例えば、ＢｉｏＰｅｒｌを任意選択で使用）。Ｔｉｓｄａｌｌ、Ｍａｓｔｅｒｉｎｇ  Ｐｅｒｌ  ｆｏｒ  Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ、Ｏ’Ｒｅｉｌｌｙ  ＆  Ａｓｓｏｃｉａｔｅｓ，  Ｉｎｃ．、Ｓｅｂａｓｔｏｐｏｌ、ＣＡ、２００３年を参照されたい。一部の実施形態において、アプリケーションは、ＢｉｏＰｅｒｌ、バイオインフォマティクスアプリケーションのオブジェクト指向開発を可能にするＰｅｒｌモジュールのコレクションを使用して開発される。ＢｉｏＰｅｒｌは、包括的Ｐｅｒｌアーカイブネットワーク（ＣＰＡＮ）のウェブサイトからのダウンロードのために利用できる。Ｄｗｙｅｒ、Ｇｅｎｏｍｉｃ  Ｐｅｒｌ、Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ（２００３年）およびＺａｋ、ＣＧＩ／Ｐｅｒｌ、第１版、Ｔｈｏｍｓｏｎ  Ｌｅａｒｎｉｎｇ（２００２年）も参照されたい。
【０１２４】
ある特定の実施形態において、アプリケーションは、Ｍａｔｔｈｅｗ  ＰｏｃｏｃｋおよびＴｈｏｍａｓ  Ｄｏｗｎによって１９９８年にＥＢＩ／Ｓａｎｇｅｒにおいて開発された、Ｊａｖａ（登録商標）および任意選択でオブジェクトのＢｉｏＪａｖａコレクションを使用して開発される。ＢｉｏＪａｖａは、アプリケーションプログラミングインターフェース（ＡＰＩ）を提供し、Ｈｏｌｌａｎｄら、ＢｉｏＪａｖａ：  ａｎ  ｏｐｅｎ−ｓｏｕｒｃｅ  ｆｒａｍｅｗｏｒｋ  ｆｏｒ  ｂｉｏｉｎｆｏｒｍａｔｉｃｓ、Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ２４巻（１８号）：２０９６〜２０９７頁（２００８年）に記述されている。Ｊａｖａ（登録商標）におけるプログラミングは、Ｌｉａｎｇ、Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｊａｖａ  Ｐｒｏｇｒａｍｍｉｎｇ，  Ｃｏｍｐｒｅｈｅｎｓｉｖｅ（第８版）、Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，  Ｕｐｐｅｒ  Ｓａｄｄｌｅ  Ｒｉｖｅｒ，  ＮＪ  （２０１１年）およびＰｏｏら、Ｏｂｊｅｃｔ−Ｏｒｉｅｎｔｅｄ  Ｐｒｏｇｒａｍｍｉｎｇ  ａｎｄ  Ｊａｖａ、Ｓｐｒｉｎｇｅｒ  Ｓｉｎｇａｐｏｒｅ，  Ｓｉｎｇａｐｏｒｅ、３２２頁（２００８年）に記述されている。
【０１２５】
アプリケーションは、Ｒｕｂｙプログラミング言語および任意選択でＢｉｏＲｕｂｙ、Ｒｕｂｙ  ｏｎ  Ｒａｉｌｓまたはこれらの組合せを使用して開発することができる。ＲｕｂｙまたはＢｉｏＲｕｂｙは、Ｌｉｎｕｘ（登録商標）、Ｍａｃ  ＯＳ  ＸおよびＷｉｎｄｏｗｓ（登録商標）においてならびにＪＲｕｂｙにより、Ｊａｖａ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅにおいて実行することができかつオブジェクト指向開発を支援することができる。Ｍｅｔｚ、Ｐｒａｃｔｉｃａｌ  Ｏｂｊｅｃｔ−Ｏｒｉｅｎｔｅｄ  Ｄｅｓｉｇｎ  ｉｎ  Ｒｕｂｙ：  Ａｎ  Ａｇｉｌｅ  Ｐｒｉｍｅｒ、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ（２０１２年）およびＧｏｔｏら、ＢｉｏＲｕｂｙ：  ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ｓｏｆｔｗａｒｅ  ｆｏｒ  ｔｈｅ  Ｒｕｂｙ  ｐｒｏｇｒａｍｍｉｎｇ  ｌａｎｇｕａｇｅ、Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ２６巻（２０号）：２６１７〜２６１９頁（２０１０年）を参照されたい。
【０１２６】
本発明のシステムおよび方法は、Ｇｒｏｏｖｙプログラミング言語およびウェブ開発フレームワークＧｒａｉｌｓを使用して開発することができる。Ｇｒａｉｌｓは、ビューによるディスプレイのためのアプリケーションデータを保有するドメインクラスを提供する、オープンソースモデル・ビュー・コントローラ（ＭＶＣ）ウェブフレームワークおよび開発プラットフォームである。Ｇｒａｉｌｓドメインクラスは、根底にあるデータベーススキーマを作製することができる。Ｇｒａｉｌｓは、ウェブアプリケーションを含むアプリケーション、ならびにデータベースおよびＧｒａｉｌｓオブジェクトリレーショナルマッピング（ＧＯＲＭ）と呼ばれるオブジェクトリレーショナルマッピングフレームワークのための開発プラットフォームを提供する。ＧＯＲＭは、リレーショナルデータベースにオブジェクトをマッピングすることができ、これらのオブジェクトの間の関係性を表すことができる。ＧＯＲＭは、Ｈｉｂｅｒｎａｔｅオブジェクトリレーショナル持続フレームワークに依拠して、複雑なドメインクラスをリレーショナルデータベース表にマッピングする。Ｇｒａｉｌｓは、ウェブコンポーネントを作成するためにＪｅｔｔｙウェブコンテナおよびサーバならびにウェブページレイアウトフレームワーク（ＳｉｔｅＭｅｓｈ）をさらに含む。ＧｒｏｏｖｙおよびＧｒａｉｌｓは、Ｊｕｄｄら、Ｂｅｇｉｎｎｉｎｇ  Ｇｒｏｏｖｙ  ａｎｄ  Ｇｒａｉｌｓ、Ａｐｒｅｓｓ、Ｂｅｒｋｅｌｅｙ、ＣＡ、４１４頁（２００８年）；Ｂｒｏｗｎ、Ｔｈｅ  Ｄｅｆｉｎｉｔｉｖｅ  Ｇｕｉｄｅ  ｔｏ  Ｇｒａｉｌｓ、Ａｐｒｅｓｓ、Ｂｅｒｋｅｌｅｙ、ＣＡ、６１８頁（２００９年）に記述されている。
【０１２７】
いずれのプログラミング方法論が用いられるとしても、方法１００１は、確率的データにより機能するように拡張することができる。
確率的事例は、共存できないノードに関する情報を使用する方法と同様である。しかし、確率データにより、不可能なノードだけではなく、ある閾値、例えば、０．０１を下回るノードもＤＡＧからフィルタリングすることがさらに可能である。このことは、アルゴリズムを示唆する：
（ｉ）領域に関して重み付けした参照ＤＡＧを取り出す。
（ｉｉ）ノードとエッジ−重みとの間の相関の補足ファイルを取り出す。
（ｉｉｉ）ＳＮＰ−チップの結果を参考にして、被験体の公知の位置におけるヌクレオチドの同一性を識別して、いずれのノードが実現されるかを確かめる。
（ｉｖ）ＤＡＧの構造および所定のノードが実現されるという事実を仮定し、不可能なパスにおけるノードをフィルタリング除去する（上記の図８におけるノード３の排除の場合のように）。
（ｖ）補足ファイルにおける情報を仮定し、他のエッジ−重みをアップデートする。
（ｖｉ）εを下回るエッジ−重みを有するあらゆるパスを排除するが、このパラメータは、計算資源、ＤＡＧに関するバックグラウンド知識等を踏まえて選ばれる。ε＝０．０１が妥当な選択となり得る。
【０１２８】
本発明の方法は、ゲノム参照の使用における相当な利益および改善を提供する。例えば、ＤＡＧのフィルタリングにより、ＤＡＧが参照として使用される場合、あらゆるその後の解析は、より高速となる。これはとりわけ、より複雑な数学的アルゴリズムが実行されることを可能にし、例えば、より優れたアライメントをもたらす。よって、より大型からより小型のＤＡＧにスイッチして関連情報の損失がない（またはほとんどない）場合、効率を獲得し、精度を獲得することもできる。実際に、低下したＤＡＧにおいて作業を行うと、多くの場合、回避できる誤りを防止する。
【０１２９】
図１１は、ゲノムスケールＤＡＧ  １１０１のほんのごく一部の例を図解する。方法１００１を使用して、ヌクレオチド情報がＤＡＧ  １１０１に適用される１００９。
【０１３０】
図１２は、ヌクレオチド情報によって被験体のゲノムに存在すると明らかにされた黒四角を有するＤＡＧ  １１０１を示す。これらの対立遺伝子を含有しないパスは、被験体由来の配列リードをマッピングする目的のため、ＤＡＧ  １１０１から排除され、これらの対立遺伝子を含有するパスが、さらなる包含のために選択される１０１５ことを意味する。よって、公知の位置における同定されたヌクレオチド（図１２における黒塗りの四角で表される）は、ＤＡＧ  １１０１内からある特定のゲノム配列を効果的に選択する。
【０１３１】
図１３は、ヌクレオチド情報を使用して選択されたゲノム配列を示す。図１３を図１１と比較することにより、本発明の方法が、配列リードを解析するための検索空間の相当な低下を提供することが分かる。
【０１３２】
対立遺伝子が、ＤＡＧ内に先在する必要がないことは注目に値する。実際に、周囲のゲノム情報が全て、優れたスコアでパスにマッピングするため、ゲノムＤＡＧは、今のところ新規のＳＮＰの発見に特に有用であり、アライメントアルゴリズムは、アライメントを行うことによりＳＮＰが発見されているため、ＳＮＰを表す新たなノードを作成する必要性を明らかにする。ＤＡＧは、アライメントにおいて使用されたことに基づいてこれを単純に含むため、新たに発見されたＳＮＰの収容は容易である。すなわち、一部の実施形態において、外部の参照ゲノムデータと被験体ゲノム配列との間の区別は、消滅する区別であり、被験体を遺伝子型決定するためにＮＧＳリードを解析する全事例は、参照を開発する事例でもある。
【０１３３】
本発明の方法によってもたらされる改善により、種々の利益が得られる。
【０１３４】
（ｉ）アライメントがより高速となる。単に、より短い配列に対するアライメントは、より長い配列に対するよりも高速となるため、より小型のＤＡＧに対するアライメントは、より大型のＤＡＧに対するよりも高速となる。
【０１３５】
（ｉｉ）記載されている方法は、他の変種の存在を仮定して、いずれの変種が存在するかに関する決定に通常使用されるよりも多くの相関情報を表し容易に取り出すことができる。先行技術パラダイムに従った方法は、一般に、単にある変種を他の変種と相関させる。本発明の方法は、より豊富な一群の情報から得られる。
【０１３６】
（ｉｉｉ）記載されている方法は、配列解析における精度に対する改善を提供する。改善された精度は、排除された可能性を有することにより（すなわち、ＳＮＰチップデータによって既に「書き込まれた（ｆｉｌｌｅｄ  ｉｎ）」いくつかのノードを有することにより）提供され、同様のただし非相同領域に対する候補アライメントが回避されるため、これは、描写の完了をより正確なものとする。
【０１３７】
確率的事例において、次のアルゴリズムが可能である。
ノードＮが実現される確率を決定するために：
（ａ）Ｎ（およびＮの代替）と他のノードとの間の相関のための補足ファイルを検索する（このファイルが、下に収載するもの等の、あるフォーマットである場合、上記の重み付けしたＤＡＧは、列２または列３におけるエントリーがＮである行を見出す。このような検索操作が、多くの方法、例えば、リレーショナルデータベースによって用いられる方法により、非常に速く行うことができることに留意する）。
（ｂ）これらの行をフィルタリングして、収載されている確率を使用するために十分な情報を有する行のみを含む（すなわち、列１におけるノードの尤度が分かる行）。
（ｃ）（１）これらのノードを仮定して、ＮおよびＮの代替の相対確率に関する特別な情報を持たない、（２）ＳＮＰ−チップまたは他のある手段による結果を仮定して、これらのノードの確率に関して分かるノードのセットを集める。このノードセットを集める自然な仕方は、ＮおよびＮの代替に十分に近いノードを探し、次に、上記の判定基準（１）に従ってあらゆるノードをフィルタリング除去することである。
【０１３８】
大部分の推移確率がおよそ独立的であるという想定においてこれらのノードのそれぞれを仮定して、ＮおよびＮの代替の確率を推定する。
【０１３９】
（ｄ）問題になっているノードの間の全パスの確率を加えることにより、ＮおよびＮの代替の確率を推定する（そのうち一方は、（ｃ）に記載されているセットに由来し、そのうち他方は、ＮまたはＮの代替となる）。これらのパスの確率のそれぞれは、パスに含まれる全エッジの重みを掛けることにより推定される。
【０１４０】
（ｅ）確率のそれぞれを踏まえてアップデートし、正規化することにより、ＮおよびＮの代替の確率をアップデートする。本発明の方法およびシステムを使用して、他方に関する一部の情報（例えば、条件付きまたは確率的情報）を仮定した精度で、一部のバリアントを決定することができる。よって、ＳＮＰチップまたは同様の「直接的」アッセイが、一部のヌクレオチドの同一性をもたらす場合、ＬＤ研究またはその類似は、ゲノム内のある特定の位置における他のヌクレオチドの確率をもたらす。
【０１４１】
本明細書に記載されている方法は、ハードウェアとソフトウェアと任意選択でファームウェアを含むシステムを使用して行うことができる。
【０１４２】
図１４は、本明細書に記載されている方法の実施に有用なシステム１４０１を図解する。同定されたヌクレオチドに関する情報を、チップ１４０５からコンピュータにおいて受け取る。配列リードを、シーケンサー１４５５から、該機器から直接的に、あるいは配列リードの予備的収集およびいずれかの処理のために使用されるコンピュータ１４５１を経由して、受け取る。ネットワーク１４１５は、異なるコンピュータの間でデータおよび情報をリレーする。本明細書に記載されている方法のステップは、サーバコンピュータ１４０９またはパーソナルコンピュータデバイス１４３３（例えば、ラップトップ、デスクトップ、タブレット等）により行うことができる。コンピューティングデバイス１４３３を使用して、サーバ１４０９と相互作用して、方法ステップを開始するまたは結果を得ることができる。一般に、コンピュータは、メモリにカップリングされたプロセッサおよび少なくとも１個の入力／出力デバイスを含む。
【０１４３】
プロセッサは、Ｉｎｔｅｌ（Ｓａｎｔａ  Ｃｌａｒａ、ＣＡ）によって登録商標ＸＥＯＮ  Ｅ７で販売されるマイクロプロセッサまたはＡＭＤ（Ｓｕｎｎｙｖａｌｅ、ＣＡ）によって商標ＯＰＴＥＲＯＮ  ６２００で販売されるマイクロプロセッサ等の、いずれか適したプロセッサであり得る。
【０１４４】
メモリは一般に、有形の非一過性コンピュータ可読記憶デバイスを含み、記憶された命令（１または複数のソフトウェアアプリケーション）、データまたはその両方をその上または中に有するいずれかの機械可読媒体（単数または複数）を含むことができる。命令は、実行されると、本明細書に記載されている機能性のいずれかまたは全てを実装することができる。用語「コンピュータ可読記憶デバイス」は、１または複数のディスクドライブ、テープドライブ、フラッシュドライブ、ソリッドステートドライブ（ＳＳＤ）、メモリデバイス（例えば、ＲＡＭ、ＲＯＭ、ＥＰＲＯＭ等）、光学記憶デバイスおよび／または他のいずれかの非一過性および有形の記憶媒体（単数または複数）を限定することなく含むものと解釈されたい。
【０１４５】
本発明に従う入力／出力デバイスは、ビデオディスプレイユニット（例えば、液晶ディスプレイ（ＬＣＤ）またはブラウン管（ＣＲＴ）モニター）、英数字入力デバイス（例えば、キーボード）、カーソル制御デバイス（例えば、マウスまたはトラックバッド）、ディスクドライブユニット、信号発生器（例えば、スピーカー）、タッチスクリーン、加速度計、マイクロフォン、セルラー式ラジオ波アンテナ、および、例えば、ネットワークインターフェースカード（ＮＩＣ）、Ｗｉ−Ｆｉカード、またはセルラー式モデムでありうる、ネットワークインターフェースデバイスを含みうる。
参照による組込み
【０１４６】
本開示を通して特許、特許出願、特許公開、雑誌、書籍、論文、ウェブコンテンツなど、他の文献に対する言及および引用を行ってきた。全てのこのような文献は、参照によりそれらの全体において全て目的で本明細書に組み込まれる。
同等物
【０１４７】
当業者には、本明細書で示され、記載される実施形態に加えて、本発明の多様な改変およびその多くのさらなる実施形態も、本明細書で引用される研究文献および特許文献への言及を含む、本明細書の全内容から明らかとなろう。本明細書における対象物は、その多様な実施形態における本発明およびその同等物の実施に適応させうる、重要な情報、例示、および指針を含有する。
【図１】
2017510871.tif 000011
【図２】
2017510871.tif 000012
【図３】
2017510871.tif 000013
【図４】
2017510871.tif 000014
【図５】
2017510871.tif 000015
【図６】
2017510871.tif 000016
【図７】
2017510871.tif 000017
【図８】
2017510871.tif 000018
【図９】
2017510871.tif 000019
【図１０】
2017510871.tif 000020
【図１１】
2017510871.tif 000021
【図１２】
2017510871.tif 000022
【図１３】
2017510871.tif 000023
【図１４】
2017510871.tif 000024
【配列表】
2017510871000001.app
【国際調査報告】
2017510871.tif 000025
2017510871.tif 000026
2017510871.tif 000027