図面 (/)

技術 配列をアラインするための方法およびシステム

出願人 セブンブリッジズジェノミクスインコーポレイテッド
発明者 デニスクラル
出願日 2019年9月6日 (1年3ヶ月経過) 出願番号 2019-162661
公開日 2020年3月19日 (9ヶ月経過) 公開番号 2020-042813
状態 未査定
技術分野 酵素、微生物を含む測定、試験
主要キーワード 単独選択 プロセッサー間 出力配列 ウェーブフロント ディジタルカード 演算セット SCモデル 各処理エレメント
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2020年3月19日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (7)

課題

配列をアラインするための方法およびシステムを提供する。

解決手段

リード(例えば、核酸リード、アミノ酸リード)を基準配列構築物にアラインするための方法、基準配列構築物を構築するための方法、ならびにアライメント法および構築物を使用して、配列を作製するシステムを含む。方法は、拡張性があり、何百万ものリードを何千もの塩基長またはアミノ酸長の構築物にアラインするのに使用することができる。本発明は加えて、構築物内の場所への核酸リードのアライメントに基づき、疾患または遺伝子型を同定するための方法も含む。

概要

背景

背景
遺伝学は、分析科学から、情報科学へと進化している。研究者はかつて、どのようにして核酸を抽出および同定するのかで奮闘したが、今や、このような技法は、些末なものとなっている。次世代シーケンシング(NGS:next−generation sequencing)(例えば、全トランスクリプトームショットガンシーケンシング、ピロシーケンシング、イオン半導体シーケンシング、合成を介するシーケンシング)は、全ゲノムカバーする何百万ものリードを、わずか数日間で作り出すことが可能である。このスループットを達成するために、NGSシーケンシングでは、小型の核酸配列に対する大規模並列化であって、併せて、大きな遺伝情報体、例えば、染色体またはゲノムを構成する並列化を使用する。遺伝子試料から出発して、核酸(例えば、DNA)を切断し、増幅し、超高速で読み取る。これらの能力を考慮して、研究者は現在、いかにして(廉価に)リードをアラインして、疾患または疾患の危険性を指し示す配列内の遺伝子座を同定するのかで奮闘している。

最新アライメント法では、重複するリードを基準にアラインして、重要な遺伝情報または構造情報の探索を可能にする配列(例えば、疾患に関するバイオマーカー)を作製するのに、膨大な計算能力を使用する。最終的に、配列アライメントの目標は、シーケンサーにより作製される核酸リードのセットを組み合わせて、その対象に由来する遺伝子試料に基づき、長いリード(すなわち、コンティグ)、なおまたは対象の全ゲノムを達成することである。次世代シーケンサーからの配列データは、併せて標的配列の全体を表示する、何百万もの短い配列を含むことが多いため、リードのアラインは、複雑で計算が高価である。加えて、ランダムシーケンシングエラー(すなわち、不正確なシーケンシングマシン出力)により引き起こされる配列の歪みを最小化するためには、プローブされた配列の各部分を、複数回にわたり(例えば、2〜100回またはこれを超える回数にわたり)シーケンシングして、任意のランダムシーケンシングエラーの、作り出される最終アライメントおよび出力配列に対する影響を最小化する。最後に、核酸リードの全てに対応するデータの全てを収集したら、対象の全ての配列(またはその一部)を決定するために、リードを、単一の基準配列、例えばGRCh37にアラインする。多くの場合、個々のリードを実際に表示するわけではなく、アラインされた配列を、配列へとアセンブルし、配列を、データファイルとして提示する。

典型的には、配列アライメントは、2つの線形的な配列情報ストリング間の対応のあるアライメントを集約することにより構築される。アライメントの例として述べると、2つのストリングである、S1(配列番号12:AGCACGTACACTACC)およびS2(配列番号13:AGCTATCGTACTAGC)は、互いにアラインすることができる。典型的には、S1はリードに対応し、S2は基準配列の部分に対応する。互いに対して、S1およびS2は、置換欠失、および挿入からなっていてもよい。典型的には、条件は、ストリングS1からストリングS2への変換に関して定義される:置換は、S2内の文字または配列が、S1内の同じ長さの異なる文字または配列で置きかえられる場合に生じ、欠失は、S2内の文字または配列が、S1の対応する区画内で「スキップ」される場合に生じ、挿入は、文字または配列が、S1内の、S2内では隣接する2つの位置の間で生じる場合に生じる。例えば、2つの配列であるS1およびS2は、下記の通りにアラインすることができる。下記のアライメントは、13箇所のマッチ、長さ1の欠失、長さ2の挿入、および1箇所の置換:
(S1)AGCTA−CGTACACTACC(配列番号12)
(S2)AGCTATCGTAC−−TAGC(配列番号13)
を表示する。

業者は、配列アライメントのための正確なアルゴリズムおよび近似的なアルゴリズムが存在することを察知すると予想される。正確なアルゴリズムは、最高スコアのアライメントを見出すと予想されるが、計算が高価でありうる。2つの最も周知の正確なアルゴリズムは、Needleman−Wunsch(J Mol Biol、48巻(3号):443〜453頁、1970年)およびSmith−Waterman(J Mol Biol、147巻(1号):195〜197頁、1981年;Adv. in Math.、20巻(3号):367〜387頁、1976年)である。Gotoh(J Mol Biol、162巻(3号):705〜708頁、1982年)による、Smith−Watermanに対するさらなる改善は、計算時間を、O(m2n)からO(mn)[式中、mおよびnは、比較される配列サイズであり、並列処理により適する]へと短縮する。バイオインフォマテクスの分野では、Gotohの改変アルゴリズムが、Smith−Watermanアルゴリズムと称されることが多い。並列計算リソースが、より広くかつ廉価に利用可能となりつつあるので、Smith−Waterman法は、より多くの配列セットをより多くの基準配列にアラインするのに使用されている。例えば、http://aws.amazon.comで入手可能な、Amazon.comのクラウドコンピューティングリソースを参照されたい。上記の雑誌論文の全ては、参照によりそれらの全体において本明細書に組み込まれる。

Smith−Waterman(SW)アルゴリズムでは、配列内の塩基間の重複に対して加点し、配列間のギャップに対して減点することにより、直鎖状の配列をアラインする。Smith−Watermanはまた、SWは、短い配列が、長い配列を記載する文字のストリングにわたることを必要としないという点でも、Needleman−Wunschと異なる。すなわち、SWは、1つの配列が、他の配列の全体についてのリードであることを仮定しない。さらに、SWは、ストリングの全長にわたり伸長するアライメントを見出さなくてもよいため、局所的アライメントは、2つの配列内のどこでも開始および終結させることが可能である。

下記の式(1):



との関連で述べると、SWアルゴリズムは、長さnおよびmの2つのストリングを表示する、n×m行列Hで容易に表示される。上記の式では、s(ai,bj)は、マッチボーナス(ai=bjである場合)またはミスマッチペナルティー(ai≠bjである場合)を表し、挿入および欠失には、それぞれ、ペナルティーWinおよびWdelが課される。大半の場合、結果として得られる行列は、ゼロである多くの成分を有する。この表示は、行列内上行下行右列左列バックトレースを容易とし、これにより、アライメントの同定を容易とする。

行列にスコアを完全に投入したら、SWアルゴリズムにより、バックトラックを実施して、アライメントを決定する。アルゴリズムは、行列内の最大値から始めて、各セルの最終的な最大値を計算するのに3つの値(Hi−1,j−1、Hi−1,j、またはHi,j−1)のうちのいずれを使用したのかに基づき、バックトラックすると予想される。バックトラッキングは、ゼロに到達すると停止される。例えば、先行技術を表すものではなく、バックトラックの概念と、バックトラックが読み取られた場合の、対応する局所的アライメントとを説明するものである、図3(B)を参照されたい。したがって、アルゴリズムにより決定された「最良のアライメント」は、可能な最小数を超える挿入および欠失を含有しうるが、可能な最大数をはるかに下回る置換を含有すると予想される。

SWまたはSW−Gotohとして適用する場合、技法では、動的計画法アルゴリズムを使用して、それぞれ、サイズをmおよびnとする、2つのストリングSおよびAの局所的配列アライメントを実施する。この動的計画法では、表または行列を採用して、マッチスコアを保存し、一連のセルについての再計算を回避する。ストリングの各成分は、配列の文字に関するインデックスが付されていてもよく、すなわち、SがストリングATCGAAであれば、S[1]=A、S[4]=Gなどである。最適のアライメントをHi,j(上記)と表す代わりに、最適のアライメントは、下記の式(2):



のB[j,k]と表すことができる。最大値関数であるB[j,k]の引数を、下記の式(3)〜(5)[式中、MISMATCH_PENALTY、MATCH_BONUS、INSERTION_PENALTY、DELETION_PENALTY、およびOPENING_PENALTYは、全て定数であり、MATCH_BONUSを除き、全て負である]に概括する。マッチの引数であるp[j,k]は、下記の式(3):



で与えられ、挿入の引数であるi[j,k]は、下記の式(4):



で与えられ、欠失の引数であるd[j,k]は、下記の式(5):



で与えられる。3つの引数全てについて、[0,0]成分は、ゼロと置いて、バックトラックの完了を確認する、すなわち、p[0,0]=i[0,0]=d[0,0]=0とする。

スコア付けパラメータは、ある程度任意のものであり、計算の挙動を達成するように調整することができる。DNAのためのスコア付けパラメータ設定の一例(Huang、3章:Bio−Sequence Comparison and Alignment、Curr Top Comp Mol Biolシリーズ、Cambridge、Mass.: TheMIT Press、2002年)であれば、
MATCH_BONUS:10
MISMATCH_PENALTY:−20
INSERTION_PENALTY:−40
OPENING_PENALTY:−10
DELETION_PENALTY:−5
となる。上記のギャップペナルティー(INSERTION_PENALTY、OPENING_PENALTY)の間の関係は、ギャップ挿入ペナルティーを、ギャップオープニングコストより大きく設定することにより、ギャップオープニングの数を制限する、すなわち、ギャップをまとめてグループ化することを支援する一助となる。当然ながら、MISMATCH_PENALTY、MATCH_BONUS、INSERTION_PENALTY、OPENING_PENALTY、およびDELETION_PENALTYの間の代替的な関係も可能である。

概要

配列をアラインするための方法およびシステムを提供する。リード(例えば、核酸リード、アミノ酸リード)を基準配列構築物にアラインするための方法、基準配列構築物を構築するための方法、ならびにアライメント法および構築物を使用して、配列を作製するシステムを含む。方法は、拡張性があり、何百万ものリードを何千もの塩基長またはアミノ酸長の構築物にアラインするのに使用することができる。本発明は加えて、構築物内の場所への核酸リードのアライメントに基づき、疾患または遺伝子型を同定するための方法も含む。

目的

最終的に、配列アライメントの目標は、シーケンサーにより作製される核酸リードのセットを組み合わせて、その対象に由来する遺伝子試料に基づき、長いリード(すなわち、コンティグ)、なおまたは対象の全ゲノムを達成することである

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

本明細書に記載の発明。

技術分野

0001

関連出願
本出願は、2013年9月3日に出願された米国特許出願第14/016,833号および2013年8月21日に出願された米国特許出願第61/868,249号の優先権を主張し、当該出願の両方は、その全体が本明細書において参考として援用される。

0002

技術分野
本発明は、配列(例えば、核酸配列アミノ酸配列)を互いにアラインして、試料(例えば、遺伝子試料タンパク質試料)に対応する連続的な配列リードを作製するための方法およびシステムに関する。本発明は加えて、試料中の変異型を同定するための方法にも関する。

背景技術

0003

背景
遺伝学は、分析科学から、情報科学へと進化している。研究者はかつて、どのようにして核酸を抽出および同定するのかで奮闘したが、今や、このような技法は、些末なものとなっている。次世代シーケンシング(NGS:next−generation sequencing)(例えば、全トランスクリプトームショットガンシーケンシング、ピロシーケンシング、イオン半導体シーケンシング、合成を介するシーケンシング)は、全ゲノムカバーする何百万ものリードを、わずか数日間で作り出すことが可能である。このスループットを達成するために、NGSシーケンシングでは、小型の核酸配列に対する大規模並列化であって、併せて、大きな遺伝情報体、例えば、染色体またはゲノムを構成する並列化を使用する。遺伝子試料から出発して、核酸(例えば、DNA)を切断し、増幅し、超高速で読み取る。これらの能力を考慮して、研究者は現在、いかにして(廉価に)リードをアラインして、疾患または疾患の危険性を指し示す配列内の遺伝子座を同定するのかで奮闘している。

0004

最新アライメント法では、重複するリードを基準にアラインして、重要な遺伝情報または構造情報の探索を可能にする配列(例えば、疾患に関するバイオマーカー)を作製するのに、膨大な計算能力を使用する。最終的に、配列アライメントの目標は、シーケンサーにより作製される核酸リードのセットを組み合わせて、その対象に由来する遺伝子試料に基づき、長いリード(すなわち、コンティグ)、なおまたは対象の全ゲノムを達成することである。次世代シーケンサーからの配列データは、併せて標的配列の全体を表示する、何百万もの短い配列を含むことが多いため、リードのアラインは、複雑で計算が高価である。加えて、ランダムシーケンシングエラー(すなわち、不正確なシーケンシングマシン出力)により引き起こされる配列の歪みを最小化するためには、プローブされた配列の各部分を、複数回にわたり(例えば、2〜100回またはこれを超える回数にわたり)シーケンシングして、任意のランダムシーケンシングエラーの、作り出される最終アライメントおよび出力配列に対する影響を最小化する。最後に、核酸リードの全てに対応するデータの全てを収集したら、対象の全ての配列(またはその一部)を決定するために、リードを、単一の基準配列、例えばGRCh37にアラインする。多くの場合、個々のリードを実際に表示するわけではなく、アラインされた配列を、配列へとアセンブルし、配列を、データファイルとして提示する。

0005

典型的には、配列アライメントは、2つの線形的な配列情報ストリング間の対応のあるアライメントを集約することにより構築される。アライメントの例として述べると、2つのストリングである、S1(配列番号12:AGCACGTACACTACC)およびS2(配列番号13:AGCTATCGTACTAGC)は、互いにアラインすることができる。典型的には、S1はリードに対応し、S2は基準配列の部分に対応する。互いに対して、S1およびS2は、置換欠失、および挿入からなっていてもよい。典型的には、条件は、ストリングS1からストリングS2への変換に関して定義される:置換は、S2内の文字または配列が、S1内の同じ長さの異なる文字または配列で置きかえられる場合に生じ、欠失は、S2内の文字または配列が、S1の対応する区画内で「スキップ」される場合に生じ、挿入は、文字または配列が、S1内の、S2内では隣接する2つの位置の間で生じる場合に生じる。例えば、2つの配列であるS1およびS2は、下記の通りにアラインすることができる。下記のアライメントは、13箇所のマッチ、長さ1の欠失、長さ2の挿入、および1箇所の置換:
(S1)AGCTA−CGTACACTACC(配列番号12)
(S2)AGCTATCGTAC−−TAGC(配列番号13)
を表示する。

0006

業者は、配列アライメントのための正確なアルゴリズムおよび近似的なアルゴリズムが存在することを察知すると予想される。正確なアルゴリズムは、最高スコアのアライメントを見出すと予想されるが、計算が高価でありうる。2つの最も周知の正確なアルゴリズムは、Needleman−Wunsch(J Mol Biol、48巻(3号):443〜453頁、1970年)およびSmith−Waterman(J Mol Biol、147巻(1号):195〜197頁、1981年;Adv. in Math.、20巻(3号):367〜387頁、1976年)である。Gotoh(J Mol Biol、162巻(3号):705〜708頁、1982年)による、Smith−Watermanに対するさらなる改善は、計算時間を、O(m2n)からO(mn)[式中、mおよびnは、比較される配列サイズであり、並列処理により適する]へと短縮する。バイオインフォマテクスの分野では、Gotohの改変アルゴリズムが、Smith−Watermanアルゴリズムと称されることが多い。並列計算リソースが、より広くかつ廉価に利用可能となりつつあるので、Smith−Waterman法は、より多くの配列セットをより多くの基準配列にアラインするのに使用されている。例えば、http://aws.amazon.comで入手可能な、Amazon.comのクラウドコンピューティングリソースを参照されたい。上記の雑誌論文の全ては、参照によりそれらの全体において本明細書に組み込まれる。

0007

Smith−Waterman(SW)アルゴリズムでは、配列内の塩基間の重複に対して加点し、配列間のギャップに対して減点することにより、直鎖状の配列をアラインする。Smith−Watermanはまた、SWは、短い配列が、長い配列を記載する文字のストリングにわたることを必要としないという点でも、Needleman−Wunschと異なる。すなわち、SWは、1つの配列が、他の配列の全体についてのリードであることを仮定しない。さらに、SWは、ストリングの全長にわたり伸長するアライメントを見出さなくてもよいため、局所的アライメントは、2つの配列内のどこでも開始および終結させることが可能である。

0008

下記の式(1):



との関連で述べると、SWアルゴリズムは、長さnおよびmの2つのストリングを表示する、n×m行列Hで容易に表示される。上記の式では、s(ai,bj)は、マッチボーナス(ai=bjである場合)またはミスマッチペナルティー(ai≠bjである場合)を表し、挿入および欠失には、それぞれ、ペナルティーWinおよびWdelが課される。大半の場合、結果として得られる行列は、ゼロである多くの成分を有する。この表示は、行列内上行下行右列左列バックトレースを容易とし、これにより、アライメントの同定を容易とする。

0009

行列にスコアを完全に投入したら、SWアルゴリズムにより、バックトラックを実施して、アライメントを決定する。アルゴリズムは、行列内の最大値から始めて、各セルの最終的な最大値を計算するのに3つの値(Hi−1,j−1、Hi−1,j、またはHi,j−1)のうちのいずれを使用したのかに基づき、バックトラックすると予想される。バックトラッキングは、ゼロに到達すると停止される。例えば、先行技術を表すものではなく、バックトラックの概念と、バックトラックが読み取られた場合の、対応する局所的アライメントとを説明するものである、図3(B)を参照されたい。したがって、アルゴリズムにより決定された「最良のアライメント」は、可能な最小数を超える挿入および欠失を含有しうるが、可能な最大数をはるかに下回る置換を含有すると予想される。

0010

SWまたはSW−Gotohとして適用する場合、技法では、動的計画法アルゴリズムを使用して、それぞれ、サイズをmおよびnとする、2つのストリングSおよびAの局所的配列アライメントを実施する。この動的計画法では、表または行列を採用して、マッチスコアを保存し、一連のセルについての再計算を回避する。ストリングの各成分は、配列の文字に関するインデックスが付されていてもよく、すなわち、SがストリングATCGAAであれば、S[1]=A、S[4]=Gなどである。最適のアライメントをHi,j(上記)と表す代わりに、最適のアライメントは、下記の式(2):



のB[j,k]と表すことができる。最大値関数であるB[j,k]の引数を、下記の式(3)〜(5)[式中、MISMATCH_PENALTY、MATCH_BONUS、INSERTION_PENALTY、DELETION_PENALTY、およびOPENING_PENALTYは、全て定数であり、MATCH_BONUSを除き、全て負である]に概括する。マッチの引数であるp[j,k]は、下記の式(3):



で与えられ、挿入の引数であるi[j,k]は、下記の式(4):



で与えられ、欠失の引数であるd[j,k]は、下記の式(5):



で与えられる。3つの引数全てについて、[0,0]成分は、ゼロと置いて、バックトラックの完了を確認する、すなわち、p[0,0]=i[0,0]=d[0,0]=0とする。

0011

スコア付けパラメータは、ある程度任意のものであり、計算の挙動を達成するように調整することができる。DNAのためのスコア付けパラメータ設定の一例(Huang、3章:Bio−Sequence Comparison and Alignment、Curr Top Comp Mol Biolシリーズ、Cambridge、Mass.: TheMIT Press、2002年)であれば、
MATCH_BONUS:10
MISMATCH_PENALTY:−20
INSERTION_PENALTY:−40
OPENING_PENALTY:−10
DELETION_PENALTY:−5
となる。上記のギャップペナルティー(INSERTION_PENALTY、OPENING_PENALTY)の間の関係は、ギャップ挿入ペナルティーを、ギャップオープニングコストより大きく設定することにより、ギャップオープニングの数を制限する、すなわち、ギャップをまとめてグループ化することを支援する一助となる。当然ながら、MISMATCH_PENALTY、MATCH_BONUS、INSERTION_PENALTY、OPENING_PENALTY、およびDELETION_PENALTYの間の代替的な関係も可能である。

先行技術

0012

J Mol Biol、48巻(3号):443〜453頁、1970年
J Mol Biol、147巻(1号):195〜197頁、1981年
Adv. in Math.、20巻(3号):367〜387頁、1976年
Gotoh(J Mol Biol、162巻(3号):705〜708頁、1982年
Huang、3章:Bio−Sequence Comparison and Alignment、Curr Top Comp Mol Biolシリーズ、Cambridge、Mass.: TheMIT Press、2002年

発明が解決しようとする課題

0013

アライメントが完了したら、アラインされた配列を、基準(すなわち、遺伝的標準)と比較して、変異型を同定しうる配列を作製するように、アセンブルすることができる。変異型は、疾患、病期再発などに関する洞察をもたらしうる。アミノ酸アライメントの場合、アセンブルされたアミノ酸配列を、標準と比較して、タンパク質についての進化情報またはタンパク質についての機能情報を決定することができる。しかし、変異型の多くは、疾患と必ずしも相関しているわけではないため、疾患比較のこの標準法は時間がかかる。例えば、遺伝的標準が、試料と異なる先祖を有する人口集団に由来する場合、判定される変異型の多くは、毛髪の色、皮膚の色などのことがらの差違に起因する。

課題を解決するための手段

0014

本発明は、アルゴリズムおよびその実行のための方法であって、例えば、Smith−Waterman−Gotohなど、線形的な局所的配列アライメント工程を、並列化の増大、速度の増大、精度の増大、および全ゲノムを通してリードをアラインする能力をもたらす、多次元的アライメントアルゴリズムへと変換するアルゴリズムおよび方法を提供する。本発明のアルゴリズムは、配列情報(Smith−Watermanにおけるのと同様な)についての「遡及」型の解析をもたらすが、公知の線形的方法とは対照的に、本発明の遡及は、全般的ミスマッチ率、欠失率、および挿入率の低下を達成しながら、錯綜として長大な配列リードについてのより精密なアライメントをもたらすために、複数の経路および複数のノードを含む多次元空間を介して実行される。

0015

実際的には、本発明は、配列リードを、一連の有向巡回配列であって、アライメント内の、可能な配列変異の全てまたはほぼ全てであり、挿入、欠失、および置換を含む配列変異を構成する分枝点間にわたる配列にアラインすることにより実行される。有向非巡回グラフ(DAG:directed acyclic graph)として表示されることが多い、このような構築物は、「受け入れられた」基準配列および変異型判定フォーマットVCF:variant call format)のエントリーを含む、利用可能な配列データベースから容易にアセンブルすることができる。したがって、DAGまたは他の有向構築物と組み合わされると、開示されるアルゴリズムは、配列アライメントへの多次元手法であって、アライメントの精度を大幅に改善し、従来のアルゴリズムでは不可能な配列分解能を可能とする多次元手法をもたらす。実際、技法は、任意の配列情報と共に使用しうるが、本明細書で論じられる通り、核酸配列およびアミノ酸配列をアラインするのに最も有用である。

0016

本発明は、加えて、基準配列構築物、例えば、ゲノムの各遺伝子座において公知の変異型を表示するDAGを使用して、特異的な遺伝子座において、特異的な塩基判定を下す方法も提供する。配列リードは、アライメント時にDAGにアラインされるため、突然変異を、基準ゲノムと突き合わせて、公知の突然変異についての表と比較する後続のステップを廃することができる。開示される方法を使用すると、それは、核酸リードを、DAG上に表示される公知の突然変異に位置するものとして同定し、その突然変異を判定することであるに過ぎない。代替的に、突然変異が公知でない(すなわち、基準配列構築物内で表示されない)場合も、アライメントは見出され、変異型は、新たな突然変異として同定される。方法はまた、特異的な疾患の危険性または疾患の進行などのさらなる情報を、基準配列構築物へと組み込まれた公知の突然変異と関連付けることも可能とする。さらに、全ての遺伝学的に関連する結果を、アライメント時に見出す潜在的可能性を有することに加えて、開示される方法は、複数の基準配列との同時比較を可能としながら、アライメントの作製に求められる計算資源縮減する。

0017

本発明は、生物の配列内の位置において、公知の変異型を表示する、有向非巡回グラフ(DAG)データ構造を構築するための方法もさらに含む。DAGは、何千箇所もの位置において、複数の配列を含むことが可能であり、各位置において、欠失、挿入、翻訳逆位、および一塩基多型(SNP)を含む、複数の変異型を含みうる。また、DAG内の各変異型に、「乳がん」など、相関する診断情報タグ付けし、これにより、試料を提供する患者に対する危険性を同定するのに必要とされるステップを縮減することも可能である。一部の実施形態では、変異型を、スコア付けするか、重み付けするか、または他の変異型と相関させ、疾患についてのマーカーとしてその変異型の発生率を反映させることになろう。

0018

本発明は、本発明の方法を実行するためのシステムもさらに含む。一実施形態では、システムは、複数の配列(すなわち、核酸配列、アミノ酸配列)を、ゲノム内またはゲノムの領域内で観察される変異を表示する基準配列構築物(例えば、DAG)と比較することが可能な、プロセッサーおよび記憶装置分散型ネットワークを含む。システムは、加えて、効率的なアライメントアルゴリズムを使用して、連続的な配列を作製するように、核酸リードをアラインすることが可能である。基準配列構築物は、膨大な冗長情報圧縮し、アライメントアルゴリズムは、極めて効率的であるため、市販のリソースを使用して、全ゲノム上でリードにタグ付けし、アセンブルすることができる。システムは、複数のリードと基準配列構築物との複数の比較を同時に実行する複数のプロセッサーを含む。比較データは、蓄積し、医療提供者へと提示することができる。比較は、計算により扱いやすいため、配列リードの解析はもはや、NGSシーケンシングと患者の遺伝的危険性についての有意義議論との間のボトルネックを表さないと予想される。

図面の簡単な説明

0019

図1は、基準配列内の遺伝子変異を表示する有向非巡回グラフ(DAG)の構築について描示する図である。図1(A)は、出発基準配列および欠失の付加を示す図である。図1(B)は、挿入およびSNPの付加であり、これにより、アライメントに使用される最終的なDAGに到達することを示す図である。
図1は、基準配列内の遺伝子変異を表示する有向非巡回グラフ(DAG)の構築について描示する図である。図1(A)は、出発基準配列および欠失の付加を示す図である。図1(B)は、挿入およびSNPの付加であり、これにより、アライメントに使用される最終的なDAGに到達することを示す図である。

0020

図2は、有向非巡回グラフとして表示される、3つの変異型判定フォーマット(VCF)のエントリーについて描示する図である。

0021

図3(A)は、核酸配列リードを、挿入イベントならびに基準配列からなる構築物にアラインすることについての、図解による表示である。図3(B)は、核酸配列リード「ATCGAA」の適正な場所を同定するのに使用される、行列およびバックトラックを示す図である。

0022

図4は、並列処理のための連想計算モデルについて描示する図である。

0023

図5は、並列計算のためのアーキテクチャーについて描示する図である。

実施例

0024

本発明は、配列(例えば、核酸配列、アミノ酸配列)を、基準配列構築物にアラインするための方法、基準配列構築物を構築するための方法、ならびにアライメント法および構築物を使用して、アライメントおよびアセンブリーを作製するシステムを含む。基準配列構築物は、下記で記載される、有向非巡回グラフ(DAG)でありうるが、基準配列は、構築物が、アライメントのためにフォーマットされていることを条件として、種内の異なる生物の配列内の遺伝的変異性を反映する任意の表示でありうる。遺伝的変異性はまた、生物における異なる組織間または異なる細胞間の遺伝的変異性でもある。一般に、基準配列構築物は、サンプリングされた配列の間で同一な部分と、サンプリングされた配列の間で変化する部分とを含むと予想される。したがって、構築物は、同じ配列を含む位置(すなわち、いくつかのカノニカル秩序付けに従う)と、遺伝的変異性を反映する代替配列を含むいくつかの位置とを有すると考えることができる。本出願は、加えて、核酸リードの、構築物内の場所に対するアライメントに基づき、疾患または遺伝子型を同定するための方法も開示する。方法は、遺伝子シーケンシングおよび突然変異スクリーニングの分野に広く適用可能である。

0025

基準配列構築物
核酸リードをアラインして遺伝子型解析するのに単一の基準配列を使用する先行技術による配列アライメント法と異なり、本発明では、種内、集団内、なおまたは単一の生物における異なる細胞間の遺伝子配列変異性を構成しうる構築物を使用する。遺伝子変異についての表示は、有向非巡回グラフ(DAG)(上記で論じた)の行−列によるアライメント行列、またはdeBruijnグラフとして提示することができ、これらの構築物は、アライメントアルゴリズムのパラメータを適正に設定する(下記で論じる)ことを条件として、本発明のアライメント法と共に使用することができる。

0026

本発明の好ましい実施形態では、構築物は、有向非巡回グラフ(DAG)である、すなわち、方向を有するが、巡回経路を有さない構築物である(すなわち、配列経路は、基準構築物上のある位置を1回より多く通って巡回し得ない)。DAGでは、配列内の遺伝子変異を、代替的なノードとして表示する。ノードは、保存的配列の区画の場合もあり、遺伝子の場合もあり、単に核酸の場合もある。構築物を通る、異なる可能な経路は、公知の遺伝子変異を表示する。DAGは、生物の全ゲノムについて構築することもでき、ゲノムの部分、例えば、染色体、または遺伝情報の小セグメントだけについて構築することもできる。一部の実施形態では、DAGは、1000を超える核酸、例えば、10,000を超える核酸、例えば、100,000を超える核酸、例えば、1,000,000を超える核酸を表示する。DAGは、種(例えば、Homo sapiens)を表示する場合もあり、選択された集団(例えば、乳がんを有する女性)を表示する場合もあり、または同じ個体における異なる腫瘍細胞間の遺伝子変異など、さらに小さな部分集団を表示する場合もある。

0027

DAG構築の簡単な例を、図1に示す。図1(A)に示される通り、DAGは、図1(A)に配列番号1:CATGTACCTAGGTCTTGGAGCTAGTCとして示される基準配列で始まる。実際的には、基準配列は、はるかに長いことが多く、全ゲノムでありうる。配列は、FASTAファイルまたはFASTQファイルとして保存される(FASTQは、次世代シーケンサーから作製された配列データのためのデフォルトフォーマットとなっている)ことが典型的である。一部の実施形態では、基準配列は、GRCh37などの標準的な基準でありうる。当業者により認識される通り、配列内の各文字(または記号)は、実際的には、ヌクレオチド(例えば、デオキシリボヌクレオチドまたはリボヌクレオチド)またはアミノ酸(例えば、ヒスチジンロイシンリシンなど)に対応する。

0028

次のステップでは、図1(A)の下図に示される通り、変異型を、基準配列へと付加する。図1(A)に示される変異型は、図中の直線間の基準からの、配列「AG」の欠失である(すなわち、配列番号2)。図上では、この欠失を、基準配列を、欠失の前後でノードへと切断し、2つのストリングを、ノードの間に挿入することにより表示する。ノードの間の1つの経路は、基準配列を表示するが、他の経路は、欠失を表示する。

0029

実際的には、変異型は、1000 Genomes Projectウェブサイトで見出されうるVCFファイルなどの、変異型判定フォーマット(VCF)ファイル内のエントリーを適用することにより、DAGに照らして判定する。各VCFファイルは、特異的な基準ゲノムに適合させてあるため、ストリングがどこに位置するのかを同定することは、困難ではない。実際、VCFファイル内の各エントリーは、図2に表示される通り、基準と組み合わせて、別個のグラフを創出するエントリーと考えることができる。図2中のVCFエントリーは、図1のVCFエントリーに対応しないことに注目されたい。

0030

図1(B)に移ると、特異的な位置における挿入「GG」に対応する、第2のVCFエントリーを付加して、伸長型DAG、すなわち、配列番号3および配列番号4を含むDAGを作製する。次に、第3のVCFエントリーを、伸長型DAGへと付加して、基準配列内の初期のSNP、すなわち、配列番号5〜8を含むSNPを構成することができる。こうして、3つのステップで、核酸リードをアラインさせることができるDAGが創出された(下記で論じられる)。

0031

実際的には、DAGは、コンピュータメモリ内(ハードディスクフラッシュメモリクラウドメモリなどの中)に、ノードのセットSとして表示され、各ノードは、ストリング、親ノードのセット、および位置により規定される。ストリングとは、ノードの「内容物」、すなわち、配列であり、親ノードは、ノードの位置を、グラフ内の他のノードに照らして規定し、ノードの位置は、システム内のいくつかのカノニカルの秩序付け、例えば、基準ゲノムに対する位置である。グラフを、基準配列に照らして規定することが厳密に必要なわけではないが、これにより、出力データの操作が簡略となる。当然ながら、Sに対するさらなる制約は、それがループを含み得ないことである。

0032

このDAG法を、大型の構造へと外挿することにより、基準の所与の領域について、遺伝子配列内の公知の変異を表示する、何千ものVCFエントリーを組み込むDAGを構築することが可能である。しかしながら、DAGが嵩高くなると、計算も長くかかるので、多くの適用では、配列の部分、例えば、染色体だけを表示しうる、小型のDAGを使用する。他の実施形態では、DAGにより包含される集団のサイズを縮減することにより、例えば、乳がんにおける変異を表示するDAGから、トリプルネガティブ乳がんにおける変異を表示するDAGへと移行することにより、DAGを小型とすることができる。代替的に、試料間不変である、DAGの大部分を結果としてもたらすことが典型的な、容易に同定される遺伝子マーカーに基づきカスタマイズされた、長大なDAGも使用することができる。例えば、アフリカ系女性に由来する核酸リードのセットを、アフリカ系女性に由来するVCFエントリーにより創出されたDAGにアラインすれば、同じ配列にわたりヒトにおいて公知の全ての変異を構成するDAGと比較して速いと予想される。本発明のDAGは、それらが、時間の経過に応じて、新たに同定された突然変異を組み込むように改変されうるという点で、動的構築物であることを認識されたい。加えて、また、アライメント結果をDAGへと再帰的に付加するアルゴリズムも可能である。

0033

ストリング対DAGアライメントの場合は、ギャップペナルティーを、ギャップ挿入のコストをなおより大きくし、これにより、全体的な配列内の新たなギャップのオープニングではなく、配列に対するアライメントを支援するように調整することができる。当然ながら、DAG内の改善(上記で論じた)により、突然変異は、DAG内で構成されるため、ギャップの発生は、なおさらに減少するはずである。

0034

アライメントアルゴリズム
一実施形態では、アルゴリズムを使用して、配列リードを、有向非巡回グラフ(DAG)にアラインする。「発明の背景」で表されたアルゴリズムと異なり、アライメントアルゴリズムでは、DAG(例えば、基準配列構築物)上の位置において含有される各配列に対する最大スコアを同定することにより、Cijの最大値を同定する。実際、先行する位置を「振り返って」見ることにより、複数の可能な経路にわたり最適のアライメントを同定することが可能である。

0035

本発明のアルゴリズムは、上記で論じた通り、リード(また「ストリング」としても公知)および有向非巡回グラフ(DAG)上で実行される。アルゴリズムを規定する目的で、Sを、アラインされるストリングとし、Dを、Sがアラインされる有向非巡回グラフとする。ストリングSの成分において、1で始まるインデックスがカッコ内に示される。したがって、SがストリングATCGAAであれば、S[1]=A、S[4]=Gなどである。

0036

DAGでは、ノードの配列の各文字は、別個の成分であるdとして表示されることになる。dの先行成分は、以下のように定義される。
(i)dが、そのノードの配列の第1の文字でなければ、そのノード内のdに先行する文字が、その(唯一の)先行成分であり、
(ii)dが、そのノードの配列の第1の文字であれば、任意のノードの配列の最後の文字であって、dのノードの親である文字が、dの先行成分である。

0037

全ての先行成分のセットは、P[d]として表示する。

0038

「最良の」アライメントを見出すために、アルゴリズムでは、Sの最初のj個の成分の、dに先行する(およびdを含む)DAGの部分による最適のアライメントについてのスコアである、M[j,d]の値を求める。このステップは、「発明の背景」節中の式1内のHijを見出すステップと同様である。具体的に、M[j,d]を決定するステップは、下記:
M[j,d]=max{a,i,e,0} (6)
[式中、
P[d]中のp*について、e=max{M[j,p*]+DELETE_PENALTY}
i=M[j−1,d]+INSERT_PENALTY
S[j]=dならば、P[d]中のp*について、a=max{M[j−1,p*]+MATCH_SCORE};
S[j]≠dならば、P[d]中のp*について、a=max{M[j−1,p*]+MISMATCH_PENALTY}
で規定される通り、a、i、e、および0のうちの最大値を見出すことを伴う。

0039

上記で記載した通り、eとは、Sの最初のj個の文字の、DAGの部分であって、dまでであるが、dを含まない部分によるアライメントのうちの最高のスコアに、追加のDELETE_PENALTYを加えた値である。したがって、dが、ノードの配列の第1の文字でなければ、唯一の先行成分pが存在し、Sの最初のj個の文字の、DAG(pまでであり、pを含む)によるアライメントスコアは、M[j,p]+DELETE_PENALTYと等しい。dが、そのノードの配列の第1の文字である場合、複数の可能な先行成分が存在することが可能であり、DELETE_PENALTYは定数であるため、[M[j,p*]+DELETE_PENALTY]を最大化することは、先行成分を、Sの最初のj個の文字による最高のアライメントスコアと共に選択することと同じである。

0040

式(6)では、iとは、ストリングSの最初のj−1個の文字の、dまでであり、dを含むDAGによるアライメントに、SWにおける挿入引数の定義(式1を参照されたい)と同様のINSERT_PENALTYを加えた値である。

0041

加えて、aとは、Sの最初のj個の文字の、DAGの部分であって、dまでであるが、dを含まない部分によるアライメントのうちの最高のアライメントに、MATCH_SCORE(Sのj番目の文字が、文字dと同じである場合)またはMISMATCH_PENALTY(Sのj番目の文字が、文字dと同じでない場合)を加えた値である。eと同様に、これは、dが、そのノードの配列の第1の文字でなければ、唯一の先行成分、すなわち、pが存在することを意味する。これは、aが、Sの最初のj−1個の文字の、DAG(pまでであり、pを含む)によるアライメントスコア、すなわち、dとSのj番目の文字とがマッチするのかどうかに応じて、MISMATCH_PENALTYまたはMATCH_SCOREを付加したM[j−1,p]であることを意味する。dが、そのノードの配列の第1の文字である場合、複数の可能な先行成分が存在しうる。この場合、{M[j,p*]+MISMATCH_PENALTYまたはMATCH_SCORE}を最大化することは、先行成分を、Sの最初のj−1個の文字による最高のアライメントスコア(すなわち、M[j−1,p*]の候補引数の最高値)と共に選択し、dとSのj番目の文字とがマッチするのかどうかに応じて、MISMATCH_PENALTYまたはMATCH_SCOREを付加することと同じである。

0042

ここでもまた、「発明の背景」で論じられたSWアルゴリズムの場合と同様に、ペナルティー、例えば、DELETE_PENALTY、INSERT_PENALTY、MATCH_SCORE、およびMISMATCH_PENALTYは、少数のギャップを伴うアライメントを促すなどのように調整することができる。

0043

上記の式で記載されている通り、アルゴリズムでは、各リードについて、その成分についての挿入スコア、欠失スコア、およびマッチスコアを計算するだけでなく、DAG上の任意の先行ノードを振り返って見て(DAGの方向と反対方向に)、最大のスコアを見出すことにより、最大値を見出す。こうして、アルゴリズムは、DAGを通る異なる経路であって、公知の突然変異を含有する経路を横断的に検討することが可能である。グラフは有向であるため、グラフの方向と反対方向に移動するバックトラックは、グラフの起点に向かって好ましい変異型配列を追跡し、最大値のアライメントスコアは、最も可能性の高いアライメントを、高い確実性で同定する。上記の式は、「最大」値として表示されるが、「最大」は、例えば、式の全てにおいて記号を切り替え最小値について解くことを含む、最適化の任意の形態を包含することを意図する。

0044

開示されるアルゴリズムの実行について、図3で例示するが、ここで配列「ATCGAA」を、基準配列である配列番号10:TTGGATATGGGと、公知の挿入イベントである



[配列中、挿入には下線を付す]とを表示するDAGにアラインする。図3(A)が、DAGと比較されるリードについての図解による表示を示すのに対し、図3(B)は、比較に対応する実際の行列を示す。「発明の背景」で論じられたSmith−Waterman法と同様に、本発明のアルゴリズムでは、最高のスコアを同定し、バックトラックを実施して、リードの適正な場所を同定する。図3(A)およびBまた、本発明が、ストリングについて、構築物に対する実際のマッチをもたらすのに対し、公知の方法(例えば、SW)であったら、ストリングを、基準の誤った部分にアラインする、またはストリングを、アライメント内に含まれるのに十分に高いアライメントスコアをもたらさないものとして棄却した可能性が高いことも強調する。配列リードが、DAG内に含まれていなかった変異型を含む場合、アラインされた配列は、ギャップ、挿入などを伴うと報告されると予想される。

0045

並列化の可能性
Smith−Waterman−Gotohアルゴリズムの逐次形は、大規模な並列化に適応し、大幅に改変されている。例えば、超並列連想処理を使用するSmith−Waterman法(SWAMP)と呼ばれるASCモデルについては、参照によりその全体において本明細書に組み込まれる、米国特許公開第2012/0239706号において記載されている。SWAMP(および他の並列処理システム)のための並列化の一部は、任意の反対角成分に沿った値が、互いから独立であるという事実から来る。こうして、所与の反対角成分に沿ったセルの全ては、計算資源を分散させるように、並列的に処理することができる。上記の再帰式で示されたデータの依存性により、達成可能な並列処理のレベルは制限されるが、ウェーブフロント法を使用することにより、この有用なアルゴリズムはさらに加速化されると予想される。Wozniak(Comput Appl in
the Biosciences(CABIOS)、13巻(2号):145〜150頁、1997年)により、Sun Ultra SPARC上で実行されるウェーブフロント法では、特化したSIMD様のビデオ処理命令を使用する。Wozniakは、SIMDレジスターを使用して、副対角成分に沿った値を保存したところ、同じマシン上の従来の実行に対して2倍の加速化を報告している。Wozniakの例に続く、コードを並列化する同様の様式は、ストリーミングSIMD拡張SSE:Streaming SIMD Extension)セットを、x86アーキテクチャーに使用することである。Intelにより設計されたベクトル演算では、少数の値(通例、4つ、8つ、または16の値)に対する単一の演算/命令を、一度に完了させる。多くのAMD製チップおよびIntel製チップが、SSEの多様なバージョンを支援しており、Intelでは、その最新チップセットのためのアドバンストベクトルエクステンション(AVX)に関して、この技術の開発を継続している。

0046

他の実行では、RognesおよびSeeberg(Bioinformatics(Oxford、England)、16巻(8号):699〜706頁、2000年)は、Intel Pentium(登録商標)プロセッサーを、SSEの先行成分に対して使用し、MMXSIMD命令を、それらの実行のために使用している。RognesおよびSeeberg(Bioinformatics、16巻(8号):699〜706頁、2000年)による、ParAlignのための作業から開発された手法では、ウェーブフロント法を使用しない(Rognes、Nuc AcidsRes、29巻(7号):1647〜52頁、2001年;Saeboら、Nuc Acids Res、33巻(増刊2号):W535〜W539頁、2005年)。代わりに、彼らは、クエリー配列並行にSIMDレジスターをアラインさせ、あらかじめ計算されたクエリー特異的なスコア行列を使用して、8つの値を一度に計算する。この方法のさらなる詳細は、参照により本明細書に組み込まれる、U.S.7,917,302において見出すことができる。RognesおよびSeebergが、SIMDレジスターを位置特定する方式である、ノースネイバー依存方式によれば、SSEによる並列「ベクトル」計算から得られる潜在的加速化のうちの最大3分の1が失われうると予想される。これを克服するために、彼らは、SWAT様最適化を組み込んでいる。アフィンギャップペナルティーを大きくすると、ノーザンネイバーは、大半の場合にゼロとなろう。これが成り立つなら、プログラムは、ノースネイバーの値の計算をスキップすることが可能であり、これを、Farrar(Bioinformatics、23巻(2号):156〜161頁、2007年)は、「F遅延評価」と称している。RognesおよびSeebergの方法では、ノースネイバーの値がある特定の閾値を下回る場合には、それをスキップすることにより、式1の計算回数を縮減して、それらのアルゴリズムを加速化することが可能である。RognesおよびSeeberg、Bioinformatics、16巻(8号):699〜706頁、2000年では、MMX/SSE命令およびSWAT様拡張を介する8元ベクトルを使用して、6倍の加速化が報告されている。

0047

Farrar(Bioinformatics、23巻(2号):156〜161頁、2007年)によりなされたSSE作業では、ストライプパターンまたはストライドパターンアクセスを使用して、SIMDレジスターを、クエリーレジスターに沿って直線状に並べる。このようにすることにより、いかなる依存性の重複も回避される。ここでもまた、SWAT様最適化(Farrar、Bioinformatics、23巻(2号):156〜161頁、2007年)を組み込むことにより、Wozniak(CABIOS、13巻(2号):145〜150頁、1997年)およびRognesおよびSeeberg(Bioinformatics(Oxford、England)、16巻(8号):699〜706頁、2000年)によるSIMD実装に対して、2〜8倍の加速化が達成されている。ブロック置換行列、および効率的で巧妙な内部ループであって、ノーザン(F)条件により、その内部ループの外部へと移動させた内部ループは、重要な最適化である。16ビットエレメント、8ビットエレメントの処理のための、ストライドパターンによるメモリアクセスもまた、メモリアクセス時間を改善し、全体的な加速化に寄与する。

0048

Farrar(Sequence Analysis、2008年)は、ソニー、東、およびIBMにより製造されたCell Processorのために、自身の作業を拡張した。このCell Processorは、1つの主コアおよび8つの副コアを有する。Cell Broadband Engineは、複数のさらなるSmith−Waterman実装であって、いずれもFarrarのストライピング法を使用する、Szalkowskiら(BMCRes Notes、1巻(107号)、2008年)によるSWPS3、およびWirawanら(BMC Bioinformatics、9巻(377号)、2008年)によるCBESWを含む実装のための、開発プラットフォームであった。Rudnickiら(Fund Inform.、96巻、181〜194頁、2009年)は、PS3を使用して、複数のデータベース配列にわたる並列化を使用する方法を開発した。

0049

Rognes(BMCBioinformatics、12巻(221号)、2011年)はまた、SWIPEと呼ばれるマルチスレッド法であって、複数のデータベース配列を、並列的に処理するマルチスレッド法も開発している。焦点は、SIMD法を、「通常のCPU」上で使用することであった。粗視化並列処理を使用するこの探索は、複数のデータベース配列を並列的に使用する作業を分割するものであり、これは、Liuら(BMC Res Notes、2巻(73号)、2009年)ならびにLigowskiおよびRudnicki(Eight Annual International Workshop on High Performance Computational Biology、Rome、2009年)によるCUDASWで説明されている画像処理装置(GPU:graphics processor unit)ベースのツールと同様である。GPU作業の他の実装は、Liuら(BMC Res Notes、3巻(93号)、2010年)およびLigowskiら(GPU Computing Gems, Emerald Edition、Morgan Kaufmann、155〜157頁、2011年)によるCUDASW++2.0でなされている。

0050

他の変化形では、小スケールのベクトルによる並列化(8、16、または32元の並列処理)を、複数の配列を並列的にアラインするGPU実装を介して、計算をアクセス可能とするのに使用することができる。計算の理論的ピーク加速化は、最適な加速化であるm倍である。96の処理エレメントを使用する、ClearSpeed実装について、96倍の加速化がなされることから、理論的な加速化が確認される。

0051

並列計算モデル
Smith−Waterman配列アライメントを開発および拡張するのに使用される、主要な並列モデルは、連想計算(ASC:ASsociative Computing)(Potterら、Computer、27巻(11号):19〜25頁、1994年)である。本明細書では、Smith−Watermanアルゴリズムの効率的な並列バージョンが記載される。本節では、このモデルおよび他の1つのモデルが詳細に記載される。

0052

ここでは、いくつかの関連する語彙が定義される。フリンによるコンピュータアーキテクチャーの分類法からの2つの目的の用語は、並列計算の2つの異なるモデルである、MIMDおよびSIMDである。複数命令複数データ(MIMD:multiple−instruction,multiple−data)モデルと分類される、コンピュータクラスターを、超大スケールのアライメントにおけるメモリの限界を克服する概念実証として使用する。第8節では、MIMDモデルの使用法について記載する。また、ASCとして公知の、拡張型データ並列単一命令複数データ(SIMD:single−instruction multiple−data)モデルについても記載される。

0053

複数命令複数データ(MIMD)
複数命令複数データモデルまたはMIMDモデルは、現在利用可能な並列システムの大半について記載するものであり、最新の一般用コンピュータクラスターを含む。MIMDプロセッサーは、各々がそれ固有ローカルメモリを伴う(Quinn、Parallel Computing: Theory and Practice、2版、New York: McGraw−Hill、1994年)、本格的中央処理装置(CPU:central processing unit)を有する。SIMDモデルと異なり、MIMDプロセッサーの各々は、それ固有のプログラムを、非同期的に保存および実行する。MIMDプロセッサーは、それらが通信することを可能とするネットワークを介して接続されるが、使用されるネットワークは、マシン(クラスターノード)間のEthernet(登録商標)接続、Myrinet接続、およびInfiniBand接続にわたり、広く変化しうる。通信は、SIMDよりはるかに拘束の緩やかな通信構造を採用する傾向があり、単一のユニット内に収まらない。データは、ネットワークに沿って、個々のプロセッサーにより、それらが実行しつつある、それらの個々のプログラムの制御下で、非同期的に移送される。通信は、メッセージ送受信を支援する複数の異なる並列言語のうちの1つにより操作されることが典型的である。このための極めて一般的なライブラリーは、メッセージパッシングインターフェース(MPI)として公知である。「SIMD様」方式の通信も可能であるが、データの移動は、非同期的となろう。MIMDによる並列計算は通例、プロセッサーにより実行される多様なタスクが、高度に独立(すなわち、いわゆる「驚異的並列(embarrassingly parallel)」問題または「完全並列(pleasingly parallel)」問題)でない限りにおいて、広範な通信および頻繁な同期化を必要とする。第8節で提示される作業では、InfiniBandを介して接続された、AMD Opteronクラスターを使用する。

0054

SIMDと異なり、メッセージの送受信に必要とされる最悪の場合の時間は、予測するのが困難であるかまたは不可能である。MIMDソフトウェアのためのメッセージの送受信の実行時間は、SIMDに典型的な、最悪の場合の理論的な査定によってではなく、試行により決定されることが多い、平均的な場合の推定値を使用して決定することが典型的である。MIMDソフトウェアの最悪の場合は、極めて悪いことが多く、生じるのはまれであるので、平均的な場合の推定値がはるかに有用である。結果として、特定の問題についてMIMDに必要とされる通信時間は、SIMDの場合より顕著に長くなる可能性があり、通例、顕著に長い。これにより、MIMDのプログラミング(とりわけ、メッセージの送受信を使用する場合)における重要な目標であって、必要とされるプロセッサー間通信の数を最小化し、プロセッサー通信間の時間の長さを最大化するという目標がもたらされる。これは、画像処理装置またはGPUを使用する場合など、単一のカードによる加速化レベルでもなお成り立つ。

0055

また、データ並列プログラミングも、MIMDのプログラミングで重要な技法であるが、この場合、全てのタスクは、異なるデータに対して同じ演算を実施し、多様な臨界点に限り同期化される。MIMDシステムのためのアルゴリズムの大半は、単一プログラム複数データ(SPMD:Single−Program、Multiple−Data)プログラミングパラダイムで書き込まれる。各プロセッサーは、同じプログラムのそれ固有のコピーであって、そのプロセッサーまたはコアに特異的なコードセクションを、そのローカルデータに対して実行するコピーを有する。SPMDパラダイムの一般性は、多数の異なるプログラムであって、異なるプロセッサーにわたり共時的に実行され、なおかつ、単一の問題を解くのに協同することが可能なプログラムを書き込むことは極めて困難であるという事実から来る。メモリ集約的ではあるが、計算集約的ではない問題に使用される別の手法は、第8節で提示される作業を使用して、JumboMemによりなされる通り、バーチャルメモリサーバーを創出することである。ここでは、その基礎となる実行においてMPIが使用される。

0056

単一命令複数データ(SIMD)
SIMDモデルは、PEと呼ばれる、複数の単純な演算処理エレメント(processing element)からなる。各PEは、それ固有のローカルメモリであって、PEがそこからフェッチおよび保存するメモリは有するが、プログラムをコンパイルまたは実行する能力は有さない。本明細書で使用される「並列メモリ」という用語は、計算システム内のローカルメモリを集合的に指す。例えば、並列メモリは、SIMDコンピュータシステム内のローカルメモリの集合体(例えば、PEのローカルメモリ)、MIMDコンピュータシステム内のプロセッサーのローカルメモリの集合体(例えば、中央処理装置のローカルメモリ)などでありうる。プログラムのコンパイルおよび実行は、制御装置(またはフロントエンド)と呼ばれるプロセッサーにより操作される(Quinn、Parallel Computing: Theory and Practice、2版、New York: McGraw−Hill、1994年)。制御装置は、通例はバスにより、全てのPEへと接続される。

0057

全てのアクティブなPEは、制御装置から受信されたプログラムの命令を、ロックステップで、同期的に実行する。「いかなる時間単位においても、単一の演算は、複数の処理装置であって、各々が異なるデータを操作する処理装置上で、同じ実行状態にある」(Quinn、Parallel Computing: Theory and Practice、2版、New York: McGraw−Hill、1994年、79頁)。全てのアクティブなPEは、同じ命令を、同時に並列的に実行するが、いくつかのPEは、任意の特定の命令をスキップすることを許容されうる(Baker、SIMD and MASC: Course notes from CS6/73301:Parallel and Distributed Computing−−power point slides、(2004年)2004年)。これは通例、PEのうちの一部が、if命令を実行し、残りのPEが、else部分を実行する、「if−else」分枝構造を使用して達成される。このモデルは、「データ並列的」な性質の問題であって、たかだか少数のif−else分枝構造であり、図像処理および行列演算など、同時に生じうる分枝構造を有する問題に理想的である。

0058

制御装置は、データを、全てのアクティブなPEへと散布することができ、制御装置はまた、制御装置とPEとの接続(通例、バス)を使用して、データ値を、特定のPEから得ることもできる。加えて、PEのセットは、直線状アレイ、2Dメッシュ、またはハイパーキューブなどの相互接続ネットワークであって、PE間の並列データの移動をもたらす相互接続ネットワークによっても接続される。データは、このネットワークを通して、同期的並列方式で、PEにより移送され、PEは、データの移動を含む命令を、ロックステップで実行する。命令を、PEへと散布するのは、制御装置である。特に、SIMDネットワークは、今日大半の並列コンピュータにより使用される、メッセージ送受信パラダイムを使用しない。このことの重要な利点は、SIMDネットワークによる通信は、極めて効率的であり、通信に必要とされる最大の時間を、その特定の通信を制御するアルゴリズムの最悪の場合の時間により決定しうることである。

0059

本節の残りは、拡張型SIMD ASCモデルについて記載することに充てる。ASCは、本論のためのアルゴリズムの設計および開発の中心にある。

0060

連想計算モデル
連想計算(ASC)モデルとは、GoodyearAerospaceのKenneth Batcher博士により設計されたSIMD式連想コンピュータであるSTARAN、および米国海軍で大いに活用されているその後継モデルであるASPROに基づく拡張型SIMDである。

0061

ケント州立大学コンピュータ科学科で開発された、ASCとは、連想計算のためのアルゴリズムモデルである(Potterら、Computer、27巻(11号):19〜25頁、1994年)(Potter、Associative Computing: A Programming Paradigm for Massively Parallel Computers、Plenum Publishing、1992年)。ASCモデルは、GoodyearAerospaceにより組み立てられた連想プロセッサーであるSTARAN上およびMPP上の作業から生じた。現在ハードウェアではサポートされていないが、現在の研究努力は、このモデルを効率的にシミュレートし、かつ、このモデルのためにコンピュータを設計しようとしてなされている。

0062

拡張型SIMDモデルとして、ASCでは、マルチタスク処理および非同期的二点間通信経路決定の両方を回避する、同期的データ並列プログラミングを使用する。いかなる時点においても、1つのタスクだけが実行され、このタスクの複数のインスタンスは、全てのアクティブな処理エレメント(PE)上で、ロックステップで実行されるので、マルチタスク処理は、不要である。SIMDプログラマーと同様、ASCも、ロードバランシング、同期化、および動的タスクスケジューリングを伴う課題、MPIパラダイムおよび他のMIMDクラスターパラダイムでは明示的に取り組まなくてはならない問題を回避する。

0063

図4は、ASCコンピュータ概念モデルを示す。命令列(IS)としてもまた公知の、単一の制御装置と、各々がそれ固有のローカルメモリを伴う、複数の処理エレメント(PE)とが見られる。制御装置とPEアレイとは、散布/低減ネットワークを介して接続され、PEは、PEデータ相互接続ネットワークを介して一体に接続される。

0064

図4で見られる通り、PEは、それ固有のローカルメモリ内に位置特定されたデータへのアクセスを有する。データは、その場にとどまり、応答する(アクティブな)PEが、それらのローカルデータを並列的に処理する。連想という語に対する言及は、データを、メモリアドレスではなく、内容により位置特定しようとする検索の使用に関する。ASCモデルでは、連想メモリを採用せず、その代わりに、ASCモデルとは、一般的なサイクルが、検索する〜処理する〜読み出すである、連想プロセッサーである。ASCモデルについての概観は、Potterら、Computer、27巻(11号):19〜25頁、1994年において入手可能である。

0065

アルゴリズムの表解的性格は、それ自体、ASCデータ構造本来の表解的構造に起因して、ASCを使用する計算をもたらす。SWAMPでは、ロックステップによるノースネイバーおよびノースウェストネイバーのデータシフトのための、PE相互接続ネットワークにわたる、高度に効率的な通信、ならびに検索および並列計算にわたる最大値のための、小定数時間による連想機能を十分に活用する。

0066

連想演算は、ASCモデルにより必要とされる、さらなるハードウェアに起因して、定数時間で実行される(Jinら、15th International Parallel and Distributed Processing Symposium(IPDPS’Ol)Workshops、San Francisco、193頁、2001年)。これらの演算は、任意のSIMD様マシンにより、効率的に(それほど速くはないが)実施することができ、複数のSIMDハードウェアプラットフォーム上で、効率的になされるように適応させることに成功している(Yuanら、Parallel and Distributed Computing Systems(PDCS)、Cambridge、MA、2009年;Trahanら、J. of Parallel and Distributed Computing(JPDC)、2009年)。したがって、SWAMPアルゴリズムおよび他のASCアルゴリズムは、SIMDと近縁の他のシステムであって、ベクトルマシンを含むシステム上でも効率的に実行することができ、このために、モデルは、パラダイムとして使用されている。

0067

制御装置は、プログラムの命令を、フェッチおよび解読し、制御信号を、PEへと散布する。PEは、制御装置の指示下で、それらの固有のローカルデータを使用して、これらの命令を実行する。全てのPEは、命令を、命令間の暗黙の同期化を伴って、ロックステップ方式で実行する。ASCは、複数の関与性の高速大域処理:連想検索、最大値/最小値検索、およびレスポンダーの選択/検出を有する。これらについては、以下の節において記載される。

0068

連想機能
SWAMPアルゴリズムに関与性の機能については、下記で論じる。

0069

連想検索
ASCアルゴリズムにおける基礎的演算は、連想検索である。連想検索では、そのローカルデータが、所与の検索キーにマッチするPEを、同時に位置特定する。マッチするデータを有するPEは、レスポンダーと呼ばれ、非マッチしないデータを伴うPEは、非レスポンダーと呼ばれる。検索を実施した後、次いで、アルゴリズムは、非レスポンダーを無効化することにより、さらなる処理を、レスポンダーに影響を及ぼす処理だけに制限することができる(またはこの逆も成り立つ)。さらなる検索を実施することにより、レスポンダーのセットをさらに精緻化することができる。連想検索は、どのPEが、対角成分内の並列動作中でアクティブなのかを選択するときに、SWAMP+により大いに活用される。

0070

最大値/最小値検索
各PEが、標準的な比較演算子(等しい、未満など)を使用して、そのローカルデータを、検索キーに照らして比較する、単純検索に加えて、連想コンピュータはまた、全PEアレイからのデータを一体に組み合わせて、レスポンダーのセットを決定する、大域検索も実施しうる。大域検索の最も一般的な種類は、レスポンダーを、それらのデータが、全PEアレイにわたる最大値または最小値であるPEとする、最大値/最小値検索である。SWAMP+は、それが処理するあらゆる対角成分内で最大値を使用して、それまでに計算された最高値を追跡する。最大値検索の使用は、高頻度で、論理的並列動作において1回ずつ、アライメント1つ当たりm+n回生じる。

0071

レスポンダーの選択/検出
連想検索は、複数のレスポンダーを結果としてもたらすことが可能であり、連想アルゴリズムは、3つの異なるモード:並列選択、逐次選択、または単独選択のうちの1つにおいて、これらのレスポンダーを処理しうる。並列レスポンダー処理では、同じ演算セットを、各レスポンダーに対して、同時に実施する。逐次レスポンダー処理では、各レスポンダーを、個別に選択し、各レスポンダーについて、異なる演算セットを許容する。単独レスポンダー選択(pickOneとしてもまた公知の)では、1つの任意選択されたレスポンダーを選択して、処理にかける。複数のレスポンダーに加えてまた、連想検索は、レスポンダーを結果としてもたらさない可能性もある。この場合を取り扱うために、ASCモデルでは、その場合に、別個のアクションのセットを検索および実施するのに何らかのレスポンダー(anyRespondersとして公知の)が存在するのかどうかを検出することが可能である。SWAMPでは、アラインされた文字を含有する複数のレスポンダーを、上述の連想検索に基づき、並列的に選択および処理する。単独レスポンダー選択は、最大値/最小値検索を使用する場合に、正確な同じ最大値を有する複数の値が存在すれば、その時点で生じる。

0072

PE相互接続ネットワーク
大半の連想プロセッサーは、アレイ内の並列データの移動を可能とする、いくつかの種類のPE相互接続ネットワークを含む。ASCモデルそれ自体は、任意の特定の相互接続ネットワークを指定せず、実際、多くの有用な連想アルゴリズムは、相互接続ネットワークを必要としない。連想プロセッサーは、1D直線状アレイまたは2Dメッシュなど、単純なネットワークを実装することが典型的である。これらのネットワークは、実装が簡単であり、データを、迅速に、同期方式転送することを可能とする。例えば、1D直線状アレイは、SWAMPアルゴリズムにおける、PE間の明示的通信に十分である。

0073

並列計算システム
一般化された並列処理アーキテクチャーを、図5に示す。各コンポーネントは、直接的な接続を有するものとして示されるが、多様なエレメントは、地理的に隔てられうるが、ネットワーク、例えば、インターネットを介して、接続されうることを理解されたい。ハイブリッドコンフィギュレーションも可能であるが、並列コンピュータ内のメインメモリは、単一のアドレス空間内の全ての処理エレメント間で共有されているか、または分散されている、すなわち、各処理エレメントが、それ固有のローカルアドレス空間を有する(分散型メモリとは、メモリが論理的に分散されているという事実を指すがまた、それが、物理的に分散されていることもしばしば示唆する)ことが典型的である。処理エレメントが、それ固有のローカルメモリおよび非ローカルプロセッサー上のメモリへのアクセスを有する場合、分散型共有メモリおよびメモリの視覚化は、2つの手法を組み合わせる。ローカルメモリへのアクセスは、非ローカルメモリへのアクセスより速いことが典型的である。

0074

メインメモリの各エレメントに、等しい待ち時間およびバンド幅でアクセスしうる、コンピュータアーキテクチャーは、ユニフォームメモリアクセス(UMA:Uniform Memory Access)システムとして公知である。UMAは、メモリが物理的に分散されていない、共有メモリシステムだけにより達成しうることが典型的である。この特性を有さないシステムは、非ユニフォームメモリアクセス(NUMA:Non−Uniform Memory Access)アーキテクチャーとして公知である。分散型メモリシステムは、非ユニフォームメモリアクセスを有する。

0075

プロセッサー間通信およびプロセッサー−メモリ間通信は、共有(マルチポート型またはマルチプレックス型)メモリ、クロスバースイッチ共有バス、またはスターリングツリー、ハイパーキューブ、ファットハイパーキューブ(ノードにおいて複数のプロセッサーを伴うハイパーキューブ)、またはn次元メッシュを含む無数トポロジーを有する相互接続ネットワークを介する方式を含む、複数の方式で、ハードウェア内に実装することができる。

0076

相互接続されたネットワークに基づく並列コンピュータは、直接的に接続されていないノード間のメッセージの送受信を可能とする経路決定を組み込まなければならない。プロセッサー間の通信に使用される媒体は、大型のマルチプロセッサーマシン内で階層的である可能性が高い。このようなリソースは、専用で市販されているか、または「クラウド」、例えば、アマゾンクラウドコンピューティングを介して、これらのリソースにアクセスすることができる。

0077

コンピュータは一般に、バスを介してメモリへと連結されたプロセッサーを含む。メモリは、RAMまたはROMを含むことが可能であり、少なくとも1つの有形の非一時的メディアであって、システムに、本明細書で記載される機能を果たさせるように実行可能な命令保存するメディアを含むことが好ましい。当業者であれば、本発明の方法の実施に必要であるかまたは最適であると認識する通り、本発明のシステムは、バスを介して互いに通信する、1または複数のプロセッサー(例えば、中央処理装置(CPU)、画像処理装置(GPU)など)、コンピュータ可読記憶装置(例えば、メインメモリ、スタティックメモリなど)、またはこれらの組合せを含む。

0078

プロセッサーは、当技術分野で公知の、任意の適切なプロセッサーであって、Intel(Santa Clara、CA)により、XEON E7という商標で販売されているプロセッサー、またはAMD(Sunnyvale、CA)により、OPTERON 6200という商標で販売されているプロセッサーなどのプロセッサーでありうる。

0079

メモリは、コンピュータ可読記憶装置を指す場合があり、命令(例えば、本明細書で見出される任意の方法または機能を統合するソフトウェア)、データ(例えば、を統合すること患者の染色体内で見出される遺伝子配列など、任意の有形の物理オブジェクト)、またはこれらの両方の1または複数のセットが保存された、任意のマシン可読メディアを含みうる。例示的な実施形態では、コンピュータ可読記憶装置は、単一のメディアでありうるが、「コンピュータ可読記憶装置」という用語は、命令またはデータの1または複数のセットを保存する、単一のメディアまたは複数のメディア(例えば、集中型データベースもしくは分散型データベース、ならびに/または関連するキャッシュおよびサーバー)を含むものと理解されたい。したがって、「コンピュータ可読記憶装置」という用語は、限定なしに述べると、ソリッドステートメモリ(例えば、加入者識別モジュール(SIM)カード、セキュアディジタルカードSDカード)、マイクロSDカード、またはソリッドステートドライブ(SSD))、光学メディアおよび磁気メディア、ならびに他の任意の有形記憶メディアを含むものと理解されたい。好ましくは、コンピュータ可読記憶装置は、有形の非一時的メディアを含む。このような非一時的メディアは、例えば、一過性波動および信号を除外する。「非一時的メモリ」は、信号それ自体など、コンピュータ可読伝送媒体を除外すると解釈されたい。

0081

試料の収集および調製
本発明は、生物学的試料から回収された核酸に対応する配列(例えば、核酸配列、アミノ酸配列)を作製するための方法を含む。一部の実施形態では、結果として得られる情報を使用して、対象から得られた核酸素材中に存在する突然変異を同定することができる。一部の実施形態では、試料、すなわち、核酸(例えば、DNAまたはRNA)を対象から得、核酸を処理し(溶解させ、増幅し、かつ/または精製し)、下記に記載される方法を使用して、核酸をシーケンシングする。多くの実施形態では、シーケンシングの結果は、直鎖状の核酸配列ではなく、何千または何百万もの個々の短い核酸リードであって、対象についての配列へとリアセンブルしなければならない核酸リードのコレクションである。リードをアラインして配列を作製したら、アラインされた配列を、基準配列と比較して、例えば、疾患を指し示す突然変異を同定することができる。他の実施形態では、リードの、基準配列構築物、すなわち、上記で記載した、有向非巡回グラフ(「DAG」)へのアライメントに基づき、特定の突然変異を伴う対象を同定することができる。

0082

上記の目的のうちのいずれのためにも、方法を生物学的試料へと適用することができる。生物学的試料は、例えば、血液試料全血液、血漿涙液乳首吸引物血清糞便、尿、唾液循環細胞組織生検試料毛包、または患者の生物学的素材を含有する他の試料を含みうる。このような試料に基づき検査を行うときの1つの問題は、大半の場合において、目的の突然変異を含有するDNAまたはRNAであって、試料中に存在しうるDNAまたはRNAは、ごく微量でありうることである。これは、とりわけ、口腔内スワブ試料または血液試料などの非侵襲的試料であって、突然変異型核酸が、極めて少量で存在する非侵襲的試料中で成り立つ。一部の実施形態では、核酸断片は、天然短鎖でありうる、すなわち、試料中の関与性の核酸のランダムなせん断により、短い断片が作り出されうる。他の実施形態では、処理を容易とするため、またはシーケンシング法では、1000塩基未満、例えば、500塩基未満、例えば、200塩基未満、例えば、100塩基未満、例えば、50塩基未満のリードだけをシーケンシングしうるため、核酸を意図的に断片化する。本明細書で記載される方法を使用して、様々な長さの配列をアラインしうるが、一部の実施形態では、複数の核酸リードの大部分は、シーケンシング法から得られ、1000塩基未満、例えば、500塩基未満、例えば、200塩基未満、例えば、100塩基未満、例えば、50塩基未満を含む。

0083

核酸は、当技術分野で公知の方法により得ることができる。一般に、核酸は、その内容が、参照によりその全体において本明細書に組み込まれる、Maniatisら、Molecular Cloning: A Laboratory Manual、Cold Spring Harbor、N.Y.、280〜281頁(1982年)により記載されている技法など、様々な技法により生物学的試料から抽出することができる。

0084

十分に純粋な核酸調製物を得るためには、まず、試料の抽出物を調製し、次いで、さらなるステップ(すなわち、示差的沈殿カラムクロマトグラフィー有機溶媒を伴う抽出など)を実施することが必要でありうる。抽出物は、当技術分野における標準的な技法を使用して、例えば、細胞の化学的溶解または機械的溶解により調製することができる。次いで、抽出物は、例えば、濾過および/もしくは遠心分離により、かつ/あるいはイソチオシアン酸グアニジニウムもしくは尿素などのカオトロピック塩、またはフェノールおよび/もしくはHCCl3などの有機溶媒によりさらに処理して、任意の夾雑的タンパク質および潜在的に干渉的なタンパク質を変性させることができる。一部の実施形態では、試料は、対象試料、例えば、血液試料から収集されたRNA、例えば、mRNAを含みうる。当技術分野では、RNA抽出のための一般的な方法が周知であり、Ausubelら、Current Protocols of Molecular Biology、John Wiley and Sons(1997年)を含む、分子生物学の標準的な教科書において開示されている。パラフィン包埋組織からのRNA抽出のための方法は、例えば、RuppおよびLocker、Lab Invest.、56巻:A67頁(1987年)、およびDe Andresら、BioTechniques、18巻:42044頁(1995年)において開示されている。これらの参考文献の各々の内容は、参照によりそれらの全体において本明細書に組み込まれる。特に、RNAの単離は、Qiagenなど、市販品の製造元による精製キット緩衝液セット、およびプロテアーゼを、製造元の指示書に従い使用して、実施することができる。例えば、培養物中の細胞に由来する全RNAは、Qiagen RNeasy miniカラムを使用して単離することができる。他の市販のRNA単離キットは、MASTERPURE Complete DNA and RNA Purification Kit(EPICENTRE、Madison、Wis.)、およびParaffin Block RNA Isolation Kit(Ambion、Inc.)を含む。組織試料に由来する全RNAは、RNA Stat−60(Tel−Test)を使用して単離することができる。腫瘍から調製されたRNAは、例えば、塩化セシウム密度勾配遠心分離により単離することができる。

0085

解析的シーケンシング
シーケンシングは、当技術分野で公知の任意の方法を介しうる。DNAシーケンシング法は、標識されたターミネーターまたはプライマーおよびスラブ内またはキャピラリー内ゲル分離を使用する、古典的なジデオキシシーケンシング反応(サンガー法)、可逆的終結型標識ヌクレオチドを使用する、合成を介するシーケンシング、ピロシーケンシング、454シーケンシング、標識されたオリゴヌクレオチドプローブのライブラリーとの、対立遺伝子特異的ハイブリダイゼーション、標識されたクローンのライブラリーとの対立遺伝子特異的ハイブリダイゼーションに続いてライゲーションを使用する、合成を介するシーケンシング、重合化ステップにおける、標識されたヌクレオチドの組込みについての、リアルタイムモニタリング、ポロニーシーケンシング、およびSOLiDシーケンシングを含む。分離された分子のシーケンシングは、より近年になって、ポリメラーゼまたはリガーゼを使用する、逐次的伸長反応または単一の伸長反応によるほか、プローブのライブラリーとの単一の示差的ハイブリダイゼーションまたは逐次的な示差的ハイブリダイゼーションによっても裏付けられている。シーケンシングの前に、試料中の核酸の一部または全部を増幅することは、さらに有益でありうる。一部の実施形態では、核酸を、当技術分野で公知のポリメラーゼ連鎖反応PCR)法を使用して増幅する。

0086

本発明の方法で使用されうるシーケンシング技術の一例は、DNAまたはRNAを増幅するのに活用されうる、合成を介するポリメラーゼベースの配列である、Illuminaシーケンシング(例えば、MiSeq(商標)プラットフォーム)である。DNAのためのIlluminaシーケンシングは、固体表面上のDNAの増幅であって、フォールドバックPCRおよびアンカリングされたプライマーを使用する増幅に基づく。ゲノムDNAを、断片化し、アダプターを、断片の5’末端および3’末端へと付加する。フローセルチャネルの表面へと接合させたDNA断片を伸長させ、架橋増幅する。断片は二本鎖となり、二本鎖分子を変性させる。複数サイクルにわたる固相増幅に続く変性により、フローセルの各チャネル内に、同じ鋳型の約1,000コピーの一本鎖DNA分子による数百万のクラスターを創出することができる。プライマー、DNAポリメラーゼ、および4つのフルオロフォアで標識された可逆的終結型ヌクレオチドを使用して、逐次シーケンシングを実施する。ヌクレオチド組込みの後、レーザーを使用して、フルオロフォアを励起し、画像を捕捉し、第1の塩基の識別を記録する。3’側ターミネーターおよび組み込まれた各塩基のフルオロフォアを除去し、組込みステップ、検出ステップ、および同定ステップを繰り返す。Illuminaシーケンシングを使用して、RNAを検出する場合、試料のRNA発現を決定するために、RNA断片を単離および増幅することを除き、同じ方法が適用される。配列は、シーケンサーで精査した後、生物学的配列および品質スコアを保存するための、テキストベースのフォーマットである、FASTQファイルなどのデータファイルに出力することができる(上記の議論を参照されたい)。

0087

本発明の方法で使用されうるDNAシーケンシング法の別の例は、Life Technologies製のIon Torrent(商標)シーケンシングである。それらの各々の内容が、参照によりその全体において本明細書に組み込まれる、米国特許出願第2009/0026082号、同第2009/0127589号、同第2010/0035252号、同第2010/0137143号、同第2010/0188073号、同第2010/0197507号、同第2010/0282617号、同第2010/0300559号、同第2010/0300895号、同第2010/0301398号、および同第2010/0304982号を参照されたい。Ion Torrent(商標)シーケンシングでは、DNAを、約300〜800塩基対の断片へとせん断すると、断片は、平滑末端となる。次いで、オリゴヌクレオチドアダプターを、断片の末端へとライゲーションする。アダプターは、断片の増幅およびシーケンシングのためのプライマーとして用いられる。断片を、表面へと接合させ、断片が個別に分解可能となるような分解能で検出する。1または複数のヌクレオチドの付加により、プロトン(H+)が放出され、このシグナルは、シーケンシング計器により検出および記録される。シグナル強度は、組み込まれたヌクレオチドの数に比例する。Ion Torrentデータはまた、FASTQファイルとしても出力される。

0088

本発明の方法で使用されうるDNAシーケンシング法およびRNAシーケンシング法の別の例は、454(商標)シーケンシング(Roche)(Margulies, Mら、2005年、Nature、437巻、376〜380頁)である。454(商標)シーケンシングは、合成を介するシーケンシング技術であって、ピロシーケンシングもまた活用する技術である。DNAの454(商標)シーケンシングは、2つのステップを伴う。第1のステップでは、DNAを、約300〜800塩基対の断片へとせん断し、断片は、平滑末端となる。次いで、オリゴヌクレオチドアダプターを、断片の末端へとライゲーションする。アダプターは、断片の増幅およびシーケンシングのためのプライマーとして用いられる。断片は、例えば、5’−ビオチンタグを含有するAdaptor Bを使用して、DNA捕捉ビーズ、例えば、ストレプトアビジンコーティングされたビーズへと接合させることができる。ビーズへと接合させた断片は、油−水エマルジョン液滴内PCR増幅する。結果は、各ビーズ上でクローン増幅されたDNA断片の複数のコピーである。第2のステップでは、ビーズを、ウェルピコリットルサイズの)内で捕捉する。ピロシーケンシングは、各DNA断片に対して並行的に実施する。1または複数のヌクレオチドの付加により、光シグナルが発生し、これを、シーケンシング計器内のCCDカメラで記録する。シグナル強度は、組み込まれたヌクレオチドの数に比例する。ピロシーケンシングでは、ヌクレオチドが付加されると放出される、ピロリン酸(PPi)を使用する。PPiは、アデノシン5’ホスホ硫酸の存在下で、ATPスルフリラーゼにより、ATPへと転換される。ルシフェラーゼは、ATPを使用して、ルシフェリンを、オキシルフェリンへと転換し、この反応が、光を発生させ、これが検出および解析される。別の実施形態では、ピロシーケンシングを使用して、遺伝子発現を測定する。RNAについてのピロシーケンシングも、DNAについてのピロシーケンシングと同様に適用され、部分rRNA遺伝子配列を微小ビーズへと接合させ、次いで、接合物を個々のウェルに入れることにより達成する。次いで、遺伝子発現プロファイルを決定するために、接合させた部分rRNA遺伝子配列を増幅する。Sharon Marsh、Pyrosequencing(登録商標) Protocols、Methodsin Molecular Biology、373巻、15〜23頁(2007年)。

0089

本発明の方法で使用されうるDNA検出法およびRNA検出法の別の例は、SOLiD(商標)技術(Applied Biosystems)である。SOLiD(商標)技術システムとは、ライゲーションベースのシーケンシング技術であって、DNAおよびRNAのいずれについての超並列次世代シーケンシングを行うのにも活用されうる技術である。DNA SOLiD(商標)シーケンシングでは、ゲノムDNAを、断片へとせん断し、アダプターを、断片の5’末端および3’末端へと接合させて、断片ライブラリーを作り出す。代替的に、内部アダプターは、アダプターを、断片の5’末端および3’末端へとライゲーションし、断片を環状化し、環状化させた断片を消化させて、内部アダプターを作り出し、アダプターを、結果として得られる断片の5’末端および3’末端へと接合させて、メートペア(MP:mate−paired)ライブラリーを作り出すことにより導入することができる。次に、クローンビーズ集団を、ビーズ、プライマー、鋳型、およびPCR成分を含有するマイクロリアクター内で調製する。PCR後、鋳型を変性させ、ビーズを濃縮して、伸長した鋳型を伴うビーズを分離する。選択されたビーズ上の鋳型を、スライドガラスへの結合を可能とする3’修飾にかける。配列は、逐次ハイブリダイゼーションと、中央部の決定された塩基(または塩基対)であって、特異的なフルオロフォアにより同定される塩基を伴う、部分的にランダムなオリゴヌクレオチドのライゲーションとにより決定することができる。色を記録した後で、ライゲーションされたオリゴヌクレオチドを切断および除去し、次いで、工程を繰り返す。

0090

他の実施形態では、SOLiD(商標)遺伝子発現連鎖解析SAGE:Serial Analysis of Gene Expression)を使用して、遺伝子発現を測定する。遺伝子発現連鎖解析(SAGE)とは、各転写物についての個別のハイブリダイゼーションプローブを準備する必要なしに、多数の遺伝子転写物についての同時的で定量的な解析を可能とする方法である。まず、タグが、各転写物内の固有の位置から得られることを条件として、短い配列タグ(約10〜14bp)であって、転写物を固有に同定するのに十分な情報を含有するタグを作り出す。次いで、多くの転写物を併せて連結して、長い連鎖分子であって、シーケンシングすることが可能であり、複数のタグの識別を同時に明らかにする分子を形成する。転写物の任意の集団の発現パターンは、個々のタグの存在度を決定し、各タグに対応する遺伝子を同定することにより、定量的に査定することができる。さらなる詳細については、例えば、それらの各々の内容が、参照によりそれらの全体において本明細書に組み込まれる、Velculescuら、Science、270巻:484〜487頁(1995年);およびVelculescuら、Cell、88巻:243〜51頁(1997年)を参照されたい。

0091

本発明の方法で使用されうる別のシーケンシング法は、例えば、Helicosの真の1分子のシーケンシング(tSMS:True Single Molecule Sequencing)(Harris T. D.ら(2008年)、Science、320巻:106〜109頁)を含む。tSMS法では、DNA試料を、約100〜200ヌクレオチドの鎖へと切断し、polyA配列を、各DNA鎖の3’末端へと付加する。各鎖を、蛍光標識されたアデノシンヌクレオチドの付加により標識する。次いで、DNA鎖を、フローセル表面へと固定化された、何百万ものオリゴ−T捕捉部位を含有するフローセルとハイブリダイズさせる。鋳型は、1cm2当たりの鋳型約1億個の密度でありうる。次いで、フローセルを、計器、例えば、HeliScope(商標)シーケンサーへとローディングし、レーザーでフローセルの表面を照射し、各鋳型の位置を明らかにする。CCDカメラにより、フローセル表面上の鋳型の位置をマッピングすることができる。次いで、鋳型の蛍光標識を、切断し、洗い落とす。DNAポリメラーゼと、蛍光標識されたヌクレオチドとを導入することにより、シーケンシング反応を開始する。オリゴ−T核酸は、プライマーとして用いられる。ポリメラーゼにより、標識されたヌクレオチドを、プライマーへと、鋳型指向的な様式で組み込む。ポリメラーゼおよび組み込まれなかったヌクレオチドは、除去する。蛍光標識されたヌクレオチドの組込みを方向付けた鋳型は、フローセル表面をイメージングすることにより検出する。イメージングの後、切断ステップにより、蛍光標識を除去し、所望のリード長が達成されるまで、他の蛍光標識されたヌクレオチドについても、工程を繰り返す。配列情報は、各ヌクレオチドの付加ステップにより収集する。tSMSについてのさらなる記載は、例えば、Lapidusら(米国特許第7,169,560号)、Lapidusら(米国特許出願第2009/0191565号)、Quakeら(米国特許第6,818,395号)、Harris(米国特許第7,282,337号)、Quakeら(米国特許出願第2002/0164629号)、およびBraslavskyら、PNAS(USA)、100巻:3960〜3964頁(2003年)において示されており、これらの参考文献の各々の内容は、参照によりその全体において本明細書に組み込まれている。

0092

本発明の方法で使用されうるシーケンシング技術の別の例は、DNAおよびRNAのいずれもシーケンシングする、Pacific Biosciencesによる単一分子リアルタイム(SMRT:single molecule,real−time)技術を含む。SMRTでは、4つのDNA塩基の各々を、4つの異なる蛍光色素のうちの1つへと接合させる。これらの色素は、リン酸連結されている。単一のDNAポリメラーゼを、鋳型である一本鎖DNAの単一の分子と共に、ゼロモード導波管ZMW:zero−mode waveguide)の底部に固定化する。ZMWとは、単一のヌクレオチドの、DNAポリメラーゼによる組込みの、ZMWの内外へと急速に(数マイクロ秒間で)拡散する蛍光ヌクレオチドのバックグラウンドに対する観察を可能とする閉じ込め構造である。ヌクレオチドを成長しつつある鎖へと組み込むには、数ミリ秒間かかる。この時間中に、蛍光標識が励起され、蛍光シグナルをもたらし、蛍光タグが切断される。色素の対応する蛍光の検出により、どの塩基が組み込まれたのかが指し示される。工程を繰り返す。RNAをシーケンシングするためには、ZMWでは、DNAポリメラーゼを、逆転写酵素で置きかえ、相応の工程に従う。

0093

本発明の方法で使用されうるシーケンシング法の別の例は、ナノ細孔シーケンシング(Soni G VおよびMeller, A、Clin Chem、53巻:1996〜2001頁、2007年)である。ナノ細孔とは、直径が1ナノメートルオーダー小孔である。ナノ細孔を、導電性流体中に浸漬し、ナノ細孔にわたり電位印加する結果として、ナノ細孔を通るイオン導通に起因する微弱電流がもたらされる。流れる電流の量は、ナノ細孔のサイズに対して感受性である。DNA分子が、ナノ細孔を通って通過するとき、DNA分子上の各ヌクレオチドは、ナノ細孔を、異なる程度で閉塞させる。こうして、DNA分子が、ナノ細孔を通って通過するときに、ナノ細孔を通って通過する電流の変化は、DNA配列読取りを表示する。

0094

本発明の方法で使用されうるシーケンシング法の別の例は、化学感受性電界効果トランジスター(chemFET:chemical−sensitive field effect transistor)アレイを使用して、DNAをシーケンシングするステップ(例えば、米国特許出願公開第20090026082号において記載されている)を伴う。技法の一例では、DNA分子を、反応チャンバー内に入れることができ、鋳型分子を、シーケンシングプライマーへと結合させたポリメラーゼとハイブリダイズさせることができる。シーケンシングプライマーの3’末端における、1または複数の三リン酸の、新たな核酸鎖への組込みは、電流の変化を介して、chemFETにより検出することができる。アレイは、複数のchemFETセンサーを有しうる。別の例では、単一の核酸を、ビーズへと接合させることができ、核酸を、ビーズ上で増幅することができ、個々のビーズを、chemFETアレイ上の個々の反応チャンバーであって、各チャンバーがchemFETセンサーを有するチャンバーへと移送することができ、核酸をシーケンシングすることができる。

0095

本発明の方法で使用されうるシーケンシング法の別の例は、電子顕微鏡(Moudrianakis E. N.およびBeer M.、Proc Natl Acad Sci USA.、1965年3月、53巻:564〜71頁)を使用するステップを伴う。技法の一例では、電子顕微鏡を使用して識別可能な金属標識を使用して、個々のDNA分子を標識する。次いで、これらの分子を、平面上で伸長させ、配列を測定するのに電子顕微鏡を使用してイメージングした。

0096

さらなる検出法では、マイクロアレイへの結合を、後続の蛍光検出または非蛍光検出、質量分析的方法を使用する、バーコードによる質量検出、発せられたラジオ波の検出、アラインされたバーコードからの散乱光の検出、定量的PCR法またはディジタルPCR法を使用する蛍光の検出のために活用することができる。比較核酸ハイブリダイゼーションアレイとは、患者の試料DNA中のコピー数変異を検出するための技法である。試料DNAと、基準DNAとを、例えば、顕著に異なるフルオロフォアを使用して、異なる様式で標識し、次いで、多数のプローブとハイブリダイズさせる。次いで、試料および基準の蛍光強度を測定し、次いで、蛍光強度比を使用して、コピー数変異を計算する。比較ゲノムハイブリダイゼーションアレイの方法については、Shinawi M、Cheung SW、The arrayCGH and its clinical applications、Drug Discovery Today、13巻(17〜18号):760〜70頁においてより詳細に論じられている。マイクロアレイによる検出から、FASTQファイルを直接作製することはできないが、マイクロアレイシーケンサーにより作成されたデータを、FASTQまたは同様のフォーマットへと転換するプログラムが利用可能である。

0097

DNA分子、RNA分子、およびコピー数を検出する別の方法は、蛍光in situハイブリダイゼーション(FISH:fluorescent in situ hybridization)(In Situ Hybridization Protocols(Ian Darby編、2000年))である。FISHとは、DNA配列内の突然変異およびコピー数変異など、特異的な染色体再配列を検出する、分子細胞遺伝学法である。DNA分子を化学的に変性させ、2つの鎖へと分離する。次いで、一本鎖プローブを、変性させたDNA鎖と共にインキュベートする。一本鎖プローブは、標的配列部分に応じて選択され、相補的配列部分に対する高アフィニティーを有する。プローブは、反復配列プローブ、全染色体プローブ、および遺伝子座特異的プローブを含みうる。インキュベート中に、組み合わされたプローブとDNA鎖とをハイブリダイズさせる。次いで、任意の変動を評価するために、結果を、顕微鏡下で視覚化および定量化する。

0098

別の実施形態では、MassARRAY(商標)ベースの遺伝子発現プロファイリング法を使用して、遺伝子発現を測定する。Sequenom,Inc.(San Diego、Calif.)により開発されたMassARRAY(商標)ベースの遺伝子発現プロファイリング法では、RNAの単離および逆転写の後、得られたcDNAを、単一の塩基を除く全て位置において、ターゲティングされるcDNA領域にマッチし、内部標準として用いられる、合成DNA分子(コンペティター)とスパイクする。cDNA/コンペティター混合物を、PCR増幅し、PCR後エビアルカリホスファターゼSAP酵素処理にかけ、その結果として、残りのヌクレオチドの脱リン酸化をもたらす。アルカリホスファターゼを不活化させた後、コンペティターおよびcDNAに由来するPCR産物を、プライマー伸長にかけ、これにより、コンペティターに由来するPCR産物およびcDNAに由来するPCR産物について、顕著に異なる質量シグナルを発生させる。精製後、これらの産物を、マトリックス支援レーザー脱着イオン化飛行間質量分析(MALDI−TOF MS:matrix−assisted laser desorption ionization time−of−flight mass spectrometry)による解析に必要とされる成分をあらかじめローディングされたチップアレイ上に分注する。次いで、反応物中に存在するcDNAを、作成された質量スペクトル内のピーク面積の比を解析することにより定量化する。さらなる詳細については、例えば、DingおよびCantor、Proc. Natl. Acad. Sci. USA、100巻:3059〜3064頁(2003年)を参照されたい。

0099

さらなるPCRベースの技法は、例えば、それらの各々の内容が、参照によりそれらの全体において本明細書に組み込まれる、示差的ディスプレイ(LiangおよびPardee、Science、257巻:967〜971頁(1992年));増幅フラグメント多型(iAFLP)(Kawamotoら、Genome Res.、12巻:1305〜1312頁(1999年));BeadArray(商標)技術(Illumina、San Diego、Calif.;Oliphantら、Discovery of Markers for Disease(Biotechniquesへの付録)、2002年6月;Fergusonら、Analytical Chemistry、72巻:5618頁(2000年));市販のLuminex100LabMAPシステムおよび複数色でコードされたマイクロスフェア(Luminex Corp.、Austin、Tex.)を、遺伝子発現のための迅速アッセイで使用される、遺伝子発現の検出のためのビーズアレイ(BADGE)(Yangら、Genome Res.、11巻:1888〜1898頁(2001年));ならびに高カバレッジ発現プロファイリング(HiCEP)解析(Fukumuraら、Nucl. Acids. Res.、31巻(16号)e94頁(2003年))を含む。

0100

ある特定の実施形態ではまた、遺伝子発現の変動も、例えば、Affymetrix(Santa Clara、CA)から市販されているアレイなど、ナイロン膜アレイ、マイクロチップアレイ、およびスライドガラスアレイを含む、マイクロアレイ法を使用して、同定または確認することができる。一般に、RNA試料は、単離され、逆転写を介して、標識されたcDNAへと転換される。次いで、標識されたcDNAを、ナイロン膜、マイクロチップ、またはスライドガラス上で、目的の細胞または組織に由来する、特異的なDNAプローブとハイブリダイズさせる。次いで、ハイブリダイズさせたcDNAを検出および定量化し、結果として得られる遺伝子発現データを、解析のために対照と比較することができる。標識化法、ハイブリダイゼーション法、および検出法は、マイクロアレイの支持体が、ナイロン膜であるのか、マイクロチップであるのか、スライドガラスであるのかに応じて変化する。ナイロン膜アレイは、P−dNTPで標識されたプローブとハイブリダイズさせることが典型的である。水ライドガラスアレイは、2つの顕著に異なる、蛍光標識されたヌクレオチドによる標識化を伴うことが典型的である。マイクロアレイを作製し、遺伝子産物の発現(例えば、RNAまたはタンパク質)を決定するための方法は、その内容が参照によりその全体において本明細書に組み込まれる、Yeatmanら(米国特許出願第2006/0195269号)に示されている。

0101

一部の実施形態では、質量分析(MS)による解析は、生物学的試料中の、本明細書で開示される、1または複数のバイオマーカーの存在および/または量を決定するのに、単独で使用することもでき、他の方法(例えば、イムノアッセイまたはRNA測定アッセイ)と組み合わせることもできる。一部の実施形態では、MS解析は、例えば、ダイレクトスポットMALDI−TOFまたは液体クロマトグラフィーMALDI−TOF質量分析による解析など、マトリックス支援レーザー脱着イオン化(MALDI)飛行時間(TOF)MS解析を含む。一部の実施形態では、MS解析は、エレクトロスプレーイオン化(ESI)MS、など、例えば、液体クロマトグラフィー(LC)ESI−MSを含む。質量分析は、市販の分光光度計を使用して達成することができる。当技術分野では、MALDI−TOF MSおよびESI−MSを含むMS解析を活用して、生物学的試料中のバイオマーカーペプチドの存在および量を検出するための方法が公知である。さらなる指針については、例えば、それらの各々が参照によりその全体において本明細書に組み込まれる、米国特許第6,925,389号;同第6,989,100号;および同第6,890,763号を参照されたい。

0102

本発明の方法、配列構築物、およびシステムを伴う使用のためのタンパク質配列は、当業者に公知の多数の技法を使用して決定することができる。例えば、アミノ酸配列およびアミノ酸配列リードは、質量分析により、またはエドマン分解を使用して、タンパク質またはタンパク質の部分を解析することにより作製することができる。質量分析は、例えば、ダイレクトスポットMALDI−TOFまたは液体クロマトグラフィーMALDI−TOF質量分析による解析などの、マトリックス支援レーザー脱着イオン化(MALDI)飛行時間(TOF)MS解析、例えば、液体クロマトグラフィー(LC)ESI−MSなどのエレクトロスプレーイオン化(ESI)MS、またはMS−MSなど、他の技法を含みうる。エドマン分解による解析は、Model 49X Prociseタンパク質/ペプチドシーケンサー(Applied Biosystems/Life Technologies)など、市販の計器を使用して実施することができる。シーケンシングされたアミノ酸配列、すなわち、ポリペプチド、すなわち、タンパク質は、少なくとも10アミノ酸の長さ、例えば、少なくとも20アミノ酸の長さ、例えば、少なくとも50アミノ酸の長さでありうる。

0103

参照による組込み
本開示を通して特許、特許出願、特許公開、雑誌、書籍、論文、ウェブコンテンツなど、他の文献に対する言及および引用を行ってきた。全てのこのような文献は、参照によりそれらの全体において全て目的で本明細書に組み込まれる。

0104

同等物
当業者には、本明細書で示され、記載される実施形態に加えて、本発明の多様な改変およびその多くのさらなる実施形態も、本明細書で引用される研究文献および特許文献への言及を含む、本明細書の全内容から明らかとなろう。本明細書における対象物は、その多様な実施形態における本発明およびその同等物の実施に適応させうる、重要な情報、例示、および指針を含有する。
例えば、本発明は以下の項目を提供する。
(項目1)
複数の配列リードをアラインするための、プロセッサーおよび非一時的メモリを含むシステムであって、前記メモリは、実行された際、前記プロセッサーに、
複数の配列リードを、記号のストリングとして得て;
配列リードに対応する記号の各ストリングを、基準配列構築物内の複数の位置と比較し、ここで前記構築物は、前記構築物内の複数の位置において、記号の少なくとも2つの異なるストリングを含み;
配列リードに対応する記号の各ストリングと、前記基準配列構築物内の前記複数の位置の各々との重複をスコア付けし、ここで高スコアは重複の量が大きいことに対応し;
各配列リードについて、最高のスコアに対応する前記重複を同定し;
各配列リードを、最高のスコアに対応する前記構築物上の場所へと割り当て;
アラインされた各配列リードの前記場所に対応するメモリにファイルを書き込む
ことをさせる命令を含む、システム。
(項目2)
前記配列リードが、核酸配列リードである、項目1に記載のシステム。
(項目3)
前記配列リードが、アミノ酸配列リードである、項目1に記載のシステム。
(項目4)
前記メモリが、実行された際、前記プロセッサーに、
各配列リードの前記割り当てられた場所に基づき、前記複数のアラインされた配列リードをアセンブルして、アセンブルされた配列を得て;
前記アセンブルされた配列に対応するメモリにファイルを書き込む
ことをさせる命令をさらに含む、項目1に記載のシステム。
(項目5)
前記アセンブルされた配列が、生物の遺伝子配列に対応する、項目4に記載のシステム。
(項目6)
前記遺伝子配列が、染色体またはゲノムを実質的に包含する、項目5に記載のシステム。
(項目7)
1または複数のアラインされた配列リードの前記場所に基づき、生物に遺伝子型を割り当てることをさらに含む、項目1に記載のシステム。
(項目8)
前記割り当てられた遺伝子型を、疾患の危険性と相関させることをさらに含む、項目7に記載のシステム。
(項目9)
前記疾患が、がんである、項目8に記載のシステム。
(項目10)
前記基準配列構築物が、非一時的コンピュータ可読メディアに保存された位置および記号についてのデータベースを含む、項目1に記載の方法。
(項目11)
前記システムが、複数のプロセッサーを含み、各プロセッサーが、前記複数の配列リードの部分を前記基準配列構築物と比較しスコア付けするように構成されている、項目1に記載のシステム。
(項目12)
前記メモリが、第2のプロセッサーが、得て、比較し、スコア付けし、同定し、割り当て、次いで前記割り当てられた場所を第1のプロセッサーへと送信することを前記第1のプロセッサーに命令させる命令をさらに含む、項目1に記載のシステム。
(項目13)
前記基準配列構築物上の各位置が、基準配列内の核酸に対応する、項目1に記載のシステム。
(項目14)
前記構築物上の各位置が、基準配列内のアミノ酸に対応する、項目1に記載のシステム。
(項目15)
前記構築物上の各位置が、基準配列内の遺伝子に対応する、項目1に記載のシステム。
(項目16)
前記基準配列構築物が、方向を有する、項目1に記載のシステム。
(項目17)
前記基準配列構築物を前記方向で通る経路が、生物のゲノムを表示する、項目16に記載のシステム。
(項目18)
前記基準配列構築物を前記方向で通る経路が、生物の染色体を表示する、項目16に記載のシステム。
(項目19)
前記基準配列構築物を前記方向で通る経路が、タンパク質を表示する、項目16に記載のシステム。
(項目20)
前記基準配列構築物を前記方向で通る経路が、非巡回経路である、項目16に記載のシステム。
(項目21)
前記構築物内の記号の前記少なくとも2つの異なるストリングが、前記位置における公知の配列変異を表示する、項目1に記載のシステム。
(項目22)
記号の前記少なくとも2つの異なるストリングが、塩基の挿入または塩基の欠失により互いに異なる核酸配列に対応する、項目1に記載のシステム。
(項目23)
記号の前記少なくとも2つの異なるストリングが、アミノ酸の挿入またはアミノ酸の欠失により互いに異なるポリペプチドに対応する、項目1に記載のシステム。
(項目24)
前記基準配列構築物が、1,000を超える記号を含む、項目1に記載のシステム。
(項目25)
前記基準配列構築物が、1,000,000を超える記号を含む、項目24に記載のシステム。
(項目26)
前記複数の配列リードが、1000を超える配列リードを含む、項目1に記載のシステム。
(項目27)
前記複数の配列リードの大部分が、記号100個を超える長さである、項目1に記載のシステム。
(項目28)
前記複数の配列リードが、次世代シーケンシング法の出力ファイルである、項目1に記載のシステム。
(項目29)
複数の配列リードをアラインする方法であって、
複数の配列リードを得るステップと;
基準配列構築物に対する各配列リードごとの配列の重複をスコア付けするステップであり、前記構築物は、前記構築物内の複数の位置において、位置1箇所当たり少なくとも2つの代替配列を含み、ここで重複が大きくなればより高いスコアがもたらされる、ステップと;
各配列リードごとの前記スコアが最大化されるように、各配列リードを前記構築物内の場所にアラインするステップと
を含む方法。
(項目30)
前記構築物に対する前記配列のアライメントに基づき、前記配列リードを互いにアセンブルするステップをさらに含む、項目29に記載の方法。
(項目31)
前記配列リードが、核酸配列リードである、項目29に記載の方法。
(項目32)
前記配列リードが、アミノ酸配列リードである、項目29に記載の方法。
(項目33)
前記構築物内の各位置が、基準配列内の塩基またはアミノ酸に対応する、項目29に記載の方法。
(項目34)
前記構築物内の各位置が、基準配列内の遺伝子に対応する、項目29に記載の方法。
(項目35)
前記基準配列構築物が、方向を有する、項目29に記載の方法。
(項目36)
前記基準配列構築物を前記方向で通る経路が、生物のゲノムを表示する、項目35に記載の方法。
(項目37)
前記基準配列構築物を前記方向で通る経路が、生物の染色体を表示する、項目35に記載の方法。
(項目38)
前記基準配列構築物を前記方向で通る経路が、タンパク質を表示する、項目35に記載の方法。
(項目39)
前記基準配列を通る経路が、非巡回経路である、項目35に記載の方法。
(項目40)
前記構築物内の前記少なくとも2つの代替配列が、前記位置における公知の遺伝子変異を表示する、項目29に記載の方法。
(項目41)
前記核酸リードの前記割り当てられた場所に基づき、生物に遺伝子型を割り当てるステップをさらに含む、項目40に記載の方法。
(項目42)
前記構築物内の前記少なくとも2つの代替配列が、前記位置における公知の構造変異を表示する、項目29に記載の方法。
(項目43)
前記少なくとも2つの代替配列が、塩基の挿入または塩基の欠失により互いに異なる、項目29に記載の方法。
(項目44)
前記少なくとも2つの代替配列が、アミノ酸の挿入またはアミノ酸の欠失により互いに異なる、項目29に記載の方法。
(項目45)
各リードが、核酸塩基の測定された配列を表示する記号のストリングを含む、項目29に記載の方法。
(項目46)
核酸塩基の前記測定された配列が、サンガーシーケンシング、ピロシーケンシング、イオン半導体シーケンシング、合成を介するシーケンシング、ライゲーションを介するシーケンシング、および単一分子リアルタイムシーケンシングから選択されるシーケンシング法により決定される、項目45に記載の方法。
(項目47)
各リードが、アミノ酸の測定された配列を表示する記号のストリングを含む、項目29に記載の方法。
(項目48)
アミノ酸の前記測定された配列が、質量分析により決定される、項目47に記載の方法。
(項目49)
前記基準配列構築物が、1,000を超える塩基を含む、項目29に記載の方法。
(項目50)
前記基準配列構築物が、1,000,000を超える塩基を含む、項目49に記載の方法。
(項目51)
前記複数のリードが、1000を超えるリードを含む、項目29に記載の方法。
(項目52)
前記複数のリードの大部分が、100塩基対を超える長さである、項目29に記載の方法。
(項目53)
前記複数のリードの大部分が、10アミノ酸を超える長さである、項目29に記載の方法。
(項目54)
前記基準配列構築物が、コンピュータ可読メディアに保存された位置および配列のデータベースを含む、項目29に記載の方法。
(項目55)
前記リードが、コンピュータ可読メディアに保存された記号のストリングを含む、項目54に記載の方法。
(項目56)
試料に由来する複数の核酸をシーケンシングするステップをさらに含む、項目29に記載の方法。
(項目57)
前記試料を患者から得るステップをさらに含む、項目56に記載の方法。
(項目58)
前記試料が、血液、尿、唾液、、糞便、乳首吸引物、、毛包、口腔内スワブ、または組織から選択される、項目56に記載の方法。
(項目59)
複数の核酸を、前記試料から単離するステップをさらに含む、項目58に記載の方法。(項目60)
前記単離された複数の核酸の少なくとも一部を増幅するステップをさらに含む、項目59に記載の方法。
(項目61)
複数の核酸リードをアラインする方法であって、
複数の核酸リードを得るステップと;
前記リード内の塩基と前記構築物内の塩基との重複をスコア付けするアルゴリズムを使用して、前記核酸リードを、基準配列構築物にアラインするステップであり、前記構築物は、前記構築物内の複数の位置において、位置1箇所当たり少なくとも2つの代替配列を含む、ステップと
を含む方法。
(項目62)
前記アルゴリズムが、前記少なくとも2つの配列間の選択に応じた最大の重複スコアを計算する、項目61に記載の方法。
(項目63)
前記基準配列構築物が、有向非巡回グラフである、項目61に記載の方法。
(項目64)
前記構築物が、少なくとも1,000塩基を含む、項目61に記載の方法。
(項目65)
前記構築物が、少なくとも1,000,000塩基を含む、項目64に記載の方法。
(項目66)
複数のアミノ酸リードをアラインする方法であって、
複数のアミノ酸リードを得るステップと;
前記リード内のアミノ酸と前記構築物内のアミノ酸との重複をスコア付けするアルゴリズムを使用して、前記アミノ酸リードを、基準配列構築物にアラインするステップであり、前記構築物は、前記構築物内の複数の位置において、位置1箇所当たり少なくとも2つの代替配列を含む、ステップと
を含む方法。
(項目67)
前記アルゴリズムが、前記少なくとも2つの配列間の選択に応じた最大の重複スコアを計算する、項目66に記載の方法。
(項目68)
前記基準配列構築物が、有向非巡回グラフである、項目66に記載の方法。
(項目69)
前記構築物が、少なくとも100アミノ酸を含む、項目66に記載の方法。
(項目70)
前記構築物が、少なくとも10,000アミノ酸を含む、項目69に記載の方法。
(項目71)
コンピュータで実行される複数のリードをアラインする方法であって、
複数のリードを、記号のストリングとして得るステップと;
コンピュータプロセッサーを使用して、リードに対応する記号の各ストリングを、基準配列構築物内の複数の位置と比較するステップであり、前記構築物は、前記構築物内の複数の位置において、記号の少なくとも2つの異なるストリングを含む、ステップと;
記号の前記ストリングと、前記基準配列構築物内の前記複数の位置の各々との重複を、プロセッサーによりスコア付けするステップであり、高スコアは重複の量が大きいことに対応する、ステップと;
各リードについて、最高のスコアに対応する前記重複を同定するステップと;
前記リードを、最高のスコアに対応する前記構築物上の場所にアラインするステップとを含む方法。
(項目72)
前記構築物上の、前記アラインされた場所に基づき、前記リードを互いにアセンブルするステップをさらに含む、項目71に記載の方法。
(項目73)
前記リードが、核酸リードである、項目71に記載の方法。
(項目74)
前記リードが、アミノ酸リードである、項目71に記載の方法。
(項目75)
前記構築物上の各位置が、基準配列内の塩基に対応する、項目71に記載の方法。
(項目76)
前記構築物上の各位置が、基準配列内のアミノ酸に対応する、項目71に記載の方法。(項目77)
前記構築物上の各位置が、基準配列内の遺伝子に対応する、項目71に記載の方法。
(項目78)
前記基準配列構築物が、方向を有する、項目71に記載の方法。
(項目79)
前記基準配列構築物を前記方向で通る経路が、生物のゲノムを表示する、項目78に記載の方法。
(項目80)
前記基準配列構築物を前記方向で通る経路が、生物の染色体を表示する、項目78に記載の方法。
(項目81)
前記基準配列構築物を前記方向で通る経路が、タンパク質を表示する、項目78に記載の方法。
(項目82)
前記基準配列構築物を前記方向で通る経路が、非巡回経路である、項目78に記載の方法。
(項目83)
前記構築物内の前記少なくとも2つの代替配列が、前記位置における公知の遺伝子変異を表示する、項目71に記載の方法。
(項目84)
前記核酸リードの前記割り当てられた場所に基づき、生物に遺伝子型を割り当てるステップをさらに含む、項目83に記載の方法。
(項目85)
前記少なくとも2つの代替配列が、塩基の挿入または塩基の欠失により互いに異なる、項目71に記載の方法。
(項目86)
各核酸リードが、核酸塩基の測定された配列を表示する記号のストリングを含む、項目71に記載の方法。
(項目87)
核酸塩基の前記測定された配列が、サンガーシーケンシング、ピロシーケンシング、イオン半導体シーケンシング、合成を介するシーケンシング、ライゲーションを介するシーケンシング、および単一分子リアルタイムシーケンシングから選択されるシーケンシング法により決定される、項目86に記載の方法。
(項目88)
前記基準配列構築物が、1,000を超える塩基を含む、項目71に記載の方法。
(項目89)
前記基準配列構築物が、1,000,000を超える塩基を含む、項目88に記載の方法。
(項目90)
前記複数の核酸リードが、1000を超えるリードを含む、項目71に記載の方法。
(項目91)
前記複数の核酸リードの大部分が、100塩基対を超える長さである、項目71に記載の方法。
(項目92)
コンピュータで実行される複数のリードをアラインする方法であって、
複数のリードを、記号のストリングとして得るステップと;
前記リードと前記構築物との重複をスコア付けするアルゴリズムを実行するプロセッサーを使用して、前記リードを、基準配列構築物にアラインするステップであり、前記構築物は、前記構築物内の複数の位置において、位置1箇所当たり少なくとも2つの代替配列を含む、ステップとを含む方法。
(項目93)
前記アルゴリズムが、前記少なくとも2つの代替配列の選択に応じて最大の重複スコアを計算する、項目92に記載の方法。
(項目94)
前記基準配列構築物が、有向非巡回グラフである、項目92に記載の方法。
(項目95)
前記複数の核酸リードが、コンピュータ可読メディアに保存される、項目92に記載の方法。
(項目96)
前記基準配列構築物が、コンピュータ可読メディアに保存されたデータベースを含む、項目92に記載の方法。
(項目97)
複数のリードをアラインするための、プロセッサーおよびメモリを含むシステムであって、前記メモリは、実行された際、前記プロセッサーに、
複数のリードを、記号のストリングとして得て;
前記リードと前記構築物との重複をスコア付けするアルゴリズムを使用して、前記リードを基準配列構築物にアラインし、ここで前記構築物は、前記構築物内の複数の位置において、位置1箇所当たり少なくとも2つの代替配列を含み;
前記アラインされた配列に対応するメモリにファイルを書き込む
ことをさせる命令を含む、システム。
(項目98)
前記メモリが、実行された際、前記少なくとも2つの代替配列の選択に応じて最大の重複スコアを計算することを前記プロセッサーにさせる命令をさらに含む、項目97に記載のシステム。
(項目99)
前記基準配列構築物が、有向非巡回グラフである、項目97に記載のシステム。
(項目100)
前記複数のリードが、コンピュータ可読メディアに保存される、項目97に記載のシステム。
(項目101)
前記基準配列構築物が、コンピュータ可読メディアに保存されたデータベースを含む、項目97に記載のシステム。
(項目102)
複数の配列リードをアラインする方法であって、
複数の配列リードを得るステップと;
基準配列構築物に対する各配列リードごとの配列の重複をスコア付けするステップであり、前記構築物は、前記構築物内の複数の位置において、位置1箇所当たり少なくとも2つの代替配列を含み、ここで重複が大きくなればより低いスコアがもたらされる、ステップと;
各配列リードごとの前記スコアが最小化されるように、各配列リードを、前記構築物内の場所にアラインするステップと
を含む方法。
(項目103)
コンピュータで実行される複数のリードをアラインする方法であって、
複数のリードを、記号のストリングとして得るステップと;
コンピュータプロセッサーを使用して、リードに対応する記号の各ストリングを、基準配列構築物内の複数の位置と比較するステップであり、前記構築物は、前記構築物内の複数の位置において、記号の少なくとも2つの異なるストリングを含む、ステップと;
記号の前記ストリングと、前記基準配列構築物内の前記複数の位置の各々との重複を、プロセッサーによりスコア付けするステップであり、低スコアは重複の量が大きいことに対応する、ステップと;
各リードについて、最低のスコアに対応する前記重複を同定するステップと;
前記リードを、最低のスコアに対応する前記構築物上の場所にアラインするステップとを含む方法。
(項目104)
複数のリードをアラインするための、プロセッサーおよびメモリを含むシステムであって、前記メモリは、実行された際、前記プロセッサーに、
複数のリードを、記号のストリングとして得て;
リードに対応する記号の各ストリングを、基準配列構築物内の複数の位置と比較し、ここで前記構築物は、前記構築物内の複数の位置において、記号の少なくとも2つの異なるストリングを含み;
記号の前記ストリングと、前記基準配列構築物内の前記複数の位置の各々との重複をスコア付けし、ここで低スコアは重複の量が大きいことに対応し;
各核酸リードについて、最低のスコアに対応する前記重複を同定し;
前記核酸リードを、最低のスコアに対応する前記構築物上の場所へと割り当て;
前記アラインされた配列に対応するメモリにファイルを書き込む
ことをさせる命令を含む、システム。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 株式会社堀場製作所の「 エクソソーム表面分子を特定する方法」が 公開されました。( 2020/10/29)

    【課題・解決手段】本発明はエクソソーム表面分子に対する結合性分子が固相化された担体をカゼイン溶液またはカゼイン分解物溶液でブロックおよび洗浄すること、ならびに該担体とエクソソームを含む被験試料の接触前... 詳細

  • 株式会社資生堂の「 レチノイドの副作用に対する感受性の決定方法」が 公開されました。( 2020/10/29)

    【課題・解決手段】SNP解析により遺伝要素に基づいて対象のレチノイドの副作用に対する感受性を決定する方法、レチノイドの副作用に対する感受性を決定するコンピュータ、及び当該コンピュータを制御するプログラ... 詳細

  • 公立大学法人福島県立医科大学の「 大腸がんの予後バイオマーカー」が 公開されました。( 2020/10/29)

    【課題・解決手段】大腸がん患者の予後を予測するための、及び/又は大腸がん患者に対する抗がん剤の有効性を判定するためのバイオマーカーを提供する。GALNT6タンパク質若しくはそのペプチド断片、又はGAL... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ