(81)【指定国】
AP(BW,GH,GM,KE,LR,LS,MW,MZ,NA,RW,SD,SL,ST,SZ,TZ,UG,ZM,ZW),EA(AM,AZ,BY,KG,KZ,RU,TJ,TM),EP(AL,AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HR,HU,IE,IS,IT,LT,LU,LV,MC,MK,MT,NL,NO,PL,PT,RO,RS,SE,SI,SK,SM,TR),OA(BF,BJ,CF,CG,CI,CM,GA,GN,GQ,GW,KM,ML,MR,NE,SN,TD,TG),AE,AG,AL,AM,AO,AT,AU,AZ,BA,BB,BG,BH,BN,BR,BW,BY,BZ,CA,CH,CL,CN,CO,CR,CU,CZ,DE,DJ,DK,DM,DO,DZ,EC,EE,EG,ES,FI,GB,GD,GE,GH,GM,GT,HN,HR,HU,ID,IL,IN,IR,IS,JP,KE,KG,KH,KN,KP,KR,KW,KZ,LA,LC,LK,LR,LS,LU,LY,MA,MD,ME,MG,MK,MN,MW,MX,MY,MZ,NA,NG,NI,NO,NZ,OM,PA,PE,PG,PH,PL,PT,QA,RO,RS,RU,RW,SA,SC,SD,SE,SG,SK,SL,SM,ST,SV,SY,TH,TJ,TM,TN,TR,TT,TZ
前記共有メモリは、ゲノムデータの複数のリード、少なくとも1つまたは複数の遺伝子参照配列、および前記1つまたは複数の遺伝子参照配列のインデックスを記憶する、請求項1に記載のゲノミクス解析プラットフォーム。
各FPGAは、前記シード、前記レコード、および前記1つまたは複数のマッチング位置を一時的に記憶するための事前構成されたハード配線されたデジタル論理回路の前記セットに接続されるメモリブロックのセットをさらに含む、請求項5に記載のゲノミクス解析プラットフォーム。
前記2地点間インターコネクトプロトコルは、前記共有メモリ内の前記遺伝子配列データおよび結果データの各CPUおよび各GPUの間のコヒーレンシを確実にするコヒーレンシプロトコルを含む、請求項1に記載のゲノミクス解析プラットフォーム。
各CPUは、前記共有メモリの第1の部分を記憶し、前記コヒーレンシプロトコルに参加する第1のキャッシュを備える、請求項10に記載のゲノミクス解析プラットフォーム。
各FPGAは、前記共有メモリの第2の部分を記憶し、前記コヒーレンシプロトコルに参加する第2のキャッシュを備える、請求項11に記載のゲノミクス解析プラットフォーム。
前記共有メモリは、ゲノムデータの複数のリード、少なくとも1つまたは複数の遺伝子参照配列、および前記1つまたは複数の遺伝子参照配列のインデックスを記憶する、請求項13に記載のゲノミクス解析プラットフォーム。
【図面の簡単な説明】
【0050】
【図1A】複数の遺伝子サンプルが載せられたシークエンシングプラットフォームを示す、複数の例示的なタイルも示されている、さらには配列決定リードの3次元表現を示す図である。
【図1B】様々なレーンが表されている流動セルの表現を示す図である。
【図1C】配列決定リードの集合を示す、図1Bの流動セルプラットフォームの下側隅を示す図である。
【図1D】図1および図2のリードに対して実行されるシークエンシングの結果の仮想配列を示す、それらのリードが列毎の順序で出力内に記述される、図である。
【図1E】列毎の順序から行毎のリード順序への結果リードの転移が実装され得る方法を示す図である。
【図1F】列毎の順序から行毎のリード順序への結果リードの転移を示す図である。
【図1G】転移を実行するためのシステムコンポーネントを示す図である。
【図1H】転移順序を示す図である。
【図1I】配列決定データを電子的に転移するためのアーキテクチャを示す図である。
【図2】一方の状態から他方の状態に移る遷移確率を例示するHMM 3状態ベースモデルを示す図である。
【図3A】HMMインターフェース構造を含む本開示の集積回路の高水準ビューを示す図である。
【図3B】HMMクラスタ特徴をより詳しく示している、図3Aの集積回路を示す図である。
【図4】ソフトウェアとハードウェアの両方の相互作用を含むシステム全体におけるHMM関係データフローの概要を示す図である。
【図5】例示的なHMMクラスタカラー接続部(HMM cluster collar connection)を示す図である。
【図6】例示的なHMMハードウェアアクセラレータ内の主要機能ブロックの高水準ビューを示す図である。
【図7】例示的なHMM行列構造およびハードウェア処理フローを示す図である。
【図8】行列内のHMM M、I、およびD状態計算における近隣セル間のデータフローおよび依存関係を示す図2の一部の拡大図である。
【図9】M、I、D状態更新に有用な例示的な計算を示す図である。
【図10】遷移確率に関係する図9の仮定を簡素化する効果、およびいくつかのM、I、D加算器リソースを最終総和オペレーションと共有する効果を含む、M、I、およびD状態更新回路を示す図である。
【図11】対数領域M、I、D状態計算詳細を示す図である。
【図12】GOP、GCP、および遷移確率の間の関係を示すHMM状態遷移図である。
【図13】図12の一般状態遷移図をサポートするためのHMM遷移確率および事前確率生成回路を示す図である。
【図14】GOP、GCP、および遷移確率の間の関係を示す簡素化されたHMM状態遷移図である。
【図15】簡素化された状態遷移をサポートするためのHMM TransprobsおよびPriors生成回路を示す図である。
【図16】例示的な理論的HMM行列を示し、そのようなHMM行列がどのようにトラバースされ得るかを例示する図である。
【図17A】多領域結合検出前処理手順(multi-region joint detection pre-processing procedure)を実行するための方法を提示する図である。
【図17B】図17Aの前処理手順などにおける接続行列を計算するための例示的な方法を提示する図である。
【図18A】リードのパイルアップ内の2つの相同配列決定領域の間の例示的な事象を示す図である。
【図18B】2つの配列の間のヌクレオチド差異を区別する、図18Aの構築されたリードを示す図である。
【図18C】加速されたバリアントコールオペレーションを実行する際に使用され得るDe Bruijnグラフの様々なバブルを示す図である。
【図18D】本明細書で説明されているようなツリー刈り込み機能の表現を示す図である。
【図18E】図18Cのバブルのうちの1つを示す図である。
【図19】図17の接続行列に従う例示的なパイルアップのグラフィック表現である。
【図20】図17Aおよび図17Bの前処理手順を実行するための処理行列を示す図である。
【図21】図20の方法によるDe Bruijnグラフ内のバブル形成の一例を示す図である。
【図22】例示的なDe Bruijnグラフを通るバリアント経路の一例を示す図である。
【図23】例示的なソーティング機能のグラフィック表現である。
【図24】刈り込まれた多領域結合検出手順に対する処理行列の別の例を示す図である。
【図25】2つの領域に対するペアリードの結合パイルアップを示す図である。
【図26】本明細書の開示による確率テーブルを述べた図である。
【図27】多領域結合検出手順に対する処理行列のさらなる例を示す図である。
【図28】図25の結合パイルアップに対する候補解の選択を表す図である。
【図29】刈り込み機能が実行された後の、図28のパイルアップに対する候補解のさらなる選択を表す図である。
【図30】MRJD機能の実行の後の、図28の最終候補、およびその関連付けられている確率を表す図である。
【図31】MRJDに対するROC曲線および従来の検出器を示す図である。
【図32】参照の配列類似度の関数として表示される図31の同じ結果を例示する図である。
【図33A】本開示のCPUとFPGAとの間の疎結合を示す例示的なアーキテクチャを示す図である。
【図33B】本開示のCPUとFPGAとの間の密結合を示す例示的なアーキテクチャを示す図である。
【図34A】本開示のCPUおよびFPGAの直接結合を示す図である。
【図34B】図34AのCPUおよびFPGAの直接結合の代替的実施形態を示す図である。
【図35】組み合わされたCPUおよびFPGAのパッケージの一実施形態を示す、2つのデバイスが共通のメモリおよび/またはキャッシュを共有する、図である。
【図36】1つまたは複数のメモリおよび/またはキャッシュを共有するCPUのコアであって、CPUは、共有されるか、または共通のメモリもしくはキャッシュも含み得る1つまたは複数のFPGAと通信するように構成されている、コアを示す図である。
【図37】システム全体を通してのデータ転送の例示的な方法を示す図である。
【図38】図36の実施形態をより詳細に示す図である。
【図39】本開示のシステムの1つまたは複数のジョブの処理のための例示的な方法を示す図である。
【図40A】オンサイトおよび/またはクラウドベースのゲノミクス処理および解析のためのゲノムインフラストラクチャに対するブロック図である。
【図40B】本明細書で開示されているBioIT解析を実行するためのクラウドベースのゲノミクス処理プラットフォームのブロック図である。
【図40C】例示的なゲノム処理および解析パイプラインに対するブロック図である。
【図40D】例示的なゲノム処理および解析パイプラインに対するブロック図である。
【図41A】オンサイトおよび/またはクラウドベースのゲノミクス処理および解析のためのゲノムインフラストラクチャに対する図40Aのローカルおよび/またはクラウドベースのコンピューティング機能のブロック図である。
【図41B】オンサイトおよび/またはクラウドベースのゲノミクス処理および解析のためのゲノムインフラストラクチャに対するコンピューティング機能に関する図41Aのより詳しいブロック図である。
【図41C】オンサイトおよび/またはクラウドベースのゲノミクス処理および解析のためのゲノムインフラストラクチャに対するサードパーティアナリティクス機能に関する図40のより詳しいブロック図である。
【図42A】ハイブリッドクラウド構成を例示するブロック図である。
【図42B】ハイブリッドクラウド構成を示す、図42Aのより詳しいブロック図である。
【図42C】ハイブリッドクラウド構成を示す、図42Aのより詳しいブロック図である。
【図43A】本明細書に提示されているような一次、二次、および/または三次解析パイプラインを示すブロック図である。
【図43B】本明細書のシステムの方法およびデバイスによる実行のための例示的な三次処理エピジェネティクス解析を示す図である。
【図43C】本明細書のシステムの方法およびデバイスによる実行のための例示的な三次処理メチル化解析を示す図である。
【図43D】本明細書のシステムの方法およびデバイスによる実行のための例示的な三次処理構造バリアント解析を示す図である。
【図43E】本明細書のシステムの方法およびデバイスによる実行のための例示的な三次コホート処理解析を示す図である。
【図43F】本明細書のシステムの方法およびデバイスによる実行のための例示的なジョイント遺伝型判定三次処理解析を示す図である。
【図44】本開示の解析パイプラインに対する流れ図である。
【図45】本開示の一実装形態によるハードウェアプロセッサアーキテクチャのブロック図である。
【図46】別の実装形態によるハードウェアプロセッサアーキテクチャのブロック図である。
【図47】さらに別の実装形態によるハードウェアプロセッサアーキテクチャのブロック図である。
【図48】遺伝子配列解析パイプラインを示す図である。
【図49】遺伝子配列解析ハードウェアプラットフォームを使用する処理ステップを示す図である。
【図50A】本開示の一実装形態による装置を示す図である。
【図50B】本開示の代替的実装形態による別の装置を示す図である。
【図51】一実装形態によるゲノミクス処理システムを示す図である。
【発明を実施するための形態】
【0051】
上で要約されているように、本開示は、遺伝子配列データに対するなど、一次処理手順を通じて生成されたデータについて、マッピング、アライメント、ソーティング、および/またはバリアントコールプロトコルなどの、1つまたは複数のゲノミクスおよび/またはバイオインフォマティクスプロトコルを実行する際にそれを使用するためのデバイス、システム、および方法を対象とする。たとえば、様々な態様において、本明細書において提供されるデバイス、システム、および方法は、たとえば次世代シークエンサ(「NGS」)によって、RNAおよび/またはDNAのシークエンシングによって生成されるデータなどの、遺伝子データに対して二次解析プロトコルを実行するように構成される。特定の実施形態において、遺伝子配列データを処理するための1つまたは複数の二次処理パイプラインが実現され、たとえば、これらのパイプライン、および/またはそれらの個別の要素は、当技術分野において現在利用可能である以上に広範にわたる配列導出データについて優れた感度および改善された精度をもたらすように分散されおよび/または最適化された方式でソフトウェア、ハードウェア、またはこれらの組合せで実装されてよい。それに加えて、上で要約されているように、本開示は、1つまたは複数のバリアントコールファイルなどを使用して、マッピングされた、アライメントされた、および/または他の遺伝子配列データ上での、マイクロアレイ解析プロトコル、ゲノム、たとえば、全ゲノム解析プロトコル、遺伝型判定解析プロトコル、エクソーム解析プロトコル、エピゲノム解析プロトコル、メタゲノム解析プロトコル、マイクロバイオーム解析プロトコル、ジョイント遺伝型判定を含む遺伝型判定解析プロトコル、構造バリアント、体細胞バリアント、およびGATKを含むバリアント解析プロトコル、さらにはRNAシークエンシングプロトコルおよび他の遺伝子解析プロトコルなどの、1つまたは複数のゲノミクスおよび/またはバイオインフォマティクス三次プロトコルの実行においてそれを使用するためのデバイス、システム、および方法を対象とする。
【0052】
したがって、本明細書において提供されるのは、DNA/RNAシークエンシングデータの二次および/または三次解析を実行するためのソフトウェアおよび/またはハードウェア、たとえば、チップベースの、加速プラットフォーム解析技術である。より具体的には、ソフトウェア実装および/またはハード配線された構成などによる、処理エンジンのプラットフォーム、すなわちパイプラインが実現され、これらは二次遺伝子解析、たとえば、マッピング、アライメント、ソーティング、および/またはバリアントコーリングを実行するように特に設計されており、ならびに/あるいは知られているソフトウェアだけで実装される標準的なパイプラインよりも数桁速い処理速度の改善をもたらす最適化されたフォーマットで生成されていてよい、遺伝子ベースのシークエンシングデータなどに関して、マイクロアレイ解析、ゲノム、たとえば、全ゲノム解析、遺伝型判定解析、エクソーム解析、エピゲノム解析、メタゲノム解析、マイクロバイオーム解析、ジョイント遺伝型判定解析を含む遺伝型判定解析、構造バリアント解析、体細胞バリアント解析、およびGATK解析を含むバリアント解析、さらにはRNAシークエンシング解析および他の遺伝子解析などの、三次遺伝子解析を実行するよう特に設計され得る。それに加えて、本明細書で提示されているパイプラインは、核酸またはタンパク質由来の配列などの、広範な配列導出データセット上でより良好な感度および精度をもたらす。
【0053】
上に示されているように、様々な事例において、バイオインフォマティクス処理の目的は、人々の個別のゲノムおよび/またはタンパク質配列を決定することであり、これらの決定は、遺伝子発見プロトコルで使用されるほかに、各特定の人および全体として人間の生活をよりよく向上させるための予防および/または治療レジメンにも使用され得る。さらに、個体のゲノムおよび/またはタンパク質コンペレーション(protein compellation)についての知識は、創薬および/またはFDA治験などにおいて使用されて、個体のゲノムおよび/またはそれから導出されるタンパク質プロファイルを解析し、それをそのような薬物投与からの予測された生物学的反応と比較することなどによって、もしあればどの薬物が個体に有効である可能性が高いか、および/または有害な副作用を有する可能性が高くなるかを詳細によりよく予測し得る。
【0054】
そのようなバイオインフォマティクス処理は、通常は、情報処理の3つの明確に定義された、ただし典型的には別個のフェーズを伴う。第1のフェーズは、一次処理と呼ばれるフェーズで、DNA/RNAシークエンシングを伴い、対象のDNAおよび/またはRNAが取得されて、様々なプロセスにさらされ、それによって、対象の遺伝子コードは、機械可読デジタルコード、たとえば、FASTQファイルに変換される。第2のフェーズは、二次処理と呼ばれるフェーズで、対象の生成されたデジタル遺伝子コードを使用して、個体の遺伝子構造を決定する、たとえば、個体のゲノムヌクレオチド配列を決定するステップを伴う。そして第3のフェーズは、三次処理と呼ばれるフェーズであり、対象の遺伝子構造に対して1つまたは複数の解析を実行して治療上有用な情報をそこから決定するステップを伴う。
【0055】
したがって、対象の遺伝子コードが、NextGenシークエンサなどによって配列決定され、それにより、たとえば、FASTQおよび/またはBCLファイルフォーマットで対象の遺伝子コードの機械可読デジタル表現を作成した後、デジタル方式で表現されているデータを二次処理に通すことなどによって、シークエンサおよび/またはシークエンシングプロトコルから得られた2値符号化遺伝子配列データをさらに処理することは有用であり得る。この二次処理は、たとえば、個体のゲノム全体および/またはタンパク質プロファイルをマッピングし、および/またはアライメントし、および/または他の何らかの形でアセンブルするために使用されてよく、たとえば、個体の遺伝子構造全体が決定される、たとえば、ありとあらゆる染色体のありとあらゆるヌクレオチドは、個体のゲノム全体の組成が識別された順番に決定される。そのような処理では、個体のゲノムは、参照標準などの参照ゲノム、たとえば、ヒトゲノムプロジェクトまたは同様のものから得られた1つまたは複数のゲノムとの比較などによってアセンブルされるものとしてよく、それにより、個体の遺伝子構造が参照先の構造とどれだけ異なるかを決定する。このプロセスは、バリアントコーリングとして一般に知られている。人同士のDNAの差異は、1,000塩基対に1の割合であるので、そのようなバリアントコーリングプロセスは、労働集約性も時間集約性も非常に高くなることがあり、対象のゲノムデータを解析し、その遺伝子配列が所与の参照とどれだけ異なっているかを決定するために、パイプラインなどで、次々に、および/または同時に、実行される必要があり得る多くのステップを必要とする。
【0056】
個別の対象の所与のクエリ配列に対するバリアントコールファイルを生成するなどのための、二次解析パイプラインを実行する際に、遺伝子サンプル、たとえば、DNA、RNA、タンパク質サンプル、または同様のものが、対象から得られるものとしてよい。次いで、対象のDNA/RNAは、たとえば、NextGen Sequencer(NGS)および/またはシークエンサオンアチップ(sequencer-on-a-chip)技術によって、たとえば、一次処理ステップにおいて配列決定されるものとしてよく、それにより、オーバーサンプリング方式などで、個体のゲノムの全部または一部をカバーする非常に多数のリード配列セグメント(「リード」)を作成する。シークエンシングデバイスによって生成される最終作成物は、対象のゲノムの小セグメントを表す短配列、たとえば、リードの集合体、たとえば、個体のゲノム全体を表現する短遺伝子配列であってよい。示されているように、典型的には、これらのリードによって表現される情報は、画像ファイルであるか、またはデジタル形式、たとえば、FASTQ、BQL、または他の類似のファイル形式をとり得る。
【0057】
特に、典型的な二次処理プロトコルにおいて、対象の遺伝子構造は、参照ゲノムとの比較によってアセンブルされる。この比較は、何百万もの短リード配列からの個体のゲノムの再構築および/または個体のDNAの全体と例示的なDNA配列モデルとの比較を伴う。典型的な二次処理プロトコルでは、画像、FASTQ、および/またはBCLファイルがシークエンサから受け取られ、これは生の配列決定されたリードデータを含む。対象のゲノムを標準参照ゲノムと比較するために、これらのリードの各々が参照ゲノムにどこでマッピングされるか、たとえば、各々が互いに関してどのようにアライメントされるか、および/または各リードがどのような位置でどの染色体に属するかを決定するために各リードも染色体の順序でどのようにソーティングされ得るかが決定される必要がある。これらの機能のうちの1つまたは複数は、完全長配列全体に対してバリアントコール機能を実行する前に、たとえばアセンブルした後に行われ得る。特に、各リードがゲノム内のどこに属しているかが決定された後、完全長遺伝子配列が決定されるものとしてよく、次いで、対象の遺伝子コードと参照先の遺伝子コードとの間の差異が評価され得る。
【0058】
たとえば、典型的な二次処理アセンブリプロトコルにおける参照ベースのアセンブリは、対象の配列決定ゲノムDNA/RNAを1つまたは複数の標準のそれ、たとえば知られている参照配列と比較することを伴う。様々なマッピング、アライメント、ソーティング、および/またはバリアントコーリングアルゴリズムは、これらのプロセスを促進する手助けとなるように開発されている。したがって、これらのアルゴリズムは、各染色体上のどこに各特定のリードが配置されているかを決定するために、シークエンサによって伝達される画像、FASTQ、および/またはBCLファイルから受け取った数百万個のリードをマッピングするステップ、アライメントさせるステップ、および/またはソーティングするステップのうちの1つまたは複数のいくつかのバリエーションを含み得る。これらのプロセスは、両方ともEdico Genome Corporationに譲渡され、参照によりその全体が本明細書に組み込まれている、米国特許第9,014,989号および米国特許第9,235,680号において説明されている方法および/またはデバイスなどによって、ソフトウェアまたはハードウェアで実装されてよいことに留意されたい。多くの場合において、これらの様々なアルゴリズムおよび/またはハードウェア実装形態の機能の背後にある共通の特徴は、それらがインデックスおよび/またはアレイを使用してその処理機能を促進することである。
【0059】
たとえば、マッピングに関しては、大量の、たとえば、すべての配列決定リードが、それらのリードが場合によってはアライメントされる可能性のある参照ゲノム内の可能な配置を決定するように処理され得る。この目的のために使用され得る一方法は、リードを参照ゲノムと直接比較してマッチングのすべての位置を見つけることである。別の方法は、リードを参照ゲノム内の様々な位置にマッピングすることを目的としてプレフィックスまたはサフィックスアレイを使用するか、またはプレフィックスまたはサフィックスツリーを構築することである。そのような機能を実行する際に有用な典型的なアルゴリズムは、Burrows-Wheeler変換であり、これはデータの反復配列を圧縮する圧縮公式を使用してリードの選択を参照にマッピングするために使用される。
【0060】
さらなる方法はハッシュテーブルを使用する方法であり、たとえば、リードの選択されたサブセット、選択された長さ「k」のk-mer、たとえばシードがキーとしてハッシュテーブル内に置かれ、参照配列は相当するk-mer長部分とそれらの部分に分けられ、その配置はアルゴリズムによってハッシュテーブル内の、ハッシング関数に従ってマッピングするテーブル内の配置のところに挿入される。この関数を実行するための典型的なアルゴリズムは「BLAST」、Basic Local Alignment Search Toolである。そのようなハッシュテーブルベースのプログラムは、クエリヌクレオチドまたはタンパク質配列を1つまたは複数の標準参照配列データベースと比較し、マッチの統計的有意性を算出する。これらのような方式で、参照ゲノムに関して所与のリードが場合によってはどの場所に配置されるかが決定され得る。これらのアルゴリズムは、より少ないメモリ、より少ない検索回数、LUTで済み、したがって、これらのアルゴリズムがない場合、たとえば、対象のゲノムが、たとえばこれらのアルゴリズムを使用せずに、直接比較によってアセンブルされる場合などと比べてそれらの機能の実行においてより少ない処理リソースおよび時間で済むので有用である。
【0061】
それに加えて、アライメント機能は、実際には元のシークエンシングプロトコルによって配列決定されることなどによって実際にそれが導出された際の配置であるゲノム内の複数の位置にリードがマッピングされ得る場合などにおいて、ゲノム上で所与のリードがマッピングされ得る可能なすべての配置から決定するように実行され得る。この機能は、ゲノムのリード、たとえば、マッピングされたリードの多くに対して実行されてよく、対象のDNA/RNAの一部または遺伝子配列全体を表す順序付けられたヌクレオチド塩基の列が取得され得る。順序付けられた遺伝子配列とともに、所与の位置における各ヌクレオチドに対してスコアが付けられるものとしてよく、これは所与のヌクレオチド位置に対して、その位置にあると予測されるヌクレオチド、たとえば、「A」、「C」、「G」、「T」(または「U」)は、実際に、その割り当てられた位置に属すヌクレオチドである確率を表す。アライメント機能を実行するための典型的なアルゴリズムは、Needleman-WunschおよびSmith-Watermanアルゴリズムを含む。いずれの場合においても、これらのアルゴリズムは、対象のクエリゲノム配列の列と参照ゲノム配列の列との間の配列アライメントを実行し、それによって、ゲノム配列全体を一方と他方とで比較する代わりに、可能な長さの選択のセグメントが比較される。
【0062】
リードがどの染色体に属すか、および/またはその染色体の先頭からのオフセットを識別するステップを含み得る、参照ゲノムなどに関する、位置をリードに割り当てることが行われた後、リードは位置でソーティングされるものとしてよい。これは、下流解析で本明細書において説明されているオーバーサンプリング手順を利用することを可能にし得る。ゲノム内の所与の位置に重なるリードはすべて、ソーティングの後に互いに隣接し、それらはパイルアップに編成され、それらの大半が参照値と合致するかどうかを決定するために容易に調べられ得る。合致しない場合、バリアントにフラグが立てられるものとしてよい。
【0063】
たとえば、様々な実施形態において、本開示の方法は、たとえば、1つまたは複数の参照ゲノムに関連して、DNA/RNAが配列決定された個体の遺伝的バリアントの1つまたは複数、たとえばすべてを識別するバリアントコールファイル(VCF)を生成するステップを含み得る。たとえば、実際のサンプルゲノムが知られ、参照ゲノムと比較された後、それら2つの間のバリエーションが決定されてよく、参照ゲノムとサンプルゲノムとの間のすべてのバリエーション/偏差のリストがコールアウトされてよく、たとえば、バリアントコールファイルが作成され得る。特に、一態様において、参照配列に対する対象の遺伝子配列のすべてのバリエーションを含むバリアントコールファイルが生成されるものとしてよい。
【0064】
上で示されているように、2つの遺伝子配列の間のそのようなバリエーションは、多数の理由から生じ得る。したがって、そのようなファイルを生成するために、対象のゲノムは配列決定され、そのバリアントを決定する前に再構築されなければならない。しかしながら、そのようなアセンブリを生成することを試みたときに生じ得るいくつかの問題がある。たとえば、化学反応、シークエンシング機、および/またはシークエンシングプロセスにおいて生じ得るヒューマンエラーに関連する問題があり得る。さらに、そのような再構築に問題を引き起こす遺伝子のアーチファクトがあり得る。たとえば、そのようなアセンブリを実行することに関連する典型的な問題は、ヌクレオチドの同じ列を含むゲノムの長いセクションなど、自己反復するゲノムの巨大な部分があることがあるという点である。したがって、遺伝子配列はすべての場所で一意的であるとは限らないので、識別されたリードが実際にゲノム内のどこでマッピングされアライメントされるかを決定するのは困難であり得る。それに加えて、一塩基多型(SNP)があり得、たとえば、対象の遺伝子配列内の1つの塩基が別の塩基と置き換えられており、複数のヌクレオチドのより広範な置換があり得、挿入または欠失があり得、たとえば、1つまたは多数の塩基が対象の遺伝子配列に加えられるか、または欠失されており、および/または、たとえば、2つの染色体の枝の交差によって引き起こされるような、構造バリアントがあり得、および/または配列内にシフトを引き起こすオフセットが単純にあり得る。
【0065】
したがって、バリエーションに対して2つの主要な可能性がある。一例として、注目している特定の配置に実際のバリエーションがあり、たとえば、ヒトのゲノムは、実際に、特定の配置において参照と異なり、たとえば、SNP(1塩基置換)、挿入もしくは欠失(ヌクレオチド1つまたは複数分の長さの)により自然なバリエーションがあり、および/または構造バリアントがあり、たとえば、1つの染色体からのDNA物質は異なる染色体または枝上に交差し、または特定の領域がDNA内で2回複製される。代替的に、バリエーションは、化学反応または機械、シークエンサまたはアライナ、もしくは他のヒューマンエラーのいずれかを通じて、リードデータ内に問題があることによって引き起こされ得る。本明細書で開示されている方法は、これらの種類のエラーを補償し、より具体的には、化学反応、機械または人間によるバリエーションと配列決定ゲノム内の現実のバリエーションにおける誤りを区別するような方式で使用され得る。より具体的には、本明細書で説明されているように、それを採用するための方法、装置、およびシステムは、これらの2つの異なる種類のバリエーションを明確に区別し、したがって真のバリアントを正しく識別するために生成されたコールファイルの精度をより確実にするように、開発された。
【0066】
したがって、特定の実施形態において、遺伝子解析を実行するための技術のプラットフォームが実現され、このプラットフォームは、マッピング、アライメント、ソーティング、局所的再アライメント、重複マーキング、塩基クオリティスコアリキャリブレーション、バリアントコーリング、圧縮、および/または復元のうちの1つまたは複数の機能の実行を含み得る。たとえば、様々な態様において、パイプラインが実現されてよく、パイプラインは、自動化シークエンサからの画像ファイルおよび/またはデジタル、たとえば、FASTQもしくはBCLファイル形式で得られたデータなどの、1人または複数の個体のゲノム配列に対して、本明細書に説明されているように1つまたは複数の解析機能を実行するステップを含む。実行されるべき典型的なパイプラインは、1人または複数の個別の対象の、一部またはゲノムの全部などの、遺伝物質を配列決定するステップのうちの1つまたは複数を含むものとしてよく、この遺伝物質は、DNA、ssDNA、RNA、rRNA、tRNA、および同様のものを含むものとしてよく、および/またはいくつかの事例において、遺伝物質は、DNAのエクソームおよび/またはエピソームなどの、コーディングまたは非コーティング領域を表し得る。パイプラインは、2値化された遺伝子データなどに対して、画像処理手順、塩基コーリング、および/または誤り訂正オペレーションを実行するステップの1つまたは複数を含むものとしてよく、ならびに/あるいは遺伝子データに対しマッピング、アライメント、および/またはソーティング機能を実行するステップの1つまたは複数を含み得る。いくつかの事例において、パイプラインは、2値化された遺伝子データに対して、再アライメント、重複除去、塩基クオリティまたはスコアリキャリブレーション、減少および/または圧縮、および/または復元のうちの1つまたは複数を実行するステップを含み得る。いくつかの事例において、パイプラインは、遺伝子データに対して、隠れマルコフモデルなどのバリアントコーリングオペレーションを実行するステップを含み得る。
【0067】
したがって、いくつかの事例において、これらのプラットフォーム機能のうちの1つまたは複数の実装形態は、対象のコンセンサスゲノム配列を決定し、および/または再構築するステップ、対象のゲノム配列を参照先配列、たとえば、参照もしくはモデル遺伝子配列と比較するステップ、対象のゲノムDNAもしくはRNAが参照先、たとえば、バリアントコーリングと異なる仕方を決定するステップのうちの1つまたは複数を実行し、および/またはたとえば、ゲノムおよび/またはトランスクリプトームのゲノム規模のバリエーション解析、遺伝子機能解析、タンパク質機能解析、たとえば、タンパク質結合解析、定量および/またはアセンブリ解析、さらには様々な診断、および/または予防および/または治療評価解析などのために、対象のゲノム配列に対して三次解析を実行することを目的とする。
【0068】
上で示されているように、一態様において、これらのプラットフォーム機能、たとえば、マッピング、アライメント、ソーティング、再アライメント、重複マーキング、塩基クオリティスコアリキャリブレーション、バリアントコーリング、圧縮、および/または復元機能のうちの1つまたは複数は、ソフトウェアで実装するように構成されている。いくつかの態様において、これらのプラットフォーム機能、たとえば、マッピング、アライメント、ソーティング、局所的再アライメント、重複マーキング、塩基クオリティスコアリキャリブレーション、復元、バリアントコーリング、圧縮、および/または復元機能のうちの1つまたは複数は、ハードウェア、たとえば、ファームウェアで実装するように構成されている。いくつかの態様において、これらの遺伝子解析技術は、より低い処理集約性でおよび/または時間をあまりかけず、および/または正確さのパーセンテージを高めて実行されるソフトウェアによって実装され得る改善されたアルゴリズムを採用するものとしてよく、たとえば、ハードウェアで実装された機能は、高速であり、処理集約性がより低く、より正確である。
【0069】
たとえば、いくつかの実施形態において、本明細書で開示されているように、そのような一次、二次、および/または三次処理を実行するための改善されたアルゴリズムが実現される。改善されたアルゴリズムは、上で述べたもののうちの1つなどの自動化シークエンサから得られたFASTQもしくはBCLファイル形式などの、シークエンシングプラットフォームから得られたDNA/RNA配列データの画像ファイルおよび/またはデジタル表現などに対してマッピング、アライメント、ソーティング、および/またはバリアントコーリングのうちの1つまたは複数の機能をより効率的に、および/またはより正確に実行するステップを対象とする。特定の実施形態において、改善されたアルゴリズムは、局所的再アライメント、重複マーキング、塩基クオリティスコアリキャリブレーション、バリアントコーリング、圧縮、および/または復元のうちの1つまたは複数の機能をより効率的に、および/またはより正確に実行するステップを対象とする。さらに、本明細書に以下でより詳しく説明されているように、いくつかの実施形態において、これらの遺伝子解析技術は、同じことをするのに様々な従来のソフトウェア実装形態と比べて低い処理集約性でおよび/または時間をあまりかけず、および/または正確さのパーセンテージを高めて実行されるソフトウェアおよび/またはハードウェアのうちの1つまたは複数によって実装され得る、改善されたアルゴリズムなどの1つまたは複数のアルゴリズムを採用し得る。様々な事例において、量子処理プラットフォーム上の実装に対する改善されたアルゴリズムが実現される。
【0070】
したがって、様々な態様において、本明細書に提示されているのは、たとえば、1つまたは複数の最適化されたアルゴリズムを介して、および/または1つまたは複数の最適化された集積および/または量子回路、たとえば1つまたは複数のハードウェア処理プラットフォーム上で、ゲノムデータなどの、遺伝子データを解析するための1つまたは複数の機能を実行するなど、バイオインフォマティクスプロトコルを実装するためのシステム、装置、および方法である。一事例において、バイオインフォマティクスプロトコルでゲノムデータを解析する1つまたは複数のステップを実行する1つまたは複数のアルゴリズムを、たとえばソフトウェアおよび/またはファームウェアで、および/または量子処理回路によって実装するためのシステムおよび方法が実現され、たとえば、これらのステップは、マッピング、アライメント、ソーティング、局所的再アライメント、重複マーキング、塩基クオリティスコアリキャリブレーション、バリアントコーリング、圧縮、および/または復元のうちの1つまたは複数の実行を含むものとしてよく、三次処理プラットフォームにおける1つまたは複数のステップをさらに含み得る。したがって、いくつかの事例では、これらの方法を実行するためのソフトウェア、ファームウェア、ハードウェア、および/または量子処理アルゴリズムを含む方法が、本明細書において提示されており、これらの方法は、マッピング、アライメント、ソーティング、再アライメント、重複マーキング、塩基クオリティスコアキャリブレーション、バリアントコーリング、圧縮、復元、および/または1つもしくは複数の三次処理プロトコルなどの1つまたは複数の遺伝子解析機能を実装するためのアルゴリズムなどの、アルゴリズムの実行を伴い、たとえばファームウェアを含む、このアルゴリズムは、それが実装される方式に従って最適化されている。
【0071】
特に、アルゴリズムがソフトウェアソリューションで実装されるべきである場合、アルゴリズムおよび/またはその付随するプロセスは、その媒体による実行に対してより高速に、および/またはより正確に実行されるように最適化されている。同様に、アルゴリズムの機能がハードウェアソリューションで、たとえば、ファームウェアとして実装されるべきである場合、ハードウェアは、その媒体による実行に対してより高速に、および/またはより正確に実行されるように最適化された方式でこれらの機能および/またはその付随するプロセスを実行するように設計されている。さらに、アルゴリズムが量子処理ソリューションで実装されるべきである場合、アルゴリズムおよび/またはその付随するプロセスは、その媒体による実行に対してより高速に、および/またはより正確に実行されるように最適化されている。これらの方法は、たとえば、反復マッピング、アライメント、ソーティング、バリアントコーリング、および/または三次処理手順などで採用され得る。別の事例では、本明細書において述べられているように、バイオインフォマティクスプロトコルでゲノムデータを解析するための1つまたは複数のステップを実行する1つまたは複数のアルゴリズムの機能を実装するためのシステムおよび方法が実現され、これらの機能は、1つまたは複数の汎用プロセッサおよび/またはスーパーコンピュータおよび/または量子コンピュータと結合されることも、結合されないこともあり得る、ハードウェアおよび/または量子アクセラレータ上に実装される。
【0072】
より具体的には、いくつかの事例において、対象の遺伝的組成に関係するデータに対して二次解析を実行するための、それらの方法を実装するための方法および/または機械が実現される。一事例において、実行されるべき解析は、対象ゲノムの参照ベースの再構築を伴い得る。たとえば、参照ベースのマッピングは、参照ゲノムの使用を伴い、単一または複数の個体のゲノムのシークエンシングから生成されてよいか、またはこれは、個体の遺伝物質、たとえば、DNA/RNAが比較され得るプロトタイプの標準的な参照ゲノムを作成するような仕方で組み合わされている様々な人々のDNA/RNAの融合であってよく、たとえば、これにより、個体の遺伝子配列を決定し、再構築し、および/または遺伝子構造と標準参照の構造との間の差異、たとえば、バリアントコーリングを決定する。
【0073】
特に、対象の配列決定されたDNA/RNAに対して二次解析を実行する理由は、対象のDNA/RNAが参照のDNA/RNAとどのように異なるかを決定し、たとえば、対象のヌクレオチド配列と参照のヌクレオチド配列との差異のうちの1つ、多数、またはすべてを決定することにある。たとえば、2つの無作為に選んだ人の遺伝子配列の差異は、1,000塩基対中おおよそ1であり、これは、30億を超える塩基対のゲノム全体を見たときに、1人につき最大3,000,000個の分岐塩基対のバリエーションになる。これらの差を決定することは、三次解析プロトコルなどにおいて有用であり、たとえば、予防または治療が対象のDNAまたはそれから生成されたタンパク質と相互作用することがどのように予想されるかなどに基づき、遺伝的異常などによる疾患状態の発生の潜在的可能性、および/または予防または治療方法の成功する可能性を予測する。様々な事例において、対象のゲノムのde novo、および参照ベースの両方の再構築を実行し、一方の結果を他方と突き合わせて確認し、望ましい場合には、バリアントコーリングプロトコルの精度を高めることは有用であり得る。
【0074】
したがって、一態様では、様々な実施形態において、対象のゲノムが再構築され、および/またはVCFが生成された後、そのようなデータは、次いで、そのデータの解釈のために三次処理に通され、たとえば、この人がどのような疾患を患い得るか、またはその潜在的可能性を有し得るかを識別することに関してデータが何を意味しているかを決定し、および/またはこの対象が疾患状態を改善し、および/または予防するためにどのような処置もしくはライフスタイルの変更を採用することを望み得るかを決定する。たとえば、対象の遺伝子配列および/またはそのバリアントコールファイルが解析され、それにより、疾患状態に対する存在または潜在的可能性および/または提案された治療もしくは予防レジメンの対象に対して有し得る効果を示す臨床的に関連する遺伝子マーカーを決定するものとしてよい。次いで、このデータは、1つまたは複数の治療もしくは予防レジメンを対象に提供し、疾患状態を処置し、および/または予防するなど、対象のクオリティオブライフをよりよくするために使用され得る。
【0075】
特に、個体の遺伝的バリエーションの1つまたは複数が決定された後、そのようなバリアントコールファイル情報は、医学的有用な情報を開発するために使用され、次いで、これは、たとえば、診断目的、たとえば、疾患または潜在性、したがって臨床的解釈(たとえば、疾患バリアントを表現するマーカーを探す)、対象が様々な治験に含まれるべきか除外されるべきかを診断する診断目的、および他のそのような目的のために、たとえば、様々な知られている統計解析モデルを使用して、健康関連データおよび/または医学的に有用な情報を決定することができる。より具体的には、様々な事例において、生成されたゲノミクスおよび/またはバイオインフォマティクス処理結果データは、マイクロアレイ解析プロトコル、ゲノム、たとえば、全ゲノム解析プロトコル、遺伝型判定解析プロトコル、エクソーム解析プロトコル、エピゲノム解析プロトコル、メタゲノム解析プロトコル、マイクロバイオーム解析プロトコル、ジョイント遺伝型判定を含む遺伝型判定解析プロトコル、構造バリアント、体細胞バリアント、およびGATKを含むバリアント解析プロトコル、さらにはRNAシークエンシングプロトコルおよび他の遺伝子解析プロトコルなどの、1つまたは複数のゲノミクスおよび/またはバイオインフォマティクス三次解析プロトコルの実行において使用され得る。
【0076】
遺伝的先天性異常によって引き起こされる疾患状態の数は有限であるので、三次処理では特定の種類のバリアント、たとえば、疾患状態の発症に関係することが知られているものは、1つまたは複数の遺伝子ベースの疾患マーカーが対象のバリアントコールファイルに含まれるかどうかを決定することなどによって問い合わされ得る。その結果、様々な事例において、本明細書で開示されている方法は、ゲノムマーカーのデータベースなどにある、知られている疾患配列バリアントと突き合わせて、VCFおよび/または生成された配列を解析し、たとえば、走査し、VCFおよび/または生成された配列内の遺伝子マーカーの存在を識別し、もし存在しているならば、遺伝的に誘発される疾患状態に対する存在もしくは潜在的可能性に関するコールを行うことを伴い得る。知られている遺伝的バリエーションが多数あり、またそのようなバリエーションによって引き起こされる疾患を患う個体が多いので、いくつかの実施形態において、本明細書において開示されている方法は、ゲノム全体および/またはたとえば1人または複数の個体からなどの、それに関連するバリアントコールファイルに対する配列決定データと疾患状態とをリンクする1つまたは複数のデータベースを生成するステップ、ならびに/あるいは生成されたデータベースを探索して特定の対象がそのような疾患状態を引き起こす傾向のある遺伝的組成を有するかどうかを決定するステップを伴い得る。そのような探索は、一方のゲノム全体を1つまたは複数の他方、またはゲノムの断片、たとえば、バリエーションのみを含む断片などとともに、参照ゲノムもしくはその断片のデータベースなどにおいて1つまたは複数の他のゲノムの1つまたは複数の断片と比較するステップを伴い得る。
【0077】
したがって、様々な事例において、本開示のパイプラインは、1つまたは複数のモジュールであって、モジュールは、遺伝子データ、たとえば配列決定遺伝子データに対して、画像処理または塩基コーリングおよび/または誤り訂正オペレーションおよび/またはマッピングおよび/またはアライメント、たとえばギャップもしくは無ギャップアライメント、および/またはソーティング機能などの、1つまたは複数の機能を実行するように構成される、1つまたは複数のモジュールを備え得る。そして、様々な事例において、パイプラインは、1つまたは複数のモジュールであって、モジュールは、遺伝子データに対して、局所的再アライメント、重複除去、塩基クオリティスコアリキャリブレーション、バリアントコーリング、たとえば、HMM、減少および/または圧縮、および/または復元のうちの1つまたは複数を実行するように構成される、1つまたは複数のモジュールを備え得る。それに加えて、パイプラインは、1つまたは複数のモジュールであって、モジュールは、マイクロアレイプロトコル、ゲノム、たとえば、全ゲノムプロトコル、遺伝型判定プロトコル、エクソームプロトコル、エピゲノムプロトコル、メタゲノムプロトコル、マイクロバイオームプロトコル、ジョイント遺伝型判定プロトコルを含む遺伝型判定プロトコル、構造バリアントプロトコル、体細胞バリアントプロトコル、およびGATKプロトコルを含むバリアント解析プロトコル、さらにはRNAシークエンシングプロトコルおよび他の遺伝子解析プロトコルなどの、三次解析プロトコルを実行するように構成される、1つまたは複数のモジュールを備え得る。
【0078】
これらのモジュールの多くは、クラウド上など、たとえば、リモートサーバおよび/または量子コンピューティングクラスタなどのサーババンク上で、たとえばソフトウェアまたはハードウェアを介してローカルもしくはリモートで、ソフトウェアによってまたはハードウェア上のいずれかで実行されてよい。それに加えて、パイプラインのこれらのモジュールおよび/またはステップの多くは任意選択のものであり、および/または任意の論理的順序で配置構成され、および/または完全に省かれてもよい。たとえば、本明細書において開示されているソフトウェアおよび/またはハードウェアは、画像処理および/または塩基コーリングまたは配列訂正アルゴリズムを含むことも、含まないこともあり得、たとえば、そのような機能が結果として統計的偏りを引き起こし得るという懸念があり得る。結果として、システムは、それぞれ望ましい精度および/または効率のレベルに応じて塩基コーリングおよび/または配列訂正機能を含むことも、含まないこともあり得る。そして上で示されているように、パイプライン機能のうちの1つまたは複数は、参照ベースのゲノム再構築などを通じて対象のゲノム配列の生成において使用されてよい。また、上で示されているように、いくつかの事例において、二次処理パイプラインからの出力は、ゲノムまたはその一部における一部またはバリアントの全部を示すバリアントコールファイル(VCF、gVCF)であってよい。
【0079】
特に、リードがどの染色体に属すかおよびその染色体の先頭からのオフセットを識別するステップを含み得る、参照ゲノムに関する位置をリードに割り当てることが行われた後、それらは、位置などにより、重複除去されおよび/またはソーティングされるものとしてよい。これは、下流解析で本明細書において説明されている様々なオーバーサンプリングプロトコルを利用することを可能にする。ゲノム内の所与の位置に重なるリードはすべて、ソーティングの後に互いに隣接して位置決めされるものとしてよく、それらはパイルアップされ、たとえば、パイルアップを形成し、それらの大半が参照値と合致するかどうかを決定するために容易に調べられ得る。上で示されているように、合致しない場合、バリアントにフラグが立てられるものとしてよい。
【0080】
したがって、マッピングに関して上で示されているように、シークエンサから得られた、画像ファイル、BCLファイル、および/またはFASTQファイルは、個体のゲノムの一部または全体を表現するヌクレオチド配列データの短い列からなる複数の、たとえば、数百万から10億またはそれ以上のリードから構成される。たとえば、本明細書において開示されている、二次解析パイプラインにおける第1のステップは、シークエンサなどのゲノムデータ生成装置などから、ゲノムおよび/またはバイオインフォマティクスデータを受信するステップである。典型的には、シークエンサ、たとえば、NextGen Sequencerによって作成されるデータは、BCLファイル形式であり、これは、いくつかの事例において、伝送の前または後のいずれかで、FASTQファイル形式に変換され、たとえば、本明細書で説明されている二次処理プラットフォームに送られるものとしてよい。特に、ヒトゲノムのシークエンシングを行うときに、対象のDNAおよび/またはRNAが、塩基毎に識別されなければならず、そのようなシークエンシングの結果がBCLファイルである。BCLファイルは、対象のゲノムの少なくとも一部または全体を構成する配列の集合体の各配列の各塩基に対して作られる塩基コールおよびクオリティスコアを含むバイナリファイルである。
【0081】
従来、シークエンサ生成BCLファイルは、FASTQファイルに変換され、その後、本明細書で開示されているような二次処理プラットフォームに伝送され、そこでさらに処理され、たとえば、それらのゲノミクスバリアントを決定し得る。FASTQファイルは、生物学的配列(たとえば、ヌクレオチド配列)およびその対応するクオリティスコアの両方を伝送し、記憶するためのテキストベースのファイル形式であり、配列文字、たとえば、A、C、G、T、および/またはUならびにクオリティスコアは両方とも、各々、簡単のため、単一のASCII文字で符号化されてよい。したがって、このシステムおよび他のシステム内で、これはさらに処理をすることを目的として使用されるFASTQファイルである。FASTQファイルをゲノミクス処理に使用することは有用であるが、生成されたBCLファイルをFASTQファイルに変換するのは、シークエンサ装置で実装されるときには、時間がかかり不効率である。したがって、一態様において、BCLファイルをFASTQファイルに直接変換する、および/またはそのようなデータを、本明細書で説明されているような、本発明のプラットフォームパイプラインに直接入力するためのデバイスおよび方法が、実現される。
【0082】
たとえば、様々な実施形態において、次世代シークエンサ、すなわち、シークエンサオンアチップ技術は、受け取った遺伝子データに対してシークエンシングオペレーションを実行するように構成され得る。たとえば、図1Aを見るとわかるように、遺伝子データ6aは、次世代シークエンサ内に挿入され、反復方式で配列決定されるように、シークエンシングプラットフォーム6に結合されるものとしてよく、それにより、各配列は1ステップずつヌクレオチドを次々に追加することによって成長する。特に、シークエンシングプラットフォーム6は、グリッド状に配置構成されプラットフォーム6上にタイル6bを形成する対象からの多数のテンプレートヌクレオチド配列6aを備えてよく、このテンプレート配列6aが配列決定される。プラットフォーム6は、シークエンシング反応を実行するように適合されているシークエンサの流動セル6cに追加されてよい。
【0083】
シークエンシング反応が生じると、各ステップにおいて、蛍光タグ6dを有するヌクレオチドが、流動セル6cのプラットフォーム6に追加される。混成化反応が生じた場合、蛍光が観察され、撮像され、次いで画像が処理され、適切な塩基コールが行われる。これは、テンプレート配列のすべて、たとえば、ゲノム全体が配列決定され、リードに変換されるまで塩基毎に繰り返され、それによって、システムのリードデータが作成される。したがって、配列決定された後、生成されたデータ、たとえば、リードは、シークエンシングプラットフォームから二次処理システムに転送される必要がある。たとえば、典型的には、この画像データは、その後システム内に転置され得るBCLおよび/またはFASTQファイルに変換される。
【0084】
しかしながら、様々な事例において、この変換および/または転送プロセスはより効率的に行われ得る。特に、本明細書に提示されているのは、二次処理システム内で高速処理され得るファイルへの促進BCL変換のための方法およびアーキテクチャである。より具体的には、特定の事例において、生のBCLもしくはFASTQファイルを伝送する代わりに、シークエンシングオペレーションの各タイルを表す作成された画像は、システム内に直接転送され、マッピングおよびアライメントなどの準備が行われ得る。たとえば、タイルは、適切に構成されているPCIeにわたって、ASIC、FPGA、またはQPUにストリーミングされてよく、リードデータはそこから直接抽出され、それらのリードはマッピングおよびアライメントおよび/または他の処理エンジン内に送られ得る。
【0085】
特に、FPGA/CPU/GPU/QPUへのシークエンサによって取得されたタイルからのデータの転送に関して、図1Aを見るとわかるように、シークエンシングプラットフォーム6は、3D立方体6cとして画像化されてよく、その中で成長する配列6aが生成される。本質的に、図1Bを見るとわかるように、シークエンシングプラットフォーム6は16レーンから構成され、前部に8レーン、後部に8レーンを備え、約96個のタイル6bを形成するように構成され得る。各タイル6b内に、配列決定されそれによってリードを形成する多数のテンプレート配列6aがあり、各リードは対象のゲノムの所与の領域に対するヌクレオチド配列を表し、各列は1つのファイルを表し、デジタル符号化されている通り、すべてのファイルについて1バイトを表し、ファイル毎に8ビットを有し、たとえば、2ビットがコールされた塩基を表し、残り6ビットはクオリティスコアを表す。
【0086】
より具体的には、Next Gen Sequencingに関して、シークエンシングは、シークエンシングのために自動化シークエンサに入れられる流動セル6cを形成するガラス板6上に典型的には実行される。図1Bを見るとわかるように、流動セル6cは8個の垂直列と8個の水平行(前後)から構成されるプラットフォーム6であり、これらが一緒になって16レーンを形成し、各レーンはゲノム全体のシークエンシングに十分なものである。配列決定されるべき対象のDNAおよび/またはRNA 6aは、タイル6bを形成するようにプラットフォーム6の列および行の流体的に絶縁されている交差の間の指定された位置内に関連付けられており、各タイルは配列決定されるべきテンプレート遺伝物質6aを含む。シークエンシングプラットフォーム6は、したがって、対象からの多数のテンプレートヌクレオチド配列を含み、この配列はプラットフォーム上にグリッド状のタイルとして配置構成される。(図1B参照)次いで、遺伝子データ6は、反復方式で配列決定され、各配列は、ヌクレオチドを次々に流動セル内に1ステップずつ導入することによって成長させられ、各反復成長ステップは、1つのシークエンシングサイクルを表す。
【0087】
示されているように、画像は各ステップの後にキャプチャされ、たとえば画像の成長する配列は、BCLファイルが生成される基礎を形成する。図1Cを見るとわかるように、シークエンシング手順からのリードはクラスタを形成するものとしてよく、これは理論的3D立方体6cを形成するクラスタである。したがって、この理論的3D立方体内で、配列決定される各成長するヌクレオチド鎖の各塩基は、x次元およびy次元を有する。この3D立方体6cからの画像データ、すなわち、タイル6bは抽出されて、2次元マップ内にコンパイルされるものとしてよく、そこから行列が、図1Dに示されているように、形成され得る。行列は、水平軸を表す、シークエンシングサイクルと、垂直軸を表す、リード識別とから形成される。したがって、図1Cを参照してわかるように、配列決定されたリードは流動セル6c内にクラスタを形成し、それらのクラスタは垂直および水平軸によって、サイクル毎に定義されるものとしてよく、各リードに対する各サイクルからの塩基毎のデータは、ストリーミングおよび/またはパイプライン方式などで、図1Dの行列内に挿入されてよい。
【0088】
特に、各サイクルは、1つのヌクレオチドの追加によって流動セル内の各リードの潜在的成長を表し、これは1つまたは複数のヒトゲノムのシークエンシングを行ったときに、1レーン当たり約10億以上のリードの成長を表し得る。たとえば、ヌクレオチド塩基の追加による、各リードの成長は、成長ステップの間の流動セル6cの、タイル6bの、画像の反復キャプチャによって識別される。これらの画像から、塩基コールが行われ、クオリティスコアが決定され、図1Dの仮想行列が形成される。したがって、行列に入れられる塩基コールとクオリティスコアの両方があり、各サイクルからの各タイルは、別個のファイルを表す。シークエンシングが集積回路上で実行される場合、感知された電子データは画像データの代わりに使用され得ることに留意されたい
【0089】
たとえば、図1Dを見るとわかるように、行列それ自体は、画像がキャプチャされ処理され、塩基がコールされ、クオリティスコアが各リードについてサイクル毎に決定されるとともに反復的に成長する。これは、流動セルの各タイルに対する、リード内の各塩基について繰り返される。たとえば、リードのクラスタ1Cは番号が振られ、垂直軸として行列内に入れられ得る。同様に、サイクル番号が水平軸として入力されてよく、次いで、塩基コールおよびクオリティスコアが入力され、行列を列毎、行毎に埋めるものとしてよい。したがって、各リードは、多数の塩基、たとえば、シークエンサに応じてリード毎に約100または150から最大1000個以上の塩基によって表され、タイル毎に最大1000万以上のリードがあり得る。したがって、各々1000万のリードを有する約100個のタイルがある場合、行列は約10億のリードを含み、これは編成され、二次処理装置にストリーミングされる必要がある。
【0090】
したがって、そのような編成は、データを高速に効率よく処理する上で基本的である。したがって、一態様において、本明細書に提示されるのは、データが本明細書で開示されているシステムのパイプライン内により直接的に効率的にストリーミングされ得るような仕方で仮想シークエンシング行列によって表されるデータを転置するための方法である。たとえば、図1Cの星形クラスタによって表されるような、シークエンシングデータの生成は、大幅に未編成状態にあり、これはデータ処理の観点からは問題である。特に、データがシークエンシングオペレーションによって生成されるときに、これはサイクル毎に1ファイルとして編成され、これはシークエンシングオペレーションの終わりまでに、何百万ものファイルが生成されることを意味し、ファイルは列内のデータによって表され、これは図1Eにおいて実線で描かれている。しかしながら、二次および/または三次処理を目的として、本明細書において開示されているように、ファイルデータはリードデータに再編成される必要があり、これは図1Eの破線で描かれている。
【0091】
より具体的には、シークエンサによって生成されるデータを二次処理データにより効率的にストリーミングするために、仮想行列によって表されるデータは、ファイルデータをサイクル毎にタイルの列毎の基準からリードの各々の塩基を識別する行毎の基準に再編成することなどによって、転置されるべきである。特に、行列を形成する生成済みファイルのデータ構造は、シークエンサによって作成されるときに、サイクル毎に、列毎の基準で編成される。本明細書で開示されているプロセスによって、このデータは、リード毎に、行毎の基準で、仮想行列内に見える通りに表されるように、たとえば実質的に同時に、転置されてよく、各行は個別のリードを表し、各リードは塩基コールおよびクオリティスコアの連番によって表され、それによって、各リードに対する配列およびその信頼度の両方を識別する。したがって、本明細書において説明されているような転置オペレーションにおいて、メモリ内のデータは、たとえば、仮想行列内で、入力データ順序を表す、列毎の基準から出力データ順序を表す、行毎の基準に再編成され、それによって、データ順序を垂直編成から水平編成に転置する。さらに、プロセスはソフトウェアで効率的に実装され得るが、これは、ハードウェアで、および/または量子プロセッサによって実装されることによってなおいっそう効率的にされ、高速化され得る。
【0092】
たとえば、様々な事例において、転置プロセスは、ハードウェアで実装されることによって加速され得る。たとえば、一実装形態において、第1のステップで、たとえばシークエンサのホストソフトウェアは、入力データをたとえば入力順序で列毎の基準で、FPGAに関連付けられるメモリ内に書き込むものとしてよい。特に、データが生成され、関連付けられているメモリ内に記憶されるときに、データはファイルに、サイクル毎に編成されてよく、そのデータは別の個別のファイルとして保存される。このデータは、図1Aの3D立方体によって表され得る。次いで、この生成された列編成データは、たとえば直ちに(in flight)ハードウェアによりキューに入れられ、および/またはストリーミングされ、専用処理エンジンは列編成データをキューに入れ、そのデータを列毎のサイクル順序構成から行毎のリード順序構成に、3Dタイルデータを2D行列に変換することなど、本明細書において上で説明される仕方で転置し、それによって、列データは行データに、たとえば、リード毎の基準に再編成され得る。次いで、この転置データは、より戦略的な順序でメモリ内に記憶され得る。
【0093】
たとえば、ホストソフトウェアは、入力データを列毎の入力順序などで、チップ、たとえばFPGAに関連付けられているメモリ内に書き込むように構成されてよく、同様に、ハードウェアは、図1Fに述べられるような、戦略的な仕方でメモリ内に読み込まれるような仕方でデータをキューに入れるように構成されてよい。特に、ハードウェアは、サイクルファイルが列から1塩基を行に編成されているレジスタ内に書き込むことなどによって、個別のリードデータに分散され再編成され得るレジスタ8aのアレイを備え得る。より具体的には、図1Gを見るとわかるように、転置処理エンジン8を備える、ハードウェアデバイス1は、転置されるべきデータをキューに入れるものとしてよいDRAMポート8aを備えるものとしてよく、ポートは、複数のレジスタおよび/または外部メモリ8cに関連付けられているメモリインターフェース8bに動作可能に結合され、サイクル毎に増大する量のトランザクションを取り扱うように構成され、キューに入れられているデータは、バーストで伝送される。
【0094】
特に、この転置は、一度に1つのデータセグメントで行われるものとしてよく、たとえば、メモリアクセスはDDR伝送速度を最大限活かすような仕方でキューに入れられる。たとえば、DRAMに関しては、DDRの最小バースト長は、たとえば、64バイトであるものとしてよい。したがって、ホストメモリに記憶される列配置構成データは、メモリアクセス毎に、たとえば64バイト分のデータが対応する列が取得されるような仕方でアクセスされ得る。したがって、メモリを1回アクセスすることで、たとえば対応する「64」サイクルまたはファイルを表す、タイルの一部は、列毎の基準でアクセスされ得る。
【0095】
しかしながら、図1Fを見るとわかるように、ホストメモリ内のデータは列データとしてアクセスされるが、ハードウェアに伝送されるときに、これは関連付けられているより小さいメモリ、たとえば、レジスタに異なる順序でアップロードされてよく、それによって、データは、DDRの最小バーストレートなどに従って行毎のリードデータのバイト、たとえば、64バイトに変換され、それにより、アクセス毎に対応する「64」メモリユニットまたはブロックを生成し得る。これは、図1Dの仮想行列によって例示され、そこでは、多数のリード、たとえば、64個のリードがブロック単位でアクセスされ、図1Eによって表されているように、セグメント単位でメモリ内に読み込まれ、たとえば、各レジスタ、またはフリップフロップは、特定のリード、たとえば、64サイクル×64リード×1リード当たり8ビット=32Kフリップフロップを占める。特に、これは、ハードウェアで様々な異なる方法により達成されるものとしてよく、たとえば、入力配線は列順序とマッチするように編成され、出力配線は行順序とマッチするように編成される。したがって、この構成では、ハードウェアは、サイクル毎に「64」個の異なるアドレスの読出しおよび/または書込みの両方を行うように適合され得る。
【0096】
より具体的には、ハードウェアは、リードの各塩基が単一のレジスタ(または行内の複数のレジスタ)に向けられ書き込まれ、各ブロックが完了したときに、新たに順序付けられた行データが出力、たとえば、FASTQデータとして行毎の編成でメモリに伝送され得るようにレジスタのアレイに関連付けられ得る。次いで、FASTQデータは、本明細書で説明されているように、マッピング、アライメント、および/またはバリアントコーリングエンジンなどによって、さらなる処理のために二次処理システムの1つまたは複数のさらなる処理エンジンによってアクセスされ得る。本明細書で説明されているように、転置は、小ブロック単位で実行されるが、システムは、場合によっては、より大きいブロックの処理にも適用されてよいことに留意されたい。
【0097】
示されているように、BCLファイルがFASTQファイルに、上で説明されているように変換され、および/またはBCLもしくはFASTQファイルが二次処理プラットフォームによって他の何らかの形で受け取られた後、マッピングオペレーションが受け取られたデータに対して実行され得る。マッピングは、一般に、マッチがある参照ゲノム内のすべての配置へのリードをプロットするステップを伴う。たとえば、リードのサイズに応じて、リードが参照ゲノム内の対応する配列と実質的にマッチする1つまたは複数の配置があり得る。したがって、本明細書で開示されているマッピングおよび/または他の機能は、1つまたは複数のリードが参照ゲノム内でマッチし得る可能なすべての配置のうちどこが実際に、マッピングされる真の配置であるかを決定するように構成され得る。
【0098】
たとえば、様々な事例において、参照ゲノムのインデックスが生成されるか、または他の何らかの形で提供されてよく、したがって、それらのリードまたはリードの一部は、たとえば、インデックスへの参照で、ルックアップテーブル(LUT)内で検索され、それによって参照内の配置の指示を取り出し、それらのリードを参照にマッピングし得る。参照のそのようなインデックスは、様々な形態で構築され、様々な仕方で問い合わせされ得る。いくつかの方法において、インデックスは、プレフィックスおよび/またはサフィックスツリーを含み得る。特定の方法において、インデックスは、参照のBurrows/Wheeler変換から導出され得る。したがって、代替的に、またはプレフィックスもしくはサフィックスツリーを採用することに加えて、Burrows/Wheeler変換がデータに対して実行され得る。たとえば、Burrows/Wheeler変換は、プレフィックスおよび/またはサフィックスツリーに抽象的に同等であるツリー状データ構造をコンパクトな形式で、たとえば、参照ゲノムを記憶するように割り振られている空間に記憶するために使用され得る。様々な事例において、記憶されているデータは、ツリー状構造ではなく、むしろ、参照配列データは、かなり特有の方法で変換するように異なる順序でスクランブルされているものとしてよい線形リストであり、それにより、付随するアルゴリズムはその参照が「ツリー」を効果的に辿るようにサンプルリードへの参照で探索されることを可能にする。
【0099】
それに加えて、様々な事例において、インデックスは、1つまたは複数のハッシュテーブルを含むものとしてよく、本明細書で開示されている方法は、リードを参照、たとえば、参照のインデックスにマッピングしようとしてリードの1つまたは複数の部分上で実行され得るハッシュ関数を含み得る。たとえば、代替的に、または一方が他方に対してどこにマッピングされるかを見つけるために、一方または両方のプレフィックス/サフィックスツリーおよび/または参照ゲノムおよび対象配列データ上のBurrows/Wheeler変換を利用することに加えて、別のそのような方法は、ハッシュテーブルインデックスの作成および/またはハッシュ関数の実行を伴う。ハッシュテーブルインデックスは、その後リードの1つまたは複数の部分と比較されて一方が他方とどこでマッチし得るかを決定し得る参照ゲノムの配列から構築される大きい参照構造であってよい。同様に、ハッシュテーブルインデックスは、その後参照ゲノムの1つまたは複数の配列と比較され、それによって一方が他方とどこでマッチし得るかを決定するために使用され得るリードの一部から構築されてよい。
【0100】
ハッシュテーブルの実装形態は、パターンマッチを実行するための高速な方法である。各検索は、実行するのにほぼ一定の時間量を要する。そのような方法は、マッチを見つけるためにクエリ毎に多数のプローブを必要とし得る(数は固有のパターンを見つけるためにビットがいくつ必要かに応じて異なり得る)Burrows-Wheeler法、またはNをテーブル内のシードパターンの数であるとしてlog
2(N)個のプローブを取る二分探索法と対比され得る。さらに、ハッシュ関数は参照ゲノムを所与の長さ、たとえば、28塩基対のシードのセグメントに分けることができ、次いで、シードを56ビットのデジタル、たとえば、バイナリ表現に変換することができるとしても、56ビットすべてが全体的に全く同時に、または同じ方法でアクセスされる必要はない、たとえば、ハッシュ関数は、各シードに対するアドレスが56ビット未満、たとえば約18から約44もしくは46ビット、たとえば約20から約40ビット、たとえば、約24から約36ビットの数によって指定されるような仕方で実装されてよく、約28から約32もしくは約30ビットを含めることは、ハッシュテーブルにアクセスするために初期キーまたはアドレスとして使用され得る。たとえば、いくつかの事例において、約26から約29ビットがハッシュテーブルに対する一次アクセスキーとして使用され、残りの約27から約30ビットが残され、第1の鍵を二重チェックするための手段として使用されてよく、たとえば、第1のキーおよび第2のキーの両方がハッシュテーブル内の同じセルに到来した場合に、前記配置がそれらが属している場所であることは比較的明らかである。
【0101】
たとえば、デジタル表現されたシードの第1の部分、たとえば、約26から約32、たとえば約29ビットは、一次アクセスキーを形成し、ハッシュされるものとしてよく、第1のステップで検索され得る。そして、第2のステップにおいて、残りの約27から約30ビット、たとえば、二次アクセスキーが、第1のパスを確認するための手段として、ハッシュチェーンなど、ハッシュテーブルに挿入され得る。したがって、どのシードについても、元のアドレスビットは第1のステップでハッシュされるものとしてよく、二次アドレスビットは、第2のステップ、確認ステップで使用され得る。そのような事例において、シードの第1の部分は、一次レコード配置に挿入されるものとしてよく、第2の部分は、テーブル内の二次レコードチェーン配置に収められ得る。そして、上で示されているように、様々な事例において、これら2つの異なるレコード配置は、チェーンフォーマットレコード(chain format record)などによって位置を隔てられ得る。
【0102】
特定の事例において、参照をリード、またはその一部と比較するために総当たりの線形走査が使用されてよい。しかしながら、総当たりの線形探索を使用してシードがマッチする配置に対する参照ゲノムを走査する場合、30億を超える配置がチェックされなければならないこともある。その探索は、本明細書で開示されている方法に従って、ソフトウェアまたはハードウェアで実行され得る。それにもかかわらず、ハッシングアプローチを使用することによって、本明細書で述べられているように、各シード検索は、おおよそ一定の時間量内に行われ得る。しばしば、配置は、少ない回数の、たとえば、単一のアクセスで確認され得る。しかしながら、複数のシードがテーブル内の同じ配置にマッピングされる場合、たとえば、十分に固有のものでない場合、現在検索されているシードを見つけるためにさらに何回かアクセスが行われ得る。したがって、参照ゲノムに関して、所与の100のヌクレオチド長のリードが合う30Mまたはそれ以上の可能な配置があり得るとしても、ハッシュテーブルおよびハッシュ関数は、そのリードが参照ゲノム内のどこに現れようとしているかを素早く決定することができる。したがって、ハッシュテーブルインデックスを使用することによって、リードがどこにマッピングしアライメントするかを決定するために、たとえば総当たりで参照ゲノム全体を探索する必要はない。
【0103】
上記に照らして、これらの目的のために好適な任意のハッシュ関数が使用されてよいが、様々な事例において、各シードに対するテーブルアドレスを決定するために使用されるハッシュ関数は、上で示されているように、2kビットプリミティブ多項式に基づき得る巡回冗長検査(CRC)であってよい。代替的に、2kビットのうちのいくつかを単純に落とすなどによって自明なハッシュ関数マッパが使用され得る。しかしながら、様々な事例において、CRCは同時にテーブルの混雑状態を回避しながら類似のシードをよりよく分離し得るより強いハッシュ関数であってよい。これは、本明細書で説明されている専用ハードウェアなどによってCRCを計算するときに速度ペナルティがない場合に特に有益であり得る。そのような事例において、各シードについて初期値を入力されたハッシュレコードは、シードが生じた参照位置と、ハッシングの前に逆相補にされたかどうかを示すフラグとを含み得る。
【0104】
マッピング機能の実行で返される出力は、1つまたは複数の、たとえば、各々のリードが1つまたは複数の参照ゲノムのどこにマッピングされるかに関する可能性のリストであってよい。たとえば、各マッピングされるリードに対する出力は、リードが参照ゲノム内のマッチする配列にマッピングされ得る可能な配置のリストであってよい。様々な実施形態において、少なくとも個片、たとえば、リードのすべてではないとしても、リードのシードに対する参照への完全マッチが求められ得る。したがって、様々な事例において、すべてのリードのすべての部分が参照ゲノムのすべての部分と完全にマッチすることは必要でない。
【0105】
本明細書で説明されているように、これらのオペレーションはすべて、ソフトウェアを介して実行され得るか、またはたとえば、回路基板の一部として、チップなどの集積回路などにハード配線され得る。たとえば、これらのアルゴリズムのうちの1つまたは複数の機能は、チップ上に、たとえばFPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)チップなどに組み込まれてよく、そのようなハードウェアにそれらを実装するのでより効率的に実行するように最適化され得る。それに加えて、これらのマッピング機能のうちの1つまたは複数、たとえば、2つまたは3つすべては、個体の実際のゲノム配列全体、またはその一部を決定するためにプロセスにおいて使用されるシステムの一部、たとえば、パイプラインを形成し得る、マッピングモジュールなどのモジュールを形成し得る。
【0106】
ハッシュモジュールをハードウェアに実装する利点は、プロセスが加速され、したがって実行をかなり速くし得る点である。たとえば、ソフトウェアがこれらの様々な機能のうちの1つまたは複数を実行するための様々な命令を含み得る場合、そのような命令の実装は多くの場合に、実行する前などに、データおよび命令が記憶され、および/またはフェッチされ、および/または読み出され、および/または解釈されることを必要とする。しかしながら、上に示されているように、また本明細書においてより詳細に説明されているように、一連の命令のうちの1つまたは複数をフェッチし、解釈し、および/または実行しなくても、これらの機能を実行するようにチップをハード配線することができる。むしろ、チップは、そのような機能を直接実行するように配線されてよい。したがって、様々な態様において、本開示は、上述のマッピング、たとえば、ハッシング、モジュールの一部または全部がFPGAまたはASICなどのチップ上にハード配線された集積回路などの1つまたは複数のネットワーク回路によって実装され得るように構成され得るカスタムハード配線された機械を対象とする。
【0107】
たとえば、様々な事例において、ハッシュテーブルインデックスが構築されてよく、ハッシュ関数はチップ上で実行されてよく、他の事例では、ハッシュテーブルインデックスは、ホストCPUによって実行されるソフトウェアなどを介して、チップから生成されてよいが、生成されると、これはハードウェア上にロードされるか、または他の何らかの形でアクセス可能にされ、たとえばハッシュモジュールを実行する際に、チップによって使用される。特に、様々な事例において、FPGAなどのチップは、QPIインターコネクトなどの低遅延インターコネクトなどによって、ホストCPUに密結合されるように構成され得る。より具体的には、チップおよびCPUは、以下でより詳しく説明されるように、キャッシュコヒーレント構成において、1つまたは複数のメモリリソース、たとえば、DRAMを共有するような仕方で一緒に密結合されるように構成されてよい。そのような事例において、ホストメモリは、ホストメモリ内に記憶され得るが、ハッシュまたは他のマッピング機能の実行の際に使用するなどのためにFPGAに容易にアクセス可能にされ得る、参照インデックス、たとえば、ハッシュテーブルを構築し、および/または含むものとしてよい。特定の実施形態において、CPUおよびFPGAの一方または両方は、一方のキャッシュ内に記憶されているデータが他方によって実質的にミラー化されるようなコヒーレント構成となるように一緒に結合され得る1つまたは複数のキャッシュもしくはレジスタを備え得る。
【0108】
したがって、上記に照らして、実行時に、たとえば、参照ゲノムのインデックスを含む、1つまたは複数の以前に構築されたハッシュテーブル、または構築されたもしくは構築されるべきハッシュテーブルは、オンボードメモリ上にロードされ得るか、または少なくとも、本明細書において以下でより詳しく説明されているように、ホストアプリケーションによってアクセス可能にされ得る。そのような事例において、たとえば、FASTQファイル形式で記憶されている、リードは、ホストアプリケーションによってオンボード処理エンジン、たとえば、メモリもしくはキャッシュもしくはそれらに関連付けられている他のレジスタに、たとえばマッピングおよび/またはアライメントおよび/またはソーティングエンジンによる使用のために送られてよく、たとえば、それらの結果はバリアントコール機能に送られ、バリアントコール機能を実行するために使用され得る。それに関して、上で示されているように、様々な事例において、重なり合うシードのパイルアップは、たとえば、シード生成機能を介して生成され、配列決定されたリード、またはリード対から抽出されてよく、生成された後、シードはインデックスなどと突き合わせてハッシュされ、参照内の候補リードマッピング位置を決定するためにハッシュテーブル内で検索され得る。
【0109】
より具体的には、様々な事例において、マッピングモジュールが実現されてよく、たとえば、マッピングモジュールはハード配線された構成などにおいて1つまたは複数のマッピング機能を実行するように構成される。特に、ハード配線されたマッピングモジュールは、CPU上で実行される1つまたは複数のアルゴリズムによって典型的には実行される1つまたは複数の機能、たとえば、プレフィックスおよび/またはサフィックスツリーを生成するソフトウェアベースのアルゴリズム、Burrows-Wheeler Transformで典型的には実装される機能を実行するように構成されてよく、あるいは/ならびにハッシュ関数、たとえば、参照ゲノム配列などの、ハッシュテーブルインデックス作成を使用するか、または他の何らかの形でそれに頼るハッシュ関数を実行する。そのような事例において、ハッシュ関数は、実行されるメモリアクセスの回数、たとえば、大メモリランダムアクセスの回数を最小化し、それによってチップアーキテクチャ内の空間などによって基本的に制約され得る、オンボードまたは他の何らかの形で関連付けられているメモリ帯域幅の利用を最大化するように構成され得る最適化されたマッピング戦略などの、戦略を実装するように構造化され得る。
【0110】
さらに、いくつかの事例において、システムをより効率的にするために、ホストCPU/GPU/QPUは、関連付けられているハードウェア、たとえば、FPGAに、低遅延インターフェース、たとえばクイックパスインターコネクト(「QPI」)などによって密結合され、それにより、集積回路の処理エンジンがホストメモリにすぐにアクセスできるようにし得る。特定の事例において、ホストCPUと結合されているチップおよびそれぞれの関連付けられているメモリ、たとえば、1つまたは複数のDRAMとの間の相互作用は、キャッシュコヒーレントであるように構成され得る。したがって、様々な実施形態において、集積回路が実現されるものとしてよく、その集積回路は、たとえば、1つまたは複数の物理的電気的インターコネクトによって相互接続され得る、配線構成をとり得る1つまたは複数のデジタル論理回路を備えるような仕方で事前構成、たとえば、事前配線されており、様々な実施形態において、ハード配線されたデジタル論理回路は、マッピングモジュールなどの、1つまたは複数のモジュールを形成するように1つまたは複数の処理エンジン内に配置構成され得る。
【0111】
したがって、様々な事例において、マッピングモジュールは、第1の事前構成された配線された、たとえば、ハード配線された構成などで実現されてよく、マッピングモジュールは、様々なマッピング機能を実行するように構成される。たとえば、マッピングモジュールは、対象の配列決定された遺伝子サンプルから導出された、複数のリードのうちの1つのリードにおけるヌクレオチドの配列の少なくとも一部、および/または遺伝子参照配列、および/または1つもしくは複数の遺伝子参照配列のインデックスに、メモリまたはそれに関連付けられているキャッシュから、たとえば、プロセスインターコネクト、たとえば、クイックパスインターコネクト、および同様のものなどのメモリインターフェースを介してアクセスするように構成され得る。マッピングモジュールは、インデックスに基づくなどして、リードを1つまたは複数の遺伝子参照配列の1つまたは複数のセグメントにマッピングするようにさらに構成され得る。たとえば、様々な特定の実施形態において、本明細書において提示されているマッピングアルゴリズムおよび/またはモジュールは、ハッシュテーブルを構築するか、または他の何らかの形で構築するために使用されてよく、それによって、対象からの配列決定遺伝物質のリード、またはその一部は、参照ゲノムの1つまたは複数のセグメントと比較され、マッピングされたリードを作成するものとしてよい。そのような事例において、マッピングが実行された後、アライメントが実行され得る。
【0112】
たとえば、参照ゲノムと突き合わせてシードに対して可能なすべてのマッチがどこにあるかが決定された後、所与のリードがマッチし得る可能なすべての配置からどれが実際にアライメントする正しい位置であるかが決定されなければならない。したがって、マッピングの後、参照ゲノム内に1つまたは複数のリードがマッチするように見える複数の位置があり得る。結果として、完全に同じことを示すように見える複数のシードがあり得る、たとえば、これらはリード内のシードの位置を考慮した場合に、参照上の完全に同じ位置とマッチし得る。したがって、実際のアライメントは、各所与のリードについて決定されなければならない。この決定は、いくつかの異なる方法で行われ得る。
【0113】
一事例において、すべてのリードは、マッピング、たとえばハッシュ検索、プロセスの間に、位置情報を返したリードからのすべてのシードによって示される位置に基づき参照ゲノムに関して正しいアライメントを決定するために評価され得る。しかしながら、様々な事例において、アライメントを実行する前に、シードチェーンフィルタリング機能がシードのうちの1つまたは複数に対して実行され得る。たとえば、いくつかの事例において、参照ゲノムと突き合わせた場合と同じ一般的な場所にマッピングするように見える所与のリードに関連付けられているシードは、同じ一般的な領域を参照する単一のチェーンに集められ得る。1つのリードに関連付けられているシードのすべてが、各シードがただ1つのチェーンのメンバーであるように1つまたは複数のシードチェーンにグループ化され得る。これは、その後、参照ゲノムにおける各示された位置にリードをアライメントさせるようなチェーンである。
【0114】
特に、様々な事例において、参照における同じ一般的な配置にすべて属することを示す根拠となる同じ証拠を有するシードのすべてが一緒にまとめられ、1つまたは複数のチェーンを形成し得る。したがって、一緒のグループになるか、またはたとえば、特定のバンド内の、参照ゲノムにおいて互いに近づこうとするように少なくとも見えるシードは、シードのチェーン内にグループ化され、このバンドの外側にあるものはシードの異なるチェーンに入れられる。これらの様々なシードが1つまたは複数の様々なシードチェーン内に集められた後、チェーンのうちのどれが実際にアライメントされるべき正しいチェーンを表すかが決定され得る。これは、少なくとも一部において、正しいものであることが非常にありそうもない弱いシードチェーンを排除するように設計されている発見的手法であるフィルタリングアルゴリズムを使用することによって行われ得る。
【0115】
これらのマッピング、フィルタリング、および/または編集機能のうちの1つまたは複数を実行した結果は、各リードについて、リードが参照ゲノムとマッチアップし得る場所への可能なすべての配置のリストを含むリードのリストである。したがって、マッピング機能は、シークエンサから得られた画像ファイル、BCLファイル、および/またはFASTQファイルのリードが参照ゲノムのどこにマッピングするか、たとえば、ゲノム全体において様々なリードがどこにマッピングするかを素早く決定するように実行され得る。しながら、リードまたは遺伝的バリエーションのどれかに誤りがある場合に、参照への完全マッチを取得し得ず、および/または1つもしくは複数のリードがマッチするように見えるいくつかの場所があり得る。したがって、様々なリードが実際に全体としてゲノムに関してどこにアライメントするかが決定されなければならない。
【0116】
したがって、マッピングおよび/またはフィルタリングおよび/または編集の後に、多数のリードに対する配置位置が決定されており、個別のリードのいくつかについて、多数の配置位置が決定されており、次に、可能なすべての配置のうちのどれが実際に、様々なリードがアライメントする真のまたは最もありそうな配置であるかが決定される必要がある。そのようなアライメントは、マッピングされたリードを参照ゲノムとマッチし、アライメント機能をそれに対して実行する動的プログラミングアルゴリズムなどの、1つまたは複数のアルゴリズムによって実行され得る。例示的なアライメント機能は、リードの1つまたは複数、たとえばすべてを、たとえば、テーブル、たとえば、仮想アレイまたは行列などにおいて、それらを互いに対してグラフ関係に入れることなどによって、参照と比較し、参照ゲノムまたはマッピングされたリードのうちの1つの配列は、一方の次元もしくは軸、たとえば、水平軸上に置かれ、他の配列は、垂直軸などの、対向する次元もしくは軸上に置かれる。次いで、概念的なスコアリング波面がアレイに受け渡され、それにより、リードと参照ゲノムとのアライメントを、行列内の各セルに対するアライメントスコアを計算することなどによって決定する。
【0117】
スコアリング波面は、Smith-Waterman、および/またはNeedleman-Wunsch、および/または関係するアルゴリズムなどの、アライメントアルゴリズムにおいて適用可能な動的プログラミングのルールに従って独立しておよび/または同時にスコアリングされ得る、行列のセル、またはそれらのセルの一部の1つまたは複数、たとえば、すべてを表す。アライメントスコアは、順次、または他の順序で、上行内のすべてのスコアを左から右に、その後、次の行内のすべてのスコアを左から右に、などと計算することなどによって計算され得る。このような仕方で、対角線上をスイープする対角線波面は、一連の波面ステップにおいて同時にまたは並行して計算されるスコアのバッチの最適な配列を表す。
【0118】
たとえば、一実施形態において、リードがマッピングされたセグメントを含む参照ゲノムのウィンドウは、水平軸上に置かれてよく、リードは、垂直軸上に位置決めされ得る。このような仕方で、アレイまたは行列が生成され、たとえば、仮想行列が生成され、それによって、リード内の各位置におけるヌクレオチドは、参照ウィンドウ内の各位置におけるヌクレオチドと比較され得る。波面がアレイ上を通り過ぎるときに、リードを参照ウィンドウにアライメントするすべての潜在的方法が、1つの配列への変更が、リードの1つもしくは複数のヌクレオチドを他のヌクレオチドに変更するか、または1つもしくは複数の新しいヌクレオチドを1つの配列に挿入するか、または1つもしくは複数のヌクレオチドを1つの配列から削除することなどによって、リードを参照配列にマッチさせるために必要になる場合を含めて、考慮される。
【0119】
完全なアライメントを達成するために行われる必要が生じるであろう変更の程度を表す、アライメントスコアが生成され、このスコアおよび/または他の関連付けられているデータは、アレイの所与のセル内に記憶され得る。アレイの各セルは、リード軸上の位置におけるヌクレオチドが参照軸上の位置におけるヌクレオチドにアライメントする可能性に対応し、各セルについて生成されるスコアは、リードおよび参照ウィンドウ内のセルの位置で終了する部分的アライメントを表す。セル内の生成される最高のスコアは、リードと参照ウィンドウとの最良の全体的アライメントを表す。様々な事例において、アライメントは大域的であってよく、リード全体は、Needleman-Wunschまたは類似のアルゴリズムなどを使用して、参照ウィンドウの何らかの部分にアライメントされなければならないか、または他の事例において、アライメントは局所的であってよく、リードの一部のみが参照ウィンドウの一部に、Smith-Watermanまたは類似のアルゴリズムなどを使用することによって、アライメントされ得る。
【0120】
したがって、様々な事例において、アライメント機能が、マッピングモジュールから得られたデータなどに対して実行され得る。したがって、様々な事例において、アライメント機能は、個体の実際のゲノム配列全体、またはその一部を決定するためにプロセスにおいて、マッピングモジュールなどとともに加えて、使用されるシステムの一部、たとえば、パイプラインを形成し得る、アライメントモジュールなどのモジュールを形成し得る。たとえば、マッピングモジュールなどからの、マッピング機能の実行から返された出力、たとえば、リードのうちの1つもしくは複数またはすべてが1つまたは複数の参照ゲノム内の1つまたは複数の位置にどこにマッピングするかに関する可能性のリストは、対象の配列決定DNAの実際の配列アライメントを決定するためにアライメント機能によって使用され得る。
【0121】
そのようなアライメント機能は、時々、上で説明されているように、しばしば、様々な異なる理由から、配列決定されたリードが必ずしも参照ゲノムと完全にはマッチしないことから有用であり得る。たとえば、リードのうちの1つまたは複数にSNP(一塩基多型)があり得る、たとえば、単一の位置における一方のヌクレオチドの他方のヌクレオチドに対する置換があり得、リード配列の1つまたは複数に沿って1つまたは複数の塩基の「インデル」、すなわち、挿入または欠失があり得、挿入または欠失が参照ゲノム内に存在しせず、ならびに/あるいはこれらの明白なバリエーションのうちの1つまたは複数を引き起こすシークエンシングの誤り(たとえば、サンプル調製および/またはシークエンサリードおよび/またはシークエンサ出力などにおける誤り)があり得る。したがって、SNPまたはインデルなどによって、リードが参照から異なるときに、これがあり得るのは、参照がサンプリングされた真のDNA配列と異なるか、またはリードがサンプリングされた真のDNA配列と異なるからである。問題は、すべての可能性において2つの配列が多数の異なる仕方で相互に変わろうとするという事実が与えられた場合にリードを参照ゲノムに正しくアライメントする方法を見つけ出すことである。
【0122】
様々な事例において、プレフィックス/サフィックスツリー、Burrows/Wheeler変換、またはハッシュテーブルおよび/またはハッシュ関数などのマッピング機能などからのアライメント機能への入力は、1つまたは複数のリードが1つまたは複数の参照配列の1つまたは複数の位置にどこでマッチし得るかに関する可能性のリストであってよい。たとえば、所与のリードについて、これはゲノム内で所与のリードがマッピングされる1つの配置または16、もしくは32、もしくは64、もしくは100、もしくは500、もしくは1,000、もしくはそれ以上の配置などにおける、参照ゲノム内の任意の数の位置とマッチし得る。しかしながら、個別のリードは、ゲノムのただ1つの特定の部分から導出、たとえば、配列決定された。したがって、所与の特定のリードが導出された場所から真の配置を見つけるために、アライメント機能、たとえば、Smith-Watermanギャップもしくは無ギャップアライメント、Needleman-Wunschアライメントなどが実行されてよく、それにより、ゲノム内のどこでリードの1つまたは複数が実際に導出されたかを、たとえば、マッチが生じる可能な配置のすべてを比較し、すべての可能性のうちのどれがリードが配列決定されたゲノム内の最もありそうな配置であるかを、どの配置のアライメントスコアが最大となるか基づき決定することなどによって決定する。
【0123】
示されているように、典型的には、そのようなアライメント機能を実行するためにアルゴリズムが使用される。たとえば、Smith-Watermanおよび/またはNeedleman-Wunschアライメントアルゴリズムは、2つまたはそれ以上の配列を互いに対してアライメントするために使用され得る。この事例では、これらは、リードが参照ゲノムにマッピングされる所与の位置についてマッピングが実際にはリードの始まりの場所からの位置である確率を決定するような仕方で使用され得る。典型的には、これらのアルゴリズムは、ソフトウェアによって実行されるように構成されるが、様々な事例において、本明細書において提示されているように、これらのアルゴリズムのうちの1つまたは複数は、本明細書において以下でより詳しく説明されているように、ハードウェアで実行されるように構成され得る。
【0124】
特に、アライメント機能は、少なくとも一部には、リードの1つまたは複数、たとえばすべてを、ミスマッチの1つまたは複数、たとえば、SNP、挿入、欠失、構造的アーチファクトなどが存在しているにもかかわらず、参照ゲノムにアライメントし、それにより、リードがゲノム内のどこで正しく適合しそうかを決定するように動作する。たとえば、1つまたは複数のリードは、参照ゲノムと突き合わせて比較され、ゲノムに対するリードの可能な最良の適合は、置換および/またはインデルおよび/または構造バリアントを考慮しながら決定される。しかしながら、リードの修正バージョンのうちのどれが参照ゲノムに対して最もよく適合するかをよりよく決定するために、提案された変更が考慮されなければならず、したがって、スコアリング機能も実行されてよい。
【0125】
たとえば、スコアリング機能は、たとえば、アライメント機能全体の一部として実行されてよく、それによって、アライメントモジュールがその機能を実行し、1つまたは複数の変更を他方と比較される配列内に導入し、たとえば、それによってそれら2つの間のよりよいまたは最良の適合を達成し、よりよいアライメントを達成するために行われる変更毎に、アライメントが実行されるときにアライメントに対するスコアも決定されるような仕方で開始スコア、たとえば完全スコアもしくはゼロ開始スコアのいずれかからある数が減じられ、たとえばマッチが検出された場合にスコアが増やされ、導入された変更毎に、ペナルティが課され、それにより、可能なアライメントに対する最良適合が、たとえば、可能な修正されたリードのすべてのうちどれが最高スコアでゲノムに適合するかを見つけ出すことによって決定され得る。したがって、事例において、アライメント機能は、最高のスコアリングのアライメントを達成するためにリードに行われる必要のある変更の最良の組合せを決定するように構成されるものとしてよく、そのアライメントは、次いで、正しい、または最もありそうなアライメントであると決定され得る。
【0126】
上記に照らして、したがって、アライメント機能を実行することから達成され得る少なくとも2つの目標がある。1つは、最良のアライメントのレポートであり、これは参照ゲノム内の位置と、その位置でリードを参照セグメントにマッチさせるのに必要な変更がどのようなものであるかの記述とを含み、もう1つは、アライメントクオリティスコアである。たとえば、様々な事例において、アライメントモジュールからの出力は、コンパクトイディオシンクラティックギャップアライメントレポート(Compact Idiosyncratic Gapped Alignment Report)、たとえば、CIGAR文字列であってよく、CIGAR文字列出力は、最良適合アライメントを達成するようにリードに対して行われたすべての変更、たとえば、クエリが実際に参照とどのようにアライメントするかを示す詳細なアライメント命令を詳述するレポートである。読み出されたそのようなCIGAR文字列は、所与の対象のゲノムヌクレオチド配列について、参照ゲノムと突き合わせて比較された予測されたバリエーションが実際には真のバリエーションであり、単に機械、ソフトウェア、または人間の誤りによるものでないとよりよく決定するために処理のさらなる段階において有用であり得る。
【0127】
上で述べたように、様々な実施形態において、アライメントは、典型的には、順次的に実行され、アルゴリズムおよび/またはファームウェアは、リードおよびリードが1つまたは複数の参照ゲノムに潜在的にマッピングし得る1つまたは複数の可能な配置に関連するリード配列データをマッピングモジュールなどから受け取り、リードがマッピングし得る1つまたは複数の参照ゲノム内の1つまたは複数の位置に関連するゲノム配列データを、関連付けられているDRAMなどの、1つまたは複数のメモリなどからさらに受け取る。特に、様々な実施形態において、マッピングモジュールは、FASTQファイルなどからのリードを処理し、それらの各々をそれらが場合によってはアライメントし得る参照ゲノム内の1つまたは複数の位置にマッピングする。次いで、アライナは、これらの予測された位置を取り、それらを使用して、リードを参照ゲノムにアライメントすることを、それによってリードを参照ゲノムと比較する仮想アレイを構築することなどによって行う。
【0128】
この機能を実行する際に、アライナは、各個別のリードに対する各マッピングされた位置を評価し、特に、参照ゲノム内の複数の可能な配置にマッピングするそれらのリードを評価し、各位置が正しい位置である確率をスコアリングする。次いで、最良のスコア、たとえば、2つの最良のスコアを比較し、特定のリードが実際にどこにアライメントするかに関する決定を行う。たとえば、第1および第2の最良のアライメントスコアを比較する際に、アライナは、スコア間の差を見て、それらの間の差が大きい場合に、より大きいスコアを有するものが正しいとする信頼スコアが高くなる。しかしながら、それらの間の差が小さい、たとえば、ゼロである場合、2つの位置のどちらからリードが実際に導出されたかを言える信頼スコアは低く、リードが導出された場所から参照ゲノム内の真の配置を明確に決定することができるためにより多くの処理が役立ち得る。
【0129】
したがって、アライナは一部において、所与のリードが参照ゲノム内の所与の配置にマッピングするというコールを行う際に第1の最良の信頼スコアと第2の最良の信頼スコアとの間の最大の差を探すことになる。理想的には、アライメントの最良の可能な選択のスコアは、その配列に対する第2の最良のアライメントに対するスコアよりも著しく大きい。アライメントスコアリング方法を実装する方法は多数あり、また様々であり、たとえば、本明細書で開示されている方法などに従って、アレイの各セルがスコアリングされ得るか、またはセルの一部分がスコアリングされ得る。様々な事例において、ヌクレオチドのマッチ、ヌクレオチドのミスマッチ、挿入、および欠失に対するスコアリングパラメータは、様々な正または負またはゼロの値を有し得る。様々な事例において、これらのスコアリングパラメータは、利用可能な情報に基づき修正され得る。たとえば、正確なアライメントは、ヌクレオチドのマッチスコア、ヌクレオチドのミスマッチスコアのどれかまたはすべてを含む、スコアリングパラメータを作ることによって達成されるものとしてよく、ギャップ(挿入および/または欠失)ペナルティ、ギャップオープンペナルティ、および/またはギャップエクステンドペナルティは、現在のリードヌクレオチドまたは位置に関連付けられている塩基クオリティスコアに応じて変化する。たとえば、スコアボーナスおよび/またはペナルティは、塩基クオリティスコアがシークエンシングまたは他の誤りが存在している高い確率を示すときにより小さくされることもあり得る。塩基クオリティに敏感なスコアリングが、たとえば、対応するスコアリングパラメータを返す、塩基クオリティスコアを使用してアクセスされる、固定されたまたは構成可能なルックアップテーブルを使用して、実装され得る。
【0130】
FPGAまたはASICなどの、集積回路によるハードウェア実装では、スコアリング波面は、16セル、または32セル、または64セル、または128セル、または同様のものなどの、スコアリングセルの線形アレイとして実装されてよい。スコアリングセルの各々は、アライメントスコアを計算するために配線構成におけるデジタル論理素子から構築され得る。したがって、波面の各ステップについて、たとえば、各クロックサイクル、または他の何らかの固定された、もしくは可変の時間単位、スコアリングセルの各々、またはセルの一部は、仮想アライメント行列内の新しいセルについて必要な1つまたは複数のスコアを計算する。概念上、様々なスコアリングセルは、たとえば、行列内の左下から右上まで伸びる直線に沿って、本明細書で説明されているようなスコアリング波面に対応する、アライメント行列内の様々な位置にあると考えられる。デジタル論理設計の分野ではよく理解されているように、物理的スコアリングセルおよびその構成されるデジタル論理は、集積回路上に類似の様式で物理的に配置構成される必要はない。
【0131】
したがって、波面が仮想アライメント行列をスイープするステップを実行するときに、スコアリングセルの概念的位置は、それに対応して、各セルを更新し、たとえば、右に1ステップ概念的に「移動する」か、またはたとえば、アライメント行列内の下方に1ステップ移動する。すべてのスコアリングセルが、同じ相対的概念的移動を行い、対角線波面配置構成を変えずにそのままにする。波面が新しい位置に、たとえば、行列内で垂直下方のステップまたは水平右方向のステップで移動するたびに、スコアリングセルは新しい概念的位置に到達し、それらが入っている仮想アライメント行列セルに対するアライメントスコアを計算する。そのような実装形態において、線形アレイ内の隣接するスコアリングセルは、クエリ(リード)ヌクレオチド、参照ヌクレオチド、および以前に計算されたアライメントスコアを伝達するように結合される。参照ウィンドウのヌクレオチドは、順次波面の一端に、たとえば、線形アレイ内の右上スコアリングセル内に送り込まれるものとしてよく、そこから波面の長さだけ順次下にシフトするものとしてよく、それにより、常に、スコアリングセルの数に等しい長さの参照ヌクレオチドのセグメントがセル内に存在し、1つの連続するヌクレオチドが各連続するスコアリングセル内にある。
【0132】
たとえば、波面が水平方向に1ステップずつ進む毎に、別の参照ヌクレオチドが右上のセルに送り込まれ、他の参照ヌクレオチドが左下にシフトして波面を通る。参照ヌクレオチドのこのシフトは、アライメント行列を通って右方向に進むスコアリングセルの波面の概念的移動の基礎となる現実であり得る。したがって、リードのヌクレオチドは、順次波面の対向端に、たとえば、線形アレイ内の左下スコアリングセル内に送り込まれるものとしてよく、そこから波面の長さだけ順次上にシフトするものとしてよく、それにより、常に、スコアリングセルの数に等しい長さのクエリヌクレオチドのセグメントがセル内に存在し、1つの連続するヌクレオチドが各連続するスコアリングセル内にある。同様に、波面が垂直方向に1ステップずつ進む毎に、別のクエリヌクレオチドが左下のセルに送り込まれ、他のクエリヌクレオチドが右上にシフトして波面を通る。クエリヌクレオチドのこのシフトは、アライメント行列を通って下方に進むスコアリングセルの波面の概念的移動の基礎となる現実である。したがって、参照ヌクレオチドのシフトを指令することによって、波面は1ステップ水平方向に移動されてよく、クエリヌクレオチドのシフトを指令することによって、波面は1ステップ垂直方向に移動されてよい。したがって、一般的に対角線上にある波面移動を作成するために、たとえば、挿入も欠失もなしでクエリおよび参照配列の典型的なアライメントに追随するために、波面ステップは垂直方向と水平方向の交互で指令され得る。
【0133】
したがって、線形アレイ内の隣接するスコアリングセルは、以前に計算されたアライメントスコアを伝達するように結合され得る。Smith-WatermanもしくはNeedleman-Wunsch、またはそのようなバリアントなどの、様々なアライメントスコアリングアルゴリズムにおいて、仮想アライメント行列の各セル内のアライメントスコアは、現在のセルのすぐ左、現在のセルの上、および現在のセルの対角線上左上に位置する3つのセルなどの、行列の他のセル内の以前に計算されたスコアを使用して計算され得る。スコアリングセルが、それが入った別の行列位置について新しいスコアを計算するときに、これはそのような他の行列位置に対応するそのような以前に計算されたスコアを取り出さなければならない。これらの以前に計算されたスコアは、同じセル内の以前に計算されたスコアの記憶域から、および/または線形アレイ内の1つまたは複数の隣接するスコアリングセルにおける以前に計算されたスコアの記憶域から取得され得る。これは、仮想アライメント行列内の3つの寄与するスコア位置(すぐ左、上、および対角線上左上)であれば現在のスコアリングセルによって、または線形アレイ内の隣接するスコアリングセルのうちの1つのセルによってのいずれかでスコアリングされているからである。
【0134】
たとえば、行列内のすぐ左にあるセルは、一番最近の波面ステップが水平(右方向)であった場合に、現在のスコアリングセルによってスコアリングされているか、または一番最近の波面ステップが垂直(下方)であった場合に、線形アレイ内で左下にある隣接するセルによってスコアリングされている。同様に、行列内のすぐ上にあるセルは、一番最近の波面ステップが垂直(下向き)であった場合に、現在のスコアリングセルによってスコアリングされているか、または一番最近の波面ステップが水平(右方向)であった場合に、線形アレイ内で右上にある隣接するセルによってスコアリングされている。特に、行列内の対角線上左上のセルは、一番最近の2つの波面ステップが異なる方向、たとえば、下次いで右、または右次いで下にある場合に、現在のスコアリングセルによってスコアリングされているか、または一番最近の2つの波面ステップが両方とも水平(右方向)であった場合に、線形アレイ内で右上にある隣接するセルによってスコアリングされているか、または一番最近の2つの波面ステップが両方とも垂直(下方)であった場合に、線形アレイ内で左下の隣接するセルによってスコアリングされている。
【0135】
したがって、最後の1つまたは2つの波面ステップ方向に関する情報を考慮することによって、スコアリングセルは、以前に計算された適切なスコアを選択して、それ自体の内部でそれらにアクセスし、および/または隣接するスコアリングセル内で隣接するセル間の結合を利用するものとしてよい。変更形態では、波面の2つの端のスコアリングセルは、その無効な、またはゼロの、または最小値のスコアにハード配線された外向きスコア入力を有するものとしてよく、それらはこれらの両端のセルにおける新しいスコア計算に影響を与えない。したがって、波面を垂直および水平、たとえば対角線方向のステップで概念的に移動するために参照およびクエリヌクレオチドをアレイを通して対向方向にシフトするためのそのような結合、および波面が入った新しい仮想行列セル位置におけるアライメントスコアを計算するために隣接するセルによって以前に計算されたスコアにアクセスするための結合により、波面がスコアリングセルの線形アレイ内に実装されているので、仮想行列内のセルのバンド、波面の幅を、波面の連続するステップで行列内をスイープすることを指令することなどによってスコアリングすることがしかるべく可能である。
【0136】
したがって、新しいリードおよび参照ウィンドウがアライメントされるように、波面はスコアリング行列の内側に位置決めされることを開始し得るか、または有利には、たとえば左へ、または上に、または対角線上左に、および行列の左上隅の上と始めて外側から徐々にスコアリング行列に入り得る。たとえば、波面は、仮想行列の左上セルのちょうど左に位置する左上のスコアリングセルから始まるものとしてよく、次いで、波面は、一連の水平ステップによって右方向にスイープして行列内に入り、行列の左上領域のセルの水平バンドをスコアリングするものとしてよい。波面が参照とクエリとの間の予測されたアライメント関係に達したときに、またはマッチングが増大するアライメントスコアから検出されたときに、波面は対角線上右下にスイープすることを、垂直ステップと水平ステップとを交互にし、行列の真ん中を通るセルの対角線上バンドをスコアリングすることによって開始し得る。左下波面スコアリングセルが、アライメント行列の底部に達したときに、波面は、連続する水平ステップにより、再び右方向にスイープすることを開始し、いくつかのまたはすべての波面セルがスイープしてアライメント行列の境界から外に出るまで行い、行列の右下領域内のセルの水平バンドをスコアリングするものとしてよい。
【0137】
そのようなアライメント手順の1つまたは複数は、本明細書で説明されている機能に対応できるように修正されているものとしてよいNeedleman-Wunschアライメントアルゴリズムおよび/またはSmith-Watermanアライメントアルゴリズムなどの、好適なアライメントアルゴリズムによって実行され得る。一般に、これらのアルゴリズムの両方およびそれらに類似のものは、基本的に、いくつかの事例において、類似の仕方で実行される。たとえば、上で述べたように、これらのアライメントアルゴリズムは、典型的には、様々な事例において、水平上境界が塩基対組成に従ってアレイの上行の端から端までレイアウトされてよい、ゲノム参照配列を表すように構成され得るように仮想アレイを構築する。同様に、垂直境界は、第1の列に沿って下方に、順に位置決めされている、配列決定され、マッピングされたクエリ配列を表すように構成されてよく、それらのヌクレオチド配列順序は、それらがマッピングした参照のヌクレオチド配列に一般的にマッチする。次いで、間にあるセルは、所与の位置におけるクエリの関連する塩基が参照に関するその配置で位置決めされる確率に関するスコアを初期値として与えられ得る。この機能を実行する際に、スワスが間にあるセル内でスコアを初期値として埋めている行列において対角線上に移動されてよく、示されている位置内にあるクエリの各塩基に対する確率が決定され得る。
【0138】
最適な大域的(または半大域的)アライメントを生成する、Needleman-Wunschアライメント機能に関して、リード配列全体を参照ゲノムの一部のセグメントにアライメントすることで、波面操縦(wave front steering)は、アライメント行列の上エッジから下エッジまで残らず典型的にスイープするように構成され得る。波面スイープが完了すると、アライメント行列の下エッジ(リードの端に対応する)の最大スコアが選択され、アライメントは行列の上エッジ(リードの始まりに対応する)上のセルまでバックトレースされる。本明細書において開示されている様々な事例において、リードは任意の長さをとることができ、任意のサイズであってよく、アライメントが実行される仕方に関して広範なリードパラメータがある必要はなく、たとえば、様々な事例において、リードは染色体の長さと同じくらいであってよい。しかしながら、そのような事例において、メモリのサイズおよび染色体の長さは、限定因子であり得る。
【0139】
最適な局所的アライメントを生成する、Smith-Watermanアルゴリズムに関して、リード配列全体またはリード配列の一部を参照ゲノムの一部のセグメントにアライメントすることで、リードの完全なまたは部分的なアライメントに基づき可能な最良のスコアリングを見つけるようにこのアルゴリズムは構成されてよい。したがって、様々な事例において、波面スコアバンド(wave front-scored band)は、非常に長いリードが参照ゲノムへの中間マッピングにおいてシードのみを有していた場合などに、アライメント行列の上エッジおよび/または下エッジまで延在し得ないが、一般には波面はそれでも行列の上から下へスコアリングし得る。局所的アライメントは、典型的には2つの調整によって達成される。第1に、アライメントスコアは、決して、ゼロ(または他の何らかの下限)を下回ることを許されず、他の何らかの方法で計算されたセルスコアが負になる場合、ゼロスコアが置き換えられ、新しいアライメントの開始を表す。第2に、必ずしも下エッジに沿っていない、行列内の任意のセルで作成された最大アライメントスコアは、アライメントの終端として使用される。アライメントは、この最大スコアから上および左に行列を通りゼロスコアまでバックトレースされ、これは行列の上行にない場合であっても、局所的アライメントの開始位置として使用される。
【0140】
上記に照らして、仮想アレイを通るいくつかの異なる可能な経路がある。様々な実施形態において、波面は仮想アレイの左上隅から始まり、下方に移動して最大スコアの識別子の方へ向かう。たとえば、可能なすべてのアライメントの結果が収集され、処理され、相関され、スコアリングされて、最大スコアを決定することができる。境界の端またはアレイの端に到達し、および/または処理されたセルのすべてに対する最高スコアをもたらす計算が決定されたときに(たとえば、全体的に最高のスコアが識別される)、その最高のスコアを達成するために取られた経路を見つけるためにバックトレースが実行されてよい。たとえば、予測された最大スコアに至る経路が識別されてよく、識別された後、その最大スコアがどのように導出されたかを決定するために、たとえば、後方に移動して最良のスコアアライメントに追随し波面スコアリングセルによって計算されるような識別された最大スコアを達成させた経路を再トレースすることによって監査が実行され得る。
【0141】
この後方再構築またはバックトレースは、決定された最大スコアから開始し、前のセルを通って後方へ進み、最大スコアを達成することをもたらしたスコアを有するセルの経路をこのテーブルに至るまでナビゲートし、初期境界に、たとえば、アレイの先頭に、または局所的アライメントの場合にはゼロスコアに、戻るようにナビゲートすることを伴う。バックトレースでは、アライメント行列内の特定のセルに到達した後、次のバックトレースステップは、隣接するセルに、すぐ左の方へ、または上に、または対角線上左上に進むステップであり、これは現在のセル内のスコアを構築するために選択された最良のスコアを与えた。この方式で、最大スコアの展開が決定されるものとしてよく、それにより最大スコアにどのように達したかを見出す。バックトレースは、隅、エッジ、または境界で終了してよいか、またはアレイの左上側の隅などの中でゼロスコアで終了し得る。したがって、これは、適切なアライメントを識別し、それによって、個体、またはその一部から導出されたサンプルゲノム配列が参照DNAのゲノム配列にどのようにマッチするか、または何らかの形でアライメントするかを表すCIGAR鎖読出しを作成するバックトレースである。
【0142】
各リードがマッピングされた場所が決定され、各リードがどこにアライメントされるかがさらに決定される、たとえば、各関連するリードが位置および位置が正しいアライメントである確率を反映するクオリティスコアを与えられて、対象のDNAに対するヌクレオチド配列が知られるようになされた後、様々なリードおよび/または対象のゲノム核酸配列の順序が、バックトレース機能を実行しアレイを通り後戻りしサンプルゲノム配列内の適切な順序のすべての核酸の同一性を決定することなどによって検証され得る。結果として、いくつかの態様において、本開示は、個体からのゲノムサンプルを形成するなどの生の配列リードデータを取り、その後ソーティングされ得る、そのデータをマッピングし、および/またはアライメントすることを対象とするパイプラインなどの、モジュールのパイプラインの一部であり得るモジュールなどの、アライメントおよびバックトレース機能の両方を実行するアライメントモジュールの一部であるような、バックトレース機能を対象とする。
【0143】
バックトレースオペレーションを円滑にするために、アライメント行列内に各スコアリングされたセルに対するスコアリングベクトルを記憶し、スコア選択決定を符号化することは有用である。線形ギャップペナルティによる古典的なSmith-Watermanおよび/またはNeedleman-Wunschスコアリングの実装では、スコアリングベクトルは、4つの可能性を符号化することができ、これは任意選択により、0から3の2ビット整数として記憶されてよく、たとえば、0=新しいアライメント(ヌルスコアが選択される)、1=垂直アライメント(上のセルからのスコアが選択され、ギャップペナルティによって修正される)、2=水平アライメント(左のセルからのスコアが選択され、ギャップペナルティによって修正される)、3=対角線上アライメント(上および左のセルからのスコアが選択され、ヌクレオチドマッチまたはミスマッチスコアによって修正される)である。任意選択により、各スコアリングされた行列セルに対する計算されたスコアも記憶され得るが(標準的に記憶されている達成された最大アライメントスコアに加えて)、これはバックトレースに一般的に必要でなく、大量のメモリを消費する可能性がある。次いで、バックトレースを実行するステップは、スコアリングベクトルに追随するという問題となり、バックトレースが行列内の所与のセルに到達したときに、次のバックトレースステップは、そのセルに対する記憶されているスコアリングベクトルによって決定され、たとえば、0=バックトレースを終了する、1=上方にバックトレースする、2=左方向にバックトレースする、3=対角線上左上にバックトレースする、となる。
【0144】
そのようなスコアリングベクトルは、アライメント行列の次元に従って配置構成された2次元テーブルに記憶されるものとしてよく、波面によってスコアリングされるセルに対応するエントリのみが初期値を入力される。代替的に、メモリを節約し、スコアリングベクトルを生成されるとともにより容易に記録し、様々なサイズのアライメント行列により容易に適応するために、スコアリングベクトルが、各行がスコアリングセルの単一の波面からのスコアリングベクトルを記憶するサイズ、たとえば64セル波面からの64個の2ビットスコアリングベクトルを記憶する128ビット、およびアライメントオペレーションにおける波面ステップの最大数に等しい行の数のサイズを有するテーブルに記憶されるものとしてよい。それに加えて、このオプションに対して、様々な波面ステップ、たとえば、各テーブル行内に余分な、たとえば、129番目の、ビットを記憶するステップ、たとえばこの波面位置に先行する垂直波面ステップに対しては0、この波面位置に先行する水平波面ステップに対しては1を符号化するステップの方向が記録され得る。この余分なビットは、各テーブル行内のスコアリングベクトルがどの仮想スコアリング行列位置に対応するかを追跡するためにバックトレースで使用されるものとしてよく、それにより、適切なスコアリングベクトルが、各連続するバックトレースステップの後に取り出され得る。バックトレースステップが垂直または水平であるときに、次のスコアリングベクトルは、前のテーブル行から取り出されるべきであるが、バックトレースステップが対角線上であるときには、次のスコアリングベクトルは、波面が一方のセルをスコアリングするステップからセルをそこから対角線上右下にスコアリングすることへ移動するのに2ステップ進まなければならなかったので、2行前から取り出されるべきである。
【0145】
アフィンギャップスコアリングの場合、スコアリングベクトル情報は、たとえば、スコアリングされたセル毎に4ビットに拡張され得る。たとえば2ビットスコア選択方向インジケータに加えて、2つの1ビットフラグ、すなわち、垂直拡張フラグ(vertical extend flag)および水平拡張フラグ(horizontal extend flag)が追加され得る。Smith-WatermanまたはNeedleman-Wunschまたは類似のアライメントアルゴリズムへのアフィンギャップスコアリング拡張の方法に従って、各セルについて、そのセル内で終端する最良スコアリングアライメントを表す一次アライメントスコアに加えて、「垂直スコア」が、最終垂直ステップでそのセルに到達する最大アライメントスコアに対応して生成されるべきであり、「水平スコア」が、最終水平ステップでそのセルに到達する最大アライメントスコアに対応して生成されるべきであり、3つのスコアのうちのどれかを計算するときに、セル内への垂直ステップは、ギャップオープンペナルティを差し引いた上のセルからの一次スコア、またはギャップエクステンドペナルティを差し引いた上のセルからの垂直スコア、のうちのいずれか大きい方を使用して計算されてよく、セル内への水平ステップは、ギャップオープンペナルティを差し引いた左側のセルからの一次スコア、またはギャップエクステンドペナルティを差し引いた左側のセルからの水平スコア、のうちのいずれか大きい方を使用して計算されてよい。ギャップエクステンドペナルティを差し引いた垂直スコアが選択された場合、スコアリングベクトル内の垂直エクステンドフラグは、セットされる、たとえば「1」であるべきであり、そうでなければ、アンセットされる、たとえば、「0」であるべきである。
【0146】
ギャップエクステンドペナルティを差し引いた水平スコアが選択された場合、スコアリングベクトル内の水平エクステンドフラグは、セットされる、たとえば「1」であるべきであり、そうでなければ、アンセットされる、たとえば、「0」であるべきである。アフィンギャップスコアリングに対するバックトレースでは、バックトレースが垂直ステップで所与のセルから上方に行くときにはいつでも、そのセルのスコアリングベクトルの垂直エクステンドフラグがセットされていれば、続くバックトレースステップも、上のセルに対するスコアリングベクトルに関係なく垂直でなければならない。同様に、バックトレースが水平ステップで所与のセルから左方に行くときにはいつでも、そのセルのスコアリングベクトルの水平エクステンドフラグがセットされていれば、続くバックトレースステップも、左のセルに対するスコアリングベクトルに関係なく水平でなければならない。したがって、スコアリングベクトルのそのようなテーブル、たとえば、ある数NR個の行について、線形ギャップスコアリングを使用する場合には64セルに対して行毎に129ビット、またはアフィンギャップスコアリングを使用する場合には64セルに対して行毎に257ビットが、スコアリング波面がNR以下のステップを進んだ場合のアライメントスコアリングを完結させた後にバックトレースをサポートするのに適している。
【0147】
たとえば、300ヌクレオチドリードをアライメントするときに、必要な波面ステップの数は、常に1024未満であってよく、したがって、テーブルは257×1024ビット、または約32キロバイトであってよく、多くの場合において、集積回路の内部の妥当なローカルメモリであり得る。しかし、非常に長いリードがアライメントされるべきである場合、たとえば、100,000個のヌクレオチドの場合、スコアリングベクトルに対するメモリの必要条件は、きわめて大きく、たとえば、8メガバイトにもなり得、集積回路の内部のローカルメモリとして備えるのに非常に高いコストがかかり得る。そのような支持では、スコアリングベクトル情報は、集積回路の外部のバルクメモリ、たとえば、DRAMに記録されてよいが、その後、この帯域幅要件、たとえば、1つのアライナモジュールにおいてクロックサイクル毎に257ビットは、過剰であり得、アライナの性能に対するボトルネックとなり、劇的に性能を低下させ得る。したがって、アライメントを完了する前にスコアリングベクトルを配設するための方法を有していることが望ましく、したがってその記憶要件は、たとえばインクリメンタルバックトレースを実行し、たとえばアライメントのスコアリングベクトル履歴の前の方の部分からインクリメンタルな部分的CIGAR文字列を生成し、それによりスコアリングベクトルのそのような前の方の部分がその後破棄され得るように上限が維持されていてよい。問題は、バックトレースが、アライメントスコアリングが完了するまでは不明である、アライメントの末端、最大スコアリングセルにおいて始まることが想定され、したがってアライメントが完了する前に始まるバックトレースは間違ったセルから、結果として生じる最終最適アライメント経路に沿わずに始まり得ることである。
【0148】
したがって、たとえば、これまでにスコアリングされたアライメント行列セルに対する部分的スコアリングベクトル情報を含む、部分的アライメント情報からインクリメンタルバックトレースを実行するための方法が与えられる。現在完結しているアライメント境界、たとえば、特定のスコアリングされた波面位置から、境界上のすべてのセル位置からバックトレースが開始される。すべての境界セルからのそのようなバックトレースは、順次実行され得るか、または有利には、特にハードウェア実装形態において、すべてのバックトレースが一緒に実行され得る。アライメント表記、たとえば、CIGAR文字列をこれらの複数のバックトレースから抽出する必要はなく、バックトレース時にそれらがどのようなアライメント行列位置を通過するかを決定するだけでよい。スコアリング境界からの同時バックトレースの実装において、多数の1ビットレジスタが利用されてよく、これはたとえばすべて1に初期化されたアライメントセルの個数に対応し、バックトレースが対応する位置を通過するかどうかを表すものとしてよい。同時バックトレースの各ステップについて、たとえば、スコアリングベクトルテーブルの1つの行からの、これらのレジスタ内のすべての現在の「1」に対応するスコアリングベクトルが調査され、それにより、次の同時バックトレースステップに対して、レジスタ内の各「1」に対応し、レジスタ内の各「1」に対する続く位置に至る、次のバックトレースステップを決定することができる。
【0149】
重要なことは、レジスタ内の複数の「1」を、共通のバックトレース経路上に一緒にマージする同時バックトレースのうちの複数に対応する、共通位置にマージさせることが容易に可能である。同時バックトレースの2つもしくはそれ以上が一緒にマージした後、それらはいつまでもマージされたままであるが、それはこれ以降同じセルからのスコアリングベクトル情報を利用することになるからである。経験的に、および理論的な理由から、高い確率で、同時バックトレースのすべてが特異バックトレース経路内に、たとえば、波面内のスコアリングセルの数の数倍、たとえば8倍であってよい、比較的少数のバックトレースステップでマージすることが観察されている。たとえば、64セル波面では、高い確率で、所与の波面境界からのすべてのバックトレースは、512のバックトレースステップ内で単一のバックトレース経路内にマージする。代替的に、すべてのバックトレースがその数の、たとえば、512個のバックトレースステップの範囲内で終了することも可能であり、また珍しいことではない。
【0150】
したがって、複数の同時バックトレースは、それらがすべて単一のバックトレース経路内に、たとえば、512以下のバックトレースステップで終端するか、またはマージするかのいずれかとなる十分に遠い後方のスコアリング境界、たとえば、スコアリングされた波面位置から実行され得る。それらがすべて特異バックトレース経路内に一緒にマージし、次いでそれらがマージするスコアリング行列内の配置からマージするか、または特異バックトレース経路に沿って任意の距離だけさらに後退する場合、部分的アライメント情報からのインクリメンタルバックトレースが可能である。マージ点からのさらなるバックトレース、または任意の距離だけ離れるさらなる後退が、対応するアライメント表記、たとえば、部分的CIGAR文字列を記録するステップを含む、通常の特異バックトレース方法によって開始される。このインクリメンタルバックトレース、およびたとえば、部分的CIGAR文字列は、アライメント完了した後に結果として生じるであろう、可能な最終バックトレース、およびたとえば、完全CIGAR文字列の一部でなければならないことは、そのような最終バックトレースが同時バックトレースを開始したスコアリング境界に到達する前に終了しないことを条件とするが、それは、スコアリング境界に到達した場合に、同時バックトレース経路のうちの1つに追随し、現在はインクリメンタルに抽出された、特異バックトレース経路内にマージしなければならないからである。
【0151】
したがって、たとえば抽出された特異バックトレースの開始に先行する波面位置に対するすべてのテーブル行内の、インクリメンタルに抽出されたバックトレースに対応する行列領域に対するすべてのスコアリングベクトルが安全に破棄され得る。最終バックトレースが、最大スコアリングセルから実行されたときに、スコアリング境界に到達する前に終了した場合(または代替的に、抽出された特異バックトレースの開始に到達する前に終了した場合)、インクリメンタルアライメント表記、たとえば、部分的CIGAR文字列は、破棄され得る。最終バックトレースが、抽出された特異バックトレースの開始まで続く場合、そのアライメント表記、たとえば、CIGAR文字列は、次いで、インクリメンタルアライメント表記、たとえば部分的CIGAR文字列上にグラフトされ得る。さらに、非常に長いアライメントでは、スコアリング境界、たとえば、スコアリングされた波面位置から同時バックトレースを、すべてのバックトレースが終了するかマージするまで実行し、その後アライメント表記抽出による特異バックトレースが続くプロセスは、様々な連続するスコアリング境界から、複数回繰り返され得る。次いで、各連続するインクリメンタルバックトレースからの、インクリメンタルアライメント表記、たとえば、部分的CIGAR文字列は、累積した前のアライメント表記上に、新しい同時バックトレースまたは特異バックトレースが早期に終了しない限りグラフトされてよく、その場合、累積した以前のアライメント表記は破棄され得る。結果として生じる最終バックトレースは、同様に、そのアライメント表記を、完全なバックトレース記述、たとえば、CIGAR文字列に対して、一番最近の累積したアライメント表記上にグラフトする。
【0152】
したがって、この仕方で、スコアリングベクトルを記憶するためのメモリは、同時バックトレースが制限された数のステップ、たとえば、512ステップで常に一緒にマージされると仮定すると、上限を維持され得る。同時バックトレースが制限された数のステップでマージするか、または終了することに失敗する希なケースでは、現在のアライメントを怠ること、またはより高い限度で、もしくは限度なしでそれを繰り返すことを含む、様々な例外的なアクションが、たぶん、外部DRAMなどに完全なアライメントに対するすべてのスコアリングベクトルを記憶することなどの異なるもしくは従来の方法によって、実行され得る。一変更形態において、そのようなアライメントを怠ることは妥当な場合があるが、それはきわめて希であり、そのような怠ったアライメントがアライメント報告で使用されるべき最良スコアリングアライメントになっているということはなおさら希であるからである。
【0153】
任意選択の変更形態において、スコアリングベクトルの記憶域は、物理的にまたは論理的に、多数の異なるブロック、たとえば、各々512行に分割されてよく、各ブロック内の最終行は、同時バックトレースを開始するためにスコアリング境界として使用され得る。任意選択により、同時バックトレースは、単一のブロック内で、たとえば512ステップで終了するか、またはマージする必要があり得る。任意選択により、同時バックトレースがより少ないステップでマージする場合、マージされるバックトレースは、それにもかかわらず、前のブロックで特異バックトレースの抽出を開始する前に、ブロック全体を通して継続され得る。したがって、スコアリングベクトルがブロックNに完全に書き込まれ、ブロックN+1への書込みを開始した後、同時バックトレースがブロックNにおいて開始し、続いてブロックN-1において特異バックトレースおよびアライメント表記抽出を開始するものとしてよい。同時バックトレース、特異バックトレース、およびアライメントスコアリングの速度がすべて類似しているか、または同一であり、同時に、たとえば、集積回路内の並列ハードウェアで実行され得る場合、ブロックN-1における特異バックトレースは、ブロックN+2に書き込むスコアリングベクトルと同時であってよく、ブロックN+3が書き込まれるべきであるときに、ブロックN-1は解放され、リサイクルされるものとしてよい。
【0154】
したがって、そのような実装形態において、最小4個のスコアリングベクトルブロックが使用され、循環的に利用され得る。したがって、アライナモジュールに対する全スコアリングベクトルの記憶域は、各々257×512ビットの4ブロック、たとえば64キロバイトであてよい。一変更形態において、現在の最大アライメントスコアが現在の波面位置よりも前の方のブロックに対応する場合、このブロックおよび前のブロックは、リサイクルされるのではなく、温存され、それにより、最終バックトレースは、最大スコアのままである場合にこの位置から開始するものとしてよく、余分な2ブロックを有しこのように温存を維持することで、最小、たとえば、6ブロックにする。
【0155】
別の変更形態では、オーバーラップしたアライメントをサポートするために、一方のアライメント行列から次のアライメント行列へ、上で説明されているように、追加のブロック、たとえば、1または2つの追加のブロックまで徐々に横切るスコアリング波面が利用されるものとしてよく、たとえば、合計8ブロック、たとえば、約128キロバイトであるものとしてよい。したがって、そのような制限された数のブロック、たとえば、4ブロックまたは8ブロックが循環的に使用される場合、任意に長いリード、たとえば、100,000個のヌクレオチド、または染色体全体、のアライメントおよびバックトレースが、スコアリングベクトルに外部メモリを使用することなく可能である。上記などを参照すると、マッピング機能がいくつかの事例において、マッパなどを参照しつつ説明されていることもあり得、および/またはアライメント機能がいくつかの事例において、アライナなどを参照しつつ説明されていることもあり得るが、これらの異なる機能は、当技術分野においてアライナとして一般に参照されている、同じアーキテクチャによって順次実行され得ることは理解されるであろう。したがって、様々な事例において、マッピング機能およびアライメント機能は両方とも、本明細書で説明されているように、特にアライメント機能を実行するためにマッピング機能が最初に実行される必要がある事例において、アライナであると理解され得る共通アーキテクチャによって実行され得る。
【0156】
様々な事例において、本開示のデバイス、システム、およびそれらの使用方法は、データセット内のリードに対する適切なアライメントを決定するためにその後スコアリングされ得る完全リード無ギャップおよび/またはギャップアライメントのうちの1つまたは複数を実行するように構成され得る。たとえば、様々な事例において、無ギャップアライメント手順が処理されるべきデータに対して実行されるものとしてよく、そこで、無ギャップアライメント手順の後に、ギャップアライメント、および/または選択的Smith-Watermanアライメント手順のうちの1つまたは複数が続くものとしてよい。たとえば、第1のステップにおいて、無ギャップアライメントチェーンが生成され得る。本明細書において説明されているように、そのような無ギャップアライメント機能は、ギャップを考慮することなどを必要とせずに、素早く実行されるものとしてよく、無ギャップアライメントを実行する第1のステップの後に、ギャップアライメントを実行することが続くものとしてよい。
【0157】
たとえば、アライメント機能は、所与のヌクレオチド配列、たとえば、リードが、リードおよび/または参照のうちの1つまたは複数にギャップを挿入する必要なく参照配列にどのようにアライメントするかを決定するために実行され得る。そのようなアライメント機能を実行するステップの重要な一部は、注目している配列と参照ゲノムの配列との間でどこでミスマッチしおよびそれがどのようにミスマッチであるかを決定するステップである。しかしながら、ヒトゲノム内では相同性が大きいので、理論上、所与のヌクレオチド配列は代表的な参照配列と大きくマッチすることとなる。ミスマッチがある場合、これらは比較的検出が容易である、一塩基多型によるものである可能性が高いか、またはそれらは、かなり検出が困難である、注目する配列内の挿入または欠失によるものである。
【0158】
結果として、アライメント機能を実行する際に、時間の大部分において、注目している配列は、参照配列とマッチすることになり、SNPによるミスマッチがある場合に、これは容易に決定される。したがって、比較的大きい処理能力量は、そのような解析を実行するためには必要でない。しかしながら、参照配列に関して注目する配列内に挿入または欠失がある場合に、そのような挿入および欠失がアライメントにおけるギャップになるので、面倒なことが起きる。そのようなギャップは、正しいアライメントを決定するためにより広範な、複雑な処理プラットフォームを必要とする。それにもかかわらず、実行される数百万の無ギャップアライメントと比較して、少ないパーセンテージのインデルしかないので、比較的少ないパーセンテージのギャップアライメントプロトコルが実行されるだけでよい。したがって、無ギャップアライメント機能すべてのうちのわずかなパーセンテージのものだけが結果として、配列内のインデルの存在によりさらなる処理を必要とすることになり、したがって、ギャップアライメントが必要である。
【0159】
無ギャップアライメント手順においてインデルが示されたときに、それらの配列のみがさらなる処理のためにアライメントエンジン、たとえば、Smith Watermanアライメント(SWA)などの高度なアライメント機能を実行するように構成されているアライメントエンジンに受け渡される。したがって、無ギャップまたはギャップアライメントのいずれかが実行されるべきなので、本明細書で開示されているデバイスおよびシステムは、リソースをかなり効率的に使用できる。より具体的には、いくつかの実施形態において、無ギャップおよびギャップアライメントは両方とも、配列の所与の選択に対して、たとえば、次々と実行されてよく、次いで、結果が各配列について比較され、最良の結果が選ばれる。そのような配置構成は、たとえば、精度の向上が望まれており、必要な処理を実行するための時間量およびリソースの量の増大が許容される場合に実装され得る。
【0160】
特に、様々な事例において、第1のアライメントステップは、処理集約的なSmith Waterman機能に関わることなく実行され得る。したがって、複数の無ギャップアライメントが、低いリソース集約性で時間をあまりかけない方式で実行されてよく、必要なリソースが少ないので、チップ上のそのような処理専用に割り当てる空間が少なくて済む。したがって、より少ない処理要素を使用し、必要な時間を短縮してより多くの処理が実行されるものとしてよく、したがって、より多くのアライメントが実行されてよく、精度の改善も達成され得る。より具体的には、Smith Watermanアライメントを実行するためにチップリソースの少ない実装が、より少ないチップ面積を使用して専用として割り当てられる必要があり、ギャップアライメントを実行するために行うような無ギャップアライメントを実行するのに必要な処理要素に対してあまり大きなチップ面積を必要としない。チップリソース要件が下がると、より短時間のうちにより多くの処理が実行され、より多くの処理が実行できることで、より高い精度が達成され得る。
【0161】
したがって、そのような事例において、たとえば、適切に構成された無ギャップアライメントリソースによって実行されるべき無ギャップアライメントプロトコルが採用され得る。たとえば、本明細書において開示されているように、様々な実施形態において、アライメント処理エンジンが実現され、たとえば、この処理エンジンは、電子データソースから、たとえば、1つまたは複数のヌクレオチド配列を表すデジタルデータなどの、ゲノムデータの1つまたは複数のリードを表すデジタル信号を受信し、そのデータに対して無ギャップアライメント機能を最初に実行し、次いで、無ギャップアライメント機能の後に、必要ならば、Smith Watermanアライメントプロトコルを実行することなどによって、ギャップアライメント機能を続いて実行することなどによってそのデータを参照配列にマッピングし、および/またはアライメントするように構成される。
【0162】
結果として、様々な事例において、無ギャップアライメント機能が、たとえば、無ギャップアライナを使用して、リードの連続部分に対して実行され、無ギャップアライメントが端から端へ進み、たとえば、リードが完了した場合、ギャップアライメントは実行されない。しかしながら、無ギャップアライメントの結果がインデルが存在していることを示している、たとえば、リードがクリップされるか、または他の何らかの形で不完全である場合に、ギャップアライメントが実行されてよい。したがって、非ギャップアライメント結果は、ギャップアライメントが必要かどうかを決定するために使用されるものとしてよく、たとえば、非ギャップアライメントは、ギャップ領域内に伸びるが、リードの全長にわたって伸びることはなく、たとえば、リードはクリップされ、たとえば、ある程度までソフトクリップされるものとしてよく、クリップされた場合にギャップアライメントが実行され得る。
【0163】
したがって、様々な実施形態において、完全性およびアライメントスコアに基づき、ギャップアライメントが実行されるのは、無ギャップアライメントが結局クリップされることになる、たとえば、端から端まで行かない場合のみである。より具体的には、様々な実施形態において、最良の識別可能な無ギャップおよび/またはギャップアライメントスコアは、ギャップアライメントを実行することなどによってスコアがさらなる解析を保証するのに十分によいスコアであるかを決定するためにカットオフラインとして推定され、使用され得る。したがって、アライメントの完全性、およびそのスコアは、高いスコアがアライメントが完全である、したがって非ギャップであることを示し、低いスコアがアライメントが完全でなく、ギャップアライメントが実行される必要があることを示すようにするために使用されてよい。したがって、高いスコアが達成された場合、ギャップアライメントは実行されず、スコアが十分に低いときのみ、ギャップアライメントが実行される。もちろん、様々な事例において、総当たりアプローチが使用されることもあり、それにより、その数のギャップおよび/または無ギャップアライナがチップアーキテクチャにおいてデプロイされ、それにより、より多くのアライメントが実行されることを可能にし、したがって、より多くのデータが見られ得る。
【0164】
より具体的には、様々な実施形態において、各マッピングおよび/またはアライメントエンジンは、1つまたは複数の、たとえば、2つのSmith-Watermanアライナモジュールを備え得る。いくつかの事例において、これらのモジュールは、大域的(エンドツーエンド)無ギャップアライメントおよび/または局所的(クリップ済み)ギャップアライメントをサポートし、アフィンギャップスコアリングを実行するように構成されてよく、各端で非クリップ済みスコア(unclipped score)ボーナスを生成するように構成され得る。塩基クオリティに敏感なマッチおよびミスマッチスコアリングもサポートされ得る。2つのアライメントモジュールが、たとえば、集積回路の一部として、含まれる場合、たとえば、各Smith-Watermanアライナはスコアリングセルの反対角線波面として構築されてよく、波面は仮想的アライメント矩形を通って「移動」し、波面がスコアリングセルをスイープする。
【0165】
しかしながら、より長いリードについては、Smith-Waterman波面も、自動操縦をサポートするように構成されてよく、それにより、蓄積されたインデルを通じて最良のアライメントを追跡し、たとえば、スコアリングされるアライメント波面およびセルがスコアリングバンドを逃れないことを確実にする。バックグラウンドでは、論理エンジンは、現在の波面スコアを調べ、最大値を見つけ、最大値よりも低い閾値距離の上でセルのサブセットにフラグを立て、2つの両端のフラグの間の中点をターゲットとするように構成され得る。そのような事例において、自動操縦は、ターゲットが波面中心にあるときに対角線上に実行するように構成されてよいが、インデルの存在などにより、ドリフトする場合にターゲットの再センタリングを行うために必要に応じて真っ直ぐ水平方向にまたは垂直方向に実行されるように構成され得る。
【0166】
アライメントモジュールからの出力は、マッピングクオリティスコア(MAPA)とともにSAM(テキスト)またはBAM(たとえば、SAMのバイナリバージョン)ファイルであり、クオリティスコアは、参照へのリードの予測され、アライメントされた配置が実際にはリードが導出される場所である信頼度を反映する。したがって、各リードがマッピングされた場所が決定され、各リードがアライメントされる場所がさらに決定される、たとえば、各関連するリードが位置および位置が正しいアライメントである確率を反映するクオリティスコアを与えられて、対象のDNAに対するヌクレオチド配列が知られ、さらには対象のDNAが参照のDNAとどれだけ異なるかが知られた後(たとえば、CIGAR文字列が決定されている)、対象のゲノム核酸配列を表す様々なリードは、染色体配置によってソーティングされ、それにより染色体上のリードの正確な配置が決定され得る。結果として、いくつかの態様において、本開示は、個体からのゲノムサンプルを形成するなどの生の配列リードデータを取り、その後ソーティングされ得る、そのデータをマッピングし、および/またはアライメントすることを対象とするパイプラインなどの、モジュールのパイプラインの一部であり得るソーティングモジュールによって実行されるような、ソーティング機能を対象とする。
【0167】
より具体的には、リードがどの染色体に属すかおよび/またはその染色体の先頭からのオフセットを識別するステップを含み得る、参照ゲノムなどに関する、位置をリードに割り当てることが行われた後、リードは位置でソーティングされるものとしてよい。ソーティングは、たとえば、下流解析などで有用な場合があり、それによって、ゲノム内の所与の位置と重なるリードのすべては、ソーティングモジュールを通じて処理された後などに、互いに隣接するようにパイルアップに形成されてよく、それによって、リードの大半が参照値と一致しているかどうかが容易に決定され得る。したがって、リードの大半が参照値と一致しない場合、バリアントコールにフラグが立てられ得る。したがって、ソーティングは、同じ配置をカバーするすべてのリードが物理的に一緒にグループ化されるように、パイルアップを作成するために、同じ染色体位置などの、比較的同じ位置にアライメントするリードをソーティングするステップの1つまたは複数を伴うものとしてよく、パイルアップのリードを解析し、それらのリードが参照ゲノムと比較してゲノム内の実際のバリアントを示し得る場所を決定するステップをさらに伴うものとしてよく、バリアントは、パイルアップのコンセンサスなどによって、機械リード誤りまたは少数のリードによって示され得るシークエンシング方法における誤りである誤りなどの、誤りから区別可能であるものとしてよい。
【0168】
データが取得された後、データをクリーンアップするために実行され得る1つまたは複数の他のモジュールがある。たとえば、個体のゲノム配列を決定するなどのために、たとえば、配列解析パイプラインに含まれ得る1つのモジュールは局所的再アライメントモジュールであってよい。たとえば、リードの端で生じる挿入および欠失を決定することは多くの場合、困難である。これは、Smith-Watermanまたは同等のアライメントプロセスが、スコアリングでその存在を検出できるインデルを超える十分なコンテキストを欠いているからである。結果として、実際のインデルは、1つまたは複数のSNPとして報告され得る。そのような事例において、所与のリードに対する予測される配置の精度は、マッピングされた、および/またはアライメントされた、および/またはソーティングされたリードデータに対して局所的再アライメントを実行することによって高められ得る。
【0169】
そのような事例において、パイルアップは、注目する位置が所与のリードの端にある場合などに、適切なアライメントを明確にしやすくするために使用されてよく、その同じ位置は、パイルアップ内の他の何らかのリードの中間にある可能性が高い。したがって、局所的再アライメントを実行する際に、パイルアップにおける様々なリードは、パイルアップにおけるリードのうちのいくつかが所与の位置で挿入または欠失があったことを示すかどうかを決定するために解析されてよく、その位置で、他のリードはインデルを含まないか、または、むしろ置換を含み、次いで、インデルは、それが存在しない場合に、参照などの中に挿入されてよく、その領域と重なる局所的パイルアップにおけるリードは、挿入および/または欠失がそこになかった場合にまとめてよりよいスコアが次いで達成されるかどうかを確認するために再アライメントされ得る。改善がある場合、パイルアップにおけるリードのセット全体が検討されるものとしてよく、セット全体のスコアが改善されている場合、実際にその位置にインデルがあったというコールを行うことは明らかである。このようなやり方で、個別のリードに対して、染色体の末端でリードをより正確にアライメントするのに十分なコンテキストがないという事実は、補償され得る。したがって、局所的再アライメントを実行するときに、1つまたは複数のインデルが位置決めされ得る1つまたは複数のパイルアップが調べられ、インデルを所与の位置に追加することによってアライメントスコア全体が高められ得るかどうかが決定される。
【0170】
個体のゲノム配列を決定するなどのために、たとえば、配列解析パイプラインに含まれ得る別のモジュールは重複マーキングモジュールであってよい。たとえば、重複マーキング機能は、シークエンシングフェーズにおいて起こり得る化学誤差を補償するために実行されてよい。たとえば、上で説明されているように、いくつかのシークエンシング手順において、核酸配列はビーズに付着され、標識ヌクレオチド塩基を使用してそこから構築される。理想的には、1つのビーズにリードが1つだけある。しかしながら、時には、複数のリードが単一のビーズに付着され、この結果、付着されたリードの複製が過剰に多くなる。この現象は、リード重複として知られている。
【0171】
アライメントが実行され、結果が得られた後、および/またはソーティング機能、局所的再アライメント、および/または重複除去が実行された後、結果として得られるデータ上でバリアントコール機能が使用され得る。たとえば、典型的なバリアントコール機能またはその一部は、集積回路などの、ソフトウェアおよび/またはハード配線された構成により実装されるように構成され得る。特に、バリアントコーリングは、すべての様々なアライメントされたリードからのすべての重なり合う領域が「パイルアップ」を形成するように参照上の所与の配置にアライメントするすべてのリードをグループ内に位置決めするステップを伴うプロセスである。次いで、参照ゲノムの所与の領域をカバーするリードのパイルアップは、サンプリングされた個体のDNA/RNAの最もありそうな実際の内容がその領域内で何であるかを決定するために解析される。次いで、これは、ゲノムのすべての領域について、1ステップずつ繰り返される。決定された内容は、他のメタデータとともに関連付けられている信頼水準を各々有する、参照ゲノムからの「バリエーション」または「バリアント」と呼ばれる差異のリストを生成する。
【0172】
最も一般的なバリアントは、単一塩基が参照と異なる、一塩基多型(SNP)である。SNPは、ヒトゲノムでは1000箇所の位置のうち約1箇所で起きる。次に一般的なのは、挿入(参照内への)および欠失(参照からの)、またはまとめて「インデル」である。これらは、長さが短いほど一般的であるが、任意の長さをとり得る。さらなる面倒な事態が起きるが、配列決定セグメント(「リード」)の集合体がランダムであるため、いくつかの領域は他に比べてより深いカバーを有する。また、多塩基置換、およびインデルと長さが変わる置換と考えられ得る置換との組合せを含むより複雑なバリアントもある。標準的なソフトウェアベースのバリアントコーラーは、これらのうちのすべてを識別することを苦手としており、バリアントの長さに様々な制限が課される。ソフトウェアおよび/またはハードウェアの両方におけるより特殊なバリアントコーラーは、染色体の大きな変化を伴う外来の「構造バリアント」のより長いバリエーション、および多くの多様性を識別するために必要である。
【0173】
しかしながら、バリアントコーリングは、ソフトウェアで実装するのが困難な手順であり、ハードウェアでデプロイするのはなおいっそう困難である。これらの種類の誤りを考慮し、および/または検出するために、典型的なバリアントコーラーは、次のタスクのうちの1つまたは複数を実行するものとしてよい。たとえば、これらは、仮説遺伝型のセット(座位にある1つまたは2つの染色体の内容)とともに現れ、ベイズ計算を使用して観察された証拠が与えられた場合に各遺伝型が真実である事後確率を推定し、最もありそうな遺伝型をその信頼水準とともに報告するものとしてよい。したがってバリアントコーラーは、単純であるか、または複雑であり得る。より単純なバリアントコーラーは、行われるコールの正確な位置でアライメントされたリードパイルアップにおける塩基の列のみを見る。より高度なバリアントコーラーは、「ハプロタイプベースコーラー」であり、これは行われるコールの周りで、ウィンドウなどにおいてコンテキストを考慮するように構成され得る。
【0174】
「ハプロタイプ」は、単一の一般的な「鎖」、たとえば、領域内の2つの二倍体鎖のうちの一方の中の特定のDNA内容(ヌクレオチド配列、バリアントのリストなど)であり、ハプロタイプベースコーラーでは、同じリード内に出現することによってどちらの差異がリンクされているかというベイズ統計での意味を考慮する。したがって、バリアントコールプロトコルは、本明細書において提案されているように、ゲノム解析ツールキット(GATK)ハプロタイプコーラーにおいて、および/または隠れマルコフモデル(HMM)ツールおよび/またはDe Bruijnグラフ機能を使用して実行されるような1つまたは複数の改善された機能を実装するものとしてよく、たとえば、典型的にはGATKハプロタイプコーラー、および/またはHMMツール、および/またはDe Bruijnグラフ機能によって使用される1つまたは複数のこれらの機能は、ソフトウェアおよび/またはハードウェアで実装されるものとしてよい。
【0175】
より具体的には、本明細書で実装されているように、様々な異なるバリアントコールオペレーションが、ソフトウェアまたはハードウェアで実行されるように構成されてよく、次のステップのうちの1つまたは複数を含み得る。たとえば、バリアントコール機能は、多数のリードが参照と一致しない場所を識別するステップ、および識別された能動領域の周りにウィンドウを生成するステップなどのための能動領域識別を含むものとしてよく、それによりこれらの領域のみがさらなる処理のために選択され得る。それに加えて、局所的ハプロタイプアセンブリが生じることがあり、たとえば、各所与の能動領域について、すべての重なり合うリードは「De Bruijn graph」(DBG)行列にアセンブルされ得る。このDBGから、行列を通る様々な経路が抽出されてよく、各経路は、どのような真のDNA配列が少なくとも1つの鎖上にあるのかについて候補ハプロタイプ、たとえば、仮説を構成する。さらに、ハプロタイプアライメントが生じることがあり、たとえば、各抽出されたハプロタイプ候補は、元の参照ゲノムにアライメントされ、たとえば、Smith-Watermanアライメントされ、それが参照からのどのようなバリエーションを意味するかを決定するものとしてよい。さらに、リード尤度計算が実行されてよく、たとえば、ハプロタイプがサンプリングされた真の元のDNAであったと仮定して、各リードが各ハプロタイプ、または仮説に対して検定され、リードを観察する確率を推定するものとしてよい。
【0176】
これらのプロセスに関して、リード尤度計算は、典型的には、多くの場合にペアHMM評価を必要とする、実行されるべき、リソース集約性が最も高く、時間も最もかかるオペレーションである。それに加えて、固有のK-merを局所的におよび大域的に識別する関連付けられているオペレーションによる、リードの各パイルアップに対するDe Bruijnグラフの構築は、以下で説明されているように、リソース集約的であり、および/または時間がかかり得る。したがって、様々な実施形態において、これらのステップのうちの1つまたは複数を実行する際に伴う様々な計算のうちの1つまたは複数は、本明細書において説明されているように、最適化されたソフトウェア方式またはハードウェアで実装されるように、たとえば、集積回路によって加速化される方式で実行されるように構成され得る。
【0177】
上に示されているように、様々な実施形態において、ソフトウェアおよび/またはハードウェアもしくはそれらの組合せで実装される、本開示のハプロタイプコーラーは、能動領域識別、局所的ハプロタイプアセンブリ、ハプロタイプアライメント、リード尤度計算、および/または遺伝型判定のうちの1つまたは複数のオペレーションを含むように構成され得る。たとえば、本開示のデバイス、システム、および/または方法は、マッピング、アライメント、および/またはソーティングが行われた結果データを生成するために対象の配列決定DNA/RNAから得られたデータに対してマッピング、アライメント、および/またはソーティングオペレーションのうちの1つまたは複数を実行するように構成され得る。次いで、この結果データは、それに対して重複除去オペレーションを実行することなどによってクリーンアップされてよく、および/またはそのデータは、その結果データに対して、上述のステップのうちの1つまたは複数を含む、バリアントコールオペレーションを実行してそれに関するバリアントコールファイルを生成するために1つまたは複数の専用のハプロタイプコーラー処理エンジンに伝達され得る。したがって、配列決定された、および/または参照ゲノム内の特定の位置にマッピングされ、および/またはアライメントされたすべてのリードは、さらなる処理を受け、それにより、決定された配列が参照ゲノム内の所与の位置における参照配列とどのように異なるかを決定し得る。
【0178】
したがって、様々な実施形態において、本明細書で開示されているような、デバイス、システム、および/またはその使用方法は、得られた結果データに対して能動領域識別オペレーションを実行するためにソフトウェアおよび/またはハード配線された構成で実装されるバリアントまたはハプロタイプコーラーシステムを含み得る。能動領域識別は、たとえば、リードのパイルアップにおける多数のリードが、参照と一致しない場所を識別し決定するステップを伴い、ウィンドウ内の領域がさらなる処理のために選択され得るようにそれらの不一致(「能動領域」)の周りに1つまたは複数のウィンドウを生成するステップをさらに伴う。たとえば、マッピングおよび/またはアライメントステップにおいて、識別されたリードは、参照ゲノム内の領域にマッピングされ、および/またはアライメントされ、そこでそれらは対象の遺伝子配列に由来していると予想される。
【0179】
しかしながら、ゲノムの所与の領域に対して配列決定されたリードのオーバーサンプリングを創出するためにそのような仕方でシークエンシングが実行されると、参照配列内の所与の位置において、その領域と一列に並びアライメントする配列決定されたリードのどれか、および/またはすべてからなるパイルアップが見られるものとしてよい。所与の領域またはパイルアップ位置においてアライメントし、および/または重なり合うこれらのリードのうちのすべては、バリアントコーラーシステム内に入力されるものとしてよい。したがって、解析される所与のリードについて、リードは重なりの疑わしい領域で参照と比較されてよく、そのリードは、参照の知られている配列から配列における差異を示すかどうかを決定するために参照と比較され得る。挿入または欠失なしでリードが参照と一列に並び、すべての塩基が同じである場合、アライメントは良好であると決定される。
【0180】
したがって、所与のマッピングされ、および/またはアライメントされたリードについて、リードは、参照と異なる塩基を有するものとしてよく、たとえば、リードは、1つまたは複数のSNPを含み、塩基がミスマッチしている位置を創出するものとしてよく、および/またはリードは、挿入および/または欠失のうちの1つまたは複数を有し、たとえば、アライメントにおいてギャップを創出し得る。したがって、これらの事例のどれかにおいて、さらなる処理によって考慮される必要がある1つまたは複数のミスマッチがある。それにもかかわらず、時間を節約し、効率を高めるために、そのようなさらなる処理は、感知されたミスマッチが非自明である、たとえば非ノイズ差異である事例に限定されるべきである。ミスマッチの有意性を決定するために、パイルアップ内の多数のリードが参照と一致しない場所は、能動領域として識別されるものとしてよく、次いで、能動領域の周りのウィンドウは、その後さらなる処理のために受けるものとしてよい不一致の座位を選択するために使用され得る。しかしながら、不一致は、非自明であるべきである。これは様々な仕方で決定されてよく、たとえば、非参照確率は、注目する各座位について、たとえば有意な仕方で参照と一致しないリードからの十分に有意な量の指示であるとみなされる所与の閾値よりも高い、塩基マッチ対ミスマッチクオリティスコアを解析することなどによって、計算され得る。
【0181】
たとえば、マッピングされた、および/またはアライメントされたリードの30個のすべてが一列に並び、および/または重なり合い、参照内の、たとえば能動領域内の所与の位置にパイルアップを形成し、30個のリードのうちの1つまたは2つのみが参照と一致しない場合、さらなる処理に対する最小閾値の条件が満たされていないとみなされるものとしてよく、非一致リードは、一致する28または29個のリードを考慮して無視されてよい。しかしながら、パイルアップ内のリードの3または4、または5、または10個、またはそれ以上が一致しない場合、その不一致は、さらなる処理を保証するのに統計的に十分に有意であるものとしてよく、差異の識別された領域の周りの能動領域は決定され得るであろう。そのような事例において、その差異を囲む塩基を確認する能動領域ウィンドウは、その差異を囲む領域に強化されたコンテキストを与えるように取られるものとしてよく、隣接する位置にわたって分布する非参照確率のガウス分布および総和を実行するステップなどの、追加の処理ステップは、その領域をさらに調査して処理し、能動領域が宣言されるべきかどうかを判断し、もしそうならば参照からのどのようなバリアントがその領域内にもしあれば実際に存在しているかを判断するために実行されるものとしてよい。したがって、能動領域を決定するステップでは、真のバリアントまたはリード誤りが生じたかどうかを明確に決定するために余分な処理が必要になることがある領域を識別する。
【0182】
特に、多くの事例において、配列のパイルアップ内のすべての領域にさらなる処理を施すことは望ましくないので、能動領域が識別されるものとしてよく、それによって、それはさらなる処理の必要に応じて決定され得る真のバリアントまたはリード誤りが生じたかどうかを明確に決定するために余分な処理が必要になり得る領域のみである。そして、上で示されているように、これは能動領域のウィンドウのサイズを決定する想定されているバリアントのサイズであり得る。たとえば、様々な事例において、能動ウィンドウの限界は、1もしくは2または約10もしくは20またはさらには約25もしくは約50から約200もしくは約300、または約500または約1000塩基長以上まで様々であり、これはさらなる処理が行われている能動ウィンドウの限界内にだけある。もちろん、能動ウィンドウのサイズは、差異の統計的重要度を決定するためのコンテキストを提供する限りは任意の好適な長さであってよい。
【0183】
したがって、1つまたは2つの孤立した差異のみがある場合、能動ウィンドウは、実際のバリアントが存在する統計的コールを行うのに十分なコンテキストを有するように能動領域内の1つまたは複数から数十までの塩基をカバーするだけでよい場合がある。しかしながら、差異がクラスタまたは束になってある場合、またはより多くのコンテキストが望ましいインデルが存在している場合に、ウィンドウは、より大きいものとなるように構成され得る。いずれかの事例において、クラスタ内に生じる可能性のあるあらゆる差異を解析し、それにより、1つまたは複数の能動領域内でそれらすべてを解析することが望ましいことがあるが、それは、そうすることで、各個別の差異に関するサポート情報を提供することができ、関わる能動ウィンドウの数を減らすことによって処理時間を削減するからである。様々な事例において、能動領域境界は、約0.00001または約0.00001または約0.0001以下から約0.002または約0.02または約0.2以上などの、所与の閾値を渡す能動確率によって決定され得る。そして、能動領域が所与の閾値より長い、たとえば、約300〜500塩基または1000塩基以上である場合、領域は、最低能動確率スコアを有する座位によって定められる部分領域などによって、いくつかの部分領域に分けられ得る。
【0184】
様々な事例において、能動領域が識別された後、局所的ハプロタイプアセンブリ手順が実行され得る。たとえば、各能動領域において、すべてのパイルアップおよび/または重なり合うリードは、「De Bruijn Graph」(DBG)にアセンブルされ得る。DBGは、選択された能動領域と重なり合ったすべてのリードに基づく有向グラフであってよく、その能動領域は約200または約300から約400または約500塩基長以上であり得、その能動領域内で、バリアントの存在および/同一性が決定されるべきである。様々な事例において、上で示されているように、能動領域は、たとえば、注目している座位の各方向にさらに約100または約200以上の塩基を含めて拡張された能動領域を生成することによって拡張されるものとしてよく、たとえば、差異を囲む追加のコンテキストがあるのが望ましい場合がある。したがって、能動領域と重なり合う部分を有するリードのすべてがパイルアップされて、たとえばパイルアップを作成し、重なり合う部分が識別され、リード配列がハプロタイプコーラーシステム内に螺入され、それによってこれはパズルのピースによく似たDe Bruijnグラフの形態で一緒にアセンブルされることは、拡張されようとされまいと、能動領域ウィンドウからである。
【0185】
したがって、所与の能動ウィンドウについて、パイルアップにおける様々な重なり合うリードの重なり合う領域が能動ウィンドウ内の配列全体をそれを通じてカバーする配列経路を一斉にパイルアップが含むようにパイルアップを形成するリードがある。したがって、能動領域内の所与の座位において、所与のリードが能動領域全体に広がることはあり得ないにもかかわらず、その座位と重なり合う複数のリードがある。この結果、パイルアップ内の様々なリードの様々な領域が、能動領域内の配列における所与の座位に対してバリアントが実際に存在しているかどうかを決定する際にDBGによって使用されることになる。それがこの決定が行われている能動ウィンドウ内にあるので、それは考慮されている能動ウィンドウの境界内にある所与のリードの部分であり、能動ウィンドウの外側にある部分は破棄され得る。
【0186】
示されているように、それはDBGシステム内に送り込まれる能動領域内の参照と重なり合うリードのセクションである。次いで、DBGシステムは、リードをパズルのようにグラフにアセンブルし、次いで、配列内の各位置について、所与のものについてマッチまたはミスマッチがあるかどうか、およびミスマッチがある場合に、そのミスマッチの確率がどれだけかが、その位置に対する重なり合うリードの集合体に基づき決定される。たとえば、パイルアップ内のリードのセグメントが互いに重なり合う個々の場所がある場合、それらは、マッチするそれらのエリアに基づき互いにアライメントされるものとしてよく、マッチするリードを一続きにするかまたは縫い合わせることから、それらのマッチする地点によって決定されるように、所与の位置にあるリードが互いにマッチするかまたはミスマッチするか、およびそれがどの程度であるかがそのセグメント内の各位置について確定され得る。したがって、コンパイルされている2つまたはそれ以上のリードが少しの間一列に並び、互いに完全に同じようにマッチする場合、単一の文字列を有するグラフが結果として生じるが、2つまたはそれ以上のリードは、差異点に達し、グラフ内に枝が形成され、2つまたはそれ以上の分岐文字列が結果として生じ、これは2つまたはそれ以上のリードの間のマッチングが再開するまで続く。
【0187】
したがって、このグラフを通る経路は、多くの場合に直線ではない。たとえば、リードのk-mersが、たとえばパイルアップ内の、参照のk-mersおよび/または1つもしくは複数の重なり合うリードからのk-mersと異なる場合、グラフ内の差異点のところに「バブル」が形成され、その結果、2つの分岐文字列が2つの配列の間のマッチングが再開するまで2つの異なる経路線に沿って続く。各頂点は、それぞれのk-mersがパイルアップ内のリードのすべてにおいて何回重なり合うかを識別する加重スコアを与えられるものとしてよい。特に、一方の側から他方の側へ生成されたグラフを通って延在する各経路は、カウントを与えられるものとしてよい。そして、同じk-mersが多数のリードから生成される場合、たとえば、各k-mersが同じ配列パターンを有する場合、それらは、k-mersがすでに存在しているk-mer経路と重なり合うその経路に対するカウントを増やすことによってグラフ内で考慮され得る。したがって、同じk-merが同じ配列を有する多数の重なり合うリードから生成される場合、グラフの間の経路のパターンは、何度となく繰り返され、グラフを通ってこの経路を横断するステップに対するカウントは、それと対応してインクリメンタルに増やされる。そのような事例では、パターンは、k-merの第1の事例に対してのみ記録され、カウントは、そのパターンを繰り返す各k-merについてインクリメンタルに増やされる。このモードでは、パイルアップにおける様々なリードは、どのようなバリエーションがどこに生じるかを決定するために獲得され得る。
【0188】
このような仕方で、グラフ行列が、すべての可能なN塩基k-mers、たとえば、10塩基k-mersを取ることによって形成されるものとしてよく、これは10塩基セグメント内のリードの長さ分を順次辿ることによって各所与のリードから生成されるものとしてよく、各新しい10塩基セグメントの始まりは、最後に生成された10塩基セグメントから1塩基だけオフセットされる。次いで、この手順は、能動ウィンドウ内のパイルアップにおけるすべてのリードについて同じことを行うことによって繰り返され得る。次いで、生成されるk-mersは、生成されたk-mersの間の同一のマッチングのエリアがそれらが重なり合うエリアにマッチするように互いにアライメントされてよく、これにより、その後走査され得るデータ構造体、たとえば、グラフを構築し、マッチおよびミスマッチのパーセンテージが決定され得る。特に、参照およびそれらとアライメントされた前に処理されたk-mersは、次の生成されたk-merに関して走査され、それにより、その瞬間の生成されたk-merが前に生成されたk-merの一部とマッチし、および/または重なり合うかどうかを決定するものとしてよく、マッチすることが見つけられた場合、次いでその瞬間の生成されたk-merが適切な位置のグラフ内に挿入され得る。
【0189】
構築された後、グラフは、走査され得、このマッチングに基づいて、参照に関するリード内の所与のSNPおよび/またはインデルが対象の遺伝子コードまたは処理もしくは他の誤りの結果における実際のバリエーションとなる可能性が高いかどうかが決定される。たとえば、所与の領域内の、リードのすべてまたはすべてのうちのかなりの部分の、k-mersのすべてまたはかなりの部分が、同じSNPおよび/またはインデルミスマッチを含むが、同じ仕方で参照と異なる場合、参照ゲノムと比較して対象のゲノムにおいて実際のSNPおよび/またはインデルバリエーションがあると決定され得る。しかしながら、限られた数のリードからの限られた数のk-mersのみがアーチファクトの証拠となる場合、機械および/または処理および/または他の誤りによって引き起こされ、注目する位置における真のバリエーションを示さないという可能性がある。
【0190】
示されているように、疑わしいバリアントがある場合、グラフ内にバブルが形成される。特に、リードの所与の領域のすべての中のk-mersのすべてが、参照とマッチする場合、それらは線形グラフを形成するように一列に並ぶ。しかしながら、所与の座位において塩基間に差異がある場合、差異のあるその座位でそのグラフが枝分かれする。この枝分かれは、k-mer内の任意の位置にあるものとしてよく、結果として、その差異点において、その差異を含む、10塩基k-merは、グラフ内のk-mersの残りから分岐する。そのような事例において、グラフを通じて異なる経路を形成する新しいノードが形成される。
【0191】
したがって、すべてが一致している場合、たとえば、グラフにされている所与の新しいk-mer内の配列がグラフ内でそれがアライメントする配列とマッチしている場合、その差異点までのそのk-merに対する経路は、グラフに対する経路と一般的にマッチし、線形であるが、差異点をポストし、新たにグラフにされたk-merの配列内に表される差異を受け入れるようにグラフを通る正しい経路が出現する。この分岐はグラフ内で新しいノードにより表される。そのような事例において、新しい分岐経路とマッチするグラフに追加されるべき新しいk-mersは、そのノードにおいてカウントを増やす。したがって、円弧をサポートするすべてのリードについて、そのカウントはインクリメンタルに増やされる。
【0192】
様々なそのような事例において、k-merおよび/またはそれが表すリードは、たとえば、分岐点の後に、もう一度マッチングを開始し、それにより、現在はk-merが参照配列のk-mersによって表されるグラフを通る主経路をマッチングするステップを開始する分岐点がある。たとえば、当然しばらくしてから枝分かれしたノードをサポートするリードが時間の経過とともにグラフを再連結するべきである。したがって、時間の経過とともに、そのリードに対するk-mersは主経路を再び再連結する。より具体的には、リード内の所与の座位におけるSNPについて、そのSNPから開始するk-merは、主グラフから分岐し、約10ノードについて分離したままとなるが、それは、リードと参照との間のミスマッチングのあるその座位と重なり合うk-mer毎に10個の塩基があるからである。したがって、SNPについて、11番目の位置において、リード内のその座位をカバーするk-mersは、完全一致のマッチングが再開されるときに主経路を再連結する。結果として、参照配列によって表される主グラフを再連結するために所与の座位においてSNPを有するリードのk-mersに対して10回のシフトを行う。
【0193】
上に示されているように、典型的には、参照経路である1つの主経路または直線またはバックボーンがあり、分岐がある場合、ノードのところにバブルが形成され、リードとバックボーングラフとの間に差異がある。したがって、バックボーンから分岐し、バブルを形成するいくつかのリードがあり、分岐はバリアントの存在を示し得る。グラフの処理が進むにつれ、バブルの中のバブルが、参照バックボーンに沿って形成されるものとしてよく、それにより、それらは積み重ねられ、グラフを通る複数の経路が創出され得る。そのような事例において、参照バックボーンによって表される主経路があるものとしてよく、第1の分岐の1つの経路、および第1の分岐内の第2の分岐のさらなる経路は、すべて所与のウィンドウ内にあり、各々の経路はグラフを通り、実際のバリエーションを表し得るか、またはシークエンシング誤り、および/またはPCR誤り、および/または処理誤り、および同様のものによって引き起こされるようなアーチファクトであってよい。
【0194】
そのようなグラフが作成された後、グラフを通るどの経路がサンプルゲノム内に存在する実際のバリエーションを表し、どれが単なるアーチファクトであるかが決定されなければならない。それにもかかわらず、ハンドリングまたは機械誤りを含むリードは、サンプルパイルアップ内のリードの大半によってサポートされないことが予想されるが、これは必ずしもその場合ではない。たとえば、PCR処理における誤りは、典型的には、DNAサンプルを調製するときに生じるクローニングミスの結果である場合があり、そのようなミスの結果、挿入および/または欠失がクローン配列に加えられる傾向がある。そのようなインデル誤りはリード間で一貫性がより高い場合があり、結果としてPCRクローニングにおけるミスからの同じ誤りを有する多数のリードを生成することになり得る。その結果、そのような分岐点に対するより高いカウント線が、そのような誤りがあるせいで生じ得る。
【0195】
したがって、多くの経路がグラフを通る、グラフ行列が形成された後、次の段階は、グラフを通る経路のすべてを、たとえば、左から右へ、トラバースし、それによって抽出することである。1つの経路が参照バックボーンであるが、その道に沿って様々なバブルに追随する他の経路がある。すべての経路がトラバースされ、そのカウントが表示されなければならない。たとえば、グラフが1つのスポットにおける2つの水平なバブルと、別のスポットにおける3つの水平なバブルを有する経路を含む場合、そのグラフを通る経路は(2×3)
6個ある。したがって、経路の各々は、個別に抽出される必要があり、その抽出された経路は、候補ハプロタイプと呼ばれる。そのような候補ハプロタイプは、何が配列決定された対象の実際のDNAを実際に表すことが可能であるかということに対する理論を表し、ハプロタイプアライメント、リード尤度計算、および/または遺伝型判定のうちの1つまたは複数を含む、次の処理ステップは、これらの理論のどれか1つおよび/または各々が正しい確率を求めるためにこれらの理論を検定するために使用され得る。したがって、De Bruijnグラフ再構築の実装は、検定すべき仮説のよいセットを確実に抽出する方法を表す。
【0196】
たとえば、バリアントコール機能を実行する際に、本明細書で開示されているように、所与の領域内のパイルアップにおける多数のリードが参照と一致しない場所を識別する、および識別された能動領域の周りにウィンドウを生成するなどのために能動領域識別オペレーションが実装されてよく、それによりこれらの領域のみがさらなる処理のために選択され得る。それに加えて、局所的ハプロタイプアセンブリが生じることがあり、たとえば、各所与の能動領域について、パイルアップ内のすべての重なり合うリードは「De Bruijn graph」(DBG)行列にアセンブルされ得る。このDBGから、行列を通る様々な経路が抽出されてよく、各経路は、どのような真のDNA配列が少なくとも1つの鎖上にあるかについて候補ハプロタイプ、たとえば、仮説を構成する。
【0197】
さらに、ハプロタイプアライメントが生じることがあり、たとえば、各抽出されたハプロタイプ候補は、元の参照ゲノムにアライメントされ、たとえば、Smith-Watermanアライメントされ、それが参照からのどのようなバリエーションを意味するかを決定するものとしてよい。さらに、リード尤度計算が実行されてよく、たとえば、ハプロタイプがサンプリングされた真の元のDNAであったと仮定して、各リードが各ハプロタイプに対して検定され、リードを観察する確率を推定するものとしてよい。最後に、遺伝型判定オペレーションが実装され、バリアントコールファイルが作成される。上で示されているように、これらのオペレーションのどれかまたはすべては、ソフトウェアおよび/またはハードウェアで最適な方式で実装されるように構成されるものとしてよく、様々な事例において、DBG行列を構築し、それから候補ハプロタイプを抽出することがリソース集約的で時間がかかるという性質があるため、および/または隠れマルコフモデル(HMM)評価に関与することを含み得る、ハプロタイプアライメントおよび/またはリード尤度計算を実行することがリソース集約的で時間がかかるという性質があるため、これらのオペレーション(たとえば、局所的ハプロタイプアセンブリ、および/またはハプロタイプアライメント、および/またはリード尤度計算)またはその一部は、オペレーションの1つまたは複数の機能をハード配線された形態で実装されるように、たとえば、本明細書において説明されているような集積回路によって加速化される方式で実行されるように構成され得る。様々な事例において、これらのタスクは、量子コンピューティングデバイスなどにおける1つまたは複数の量子回路によって実装されるように構成され得る。
【0198】
したがって、様々な事例において、それを実行するためのデバイス、システム、および方法は、ハプロタイプアライメントおよび/またはリード尤度計算を実行するように構成され得る。たとえば、示されているように、各抽出されたハプロタイプは、元の参照ゲノムにアライメントされ、たとえば、Smith-Watermanアライメントされ、それが参照からのどのようなバリエーションを意味するかを決定するものとしてよい。様々な例示的な事例において、スコアリングが、例示的なスコアリングパラメータ、マッチ=20.0、ミスマッチ=-15.0、ギャップオープン=-26.0、およびギャップエクステンド=-1.1などに従って行われてよく、他のスコアリングパラメータも使用されてよい。したがって、この方式で、CIGAR鎖が生成され、ハプロタイプと関連付けられて、アセンブルされたハプロタイプを作成し、アセンブルされたハプロタイプは結局、バリアントを識別するために使用され得る。したがって、このような方式において、所与のハプロタイプに関連付けられている所与のリードの尤度は、すべてのリード/ハプロタイプの組合せについて計算され得る。そのような事例において、尤度は、隠れマルコフモデル(HMM)を使用して計算され得る。
【0199】
たとえば、様々なアセンブルされたハプロタイプは、SWアライメントに類似する動的プログラミングモデルに従ってアライメントされ得る。そのような事例において、仮想行列は、たとえばDBGによって生成される、候補ハプロタイプが仮想アレイの一方の軸上に位置決めされてよく、リードが他方の軸上に位置決めされ得る場合などに生成され得る。次いで、行列に、グラフを通る抽出された経路をトラバースし、所与の経路が真の経路である確率を計算することによって生成されるスコアを書き込むものとしてよい。したがって、そのような事例において、典型的なSWアライメントプロトコルからのこのアライメントプロトコルの差異は、アレイを通る最もありそうな経路を見つけることに関して、最大尤度計算が使用され、たとえば、計算はハプロタイプへのリードのアライメントに対する全確率を提供するように構成されているHMMモデルによって実行される。したがって、実際のCIGAR鎖アライメントは、この事例では、作成される必要はない。むしろ、可能なすべてのアライメントが考慮され、その確率が総和される。ペアHMM評価は、リソースおよび時間集約的であり、したがって、集積回路内のハード配線された構成の中に、または量子コンピューティングプラットフォーム上の量子回路を介してそのオペレーションを実装することは、非常に有利である。
【0200】
たとえば、各リードは、各候補ハプロタイプと突き合わせて検定されてよく、それにより、ハプロタイプがサンプリングされた元のDNAの真の代表であると仮定してリードを観察する確率を推定する。様々な事例において、この計算は、PCRまたはシークエンシング誤り、および同様のものなどによって、ハプロタイプ候補が修正されていると思われる様々な可能な方法をモデル化するように構成され得る、「ペア隠しマルコフモデル」(HMM)と、観察されたリードに導入されるバリエーションとを評価することによって実行されてよい。そのような事例において、HMM評価では、動的プログラミング法を使用して、リード内の分岐が誤りモデルの結果であり得る確率を考慮して観察されたリードに到達する任意の一連のマルコフ状態遷移の全確率を計算し得る。したがって、そのようなHMM計算は、増幅および/またはシークエンシングアーチファクトなどによって、リードのうちの1つまたは複数に導入されている可能性のある可能なすべてのSNPおよびインデルを解析するように構成され得る。
【0201】
特に、ペアHMMは、仮想行列内で、参照候補ハプロタイプへのリードの可能なすべてのアライメントをすべての確率が加算されるそれらの各々に関連付けられている確率とともに考慮する。所与の経路に沿ったすべてのバリアントの確率のすべての総和は、加算されて、各リードに対する1つの包括的な確率が得られる。次いで、このプロセスは、すべてのペア、すべてのハプロタイプ、リードペアについて実行される。たとえば、所与の領域、たとえば、6個のハプロタイプ候補の領域と重なり合う6個のパイルアップクラスタがある場合、およびそのパイルアップが約100個のリードを含む場合、600HMMオペレーションが実行される必要がある。より具体的には、6個のハプロタイプがある場合、経路を通る6個の分岐があることになり、各分岐がその領域に対して対象の実際の遺伝子コードとマッチする正しい経路である確率が計算されなければならない。その結果、リードのすべてに対する各経路が考慮されなければならず、この所与のハプロタイプにあなたが到達することになるであろう各リードに対する確率は、計算されるべきである。
【0202】
ペア隠れマルコフモデルは、サンプリングされたDNA内の真のハプロタイプが可能な異なる検出されたリードにどのように変換され得るかに関する近似モデルである。これらの種類の変換は、PCRプロセス、他のサンプル調製ステップのうちの1つまたは複数、および/またはシークエンシングプロセスによって引き起こされる誤り、および同様のものによって遺伝子サンプル内に導入されているSNPおよびインデルの組合せであることが観察されている。図2を見るとわかるように、これらの種類の誤りを考慮するために、基礎となる3状態塩基モデルが使用されてよく、たとえば、(M=アライメントマッチ、I=挿入、D=欠失)、さらに遷移はI<->Dを除き可能である。
【0203】
図2を見るとわかるように、3状態塩基モデル遷移は、時間系列内にないが、むしろ、各配列内で位置0から始まり、第1の塩基が位置1である、候補ハプロタイプを通る進行の配列およびリード配列内にある。Mへの遷移は、両方の配列内で位置+1を意味し、Iへの遷移は、リード配列のみにおける位置+1を意味し、Dへの遷移は、ハプロタイプ配列のみにおける位置+1を意味する。同じ3状態モデルは、その上、本明細書において説明されているように、Smith-Watermanおよび/またはNeedleman-Wunschアライメントの基礎となるように構成され得る。したがって、そのような3状態モデルは、本明細書で述べているように、SWおよび/またはNWプロセスにおいて使用されてよく、それによって、アフィンギャップ(インデル)スコアリングを可能にするが、その際にギャップオープン(IまたはD状態に入る)はギャップエクステンション(IまたはD状態に留まる)より可能性が低いと仮定される。したがって、この事例において、ペアHMMは、アライメントとして見られるものとしてよく、様々な状態遷移の配列を符号化するためにCIGAR文字列が作成され得る。
【0204】
様々な事例において、3状態塩基モデルは、遷移確率が位置で異なるようにすることで複雑なものとなり得る。たとえば、M個のすべての遷移の確率に、その塩基クオリティスコアを与えられた次のリード塩基および対応する次のハプロタイプ塩基を観察する事前確率を掛けるものとしてよい。そのような事例において、塩基クオリティスコアは、シークエンシングSNP誤りの確率に変換されてよい。2つの塩基がマッチしたときに、その事前確率は、1からこの誤り確率を引いたものとみなされ、それらがミスマッチであったときに、それは、可能な3つのSNP結果があるので、誤り確率を3で除算したものとみなされる。
【0205】
上記の議論は、抽象「マルコフ」モデルに関するものである。様々な事例において、最大尤度遷移配列も決定されてよく、これは本明細書においてアライメントと呼ばれ、Needleman-Wunschまたは他の動的プログラミングアルゴリズムを使用して実行され得る。しかし、様々な事例において、バリアントコール機能を実行する際に、本明細書において開示されているように、最大尤度アライメント、または特定の任意のアライメントは、一番の関心事である必要はない。むしろ、全確率は、たとえば、グラフを通り、任意のハプロタイプ位置におけるリード位置0から、任意のハプロタイプ位置におけるリード終了位置までの可能なすべての遷移経路の確率の総和であり、各コンポーネント経路確率は単純に様々な構成要素である遷移確率の積である、ハプロタイプを与えられたリードを観察する全確率を計算することによって計算され得る。
【0206】
経路確率の総和を求めることは、上で説明されているように、仮想アレイを使用し、動的プログラミングアルゴリズムを使用することによって実行されてもよく、これにより、(0 ... N)×(0 ... M)行列の各セルにおいて、M、D、およびI遷移状態に対応する、計算された3つの確率値がある。(または、同じことであるが、3つの行列がある。)行列の上行(リード位置ゼロ)は、D状態では確率1.0に、IおよびM状態では0.0に初期化され、左列の残り(ハプロタイプ位置ゼロ)は、すべてゼロに初期化され得る。(ソフトウェアでは、初期D確率は、倍精度最大値の近く、たとえば、約2^1020に設定され、それにより、アンダーフローを回避し得るが、この係数は後で完全に正規化されてよい。)
【0207】
この3対1計算依存性は、セルが計算され得る順序を制限する。これらは、各行において左から右に計算され、行を通り上から下へ、または各列内で上から下へ進行し、右方向に進行するものとしてよい。それに加えて、それらは、反対角線波面において計算されてよく、次のステップは、すべてのセル(n,m)を計算することであり、n+mはインクリメントされたステップ数に等しい。この波面順序は、反対角線におけるすべてのセルが互いに無関係に計算され得るという利点を有する。次いで、行列の下行は、最終リード位置において、完了したアルゴリズムを表すように構成され得る。そのような事例において、ハプロタイプコーラーは、すべての下行のセルのIおよびM確率を総和することによって働く。様々な実施形態において、システムは、どのD遷移も下行内で許されないようにセットアップされ得るか、または0.0のD遷移確率は、そこで使用されて、二重カウントを回避するものとしてよい。
【0208】
本明細書において説明されているように、様々な事例において、各HMM評価は、候補ハプロタイプおよびリードペアなどの、配列ペアに動作し得る。たとえば、所与の能動領域内で、ハプロタイプのセットの各々は、リードのセットの各々に対してHMM評価され得る。そのような事例において、ソフトウェアおよび/ハードウェア入力帯域幅は、リードのセットおよびハプロタイプのセットを一度に転送し、ソフトウェアおよび/またはハードウェアにN×Mペアオペレーションを生成させることによって低減され、および/または最小にされ得る。いくつかの事例において、Smith-Watermanエバリューエータは、個別のHMMオペレーションをキューに入れるように構成され、各々はリードおよびハプロタイプデータのコピーをそれぞれ有するものとしてよい。Smith-Waterman(SW)アライメントモジュールは、線形空間内でペアHMM計算を実行するように構成され得るか、または対数確率空間内で動作し得る。これは、固定小数点値を有する非常に大きな範囲の確率値にわたって精度を保持する上で有用である。しかしながら、他の事例では、浮動小数点演算が使用され得る。
【0209】
3つの並列乗算(たとえば、対数空間内の加算)があり、次いで2つの直列加算(約5-6段階近似パイプライン)があり、次いで追加の乗算がある。そのような事例において、完全なパイプラインは、約L=12-16サイクル長である。I&D計算は、その長さの約半分であるものとしてよい。パイプラインは、1つまたは複数のすでに計算されている隣接セル(左からMおよび/またはD、上からMおよび/またはI、ならびに/あるいは左上からMおよび/またはIおよび/またはD)などから、各サイクルで2または3または5または7またはそれ以上の入力確率などの多数の入力確率を供給され得る。また、1つもしくは複数のハプロタイプ塩基、および/または1つもしくは複数のリード塩基を、たとえば関連付けられているパラメータ、たとえば、事前処理されたパラメータとともに各サイクルについて含み得る。これは、フォールスルー待ち時間の後に、サイクル毎に1つのセルに対するM&I&D結果セットを出力する。
【0210】
上で示されているように、本明細書において開示されているように、バリアントコール機能を実行する際に、De Bruijnグラフが形成されるものとしてよく、パイルアップ内のリードのすべてが同一であるときに、DBGは線形となる。しかしながら、差異がある場合。グラフは差異の領域を示す「バブル」を形成し、その結果、多数の経路が参照アライメントとのマッチから分岐し、その後、マッチングアライメントにおいて再連結する。このDBGから、様々な経路が抽出されてよく、これらの経路はたとえば、どのような真のDNA配列が少なくとも1つの鎖上にあるかに対する候補ハプロタイプ、たとえば、仮説を形成し、仮説はデータに対してHMM、または修正HMMオペレーションを実行することによって検定され得る。さらになおも、遺伝型判定が、候補ハプロタイプの可能な二倍体組合せが形成され得る場合などに使用されるものとしてよく、それらの各々について、リードパイルアップ全体を観察する条件付き確率が計算され得る。次いで、これらの結果は、ベイズ公式モジュールに送られ、リードパイルアップ全体が観察された場合に、各遺伝型が真実である絶対確率を計算するものとしてよい。
【0211】
したがって、本明細書で説明されているデバイス、システム、およびそれらの使用方法に従って、様々な事例において、遺伝型判定オペレーションが実行されてよく、遺伝型判定オペレーションは、ソフトウェアおよび/またはハードウェアでおよび/または量子処理ユニットによって最適な仕方で実装されるように構成され得る。たとえば、候補ハプロタイプの可能な二倍体組合せが形成され、各組合せについて、リードパイルアップ全体を観察する条件付き確率が、ペアHMM評価から各ハプロタイプが与えられた各リードを観察する構成要の確率を使用することなどによって計算され得る。これらの計算の結果は、ベイズ公式の中に送られ、リードパイルアップ全体が観察された場合に、各遺伝型が真実である絶対確率を計算する。
【0212】
したがって、様々な態様において、本開示は、生成され、および/または供給されるデータに対してハプロタイプまたはバリアントコールオペレーションを実行し、それに関してバリアントコールファイルを作成するシステムを対象とする。特に、本明細書において上で説明されているように、特定の事例において、バリアントコールファイルは、サンプル配列と参照配列との間の差異などの、一方の配列と他方の配列との間の差異を符号化しているデジタルまたは他のそのようなファイルであってよい。特に、様々な事例において、バリアントコールファイルは、1つまたは複数の参照ゲノムと比較したときに人の遺伝子構造における遺伝的および/または構造的バリエーションを述べるか、または他の何らかの形で詳述しているテキストファイルであってよい。
【0213】
たとえば、ハプロタイプは、人の染色体内に存在する多型などの、遺伝子、たとえばDNAおよび/またはRNAバリエーションのセットであり、したがって、子孫に伝えられ、それによって一緒に継承され得る。特に、ハプロタイプは、突然変異によって生じ得るような遺伝子のアレルの組合せ、たとえば複数の代替的形態のうちの1つを指すものとしてよく、アレルバリエーションは典型的には染色体上の同じ場所に見つかる。したがって、人のゲノムの同一性を決定する際に、様々な異なる可能なアレルのどの形態に対して特定の人の遺伝子配列がコードするのかを知ることが重要である。特定の事例において、ハプロタイプは、同じ染色体上の同じ位置に見つかる場合があるヌクレオチド多型(たとえば、SNP)の1つまたは複数、たとえば、セットを指すものとしてよい。
【0214】
典型的には、様々な実施形態において、本明細書でまた上で説明されているように、対象に対する遺伝型、たとえば、アレルハプロタイプを決定するために、個体の遺伝子配列中のSNPおよび/または挿入および/または欠失、すなわち、インデルを同時に決定するために、ハプロタイプコールプログラム、たとえば、GATKを使用するアルゴリズムなどの、ソフトウェアベースのアルゴリズムが関わるものとしてよい。特に、アルゴリズムは、処理されている遺伝子配列の1つまたは複数の能動領域におけるハプロタイプの局所的なde novoアセンブリなどに対する1つまたは複数のハプロタイプアセンブリプロトコルを伴い得る。そのような処理は、典型的には、システム内の将来の状態が現在の状態にのみ依存し、それに先行する事象の配列には依存しないと仮定した場合など、ランダムに変化するシステムを例示するために使用される確率論的および/または統計的モデルである隠れマルコフモデル(HMM)と称される処理機能のデプロイを伴う。
【0215】
そのような事例において、モデル化されるシステムはそれらの特性を有するか、または他の何らかの形で観察されない(隠れ)状態を有するマルコフ過程であると仮定される。特定の事例において、モデルは、単純動的ベイジアンネットワークを伴い得る。特に、遺伝的バリエーションを決定することに関して、その最も単純な形態において、参照配列、たとえば、仮説的ハプロタイプ、および対象のDNAまたはRNAの配列、たとえば、シークエンサから導出されたリードのセグメントを比較するときなどに、処理される配列内の所与の塩基の同一性に対する4つの可能性のうちの1つがある。しかしながら、そのようなバリエーションを決定するために、第1の事例において、対象の遺伝子コードを識別するリードアウトまたは「リード」を作成するために、対象のDNA/RNAは、たとえば、Next Gen Sequencer(「NGS」)を介して配列決定されなければならない。次に、1つまたは複数のリードを作成するために、対象のゲノムが配列決定された後、対象のDNAおよび/またはRNAを表す様々なリードは、本明細書において上で詳しく説明されているように、マッピングされ、および/またはアライメントされる必要がある。次いで、このプロセスの次のステップは、決定されたばかりの、たとえば、マッピングされおよび/またはアライメントされた、対象の遺伝子がプロトタイプ参照配列の遺伝子とどれだけ異なるかを決定することである。したがって、そのような解析を実行する際に、対象の所与の遺伝子を潜在的に表すリードは、現在決定されるべきである様々なSNPおよび/またはインデルを有するにもかかわらずプロトタイプハプロタイプの表現であると仮定される。
【0216】
特に、特定の態様において、たとえば、高速ハプロタイプコーラーにおける、HMM機能をデプロイするなどの、ハプロタイプおよび/またはバリアントコール機能を実行するなどのそれを実施するためのデバイス、システム、および方法が実現される。様々な事例において、当技術分野で知られているこれらのおよび他のそのような様々な問題を克服するために、本明細書において提示されているHMMアクセラレータは、ソフトウェアで実装されるか、ハードウェアで実装されるか、または一部はソフトウェアによっておよび/または一部はハードウェアによって実装され、および/または他の何らかの形で制御されることの組合せで実装される仕方で操作されるように構成されてよく、ならびに/あるいは量子コンピューティング実装形態を含み得る。たとえば、特定の態様において、本開示は、対象のDNAおよび/またはRNA配列同一性に関連するデータならびに/あるいは対象の遺伝情報が参照ゲノムの遺伝情報とどのように異なり得るかを決定し得る方法を対象とする。
【0217】
そのような事例において、この方法は、HMMプロトコルを使用するなどの、ハプロタイプまたはバリアントコール機能の実装形態によって実行され得る。特に、HMM機能は、本明細書で説明されている方法に従って、ハードウェア、ソフトウェアで、または加速化されたデバイスなどに載っている1つまたは複数の量子回路を介して実行され得る。そのような事例において、HMMアクセラレータは、配列決定され、マッピングされ、および/またはアライメントされたデータを受け取り、処理して、それを処理し、たとえば、バリアントコールファイルを作成し、さらには処理済みデータをシステム全体に伝送して戻すように構成され得る。したがって、この方法は、データがソフトウェア制御CPUもしくはGPUまたはさらにはQPUなどのプロセッサから加速化されたHMMを実装するハプロタイプコーラーに送信され得るシステムをデプロイするステップを含むものとしてよく、ハプロタイプコーラーは、FPGA、ASIC、もしくは構造化ASICなどのマイクロプロセッサチップ上にデプロイされるか、または1つもしくは複数の量子回路によって実装され得る。この方法は、データを処理してHMM結果データを作成するためのステップをさらに含むものとしてよく、次いで、それらの結果はCPUおよび/またはGPUおよび/またはQPUにフィードバックされ得る。
【0218】
特に、一実施形態において、図3Aを見るとわかるように、HMMアクセラレータを備えるバイオインフォマティクスパイプラインシステムが実現される。たとえば、一事例において、バイオインフォマティクスパイプラインシステムは、バリアントコールシステム1として構成され得る。システムは、ハードウェアで実装されているものとして例示されているが、量子コンピューティングプラットフォームなどの、1つまたは複数の量子回路を介して実装されてもよい。特に、図3Aは、HMMインターフェース構造の高水準の図を示している。特定の実施形態において、バリアントコールシステム1は、HMMオペレーションなどの、バリアントコールオペレーションの少なくとも一部を加速するように構成される。したがって、様々な事例において、バリアントコールシステムは、HMMシステム1として本明細書において参照され得る。システム1は、配列決定された遺伝子配列を1つまたは複数の参照配列と比較するなどのために、遺伝情報のシークエンシングおよび/または処理に関係する1つまたは複数のルーチンを実行するように構成されている1つまたは複数の中央演算処理装置(CPU/GPU/QPU)1000を有するサーバを含む。
【0219】
それに加えて、システム1は、FPGA、ASIC、またはsASICなどの、マイクロチップ7を備える、拡張カードなどの周辺デバイス2を備える。いくつかの事例において、本明細書で述べられている様々なオペレーションを実行するために1つまたは複数の量子回路が実現され構成され得る。また、ASICという用語は、適切ならば、構造化ASIC(sASIC)を等しく指すものとしてよいことに留意されたい。周辺デバイス2は、CPU/GPU/QPU1000をチップ7と接続する、パラレルまたはシリアルバスなどの、インターコネクト3およびバスインターフェース4を備える。たとえば、デバイス2は、PCI、PCI-X、PCIe、またはQPI(クイックパスインターコネクト)などの、ペリフェラルコンポーネントインターコネクトを備えるものとしてよく、低遅延、高データ転送速度などのために、CPU/GPU/QPU1000を周辺デバイス2に動作可能におよび/または通信可能に接続するよう適合されている、バスインターフェース4を備え得る。したがって、特定の事例において、インターフェースは、マイクロチップ7に関連付けられているペリフェラルコンポーネントインターコネクトエクスプレス(PCIe)4であってよく、このマイクロチップはHMMアクセラレータ8を備える。たとえば、特定の事例において、HMMアクセラレータ8は、加速化されたHMM機能を実行するように構成され、たとえば、HMM機能は、いくつかの実施形態において、FPGA、ASIC、もしくはsASICのハードウェアで、または1つもしくは複数の適切に構成されている量子回路を介して少なくとも部分的に実装されてよい。
【0220】
特に、図3Aは、HMMタスクを含むなど、バリアントコール機能の1つまたは複数のプロセスを実行するために、複数の処理エンジン13a〜13
m+1などの、1つまたは複数のエンジン13の例示的な編成を有するHMMアクセラレータ8の高水準の図を示している。したがって、HMMアクセラレータ8は、データディストリビュータ9、たとえば、CentComと、1つまたは複数のインスタンス13として編成されるか、または他の何らかの形で含むものとしてよい1つまたは多数の処理クラスタ11〜11n+1とから構成されるものとしてよく、たとえば、各インスタンスは、小エンジン13a〜13
m+1などの処理エンジンとして構成され得る。たとえば、ディストリビュータ9は、CPU/GPU/QPU1000などからデータを受信し、そのデータを多数のHMM処理クラスタ11のうちの1つまたは複数に分配するか、または他の何らかの形で転送するように構成され得る。
【0221】
特に、いくつかの実施形態において、ディストリビュータ9は、オンボードPCIeインターフェース4とHMMアクセラレータモジュール8との間に論理的に位置決めされてよく、たとえば、インターフェース4は、インターコネクトまたは他の適切に構成されているバス5、たとえば、PCIeバスなどでディストリビュータ9と通信する。ディストリビュータモジュール9は、1つまたは複数のクラスタバス10などで1つまたは複数のHMMアクセラレータクラスタ11と通信するように適合され得る。たとえば、HMMアクセラレータモジュール8は、クラスタ11a〜11
n+1のアレイとして構成されるか、または他の何らかの形で含むものとしてよく、たとえば、各HMMクラスタ11は、クラスタハブ11として構成されるか、または他の何らかの形で含むものとしてよく、および/または1つもしくは複数のインスタンス13を含むものとしてよく、そのインスタンスは、それによって受信されたデータに対して1つまたは複数のオペレーションを実行するように適合されている処理エンジン13として構成され得る。したがって、様々な実施形態において、各クラスタ11は、クラスタハブ11a〜11
n+1として形成されるか、または他の何らかの形で含むものとしてよく、ハブの各々は、多数のHMMアクセラレータエンジンインスタンス13a〜13
m+1に動作可能に関連付けられるものとしてよく、たとえば、各クラスタハブ11は、データをクラスタ11内の複数の処理エンジン13a〜13
m+1に向けるように構成され得る。
【0222】
様々な事例において、HMMアクセラレータ8は、リード形式などの、対象の配列決定された遺伝子コードの各塩基を参照配列の様々の知られているまたは生成された候補ハプロタイプと比較し、考慮されている位置における所与の塩基が関連するハプロタイプとマッチするかまたはマッチしないかのいずれかである、たとえば、リードがSNP、挿入、または欠失を含み、それによって結果としてその位置における塩基のバリエーションが考慮される確率を決定するように構成される。特に、様々な実施形態において、HMMアクセラレータ8は、本明細書において以下でより詳しく説明されているようなこれらの状態、マッチ(「M」)、挿入(「I」)、または欠失(「D」)の各々の間に入るリードの塩基の配列に対する遷移確率を割り当てるように構成される。
【0223】
より具体的には、構成に応じて、HMM加速機能は、CPU/GPU/QPU1000および/またはマイクロチップ7などによって、いずれかのソフトウェアで実装されてよく、および/またはハードウェアで実装されてよく、周辺拡張カードもしくはボード2上に位置決めされるような、マイクロチップ7内に存在し得る。様々な実施形態において、機能は、たとえばCPU/GPU/QPU1000などによって実行される、ソフトウェアとして部分的に実装され、部分的にハードウェアとして、チップ7上に、または1つもしくは複数の量子処理回路を介して実装され得る。したがって、様々な実施形態において、チップ7は、CPU/GPU/QPU1000のマザーボード上に存在してよいか、または周辺デバイス2の一部であり得るか、またはその両方である。その結果、HMMアクセラレータモジュール8は、様々なインターフェース、たとえば、3、5、10、および/または12を備えるか、または他の何らかの形で関連付けられ、それにより、データを処理エンジン13に、および処理エンジン13から効率よく転送することを可能にする。
【0224】
したがって、図2および図3を見るとわかるように、様々な実施形態において、バリアント、たとえば、ハプロタイプ、コール機能を実行するように構成されているマイクロチップ7が実現される。マイクロチップ7は、これに直接結合される、たとえば、コンピュータのマザーボード上に搭載される、または1つまたは複数のインターコネクト、たとえば、3、4、5、10、および/または12などを介して、CPU/GPU/QPU1000に動作可能に結合されている周辺デバイス2の一部として搭載されるなど、それに間接的に結合される、ようなCPU/GPU/QPU1000に関連付けられ得る。この事例において、マイクロチップ7は、周辺デバイス2上に存在する。マイクロチップとして構成されているが、アクセラレータは量子処理ユニットの1つまたは複数の量子回路として構成されることも可能であると理解されるべきであり、量子回路は、本明細書で開示されている機能のうちの1つまたは複数を実行するように1つまたは複数の処理エンジンとして構成される。
【0225】
したがって、周辺デバイス2は、インターフェース3、たとえば、DMAなどを介して、周辺デバイス2をコンピュータおよび/またはサーバの中央演算処理装置(CPU/GPU/QPU)1000に接続するなどのためにパラレルまたはシリアル拡張バス4を備え得る。特定の事例において、周辺デバイス2および/またはシリアル拡張バス4は、接続部5などを介して、マイクロチップ7と通信するか、または他の何らかの形で備えるように構成されているペリフェラルコンポーネントインターコネクトエクスプレス(PCIe)であってよい。本明細書において説明されているように、マイクロチップ7は、HMMアクセラレータ8として少なくとも部分的に構成され得るか、または他の何らかの形で備え得る。HMMアクセラレータ8は、マイクロチップ7の一部として、たとえばハード配線されるものとして、および/またはそれと関連して実行されるコードとして構成されてよく、PCIeインターフェース4などで、CPU/GPU/QPU1000によってマイクロチップ7に供給されるデータに対して、隠れマルコフモデルの1つまたは複数のオペレーションを実行するなどのために、バリアントコール機能を実行するように構成される。同様に、1つまたは複数のバリアントコール機能が実行された後、たとえば、1つまたは複数のHMMオペレーションが実行された後、その結果は、接続部3などを介して、チップ7のHMMアクセラレータ8からバス4でCPU/GPU/QPU1000に転送され得る。
【0226】
たとえば、特定の事例において、情報を処理しおよび/または転送し、ならびに/あるいは命令を実行するためのCPU/GPU/QPU1000は、HMMアクセラレータ8として少なくとも部分的に構成されているマイクロチップ7とともに実現される。CPU/GPU/QPU1000は、CPU/GPU/QPU1000とマイクロチップ7のHMMアクセラレータ8との間の通信を円滑にするように適合されているインターフェース5でマイクロチップ7と通信し、したがって、CPU/GPU/QPU1000をマイクロチップ7の一部であるHMMアクセラレータ8に通信可能に接続され得る。これらの機能を円滑にするために、マイクロチップ7は、たとえば、1つまたは複数のクラスタ11を介して、データを多数のHMMエンジン13に転送するように構成されている、CentComであってよい、ディストリビュータモジュール9を備え、各エンジン13は、データの受信および処理を、HMMプロトコルをそのデータに対して実行することなどによって行い、最終値を計算し、その結果を出力し、それを繰り返すように構成される。様々な事例において、HMMプロトコルの実行は、本明細書において以下で説明されているように、1つまたは複数の遷移確率を決定するステップを含み得る。特に、各HMMエンジン13は、それに関して最終総和値を作成し出力するためにHMM仮想行列の生成および/または評価の1つまたは複数などを含むジョブを実行するように構成されてよく、最終総和値は、本明細書において以下で説明されているように、コールされた塩基がマッチするか、または仮説的ハプロタイプ配列における対応する塩基と異なる確からしい尤度を表す。
【0227】
図3Bは、図3AのHMMクラスタ11の詳細な図を示している。様々な実施形態において、各HMMクラスタ11は、1つまたは複数のHMMインスタンス13を含む。チップまたは量子コンピューティングプロセッサなどに用意されるリソースの量に従って望むようなクラスタの1つまたは多数が実現され得る。特に、HMMクラスタが実現されてよく、このクラスタは、クラスタハブ11として構成される。クラスタハブ11は、ディストリビュータ9から1つまたは複数のジョブ20に関連するデータを受け取り、1つまたは複数のHMMインスタンスバス12などを介して1つまたは複数の、たとえば、複数のHMMインスタンス13にさらに通信可能に接続され、これにクラスタハブ11がジョブデータ20を伝送する。
【0228】
システム全体を通してのデータの転送に対する帯域幅は、比較的低い帯域幅のプロセスであってよく、ジョブ20が受け取られた後、システム1は、記憶のためチップ7を出ることなくジョブを完了するように構成され得る。様々な実施形態において、1つのジョブ20aが所与の時刻に1つの処理エンジン13aに送信されるが、いくつかのジョブ20
a〜nがクラスタハブ11によっていくつかの異なる処理エンジン13a〜13
m+1に分配されてよく、たとえば、処理エンジン13の各々は、単一のジョブ20、たとえば、1つまたは複数のリードと1つまたは複数のハプロタイプ配列との間の単一の比較を、並列方式で、高速に実行している。以下で説明されているように、そのようなジョブ20の実行は、典型的には、仮想行列の生成を伴うものとしてよく、それによって、対象の「リード」配列は、1つまたは複数の、たとえば2つの、仮説的ハプロタイプ配列と比較され、それにより、それらの間の差異を決定し得る。そのような事例において、単一のジョブ20は、たとえば塩基毎に、行われる各比較に対して処理される必要がある中に多数のセルを有する1つまたは複数の行列の処理を伴い得る。ヒトゲノムは約30億塩基対なので、ヒトゲノムの30Xオーバーサンプリング(関連付けられているすべてのHMMジョブの行列内の約20兆個のセルに相当する)を解析するときに実行されるべき異なるジョブは10億から20億程度になり得る。
【0229】
したがって、本明細書で説明されているように、各HMMインスタンス13は、CPU/GPU/QPU1000からそれによって受け取られたデータなどの、配列データに対して、HMMプロトコル、たとえば、HMM行列の生成および処理を実行するように適合され得る。たとえば、上で説明されているように、DNAまたはRNAなどの対象の遺伝物質のシークエンシングを行う際に、DNA/RNAは、たとえば約100塩基長までの、いくつかのセグメントに分けられる。次いで、これらの100個の塩基セグメントの同一性は、自動化シークエンサなどによって決定され、Phredクオリティスコアとともにリードの両方の各塩基同一性を記憶するFASTQテキストベースファイルまたは他の形式に「読み込まれる」(たとえば、典型的には、対数スケールで0から63の間の数。スコア0はコールされた塩基が正しい最小の信頼度を示し、20から45の間のスコアは一般的に比較的正確であると認められ得る)。
【0230】
特に、上で示されているように、Phredクオリティスコアは、シークエンシングプロセッサによって、たとえば、自動化DNA/RNAシークエンサによって、生成される核酸塩基同一性の識別のクオリティを測定するクオリティ指標である。したがって、各リード塩基は、シークエンサがその特定の識別のクオリティをどのようなクオリティに評価したかに基づくそれ独自のクオリティ、たとえば、Phred、スコアを含む。Phredは、それがコールされた塩基同一性が正しいとシークエンサが推定する際の信頼度を表す。次いで、このPhredスコアは、以下で詳しく説明されているように、実装されたHMMモジュール8によって使用され、たとえば、マッチ状態を出入りする、マッチ、挿入、および/または欠失遷移確率を決定することなどによって、それのマッピングおよび/またはアライメント先のハプロタイプと比較してリードにおける各コールされた塩基の正確さをさらに決定する。様々な実施形態において、システム1は、隣接する塩基/スコアおよび/または隣接するDNAの断片を考慮し、そのようなファクタが調査対象の、塩基、たとえば、セルのPhredスコアに影響を及ぼすことを可能にすることなどによって、初期Phredスコアを修正するか、または他の何らか形で調節することを、それに対するHMMプロトコルの実行前に行い得ることに留意されたい。
【0231】
そのような事例において、図4を見るとわかるように、システム1、たとえば、コンピュータ/量子ソフトウェアは、探索され、および/またはシステム1全体を通して様々なコアおよび利用可能なスレッド1007の間で並列化され得るいくつかのジョブ20
nに分けられ得る、本明細書で説明されているようなさらなる処理を他の何らかの形で受けるものとしてよい配列決定されたゲノム内の様々な能動領域500
nを決定し、識別し得る。たとえば、そのような能動領域500は、配列決定されたゲノムと参照ゲノムとの間のバリエーションの発生源であるとして識別され得る。特に、CPU/GPU/QPU1000は、実行し、能動領域500a、500b、および500cを識別し、現在調査されている能動領域500a〜cに基づき、たとえば、適切に構成されたアグリゲータ1008を介して、実行されるべき様々な異なるジョブ20
nをコンパイルしアグリゲートする多数のスレッド1007を有するものとしてよい。適切な数のスレッド1007が、システム1を最大効率で実行させられるようにするために使用されるものとしてよく、たとえば、より多くのスレッドが時間をあまり能動的に使わずに待機する。
【0232】
識別され、コンパイルされ、および/またはアグリゲートされた後、スレッド1007/1008は、次いで、能動的ジョブ20を、たとえばファイアアンドフォーゲット方式で、PCIeインターフェース4などを介して、HMMモジュール8のデータディストリビュータ9、たとえば、CentComに転送し、次いで、マッピングおよび/またはアライメント先の対応する能動領域500までマッチングされて戻るようにHMM8が出力データを送り返すのを待ちながら異なるプロセスに移る。次いで、データディストリビュータ9は、たとえばジョブ毎に、様々な異なるHMMクラスタ11にジョブ20を分配する。すべてが効率よく実行されている場合、これは、先入れ先出し形式であってよいが、そのようでなくてもよい。たとえば、様々な実施形態において、生ジョブデータおよび処理済みジョブ結果データは、利用可能になったときにシステムを通してシステム全体に送信されてよい。
【0233】
特に、図2、図3、および図4を見るとわかるように、様々なジョブデータ20は、データの4Kバイトページにアグリゲートされてよく、これは、PCIe4を介して、CentCom9に送られCentCom9を通り、処理エンジン13に、たとえば、クラスタ11を介して送信されるものとしてよい。送信されるデータの量は、4Kバイトより多くても少なくてもよいが、典型的にはデータの4K(たとえば、1024)ページ当たり約100HMMジョブを含む。特に、これらのデータは、次いで、データディストリビュータ9によって取り込まれ、各クラスタ11に供給され、たとえば、1つの4Kページは、1つのクラスタ11に送信される。しかしながら、所与のジョブ20は、利用可能になったクラスタ、およびそれがいつなのかに基づき、所与のクラスタ11に送信され得るので、そうである必要はない。
【0234】
したがって、本明細書で提示されているようなクラスタ11のアプローチは、着信データを処理エンジン13に高速に効率よく分配する。特に、データがCPU/GPU/QPU1000から、たとえば、DMA接続3でPCIeインターフェース4に到達すると、受信されたデータは、次いで、PCIeバス5でバリアントコーラーマイクロチップ7のCentComディストリビュータ9に送信され得る。次いで、ディストリビュータ9は、1つまたは複数のクラスタ専用バス10などで、データを1つまたは複数のHMM処理クラスタ11に送信し、次いで、クラスタ11は、データを、処理などのために、たとえば、1つまたは複数のインスタンスバス12を介して、1つまたは複数の処理インスタンス13に伝送するものとしてよい。この事例において、PCIeインターフェース4は、たとえば長期間にわたって、フルタイムで、システム1が実行されており、ジョブ20が処理されている期間に、およびPCIeインターフェース4で、1つまたは複数のCPU1000に送り返されるべき処理済みHMMデータの出力にも遅れずに追随しながら、ビジーであるHMMクラスタ11
a-(n+1)の1つまたは複数、たとえば、すべての中でHMMアクセラレータインスタンス13
a-(m+1)の1つまたは複数、たとえばすべてを保持できる速度など、高速に周辺拡張バス5、ディストリビュータ9、および/またはクラスタ10および/またはインスタンス12バスを通じてデータを提供するように適合される。
【0235】
たとえば、HMMアクセラレータインスタンス13のうちの1つまたは複数に対してアイドル時間をもたらすインターフェース3、5、10、および/または12における不効率は、システム1の処理時間全体に直接的な影響を及ぼし得る。特に、ヒトゲノムを解析するときに、様々なHMMクラスタ11に分配され、1時間未満、45分未満、30分未満、20分未満など、15分、10分、5分、またはそれ以下を含む時間などの期間にわたって処理される必要がある異なるジョブ20は20億程度以上あり得る。
【0236】
したがって、図4では、上で一般的に説明されているように、システム1のソフトウェアおよび/またはハードウェア全体の例示的なデータフローの概要を述べている。図4を見るとわかるように、システム1は、PCIeバス5などで、たとえば、PCIeインターフェース4とディストリビュータ9、たとえば、CentComとの間で、データを転送するように一部は構成され得る。それに加えて、システム1は、1つまたは複数のクラスタバス10などで、たとえば、ディストリビュータ9と1つまたは複数のHMMクラスタ11との間で、受信されたデータを転送するように一部はさらに構成され得る。したがって、様々な実施形態において、HMMアクセラレータ8は、HMM機能の1つまたは複数のプロセスを実行するように構成されている1つまたは複数のクラスタ11などの、1つまたは複数のクラスタ11を備え得る。そのような事例において、CentCom9をHMMクラスタ11に接続する、クラスタバス10などのインターフェースがある。
【0237】
たとえば、図5は、HMMモジュール8を出入りする、たとえば、クラスタモジュールなどを出入りする、インターフェースを示す高水準図である。図6を見るとわかるように、各HMMクラスタ11は、専用クラスタバス10を通じてCentComデータディストリビュータ9と通信する、たとえば、CentComデータディストリビュータ9からデータを受信し、および/またはCentComデータディストリビュータ9に最終結果データ、たとえば、総和データを送信するように構成され得る。特に、適切なインターフェースまたはバス5は、それがPCIeインターフェース4がデータディストリビュータ9と通信することを可能にする限り用意されてよい。より具体的には、バス5は、データディストリビュータ9と通信する際に有用な解釈論理を備えるインターコネクトであってよく、その解釈論理は、この機能を提供するために採用されている任意のプロトコルに適応できるように構成され得る。特に、様々な事例において、インターコネクトは、PCIeバス5として構成されてよい。
【0238】
それに加えて、クラスタ11は、本明細書において単一のまたは多数のクロック領域が使用されるように構成されてよく、したがって、1つまたは複数のクロックは、クラスタ11内に存在し得る。特定の事例において、多数のクロック領域が提供され得る。たとえば、より低速のクロックが、たとえば、クラスタ11との間の、通信などのために用意され得る。それに加えて、本明細書で説明されている様々な状態計算を実行する際に使用するためにHMMインスタンス13によって使用され得るより速い、たとえば、高速の、クロックが用意され得る。
【0239】
特に、様々な実施形態において、図6を見るとわかるように、システム1は、第1の事例において、データディストリビュータ9が既存のCentCom IPを利用するときに、ガスケットなどのカラーが提供され得るようにセットアップされてよく、ガスケットは、HMMクラスタインターフェースまたはバス10からCentComインターフェース5に、およびCentComインターフェース5からHMMクラスタインターフェースまたはバス10に信号を変換するように構成される。たとえば、HMMクラスタバス10は、CPU/GPU1000をHMMアクセラレータモジュール8の様々なクラスタ11に通信可能に、および/または動作可能に接続し得る。したがって、図6を見るとわかるように、各ハプロタイプおよび/または各リードに対する構造化された書込みおよび/または読出しデータは、システム1全体に送信され得る。
【0240】
ジョブ20がHMMエンジンに入力された後、HMMエンジン13は、典型的には、a)IDLEであれば即座に、またはb)その現在割り当てられているタスクを完了した後に、のいずれかで開始し得る。各HMMアクセラレータエンジン13は、ピンポン入力を取り扱うことができ(たとえば、一方のデータセットを他方のデータセットがロードされている間に操作しているものとしてよい)、それにより、ジョブ間のダウンタイムを最小限度に抑えられることに留意されたい。それに加えて、HMMクラスタカラー11は、データディストリビュータ9によって送信された入力ジョブ20を自動的に受け取り、それを新しいジョブを受信することができるクラスタ11内のHMMエンジンインスタンス13のうちの1つに割り当てるように構成され得る。特定のジョブ20に対して特定のHMMエンジンインスタンス13を選択することができるコントロールがソフトウェア側にある必要はない。しかしながら、様々な事例において、ソフトウェアは、そのようなインスタンスを制御するように構成され得る。
【0241】
したがって、上記に照らして、システム1は、結果データをCPU/GPU/QPUに転送して戻したときに合理化され、この効率のおかげで、結果を役立てるためにCPU/GPU/QPUに戻る必要があるデータはあまりない。これは、システムがシステム構成に応じて、約30分以下、たとえば、約25もしくは約20分以下、たとえば、約10もしくは約7分以下、さらには約5もしくは3分以下を含む、約18もしくは約15分以下、のバリアントコールオペレーションを達成することを可能にする。
【0242】
図6は、FPGAまたはASIC7上のハードウェアアクセラレータ8内の例示的なHMMエンジン13内の様々な機能ブロックの高水準ビューを示す。特に、ハードウェアHMMアクセラレータ8内に、多数のクラスタ11があり、各クラスタ11内に、多数のエンジン13がある。図6は、HMMエンジン13の単一のインスタンスを示している。図6を見るとわかるように、エンジン13は、インスタンスバスインターフェース12、複数のメモリ、たとえばHMEM16およびRMEM18、様々な他のコンポーネント17、HMM制御論理15、さらには結果出力インターフェース19を備えるものとしてよい。特に、エンジン側では、HMMインスタンスバス12は、メモリ、HMEM16およびRMEM18に動作可能に接続され、クラスタハブ11と通信するインターフェース論理を備えるものとしてよく、そのハブはディストリビュータ9と通信し、次いでこれはCPU/GPUおよび/またはサーバ1000によって実行されているバリアントコールソフトウェアと通信するPCIeインターフェース4と通信している。したがって、HMMインスタンスバス12は、データをCPU1000から受信し、それをメモリ、たとえば、HMEMおよびRMEMのうちの1つまたは複数にロードする。この構成は、1つまたは複数の量子回路でも実装され、しかるべく適合され得る。
【0243】
これらのインスタンスにおいて、少なくとも1つまたは2つまたはそれ以上のハプロタイプ、たとえば、2つのハプロタイプが、たとえば、HMEM16に、たとえばRMEM18内にロードされる所与のリード配列毎に、ロードされ、このことが多数のハプロタイプがロードされたときに結果としてPCIeバス5の帯域幅にかかる負担を緩和するように十分なメモリ空間が割り振られるべきである。特定の事例において、2つのハプロタイプおよび2つのリード配列がそれぞれのメモリにロードされてよく、それにより、4つの配列が関連するすべての組合せで一緒に処理されることを可能にし得る。他の事例において、4個、または8個、または16個の配列、たとえば、配列ペアがロードされ、同様にして、組合せで処理され、たとえば、望んだときに帯域幅をさらに緩和するものとしてよい。
【0244】
それに加えて、十分なメモリが確保され得、ピンポン構造がその中に実装され、メモリがメモリのピン側などで新しいジョブ20aをロードされると新しいジョブの信号が示され、制御論理15は、本明細書において以下で説明されているように、行列を生成し、必要な計算を実行することなどによって、新しいジョブ20aを処理することを開始し得る。したがって、これは、別のジョブ20bをロードするために利用可能なメモリのポン側を残し、これは第1のジョブ20aが処理されている間に中にロードされてよく、第1のジョブ20aが終了したときに、第2のジョブ20bが制御論理15によって処理されることが即座に開始し得る。
【0245】
そのような事例において、ジョブ20bに対する行列は、第1のジョブ20aの処理の終了から第2のジョブ20bの処理の開始まで、事実上ダウンタイムなし、たとえば1もしくは2クロックサイクルであるように前処理され得る。したがって、メモリ構造のピンとポンの両側を利用したときに、HMEM16は、典型的には、4個のハプロタイプ配列、たとえば、2つのピースを記憶してよく、RMEM18は、典型的には、2個のリード配列を記憶し得る。このピンポン構成は、少し余分なメモリ領域を単に必要とするが、エンジン13のスループットの二重化を可能にするので、有用である。
【0246】
処理中および/または処理後に、メモリ16、18は、以下で説明されているように、「Priors」データに関係する様々な情報を計算するように構成されている、遷移確率計算機およびルックアップテーブル(LUT)ブロック17aに送り、次いで、事前結果データをM、I、およびD状態計算機ブロック17bに送り込み、遷移確率を計算するときに使用する。1つまたは複数のスクラッチRAM17cも含まれ、たとえば、スワスの境界におけるM、I、およびD状態、たとえば、処理しているスワスの下行の値を保持し、示されているように、様々な事例において、これはスワス35の長さに比例するように長さが適切な量のセル、たとえば、約10セルであるものとしてよい。
【0247】
それに加えて、別個の結果出力インターフェースブロック19が、総和が終了したときにそれらが、たとえば、4個の32ビットワードが、CPU/GPU/QPU1000のバリアントコールソフトウェアに伝送されて即座に戻され得るように含まれ得る。この構成は、システム1、特にM、I、およびD計算機17bが、たとえば、結果をクリアするのにジョブ20を実行するほどの時間がかからない限り、出力インターフェース19がクリアするのを待つのを妨げられないように適合され得ることに留意されたい。したがって、この構成では、メモリをロードする、MID計算を実行する、および結果を出力するなどの、システム全体のパイプラインを形成するように協力して機能する3つのパイプラインステップがあり得る。さらに、所与のHMMエンジン13は、それ専用の出力インターフェース19を備える多数あるうちの1つであるが、それらはデータディストリビュータ9に戻る共通インターフェース10を共有し得ることに留意されたい。したがって、クラスタハブ11は、衝突を回避するためにHMMアクセラレータ8を通じて情報の転送(「xfer」)を管理する管理能力を備える。
【0248】
したがって、以下では、上で一般的に概要を述べたように、ハプロタイプおよびリード配列データを受け取り、それを処理し、それに関連する結果データを出力するときのHMMエンジン13の各モジュール内で実行されるプロセスを詳述する。特に、HMMクラスタ11内の、HMMエンジン13における高帯域計算は、上で説明されているように、マッチ(M)、挿入(I)、および欠失(D)状態値を計算し、および/または更新することに向けられており、これらは、調査されている特定のリードがハプロタイプ参照さらにはそれの範囲とマッチするかどうかを決定する際に使用される。特に、リードはリード内の各塩基に対するPhredスコアanf GOP値とともに、ディストリビュータ9からクラスタ11に伝送され、それによって、処理のために特定の処理エンジン13に割り当てられる。次いで、これらのデータは、処理エンジン13のM、I、およびD計算機17によって、リード内のコールされた塩基が、正しい、および/またはハプロタイプ内のそれぞれの塩基とのマッチである、またはバリエーションの産物である、たとえば、挿入もしくは欠失である可能性が高いか、または低いかを決定し、ならびに/あるいはバリエーションがある場合、そのようなバリエーションが、ハプロタイプ内の真の変動または配列生成および/またはマッピングおよび/またはアライメントシステムにおける誤りのアーチファクトの起こりそうな結果であるかどうかを決定するために使用される。
【0249】
上で示されているように、そのような解析の一部は、MID計算機17が、マッチ状態から別のマッチ状態へ、またはマッチ状態から挿入状態もしくは欠失状態のいずれかへなど、参照と比較する一方のM、I、またはD状態から他方のM、I、またはD状態へ進むリードにおける一方の塩基から他方の塩基への遷移確率を決定するステップを含む。そのような決定を行う際に、関連付けられている遷移確率の各々は、リードと参照との間の観察されたバリエーションが真のバリエーションであり、単なる何らかの機械もしくは処理の誤りでないかどうかを評価するときに決定され考慮される。これらの目的のために、考慮される各塩基に対するPhredスコアは、比較においてマッチ状態から挿入もしくは欠失、たとえば、ギャップ、状態に進むなど、マッチ状態を出入りする遷移確率を決定する際に有用である。同様に、ギャップ状態を継続するか、またはギャップ状態、たとえば、挿入もしくは欠失状態からマッチ状態に戻る遷移確率も、決定される。特定の事例において、欠失または挿入状態を出入りする、たとえば、ギャップコンティニュエーション状態を出る確率は、固定値であってよく、本明細書ではギャップコンティニュエーション確率またはペナルティとして参照され得る。それにもかかわらず、様々な事例において、そのようなギャップコンティニュエーションペナルティは、浮動であり、したがって、システム構成の精度要求に応じて変化を受けるものとしてよい。
【0250】
したがって、図7および図8に示されているように、M、I、およびD状態値の各々は、可能な各リードおよびハプロタイプ塩基対合について計算される。そのような事例において、行列の一方の軸上で評価されるリード配列および他方の軸上の関連付けられているハプロタイプ配列を含むセルの仮想行列30が形成され、たとえば、行列内の各セルは、リードおよびハプロタイプ参照における塩基位置を表す。したがって、リードおよびハプロタイプ配列の各々の長さが100塩基である場合、行列30は、100×100セルを含み、その所与の一部は、この特定のリードがこの特定の参照とマッチする尤度および/または程度を決定するために処理される必要があり得る。したがって、事実上形成された後、行列30は、次いで、図7および図8に示されているように、リード配列内の一方の塩基から別の塩基に移動し、それをハプロタイプ配列の塩基と比較したときに生じる様々な状態遷移を決定するために使用され得る。特に、処理エンジン13は、多数のセルが、制御論理15で行列をトラバースするときに並列および/または逐次方式で処理されるように構成される。たとえば、図7に示されているように、仮想処理スワス35が伝搬し、行列30を横断して下り、たとえば、左から右へ移動し、行列30の個別のセルを右から左に対角線上を下って処理してゆく。
【0251】
より具体的には、図7を見るとわかるように、行列30内の各個別の仮想セルは、コールされた塩基の同一性の性質を評価するために計算される必要があるM、I、およびD状態値を含み、図7に示されているように、このプロセスにおける各セルに対するデータ依存関係が明確に見える。したがって、処理されている現在のセルの所与のM状態を決定するために、現在のセルの対角線上で上にあるセルのマッチ、挿入、および欠失状態は、現在のセルに押し込まれ、現在計算されているセルの状態の計算で使用される必要がある(たとえば、それにより、行列を通る対角線方向、下方、前方の進行は、マッチングを示す)。
【0252】
しかしながら、I状態を決定するためには、現在のセルの真上にあるセルに対するマッチおよび挿入状態のみが処理されている現在のセル内に押し込まれる必要がある(したがって、挿入状態を続けているときの垂直下方の「ギャップ」進行)。同様に、D状態を決定するためには、現在のセルのすぐ左にあるセルに対するマッチおよび欠失状態のみが現在のセル内に押し込まれる必要がある(したがって、欠失状態を続けているときの水平横断方向の「ギャップ」進行)。図7を見るとわかるように、セル1(一番上の行内の斜線を施したセル)の計算が開始した後、セル2(第2の行内の斜線を施したセル)の処理も、セル1から結果が返るのを待つことなく開始することもできるが、それは、行2内のこのセルと処理が始まった行1のセルとの間にデータ依存関係がないからである。これは、処理が赤い矢印で示されているように下方に、そして左に進行する逆対角線35を形成する。この逆対角線35処理アプローチは、システム全体の処理効率およびスループットを高める。同様に、セル1内で生成されるデータは、即座に、前方へ押されて下のセルに送られ、前方へ押されて一番上のセル1の右に送られ、それによって、スワス35を前方へ前進させることができる。
【0253】
たとえば、図7は、ハードウェア処理フローを示す例示的なHMM行列構造35を示している。行列35は、水平軸の上エッジに沿って走るように位置決めされている、たとえば、36塩基を含む、ハプロタイプ塩基インデックスを含み、セルの構造からそのような方式で垂直軸の側エッジに沿って落下するように位置決めされている塩基リードインデックス、たとえば、10塩基をさらに含み、セルの選択はM、I、およびD確率状態、および現在の状態から隣接する状態に遷移する遷移確率を初期値として書き込まれてよい。そのような事例において、上でより詳しく説明されているように、マッチ状態からマッチ状態への移動の結果、行列30を通る前方対角線進行が行われ、マッチ状態から挿入状態への移動の結果、垂直下方の進行ギャップが生じ、マッチ状態から欠失状態への移動の結果、水平進行ギャップが生じる。したがって、図8に示されているように、所与のセルについて、各セルについてマッチ、挿入、および欠失状態を決定したときに、その3つの隣接するセルのマッチ、挿入、および欠失確率が使用される。
【0254】
図7の下方の矢印は、データ依存関係に従って仮想行列に沿って漸次移動する処理スワスまたは波35を作成するように構成されている処理エンジンの並列的および逐次的な性質を表すが、構造30内の各特定のセルに対するM、I、およびD状態を決定することについては図7および図8を参照されたい。したがって、いくつかの事例において、各セルの同一性を、上で説明されているように、垂直または水平軸に沿って排他的に各セルを単に計算するのではなく、下方対角線方式で各セルの同一性を計算することが望ましい場合があるが、そうしたければそれも可能である。これは、行列35の仮想セルを個別に、および逐次的に、ハードウェア構成などを介して、垂直もしくは水平軸だけに沿って処理するときに必要になるであろう待ち時間、たとえば、遅延の増大によるものである。
【0255】
たとえば、そのような事例において、仮想行列を通って直線的に、および逐次的に、行毎または列毎の仕方などで移動するときに、各新しいセルを処理するために、各先行するセルの状態計算は完了していなければならず、それによって全体的に待ち時間が増大する。しかしながら、各新しいセルのM、I、D確率を下方および対角線方向に伝搬するときに、システム1は、行列の行2における隣接するセルの処理を開始する前に先行するセルの、たとえば行1の処理が完了するのを待たなくてよい。これは、対角配置構成のセルの並列および逐次処理が行われることを可能にし、さらに、M、I、およびD状態計算を有するパイプラインの様々な計算遅延を隠すことを可能にする。したがって、スワス35が行列30を左から右に移動するときに、計算処理は対角線上下方に、たとえば、左の方へ移動する(図7の矢印で示されているように)。この構成は、ハードウェアおよび/または量子回路実装に特に有用であり得、たとえば、そこではメモリおよび/またはクロック毎の待ち時間が主たる関心事である。
【0256】
これらの構成において、たとえば、行列30全体を計算した後、HMMエンジン13の各コールから出力された実際の値は、M、I、およびD状態を含む下行(たとえば、図21の行35)であってよく、MおよびI状態は総和されてよく(D状態は、上記の計算を処理する際にその機能をすでに遂行しているのでこの時点で無視されてよい)、それにより、各リードおよびハプロタイプインデックスについて、たとえば、ハプロタイプがサンプリングされた真の元のDNAであったと仮定してリードを観察する確率を推定する単一の確率であり得る最終総和値を作成するものとしてよい。
【0257】
特に、たとえば、図7の行列30の処理の結果は、リードがそのハプロタイプの実際の表現である確率を表現する単一値であり得る。この確率は0と1との間の値であり、HMM行列30内のセルの下行からMおよびI状態のすべてを総和することによって形成される。本質的に、評価されているものは、シークエンシングの前に何かがシークエンサ内で、または関連付けられているDNA調製方法において間違っている可能性があり、対象の遺伝子配列内に実際には存在していないリード内にミスマッチ、挿入、または欠失を不正に作成するという確率である。そのような事例において、リードは、対象の実際のDNAの真の反映ではない。
【0258】
したがって、そのような作成の誤りを考慮して、所与のリードが実際にハプロタイプに関して何を表しているかが決定されるものとしてよく、それによって、システムが対象の遺伝子配列が、たとえば、一斉に、参照配列の遺伝子配列とどのように異なり得るかをよりよく決定することを可能にする。たとえば、多くのハプロタイプは、多数のリード配列に対して実行されるものとしてよく、それらのうちのすべてに対するスコアを生成し、どのマッチが最良のスコアを有するかに基づき、個体の実際のゲノム配列同一性が何であるかおよび/またはそれが参照ゲノムからどれだけ本当に異なっているかを決定する。
【0259】
より具体的には、図8は、図7からのHMM状態行列30の一部の拡大図を示している。図8に示されているように、行列30内の各セルの内部構成、さらには全体として行列の構造が与えられた場合、計算される所与の「新しい」セルに対するM、I、およびD状態確率は、すでに計算されている囲む隣接要素のうちのいくつかのM、I、およびD状態に依存する。特に、図1および図16に関してより詳しく示されているように、例示的な構成において、マッチ状態から別のマッチ状態に進む確率は約0.9998であり、マッチ状態から挿入または欠失、たとえば、ギャップ、状態のいずれかに進む確率はたった0.0001(ギャップオープンペナルティ)だけであり得る。さらに、ギャップ挿入またはギャップ欠失状態のいずれかにおいてそのギャップ状態に留まる確率はたった0.1(ギャップエクステンションまたはコンティニュエーションペナルティ)だけであり得るが、マッチ状態に戻る確率は0.9である。このモデルに従って、所与の状態を出入りする確率はすべて総和すると1になるべきであることに留意されたい。特に、行列30の処理は、遷移確率を計算し、様々なギャップオープンまたはギャップコンティニュエーションペナルティを考慮することを中心として展開され、最終総和が計算される。
【0260】
したがって、これらの計算された状態遷移確率は、図16に示されているように、もっぱら行列30内の直接隣接するセルから、たとえば現在計算されているその所与のセルのすぐ左、上、および対角線上左上にあるセルから導出される。それに加えて、状態遷移確率は、各リード塩基に付随する「Phred」クオリティスコアから一部は導出され得る。これらの遷移確率は、したがって、その特定のセルについて、および同様に、計算されている関連付けられた新しいセルについて、M、I、およびD状態値を計算する上で有用である。本明細書において説明されているように、ギャップオープンおよびギャップコンティニュエーションペナルティは、固定値であってよいが、様々な事例において、ギャップオープンおよびギャップコンティニュエーションペナルティは、そのような可変遷移確率計算を決定するステップ専用の追加のハードウェアリソースを用いるが、可変であり、したがって、システム内でプログラム可能であり得ることに留意されたい。そのような事例は、より高い精度が望ましい場合に有用であり得る。そうであるとしても、そのような値が一定であると仮定されたときに、リソース使用量を減らしおよび/またはチップサイズを縮小することが可能であり、それにより、以下で説明されているように処理速度を上げることができる。
【0261】
したがって、各新しいM、I、およびD状態値を導出する際に伴う、乗算および/または加算などの、計算および/または他の数学的計算が多数ある。そのような事例において、最大スループットを計算するなどのために、各M、I、およびD遷移状態計算に伴うプリミティブな数学的計算がパイプライン化され得る。そのようなパイプライン化は、対応するクロック周波数が高いが、パイプラインの深さは非自明的であり得る仕方で構成されてよい。さらに、そのようなパイプラインは、有限の深さを有するように構成されてよく、そのような事例において、オペレーションを完了するのに複数クロックサイクルを要することがある。
【0262】
たとえば、これらの計算は、約300MHzなど、高速でプロセッサ7内部において実行され得る。これはレジスタを多用してFPGAまたはASICをパイプライン化することなどによって達成されるものとしてよく、したがって各フリップフロップの間で行われる数学的計算はわずかである。このパイプライン構造は結果として、マッチ状態の入力から出力に進む際に複数サイクルの待ち時間を引き起こすが、逆対角計算構造が与えられた場合に、上で図7において述べられているように、これらの待ち時間は、HMM行列30全体にわたって隠されるものとしてよく、たとえば、各セルは1クロックサイクルを表す。
【0263】
したがって、M、I、およびD状態計算回数は制限されてよい。そのような事例において、処理エンジン13は、行列30の多数の行内のセルのグルーピング、たとえば、スワス35が、以下の第2のスワスの処理に進む前にグループとして(図7の矢印で例示されているように下左対角線方式などで)処理されてよく、たとえば、第2のスワスは第1のものとして処理されるべき行内の同じ数のセルを含むように構成され得る。このような方式で、本明細書で説明されているような、アクセラレータ8のハードウェア実装形態は、上で説明されているように、システム全体を効率化するように適合され得る。