(57)【要約】ゲノムシーケンシング装置によって生成された圧縮ゲノムシーケンスデータのコード化および選択的アクセスのための方法および装置。コード化プロセスは、既存のまたは構築された参照シーケンスに対してシーケンスリードをアラインさせること、一連の記述子を用いてシーケンスリードを分類およびコード化すること、さらに記述子セットを異なるタイプのアクセスユニットに分割することに基づく。それらの領域にマッピングされた全てのシーケンスリードを回収することを保証する特定のゲノム領域への効率的な選択的アクセスは、以下によって提供される。ゲノム領域にアクセスするために検索およびデコードされ、データアクセスプロセスを最適化するためのすべての情報を含むマスターインデックステーブルを提供する。【選択図】図１９
2020500382.tif 000002
【特許請求の範囲】
【請求項１】
ファイル内のゲノム領域に選択的にアクセスするための方法であって、前記ファイルはエントロピーコード化されたアクセスユニットＡＵｉに配置され、
・ファイル格納情報の場合、前記ファイルに含まれ、前記ＡＵｉから分離してコード化されたインデックステーブルから、前記アクセスユニットＡＵｉの開始座標ｓｉと終了座標ｅｉの値を抽出し、および
・リードペアが前記ファイルに存在する場合、前記ファイルのデータセットヘッダ（１６０２）から閾値ＭａｘＤを抽出し、前記閾値ＭａｘＤはリードペアのペアリング距離がとることができる最大値を特定する、ことを含む方法。
【請求項２】
前記インデックステーブルテーブルは、前記アクセスユニットをエントロピーデコードする必要なしに、ポインタのベクトルを使用することによってデータのクラスに従ってエントロピーコード化されたアクセスユニットを選択的に識別するためにアクセスユニットのクラスを含む、請求項１に記載の方法。 
【請求項３】
前記ＡＵｉは、前記ＡＵに含まれる全ゲノムレコードのうちＡＵ開始位置と最も右のゲノムレコード位置との間に含まれるゲノム範囲を表す、アクセスユニット範囲と呼ばれる範囲情報を含む、請求項２に記載の方法。
【請求項４】
前記ＡＵは、２つの異なるモードからなり、
・同じＡＵの異なる記述子からのデータのブロックが連続して格納される第１のモードと、
・同じ記述子に属するが異なるアクセスユニットに属するデータブロックがファイルの連続領域に格納される第２のモードと、を含む、請求項３に記載の方法。
【請求項５】
前記モード情報は、パラメータセットのフィールドにコード化されて前記データセットヘッダに含まれる、請求項４に記載の方法。 
【請求項６】
前記第１のモードにおいて、さらに２つの異なるサブモードで表すことができ、
・同じクラスのすべてのＡＵｉがファイルに連続して格納される第１のサブモードと、
・同じゲノム領域のＡＵｉがファイルに連続して格納される第２のサブモード、を含む、請求項４に記載の方法。
【請求項７】
前記インデックステーブルが、
・参照に関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左にマッピングされた塩基のヌクレオチド数として表される位置情報、
・参照に関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右にマッピングされた塩基のヌクレオチド数として表される位置情報、
・データセットペイロードの第１のバイトを基準にした、各アクセスユニットの各記述子データブロックの第１のバイトのバイト数として表されるオフセット数のリスト、
・前記第１のモードが使用されている場合の記述子ストリームサイズのリスト、
・前記第２のモードが使用されている場合のアクセスユニットサイズのリスト、の情報を含む、請求項６に記載の方法。
【請求項８】
ストリーミング情報の場合、前記アクセスユニットＡＵｉの開始座標ｓｉおよび終了座標ｅｉの値が、各アクセスユニットＡＵｉのヘッダから抽出される、請求項７に記載の方法。
【請求項９】
前記リードペアの距離は、参照系における塩基の数または座標として表される、請求項８に記載の方法。
【請求項１０】
ゲノム領域を含むゲノムデータをコード化するための方法であって、前記ゲノムデータはエントロピーコード化されたアクセスユニットＡＵｉに配置され、
・ファイル格納情報の場合、前記アクセスユニットから分離してコード化されたインデックステーブルにおけるアクセスユニットＡＵｉの開始座標ｓｉおよび終了座標ｅｉの値をコード化し、
・−リードペアがコード化される前記ゲノムデータに存在する場合に、前記ファイルのゲノムデータセットヘッダ（１６０２）に閾値ＭａｘＤをさらにコード化し、前記閾値ＭａｘＤはリードペアのペアリング距離が想定できる最大値を指定する、ことを含む。
【請求項１１】
前記インデックステーブルはさらに、前記アクセスユニットのエントロピーデコード化を必要とせずに、デコーダでポインタのベクトルを使用することによって、エントロピーコード化アクセスユニットをデータクラスに従って選択的に識別することができるようにマッピングされたアクセスユニットクラスをさらに含む、請求項１０に記載の方法。
【請求項１２】
前記ＡＵｉは、ＡＵに含まれる全ゲノムレコードのうちのＡＵ開始位置と最も右のゲノムレコード位置との間に含まれるゲノム範囲を表す、アクセス単位範囲と呼ばれる範囲情報を含む、請求項１１に記載の方法。
【請求項１３】
前記ＡＵは、２つの異なるモードからなり、
・同じＡＵの異なる記述子からのデータのブロックが連続して格納される第１のモードと、
・同じ記述子に属するが異なるアクセスユニットに属するデータブロックがファイルの連続領域に格納される第２のモードと、を含む、請求項１２に記載の方法。
【請求項１４】
前記モード情報は、パラメータセットのフィールドにコード化されて前記データセットヘッダに含まれる、請求項１３に記載の方法。 
【請求項１５】
前記第１のモードにおいて、さらに２つの異なるサブモードで表すことができ、
・同じクラスのすべてのＡＵｉがファイルに連続して格納される第１のサブモードと、
・同じゲノム領域のＡＵｉがファイルに連続して格納される第２のサブモード、を含む、請求項１３に記載の方法。 
【請求項１６】
前記インデックステーブルが、
・参照に関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左にマッピングされた塩基のヌクレオチド数として表される位置情報、
・参照に関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右にマッピングされた塩基のヌクレオチド数として表される位置情報、
・データセットペイロードの第１のバイトを基準にした、各アクセスユニットの各記述子データブロックの第１のバイトのバイト数として表されるオフセット数のリスト、
・前記第１のモードが使用されている場合の記述子ストリームサイズのリスト、
・前記第２のモードが使用されている場合のアクセスユニットサイズのリスト、の情報を含む、請求項１５に記載の方法。
【請求項１７】
前記リードペアの距離は、参照系における塩基の数または座標として表される、請求項１６に記載の方法。
【請求項１８】
ゲノム領域を含む圧縮コード化ゲノムデータをデコード化するための方法であって、エントロピーコード化されたアクセスユニットＡＵに配置され、
・ファイル格納情報の場合、前記アクセスユニットから分離してコード化されたインデックステーブルからの、前記アクセスユニットＡＵの開始座標ｓおよび終了座標ｅの値を構文解析し、
−リードペアが前記ゲノムコード化データに存在する場合、前記ファイルのゲノムデータセットヘッダ（１６０２）から閾値ＭａｘＤをさらに解析し、前記閾値ＭａｘＤは、リードペアのペアリング距離が想定することができる最大値を指定する、ことを含む。
【請求項１９】
前記インデックステーブルは、前記アクセスユニットの前記エントロピーデコード化を必要とせずに、ポインタのベクトルを使用することによって、データのクラスに従ってエントロピーコード化アクセスユニットを選択的に識別できるようにマッピングされたアクセスユニットのクラスをさらに含む請求項１８に記載の方法。ニット 
【請求項２０】
前記アクセスユニットは、アクセスユニット範囲と呼ばれる範囲情報を含み、前記アクセスユニット範囲は、前記ＡＵに含まれる全ゲノムレコードのＡＵ開始位置と最も右側のゲノムレコード位置との間に含まれるゲノム範囲を表す、請求項１９に記載の方法。
【請求項２１】
前記ＡＵは、２つの異なるモードからなり、
・同じＡＵの異なる記述子からのデータのブロックが連続して格納される第１のモードと、
・同じ記述子に属するが異なるアクセスユニットに属するデータブロックがファイルの連続領域に格納される第２のモードと、を含む、請求項２０に記載の方法。
【請求項２２】
前記モード情報は、パラメータセットのフィールドから解析されて前記データセットヘッダに含まれる、請求項２１に記載の方法。 
【請求項２３】
前記第１のモードは、さらに２つの異なるサブモードで表すことができさらに２つの異なるサブモードで表すことができ、
・同じクラスのすべてのＡＵｉがファイルに連続して格納される第１のサブモードと、
・同じゲノム領域のＡＵｉがファイルに連続して格納される第２のサブモード、を含む、請求項２１に記載の方法。
【請求項２４】
前記インデックステーブルが、
・参照に関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左にマッピングされた塩基のヌクレオチド数として表される位置情報、
・参照に関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右にマッピングされた塩基のヌクレオチド数として表される位置情報、
・データセットペイロードの第１のバイトを基準にした、各アクセスユニットの各記述子データブロックの第１のバイトのバイト数として表されるオフセット数のリスト、
・前記第１のモードが使用されている場合の記述子ストリームサイズのリスト、
・前記第２のモードが使用されている場合のアクセスユニットサイズのリスト、の情報を含む、請求項２３に記載の方法。
【請求項２５】
前記リードペアの距離は、参照系における塩基の数または座標として表される、請求項２４に記載の方法。
【請求項２６】
実行されると少なくとも１つのプロセッサに請求項１に記載の選択的アクセス方法を実行させる命令を含むコンピュータ可読媒体。 
【請求項２７】
実行されると少なくとも１つのプロセッサに請求項１０に記載のコード化方法を実行させる命令を含むコンピュータ可読媒体。 
【請求項２８】
実行されると少なくとも１つのプロセッサに請求項１８のデコード方法を実行させる命令を含むコンピュータ可読媒体。 
【請求項２９】
請求項１０に記載の方法に従ってコード化されたゲノムデータを保存するサポートデータ。
【請求項３０】
請求項１０に記載の方法に従ってゲノムデータがコード化されているファイルフォーマット。 
【請求項３１】
前記コード化情報は暗号化されている請求項３０に記載のファイルフォーマット。 
【請求項３２】
請求項１に記載の選択的アクセスの工程を実行するための手段を含む、請求項１０に従ってコード化されたゲノム情報の選択的アクセスのための装置。 
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、既知の従来技術の表現方法では利用できない新しい効率的な機能を提供することによって、圧縮性能が向上し、アクセスする必要があるデータ量が減り、デコーディングプロセスのアルゴリズムの複雑さが軽減され、シーケンス・データ・アクセス性能が向上した、アクセスユニットに構成される圧縮されたゲノムシーケンスデータへの効率的な選択的アクセスのための新しい方法を提供する。
【背景技術】
【０００２】
ゲノムシーケンスデータの適切な表示は、シーケンスデータおよびメタデータを処理することによって、様々な目的で行われるゲノムバリアントの決定および他のすべての分析のような効率的なゲノム解析アプリケーションを可能にするために基本的なことである。
【０００３】
ヒトゲノムシーケンシングは、ハイスループット低コストシーケンシング技術の出現によって手頃な価格になってきた。そのような機会は、癌の診断と治療から遺伝病の同定まで、抗体の同定のための病原体サーベイランスから、新しいワクチン、薬物の創製、そして個別化された健康治療のカスタマイズまで、様々な分野の範囲にわたる。
【０００４】
病院、ゲノム解析プロバイダ、バイオインフォマティクス、および大規模な生物学データストレージセンターは、ゲノム医療を世界規模に拡大することを可能にする、手頃な価格、高速、信頼性および相互接続されたゲノム情報処理ソリューションを探している。データ記憶およびデータアクセスは、シーケンスデータの使用において大きなボトルネックとなっているので、ゲノムシーケンスデータを圧縮形式で表すための方法がますます研究されている。シーケンスデータの最も使用されているゲノム情報表現は、生のゲノム配列についてはＦＡＳＴＱフォーマットであり、参照ゲノムにマッピングされたゲノムシーケンスについてはＳＡＭ（Ｓｅｑｕｅｎｃｅ  Ａｌｉｇｎｍｅｎｔ  Ｍａｐｐｉｎｇ）フォーマットである。これらは、ゲノム情報が乏しく貴重なものであり、ユーザがシーケンスされたデータを読んで手動で編集できることを望んだときに考え出されたテキストベースのフォーマットである。ＦＡＳＴＱは記録の概念に基づいている。各ＦＡＳＴＱレコードは４つのセクションで構成され、最初のレコードはレコードを識別するストリング（リード名またはリードＩＤ）に割り当てられ、２番目のセクションはリードを構成するヌクレオチドのシーケンスを表し、３番目のセクションはセパレーター（通常は＋で表される）で、４番目のセクション（2番目のセクションとまったく同じ長さ）には、各ヌクレオチドを「呼び出す」ときにシーケンス処理で得られた信頼度を表すシーケンス品質スコアが含まれている。
【０００５】
ＦＡＳＴＱ及びＳＡＭとして表される情報に最もよく使用される圧縮アプローチは、ＬＺ（ＬｅｍｐｅｌおよびＺｉｖ、最初のバージョンを公開した作者）スキーム（よく知られているｚｉｐ、ｇｚｉｐなど）などの汎用アルゴリズムの使用に依存している。 Ｇｚｉｐなどの汎用コンプレッサを使用する場合、圧縮の結果は通常、単一のバイナリデータのブロブである。このようなモノリシック形式の情報は、データのボリュームが非常に大きい高スループットシーケンシングの場合には、アーカイブ、転送、および処理が非常に困難である。ＢＡＭフォーマットは、ＳＡＭフォーマットに含まれる実際の必須ゲノム情報を抽出するのではなく、冗長で構造化が不十分なＳＡＭフォーマットに一般的エントロピーコード化を適用するだけであるという事実により、圧縮性能が低いという特徴がある。そのため、各データソースの固有の性質（ゲノムデータ自体）を利用するのではなく、「ｇｚｉｐ」などの汎用テキスト圧縮アルゴリズムを適用することは、非常に非効率的な圧縮アプローチになる。ＢＡＭは、ビンで表されるゲノム領域に重なる圧縮ファイル内のデータブロックのオフセットを含む外部インデックスを作成することによって、データへの選択的なアクセスをサポートする。階層的ビン構造は、各ビンが特定のゲノム間隔と重なるＢＡＭインデックス作成に使用される。各ビンは、他のビンによって重ならないか又は完全に含まれるかのいずれかである。このアプローチの主な欠点は、以下のとおりである。
・インデックスファイルは、コンテンツの外部にあり、個別のリソースとして計算し管理する必要がある。これは、インデックスファイルに含まれる情報がデータファイルに既に含まれている情報と冗長であるため、データ操作および処理の点で効率的ではない。
・ビンサイズは、６つの値（２２９、２２６、２２３、２２０、２１７、又は２１４）に制限される。これは、これらの６個の値を使用することによってのみ識別可能なゲノム領域への選択的アクセスの柔軟性を制限する。
・ビニングおよびインデックスの特定の構造に応じて、それらにマッピングされたすべてのリードが正しく取得されることを保証したゲノム領域への選択的アクセスには、要求された区間に重複する全てのリードが実際に検索されることを確実にするためにいくつかのファイルシークコール（たとえば、ファイルリードポインターを目的の位置に移動する関数の呼び出し）が必要である。
【０００６】
ＢＡＭよりもゲノムデータ圧縮の方法としてはあまり使用されてないが、より高度で効率的なのがＣＲＡＭである。ＣＲＡＭは参照に関して差分コード化を採用するためのより効率的な圧縮を提供する（データソースの冗長性をを部分的に利用する）が、それでも増分更新の可能性、ストリーミングのサポート、特定クラスの圧縮データへの選択的アクセスなどまだいくつかの機能が欠けている。ＢＡＭに対してＣＲＡＭフォーマットによって提供されるゲノムデータのより良い圧縮は、コード化されるゲノムデータの特定の種類に従って異なるアルゴリズムを採用することによって得られる。したがって、エントロピーコード化段階に関連する適切な情報源モデリング段階がまだ不足しているとしても、それはＢＡＭと比較して一歩前進と見なされる。
【０００７】
データ操作に関して、ＣＲＡＭファイルインデックス付けは、複数のタブ区切りファイルによって構成される外部インデクスファイルによって実施される、コード化されたゲノムデータの各ゲノム領域に重複するデータブロックを記述する６つのカラムを含む。このようなインデックス付け手法の主な欠点は、以下の通りである。
・インデックスファイルは、コンテンツの外部にあり、ＢＡＭの場合と同様に、別個のリソースとして計算し管理する必要がある。このような技術的解決策は、インデックスファイルに含まれる情報が既にデータファイルに含まれている情報と重複しているので、記憶、データ操作および処理に関して効率的ではない。
・インデックスは、単一のブロブとして提供される、したがって、小さなゲノム領域へのアクセスは、ファイル全体を強制解除し、構文解析することを必要とする。
・ｇｚｉｐタブで区切られたフォーマットは、ｕｎｚｉｐされたときに人間が読める形式であるが、装置によって解析され処理されるのには効率的な形式ではない。
【０００８】
記載された先行技術の方法は、圧縮された後はナビゲートおよび操作が困難な、不十分な圧縮率およびデータ構造を生成する。下流分析は、単純な操作を実行するため、そして特にゲノムデータセットの選択された領域にアクセスするためでさえも、これらの大きくて硬いデータ構造を取り扱う必要があるために非常に遅くなり得る。 
【０００９】
ＣＲＡＭは、ＣＲＡＭレコードの概念に依存する。各ＣＲＡＭレコードは、それを再構成するために必要なすべての要素をコード化することによって、単一のマップされたまたはマッピングされていないリードをコード化する。特に、シーケンスデータ圧縮へのＣＲＡＭアプローチは、以下の欠点および制限を提示する。
・ＣＲＡＭは、特定の特徴を共有するデータサブセットへのデータのインデックス作成およびランダムアクセスをサポートしない。データインデックス作成は、仕様の範囲外であり(ＣＲＡＭ仕様ｖ３．０のセクション１２参照)、別のファイルとして実装される。逆に、この明細書に記載されている本発明のアプローチは、コード化プロセスと統合されており、インデックスがコード化された（すなわち、圧縮された）ビットストリームに埋め込まれているデータインデックス方法を採用する。
・ＣＲＡＭは、あらゆるタイプのマップされたリード（完全一致リード、置換付きリード、挿入または欠失付きリード（「インデル」とも呼ばれる））を含むことができるコアデータブロックによって構築される。参照シーケンスに関するマッピングの結果に応じた、データの分類およびクラス内のリードのグループ化の概念はない。つまり、特定の機能を持つリードのみが検索された場合でも、すべてのデータを検査する必要がある。このような制限は、コード化の前にデータをクラスに分類し区分することによってこの出願に開示された発明によって解決される。
・ＣＲＡＭは、各リードを「ＣＲＡＭレコード」にカプセル化するという概念に基づく。これは、特定の生物学的特徴を特徴とするリード（例えば、置換はあるが「インデル」は含まないリード、または完全にマッピングされたリード）を検索するときに、それぞれの完全な「レコード」を調べる必要があることを意味する。
・逆に、本発明では、別個の情報レイヤで別々にコード化されたデータクラスの概念があり、各リードをカプセル化するレコードの概念はない。これは、その特徴を検査するために各（複数の）ブロックのリードを必要とせずに、特定の生物学的特性を有する一連のリード（例えば、置換を伴うが「インデル」なしのリード、または完全にマッピングされたリード）へのより効率的なアクセスを可能にする。
・ＣＲＡＭレコードにおいて、各ＣＲＡＭレコードが任意の異なるタイプのデータを含むことができるので、レコード内の各フィールドは特定のフラグに関連付けられ、各フラグはコンテキストの概念がないので常に同じ意味を有していなければならない。このコーディングメカニズムは、冗長な情報を導入し、効率的なコンテキストベースのエントロピーコーディングの使用を防げる。
・代わりに、逆に、本発明では、データが属する情報「レイヤ」によって本質的に定義されているので、データを示すフラグの概念は存在しない。これは、使用されるシンボルの数が大幅に削減され、結果として情報ソースのエントロピーが減少し、結果としてより効率的な圧縮がもたらされることを意味する。このような改善は、異なる「レイヤ」を使用することにより、エンコーダはコンテキストに応じて異なる意味を有する各レイヤにわたって同一のシンボルを再利用することによって可能である。ＣＲＡＭでは、コンテキストの概念が存在しないので、各フラグは常に同じ意味を有していなければならず、各ＣＲＡＭレコード、任意のタイプのデータを含むことができる。
・ＣＲＡＭにおいて、置換、挿入および欠失は、異なる構文要素、情報ソースアルファベットのサイズを増大させ、より高いソースエントロピーをもたらすオプションを使用することによって表される。逆に、開示された本発明のアプローチは、単一のアルファベットを使用し、置換、挿入および欠失をコード化する。これにより、コード化およびデコード化プロセスが単純化され、コード化がもたらす高い圧縮性能を特徴とするビットストリームである低エントロピーソースモデルが生成される。
【００１０】
本明細書に開示された発明は、高性能圧縮をもたらし、シーケンスリードおよび関連情報（またはその一部のみ）への効率的な選択的アクセスを直接圧縮領域で提供するいくつかの革新的な要素を紹介する。
現在の慣例では利用できないこのような新しい特徴を達成するために、本発明は、エンコーダ側において、以下の要素によって特徴付けられる。
１.   シーケンスリードはアラインされ、既存の又は構築された参照シーケンスにマップされる。
２.  リードは、マッピングプロセスの結果に従ってクラスとサブクラスに分類される（つまり、参照シーケンスセグメントと完全に一致する、あるタイプのミスマッチのみを含み一致する、制限される数の特定のタイプのミスマッチを含み一致するなどなど・・・以下のセクションで詳しく説明する。 
３.   それらの分類によれば、シーケンスリードおよびそれらに関連するアライメント情報は、高い圧縮効率を達成するようにエントロピーコード化された特定のサブセットの「記述子」によって表される（すなわち、各クラスは、特定のリード値の値のセットが「ゲノムレコード」とも呼ばれる記述子の特定の「最小」サブセット）。
４.   各クラス内で、記述子のコード化されたサブセット（すなわち、ゲノムレコード)は、さらに、圧縮されたゲノムレコードによって表されるシーケンスリードがマッピングされるゲノム領域の境界によって特徴付けられるアクセスユニットと呼ばれるデータユニットの順序付けられたリストに分割される。
５.   各データセットに対するアクセスユニットへの分割は、２つの異なるモードのうちの１つに従って実行されるa)非重複モード（すなわちアクセスユニットに関連するゲノム領域は重複しない）b)重複モード（すなわち、１つのアクセスユニットに関連するゲノム領域は、他のアクセスユニットに関連するゲノム領域と重複してもよい)。非重複モードでは、アクセスユニットはそれらが関連するゲノム領域の両方の座標（開始および終了）の増加する値に従って順序付けされる。重複モードでは、アクセスユニットは開始座標の増加する値（すなわち、関連するゲノム領域の座標の最小値）に従って順序付けされる。
６．  アクセスユニットへのシーケンスリードの圧縮および構造化のためにエンコーダによって使用される分割のタイプ、すなわち重複モードまたは非重複モードは、完全なデータセットに対するデータセットヘッダのフィールドとして登録される。この情報フィールドは、アクセスユニットがファイルシステムに格納された後またはクライアントにストリーミングされた後にアクセスされる２つの場合に、必要なデータを検索するための選択的アクセス手順を最適化するためにデコーディング装置によって使用される。
【００１１】
ペアのシーケンスリードの場合、アイテム１−６に列挙された全てのステップに加えて、以下の要素もまた、コード化手順において使用される。
１．  シーケンスリードペアおよび関連するアライメント情報は、記述子の特定のサブセットによって単一の要素として表され（すなわち、各シーケンスペアに対して単一のゲノムレコードが使用される）、高性能圧縮を実現するための単一のアクセスユニットに含まれる。
２．  アクセスユニットの境界を超え、各参照シーケンスに対して定義された所与のパラメータ値を超えるペアの長さによって特徴付けられるリードペアは、代わりに分割され、記述子の２つのサブセットによる単一リードとして表され、それぞれのマッピング位置に従って異なるアクセスユニットにコード化および含まれる。
【００１２】
リードペアを同じアクセスユニット内の単一のエンティティとしてコード化する必要があるか、単一のリードに分割して２つの異なるアクセスユニットにコード化する必要があるかを決定するためにエンコーダによって使用されるコーディングパラメータの値は、データセットヘッダフィールドに登録される。各参照シーケンスごとに異なるコード化パラメータを使用することができる。この情報は、圧縮ドメイン内のゲノム領域への選択的アクセスが必要とされるときにアクセスされデコードされるアクセスユニットの数を最小限に抑えることを可能にする。
【００１３】
コーディング段階の後にアクセスユニットがファイルシステムに格納されると、以下のステップが実行される。
1.  アクセスユニットを構成するデータブロックは、２つの可能なフォーマットに従ってファイルシステムに記憶されるａ）同一の記述子に属するデータがストリーム化されて記憶装置の隣接領域に記憶された記述子ストリーム連続（ＤＳＣ）フォーマット、ｂ）異なる記述子に属するが同じアクセスユニットに属するデータが記憶装置の連続領域に記憶されるアクセスユニット連続（ＡＵＣ）フォーマット。
２.  ＡＵＣデータフォーマットがデータ記憶のために使用される場合、データ連続性は２つの異なるモードで実施されることができる：ａ）記憶装置の同じ領域に記憶された同じクラスのすべてのアクセスユニットを有するクラスベース（クラス連続モード、ＣＣ）、ｂ）すべてのアクセスユニットが同じゲノム領域にマッピングされ、記憶装置の同じ領域に記憶されているゲノム領域ベース（ゲノム領域連続モード、ＧＲＣ）。
３.  データセットをファイルシステムＤＳＣ、ＡＵＣ／ＣＣ、又はＡＵＣ／ＧＲＣに格納するために使用されるアクセスユニット記憶フォーマットに関する情報は、データアクセスプロセスを最適化するためにデータが検索されデコード化されるときに情報が利用可能になるように、データセットヘッダのフィールドに登録される。ＡＵＣデータフォーマットは、同じアクセスユニットに属するデータを記憶装置の連続した領域に記憶することを可能にするので、領域ベースの選択的アクセスの場合のファイルシステムアクセスの最小化にとって特に興味深い。ＡＵＣデータフォーマットの場合、ＣＣモードは異なるクラスの任意のサブセットのデータにアクセスするときにより効率的になり、一方ＧＲＣモードは同じゲノム領域にマッピングするすべてのクラスのデータにアクセスするとき効率的になる。逆に、ＤＳＣフォーマットは、例えば、暗号化アルゴリズムを適用することによって1つ以上の記述子ストリームが保護されている場合など、他の使用例に対して効率的になる。この場合、記述子ストリームのデータ連続性により保護およびアクセス操作がより効率的になる。
４.  アクセスユニットに含まれるデータに関連するゲノム領域を特徴付ける情報は記憶され、以下のように構造化されるマスターインデックステーブルと呼ばれる多次元データ構造に利用可能である。
ａ．参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左に一致する塩基のヌクレオチド数としての位置。
ｂ．参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右に一致する塩基のヌクレオチド数としての位置。
ｃ．アクセスユニットサイズのリスト(ＡＵＣモードが使用される場合)
ｄ．データセットペイロードの最初のバイトを基準とした、各アクセスユニットの各記述子データブロックの最初のバイトのオフセット数のリストのバイト数。
【００１４】
データ検索側では、アクセスユニットが圧縮された形でファイルシステムに格納されている場合には、そのアクセスユニットは、圧縮された形式でファイルシステムに格納されている特定のゲノム領域にマッピングされた記述子を任意のサブセットに選択的にアクセスすることが必要であり、以下のステップが実行される。
１．  デコーダーは、適切なデータセットヘッダフィールドから情報をフェッチする；ａ．前記ゲノムデータが前記ファイルシステムに格納されたＡＵｓに分割されたモードであることを特徴とする：非重複モード又は重複モード
ｂ．システム内の全てのＡＵＳのデータを記憶するために使用されるフォーマット：ＤＳＣまたはＡＵＣ／ＣＣまたはＡＵＣ／ＧＲＣ
２.  ステップ１で得られた情報を用いて、ＭＩＴに格納された情報にアクセスし処理することにより、選択的アクセス要求を満たすデータを含む全てのＡＵが識別される。
３．  最小数のファイルアクセスコールを使用して、選択的データアクセス要求を満たす全てのデータを取得するために使用される、最小数のＡＵ、最小数のデータブロック。
４.  データの最小容量は、選択的なデータアクセス要求を満たすためにデコードされる。
【００１５】
ポイント１と２のステップに加えて、ペアのリード記述子を持つアクセスユニットの場合は、リードペアは単一のエンティティーとしてコードされず、リードは２つの異なるＡＵに分離してコードされる場合の決定に使用されるコーディング・パラメーターは、各参照シーケンスのデータ・セット・ヘッダーから取得される。そのようなパラメータは、選択的アクセス要求を満たし、分割ペアのすべてのリードが正しく取り出されることを保証するために取り出されデコードされる必要がある最小数のＡＵを識別するために使用される。
【００１６】
クライアント側で、アクセスユニットが圧縮された形式でクライアントにストリーミングされ、特定のゲノム領域にマッピングされた記述子が任意のサブセットに選択的にアクセスされることが要求されるとき、以下のステップが実行される。
１．  デコーダは、トランスポートブロックヘッダから、データのクラスを特定する情報とＡＵがカバーする範囲とを取得して、ＡＵが選択的アクセス要求に応答するためにデコードされなければならないか、または無視され得るかを決定する。
【００１７】
ポイント１のステップに加えて、ペアのリード記述子を持つアクセスユニットの場合は、リードペアは単一のエンティティーとしてコードされず、リードは２つの異なるＡＵに分離してコードされる場合の決定に使用されるコーディング・パラメーターは、各参照シーケンスのデータ・セット・ヘッダーから取得される。そのようなパラメータは、選択的アクセス要求を満たすために着信ＡＵをレコードする必要があるかどうかを識別するために使用される。 
【図面の簡単な説明】
【００１８】
【図１】図１は、参照シーケンス上の座標系と、参照シーケンス上にどのようにリード及びリードペアがマップされるかを示す。
【図２】図２は、参照シーケンス上の座標が、参照上の塩基の位置として参照される方法を示す。
【図３】図３は、ゲノムレコードのマッピング位置の定義を示す図である。
【図４】図４は、ゲノムレコード位置に関するアクセスユニット範囲およびカバー領域の定義を示す図である。
【図５】図５は、そのゲノムレコード長が、リードまたはリードペアの最も左にマッピングされた塩基から最も右にマッピングされた塩基を分離する参照シーケンス上のゲノム位置の数としてどのように定義されるかを示す。リードペアの場合、これは、両方のリードが同じ参照シーケンスにマッピングされているときに、リード１の左端の塩基をその相手のリード２の右端の塩基から隔てる参照シーケンス上のゲノム位置の数である。「ペアリング距離」は、リード１の最も左の位置とリード２の最も左の位置との間の差として定義される。
【図６】図６は、ゲノムレコード長の計算の一例を示す。
【図７】図７は、どのようにアラインされたリードまたはリードペアが２つ以上のアクセスユニットにまたがることができるかを示す。これは、各ゲノムレコード長が、レコードを含むＡＵの端部からのリードまたはリードペアマッピング位置の距離よりも大きい場合に起こる。一貫した選択的アクセスアルゴリズムは、指定されたゲノム領域をカバーしないアクセスユニットにおいてリードがコード化されていても、指定されたゲノム領域に重複する全ての塩基を検索することができる。
【図８】図８は、リードペアが異なるアクセスユニット範囲にわたるゲノム領域にマッピングされるという事実が、選択的アクセス手順が選択的アクセス要求によって指定されたゲノム領域Ｒにマッピングするゲノムレコードを含み得るすべてのアクセスユニットを識別できなければならないことを示す。
【図９】図９は、ペアリング距離閾値ｍａｘｄによって制限される単一エンティティのペアのリードペアおよびコード化の場合に、位置sとeとの間に含まれる領域への選択的アクセスのためのＡＵおよびデコードプロセスの識別の例を示す。
【図１０】図１０は、特定の選択的アクセス動作に従って、リード７０１、７０２、７０３、および７０４が部分的にまたは全体的にどのように返されるかを示す。両方の場合において、アクセスユニットｋおよびｋ＋（１）がデコードされる。
【図１１】図１１は、参照シーケンス(クラスＰ)上で完全にマッピングされる一対の固定長リードをコード化するために使用される記述子を示す。
【図１２】図１２は、参照シーケンス(クラスＰ)上で完全にマッピングされる可変長のリードをコード化するために使用される記述子を示す。
【図１３】図１３は、参照配列（クラスＮ）に関して未知の塩基を有する一対の固定長リードをコード化するために使用される記述子を示す。
【図１４】図１４は、少なくとも１つの置換（クラスＭ）を有し、参照シーケンス上にマッピングする一対の固定長リードをコード化するために使用される記述子を示す。
【図１５】図１５は、少なくとも１つの挿入、欠失またはソフトクリップベース（クラスＩ）を有し、参照シーケンス上にマッピングする一対の固定長リードをコード化するために使用される記述子を示す。
【図１６】図１６は、同じクラスのデータのアクセスユニットをファイルシステムに格納する２つの方法を示す。ＤＳＣモードを使用して、異なるアクセスユニットに属する同じ記述子ストリームのデータブロックが連続して格納される。ＡＵＣモードを使用して、異なる記述子ストリーム同じアクセスユニットに属するデータブロックは連続して格納される。縦軸には、特定の識別子（Descriptor_Stream_ID）によって識別され、横軸にはマスターインデックステーブルで順序付けされた各アクセスユニットが識別され、重複する場合と重複しない場合の両方において各ディスクリプタストリームおよびデータクラス内のインデックスによって識別される。
【図１７】図１７は、同じクラスのデータのアクセスユニットをファイルシステムに記憶する２つの方法を示す。ＡＵＣ／ＣＣ及びＡＵＣ／ＧＲＣモードを使用する。ＡＵＣ／ＣＣモードを使用して、同じデータクラスに属するデータのブロックが連続して記憶される。ＡＵＣ／ＧＲＣモードを使用して、異なるデータクラスの同一のゲノム領域に属するデータブロックが連続して記憶される。縦軸には特定の識別子（ＣｌａｓｓＪＤ）によって識別された異なるデータクラス、横軸には異なる隣接ゲノム領域が報告されている。
【図１８】図１８は、データクラスごとに区分されたＡＵ開始位置（Ｃｓｊｋ）および終了位置（Ｃｅｊｋ）を格納するマスターインデックステーブルを示す。
【図１９】図１９は、使用されるアクセスユニット分割モード（重複または非重複）およびデータ記憶フォーマット（ＤＳＣ、ＡＵＣ／ＣＣ、ＡＵＣ／ＧＲＣ）およびそれに続く情報に関する情報を含むデータセットヘッダを圧縮データセットに関連付けるエンコーダを示す。マスターインデクステーブル、リードとリードペア、およびコード化されたリードをエンコードするために各参照シーケンスに使用されるエンコードパラメーターのベクトル。
【図２０】図２０は、より長いシーケンス（別名「コンティグ」）をマッピングされていないリードと組み合わせることによって、ハーフマッピングされたリードペア（クラスＨＭ）を使用して参照シーケンスの未知の領域を埋める方法を示す。
【発明の概要】
【課題を解決するための手段】
【００１９】
特許請求の範囲の特徴は、エントロピーコード化されたアクセスユニットＡＵに配置されたファイル内のゲノム領域に選択的にアクセスする方法を提供することにより、既存の先行技術の解決策の問題を解決し、前記方法は、以下のステップを含む。
−ファイル格納情報の場合には、ファイルに含まれる前記ＡＵから分離してコード化されたインデックステーブルから、前記アクセスユニットＡＵの開始座標sおよび終了座標ｅの値を抽出する。
−リードペアが前記ファイル内に存在する場合に、前記ファイルのゲノムデータセットヘッダ（１６０２）から閾値ＭａｘＤを抽出することをさらに含み、前記閾値ＭａｘＤは、リードペアのペアリング距離がとることができる最大値を特定する。
【００２０】
選択的アクセス方法の別の態様では、前記インデックステーブルは、前記アクセスユニットをエントロピーデコード化する必要なしに、ポインタのベクトルを使用することによってデータのクラスに従ってエントロピーコード化アクセスユニットを選択的に識別するためのアクセスユニットのクラスを含む。
【００２１】
選択的アクセス方法の別の態様では、前記ＡＵは、ＡＵに含まれる全ゲノムレコードのうちＡＵ開始位置と最も右のゲノムレコード位置との間に含まれるゲノム範囲を表すアクセスユニット範囲と呼ばれる範囲情報を含む。
【００２２】
選択的アクセス方法の別の態様では、前記アクセスユニットは２つの異なるモードであり得る。
−同じＡＵの異なる記述子からのデータブロックが連続して格納される第１のモード
−同じ記述子に属するが異なるアクセスユニットに属するデータブロックがファイルの連続領域に格納される第２のモード
【００２３】
選択的アクセス方法の別の態様では、前記モード情報はパラメータセットのフィールドにコード化されてゲノムデータセットヘッダに含まれる。
【００２４】
選択的アクセス方法の別の態様では、前記第１のモードはさらに２つの異なる異なるサブモードで表すことができる。
−同じクラスのすべてのＡＵがファイルに連続して格納される第１のサブモード
−同じゲノム領域のＡＵがファイルに連続して格納される第２のサブモード
【００２５】
コード化方法の別の態様では、前記インデックステーブルは以下の情報を含む：
参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左にマッピングされた塩基の、ヌクレオチド数として表される位置情報。
参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右にマッピングされた塩基の、ヌクレオチド数として表される位置情報。
データセットペイロードの第１のバイトを基準にした、各アクセスユニットの各記述子データブロックの第１のバイトのオフセット数のリスト（バイト数）。
前記第１のモードが使用されている場合の記述子ストリームサイズのリスト。
前記第２のモードが使用されている場合のアクセスユニットサイズのリスト。
【００２６】
選択的アクセス方法の他の態様では、ストリーミング情報の場合、前記アクセスユニットＡＵの開始座標ｓおよび終了座標ｅの値は、各アクセスユニットＡＵのヘッダから抽出される。
【００２７】
選択的アクセス方法の他の態様では、前記リードペアの距離は、参照系における基数または座標の数として表される。
【００２８】
ゲノム領域を含むゲノムデータをコード化するための方法であって、前記ゲノムデータはエントロピーコード化されたアクセスユニットＡＵｉに配置され、前記方法は以下のステップを含む。
−ファイル格納情報の場合、前記アクセスユニットから分離してコード化されたインデックステーブルにおける前記アクセスユニットＡＵの開始座標ｓおよび終了座標ｅの値をコード化。
−リードペアがコード化される前記ゲノムデータに存在する場合に、前記ファイルのゲノムデータセットヘッダ（１６０２）に閾値ＭａｘＤをさらにコード化し、前記閾値ＭａｘＤはリードペアのペアリング距離が想定できる最大値を指定する。
【００２９】
コード化方法の別の態様では、前記インデックステーブルはさらに、前記アクセスユニットのエントロピーデコード化を必要とせずに、デコーダでポインタのベクトルを使用することによって、エントロピーコード化アクセスユニットをデータクラスに従って選択的に識別することができるようにマッピングされたアクセスユニットクラスをさらに含む。
【００３０】
コード化方法の別の態様では、前記ＡＵは、ＡＵに含まれる全ゲノムレコードのうちＡＵ開始位置と最も右側のゲノムレコード位置との間に含まれるゲノム範囲を表すアクセスユニット範囲と呼ばれる範囲情報を含む。
【００３１】
コード化方法の他の態様では、前記ＡＵは、２つの異なるモードであり得る。
−同じＡＵの異なる記述子からのデータブロックが連続して格納される第１のモード
−同じ記述子に属するが異なるアクセスユニットに属するデータブロックがファイルの連続領域に格納される第２のモード
【００３２】
コード化方法の他の態様では、前記モード情報はパラメータセットのフィールドにコード化され、ゲノムデータセットヘッダに含まれる。
【００３３】
コード化方法の別の態様では、前記第１のモードはさらに２つの異なる異なるサブモードで表すことができる。
−同じクラスのすべてのＡＵがファイルに連続して格納される第１のサブモード
−同じゲノム領域のアクセスユニットが連続して保存される第２のサブモード
【００３４】
コード化方法の他の態様では、前記インデックス表は次の情報を含む。
参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左にマッピングされた塩基の、ヌクレオチド数として表される位置情報。
参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右に一致する塩基の、ヌクレオチドの数として表される位置情報。
データセットペイロードの第１のバイトを基準とした、各アクセスユニットの各記述子データブロックの第１のバイトのオフセット数のリスト（バイト数）。
前記第１のモードが使用されるときの記述子ストリームサイズのリスト前記第２のモードが使用されるときのアクセスユニットサイズのリスト。
【００３５】
コード化方法の他の態様では、リードペアの距離は参照系における塩基または座標の数として表される。
【００３６】
ゲノム領域を含む圧縮コード化ゲノムデータをデコード化する方法であって、エントロピーコード化アクセスユニットＡＵに配置されている、前記コード化ゲノムデータ。
−ファイル格納情報の場合、前記アクセスユニットから分離してコード化されたインデックステーブルからの、前記アクセスユニットＡＵの開始座標ｓおよび終了座標ｅの値を構文解析。
−リードペアが前記ゲノムコード化データに存在する場合、前記ファイルのゲノムデータセットヘッダ（１６０２）から閾値ＭａｘＤをさらに解析し、前記閾値ＭａｘＤは、リードペアのペアリング距離が想定することができる最大値を指定する。
【００３７】
デコード化方法の別の態様では、前記インデックステーブルは、前記アクセスユニットの前記エントロピーデコード化を必要とせずに、ポインタのベクトルを使用することによって、データのクラスに従ってエントロピーコード化アクセスユニットを選択的に識別できるようにマッピングされたアクセスユニットのクラスをさらに含む。
【００３８】
デコード化方法の別の態様では、前記アクセスユニットは、アクセスユニット範囲と呼ばれる範囲情報を含み、前記アクセスユニット範囲は、前記ＡＵに含まれる全ゲノムレコードのＡＵ開始位置と最も右側のゲノムレコード位置との間に含まれるゲノム範囲を表す。
【００３９】
デコード化方法の別の態様では、前記ＡＵは２つの異なるモードであり得る。
−同じＡＵの異なる記述子からのデータブロックが連続して格納される第１のモード
−同じ記述子に属するが異なるアクセスユニットに属するデータブロックがファイルの連続領域に格納される第２のモード
【００４０】
デコード化方法の他の態様では、前記モード情報はパラメータセットのフィールドから解析され、ゲノムデータセットヘッダに含まれる。
【００４１】
デコード化方法の別の態様では、前記第１のモードはさらに２つの異なる異なるサブモードで表すことができる。
−同じクラスのすべてのＡＵがファイルに連続して格納される第１のサブモード
−同じゲノム領域のアクセスユニットが連続して保存される第２のサブモード
【００４２】
デコード化方法の別の態様では、前記インデックス付けテーブルは以下の情報を含む。
参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左にマッピングされた塩基の、ヌクレオチド数として表される位置情報。
参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右にマッピングされた塩基の、ヌクレオチド数として表される位置情報。
データセットペイロードの第１のバイトを基準とした、各アクセスユニットの各記述子データブロックの第１のバイトのオフセット数のリスト（バイト数）。
前記第１のモードが使用されるときの記述子ストリームサイズのリスト。
前記第２のモードが使用されるときのアクセスユニットサイズのリスト。
【００４３】
デコード化方法の別の態様では、前記リード対の距離は、参照系における基数または座標の数として表される。
【００４４】
実行されると少なくとも１つのプロセッサに前記選択的アクセス方法を実行させる命令を含むコンピュータ可読媒体。
【００４５】
実行されると少なくとも１つのプロセッサに前記コード化方法を実行させる命令を含むコンピュータ可読媒体。
【００４６】
実行されると少なくとも１つのプロセッサに前記デコード方法を実行させる命令を含むコンピュータ可読媒体。
【００４７】
前記コード化方法に従ってコード化されたゲノムデータを保存するサポートデータ。
【００４８】
ゲノムデータが前記コード化方法に従ってコード化されているファイルフォーマット。
【００４９】
コード化情報が暗号化されている前記コード化方法に従ってコード化されたファイル。
【００５０】
前記選択的アクセスの工程を実行するための手段を含む、前記コード化ゲノム情報の選択的アクセスのための装置。
【発明を実施するための形態】
【００５１】
関連アプリケーションとの相互参照
本出願は、特許出願ＰＣＴ／ＥＰ２０１６／０７４３１１、ＰＣＴ／ＥＰ２０１６／０７４３０１、ＰＣＴ／ＥＰ２０１６／０７４３０７、ＰＣＴ／ＥＰ２０１６／０７４２９７、ＰＣＴ／ＵＳ２０１７／１７８４２、ＰＣＴ／ＵＳ２０１７／１７８４１に優先権と利益を主張する。
【００５２】
本発明において参照されるゲノムまたはプロテオームシーケンスは、限定されるものではないが、例えば、ヌクレオチドシーケンス、核酸（ＤＮＡ）シーケンス、リボ核酸（ＲＮＡ）およびアミノ酸シーケンスを含む。本明細書中の記載はヌクレオチドシーケンスの形態のゲノム情報に関してかなり詳細であるが、当業者によって理解されるように、圧縮のための方法およびシステムは、いくつかのバリエーションを伴い、他のゲノムまたはプロテオームシーケンスについても同様に実施され得ることが理解される。
【００５３】
ゲノムシーケンス情報は、定義された語彙からの文字列によって表されるヌクレオチド（別名「塩基」）のシーケンスの形でハイスループットシークエンシング（ＨＴＳ）装置によって生成される。最小の語彙は５個のシンボルであらわされる{Ａ、Ｃ、Ｇ、Ｔ、Ｎ}は、ＤＮＡに存在する４種類のヌクレオチド、すなわちアデニン、シトシン、グアニン、およびチミンを表す。ＲＮＡでは、チミンはウラシル（Ｕ）に置き換えられている。Ｎは、シーケンシング装置がいかなる塩基も呼び出せなかったことを示し、したがってその位置におけるヌクレオチドの実際の性質は決定されていない。ＩＵＰＡＣあいまいコードが語彙としてシーケンシング装置によって採用されている場合、シンボルに使用されるアルファベットは以下のシンボルからなる｛Ａ、Ｃ、Ｇ、Ｔ、Ｕ、Ｗ、Ｓ、Ｍ、Ｋ、Ｒ、Ｙ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎまたは−｝。
【００５４】
本発明の文脈において、「ゲノムデータセット」は、例えば、生物のゲノムデータ、生物のゲノムシーケンシングによって、または元のシーケンスデータに対して行われたゲノムデータ処理の任意の他のステップによって生成された１つ以上のシーケンスおよびメタデータを含む構造化されたゲノムデータのセットとして定義される。
【００５５】
シーケンシング装置によって生成されたヌクレオチドシーケンスは、「リード」と呼ばれる。シーケンスリードは、数十から数千の範囲の数のヌクレオチドから構成することができる。いくつかのシーケンシング技術は、１つのリードが１つのＤＮＡ鎖から生じ、他方が他方の鎖から生じる「ペア」から構成されるシーケンスリードを生成する。ペアを生成するシーケンシングプロセスにおいてリードに関連する他のリードは、その「メイト」であると言われる。
【００５６】
本開示を通して、参照シーケンスは、各整数座標が単一のヌクレオチドに関連している一次元整数座標系に関連したヌクレオチドのシーケンスである。座標値は、ゼロ以上でなければならない。本発明の文脈におけるこの座標系はゼロを基準とし（すなわち、最初のヌクレオチドは座標０を有し、それは位置０にあると言われる）そして左から右へ直線的に増加するように構成されている。
【００５７】
マッピングシーケンスが参照シーケンス上で読み取りを行う場合、前記参照シーケンスは、最も左の位置が位置０として示される一次元座標系の軸として用いられる。参照シーケンスにマッピングされたシーケンスリードにおいて、参照シーケンス位置に特定されたリードを構成するヌクレオチドは、最小の座標番号で識別されるものは通常、「最も左」のヌクレオチドと呼ばれ、一方、最大の座標番号によって識別される参照シーケンス位置にマッピングされたリードを構成するヌクレオチドは「最も右」のヌクレオチドと呼ばれる。図を参照されたい。この開示全体を通して、ヌクレオチドは"塩基"とも呼ばれる。図１も参照されたい。本開示を通して、ヌクレオチドは「塩基」とも呼ばれる。
【００５８】
シーケンスリードが参照シーケンスにマッピングされるとき、最も左にマッピングされた塩基の座標は、参照シーケンス上のリードのマッピング位置を表すと言われる。
【００５９】
参照ゲノムは、１つ以上の参照シーケンスによって構成され、それは、種の遺伝子のセットの代表例として科学者によって組み立てられる。例えば、ＧＲＣｈ３７、ゲノムリファレンスコンソーシアムのヒトゲノム（構築物３７）は、ニューヨーク州バッファローからの１３人の匿名のボランティアに由来する。しかしながら、参照シーケンスはまた、それらのさらなる処理を考慮してリードの圧縮性を改善するために考えられそして単に構築された合成シーケンスからなることもできる。
【００６０】
本開示全体を通して、ゲノムレコードは、コード化された表現として以下のように定義される。
・アライメント情報、リード識別子および品質値に任意に関連付けられた単一シーケンスリードまたはペアシーケンスリードのいずれか。
・参照シーケンス（例えば、染色体）またはその一部。
【００６１】
本開示全体を通して、ゲノムレコードの位置は、ゲノムレコードにコード化されたリードまたはリードペアの最も左にマッピングされた塩基の参照シーケンス上の位置として定義される。リードまたはリードペアのレコードにおけるマッピングされたベースは、以下のように意図される。
【００６２】
・参照シーケンス上の対応する塩基と一致するアラインされたリードの塩基
・対応する塩基と一致しないアラインされたリードの塩基（別名一塩基多型）
【００６３】
アラインメントされたリードに存在し、参照シーケンスには存在しない塩基（挿入）、およびアラインメントプロセスによって保存されるが参照シーケンスにはマッピングされない塩基（ソフトクリップ）は、いかなるマッピング位置にも対応しない。 本開示では、参照上の最小座標上のベースマッピングを有するリードペアを構成するリードを「リード１」と呼び、そのペアを「リード２」と呼ぶ。
【００６４】
今日の技術を使用するシーケンシング装置により、ペアとして生成された２つのリードを隔てるヌクレオチド（または塩基）の数または座標として表される距離は未知であり、それはペアを構成する両方のリードを参照シーケンスにマッピングすることによって決定される（すなわち、適切なマッチング関数を最小化する）。
【００６５】
本開示を通して、ゲノムレコード長は、レコード中にコード化された最も左のマッピングされた塩基とレコード中にコード化された最も右のマッピングされた塩基との間の距離として定義される。
【００６６】
両方のリードが同じ参照上にマップされ、同じゲノムレコードにおいてコード化されるリードペアの場合には、両方のリードが同じ参照にマッピングされ、同じゲノムレコード内でコード化されるリードペアの場合には、ペアリング距離は、リード１の最も左にマップされたベースとリード２の最も左のマップされたベースとの間の距離として定義される。ペアリング距離の一例を図５に示す
【００６７】
本開示を通して、シングルリードの場合、ゲノムレコード長（ＧＲＬ）は、最も右にマッピングされた塩基のマッピング位置から最も左の塩基のマッピング位置を減算し、そして「１」を加えることによって得られる整数として定義される。
ＧＲＬ＝（最も右のベース位置）−（最も左のベース位置）＋１
【００６８】
本開示全体を通して、リードペアの場合、ゲノムレコード長（ＧＲＬ）は、シーケンスのマッピング位置を差し引くことによって得られる整数として定義される。参照シーケンス（リード１）の一番右の塩基のマッピング位置の座標（リード２）から最も左の位置にリードマッピングの一番左の塩基を追加し、「１」を追加する。ゲノムレコード長のそのような定義は図５に示す。
【００６９】
本開示全体を通して、参照シーケンスまたはその一部をコードするゲノムレコードの場合、ゲノムレコード長は、コード化されたシーケンスを構成するヌクレオチドの数として定義される。
【００７０】
本開示を通して、ゲノム範囲は、Ｓ＜Ｅであるように、開始座標Ｓおよび終了座標Ｅによって定義される参照シーケンス上の連続した座標のセットとして定義される。ゲノム範囲の開始位置および終了位置は、ゲノム範囲に常に含まれる。
【００７１】
本発明は、アクセスユニットと呼ばれる複数のデータブロックに含まれる記述子のセットによってシーケンスリードが圧縮されたときに、任意のゲノム領域にマップされたアラインされたゲノムシーケンスリードに効率的にアクセスすることができる新しい方法を定義することを目的とする。
【００７２】
本開示全体を通して、アクセスユニット（ＡＵ）は、データアクセスおよび操作を容易にするように構成されたゲノム情報または関連するメタデータのコード化表現を含む論理データ構造として定義される。本開示に記載された本発明を実施するデコーダーによってデコード可能な最小のデータ構造である。
【００７３】
ＡＵによって運ばれるコード化された情報の種類に応じて、他のＡＵとは独立してデコードされてもよいし、他のＡＵｓに含まれる情報を用いてデコードされてもよい。
【００７４】
ＡＵｓは、コード化されたデータの性質に応じていくつかの種類があり得る。アクセスユニットは、参照シーケンス、またはその一部、あるいは単一クラスのデータに属するコード化されたリードまたはリードペアを含む。リードのクラスは、参照シーケンスに対するリードまたはリードペアのマッチング結果に従って定義される。
【００７５】
たとえば、アクセスユニットには、ゲノムリファレンスコンソーシアムのヒトゲノム であるＧＲＣｈ３７の1番染色体全体を含めることができる（構築物３７）。他のアクセスユニットは、座標５０００と１５０００の間に位置するＧＲＣｈ３７の第1染色体のヌクレオチドのコード化表現を含み得る。他のアクセスユニットは、ミスマッチなしに参照シーケンスに完全にマッピングするリードまたはリードペアのみを含み得る。別のアクセスユニットは、参照シーケンスに関して「Ｎ」のシンボルのミスマッチのみを含むリードまたはリードペアを含み得る。他のアクセスユニットは、任意の種類の置換を含むリードまたはリードペアを含み得る（例えば、リードまたはリードペアに存在する１つの塩基は、参照シーケンス中の対応するマッピング位置の塩基とは異なる）。他のアクセスユニットは、ミスマッチ、挿入、欠失およびソフトクリップされた塩基を含むリードまたはリードペアを含み得る。他のアクセスユニットは、参照シーケンスにマッピングされていないリードまたはリードペアのみを含み得る。他のアクセスユニットは、一方のリードがマッピングされ、他方が参照シーケンスにマッピングされていないリードペアのみを含むことができる。別のタイプのアクセスユニットは、１つ以上の参照シーケンス（例えば、染色体）によって構成される参照ゲノムのコード化セグメントのみを含み得る。
【００７６】
アクセスユニットの本質的な特徴は、それが表すゲノム情報（シーケンスリードまたはリードペア、参照シーケンス）、関連するアラインメント情報およびリードまたはリードペアのメタデータを再構築するのに必要なすべての要素を圧縮形式で含むことである。言い換えれば、ｎ個のアクセスユニットによって運ばれるリード、リードペアまたは参照シーケンスおよび関連情報を完全に再構築するためには、アクセスユニット自体、および必要なときにはそれが参照する参照シーケンスを含むアクセスユニットを取り出すことだけが必要である。
【００７７】
各アクセスユニットにおいて、コード化されたリードまたはリードペアを表す次のセクションにリストされた記述子は、エントロピーコード化が適用されてそれらを圧縮する際にそれらの均一な統計的特性を利用するために、タイプごとに別個のデータブロックに集約される。
【００７８】
各アクセスユニットは、参照シーケンス上のゲノム領域にマッピングされた同じクラスに属するシーケンスリードまたはリードペアを表す記述子の圧縮されたサブセットを含む。このような参照シーケンス上のゲノム領域は、開始座標（または開始位置）と、終了座標（または終了位置）とによって定義される。
【００７９】
記述子は、コード化された参照シーケンス、シーケンスリードおよび関連するマッピング情報またはシーケンスルードペアおよび関連するマッピング情報を再構成(デコード)するのに必要な情報の一部を表す構文要素である。異なるタイプの記述子は、以下のように定義される。
・参照シーケンス上でのリードのマッピング位置
・リードとそのメイトとの間の距離
・シーケンスの長さ
・参照シーケンスに対するアラインされたリードにおけるミスマッチの位置
・関連付けられた位置における参照シーケンスに対するミスマッチのタイプ
・マッピング手順によって参照シーケンス上にマップされることができず、「ソフトクリップ」として分類されるベース
・シーケンスリードの長さ
・ＳＡＭ仕様によって指定されたマッピングフラグ
・マッピング手順によって単一のリードまたはリードペアに関連付けられた複数のマッピング位置
・スプライスされたリードの存在の識別（すなわち、リードがチャンクに分割されたときに、より高いマッチング精度でマッピング位置を見つけ、次いでそれらが参照シーケンス上の単一位置にマッピングされた単一連結リードとしてマッピングされるとき）。
・使用される特定のタイプの参照シーケンス
・ゲノムリファレンスコンソーシアム（例：ＧＲＣｈ３７）、カリフォルニア大学サンタクルーズ（例：ｈｇｌ９）のようなコンソーシアムによって公開されているものとしての参照ゲノム
・指定されたセットのリードおよび指定されたセットのアセンブリルールを使用して構築された参照シーケンス
・そのような修正された参照シーケンスにマップされたシーケンスリードのミスマッチを表すために使用される記述子のエントロピーを低減する目的を有する参照シーケンスに適用される修正の位置および種類
・指定された程度のマッチング精度で参照シーケンスのいずれの位置にもマッピングできないシーケンスリードの表現
・参照シーケンス全体のまたはその一部の表現
【００８０】
本開示において参照される各記述子の完全なリストおよび正確な定義、本発明により使用されるものは、以下のセクションにおいて提供される。
【００８１】
上述のように、いくつかの記述子が、圧縮された形式の参照シーケンスを表すために、本発明によって使用される、それらの関連する情報を用いて完全に再構成することができるように、シーケンスリードまたはリードペアを実行するように構成されている。リード又はリードペアがまた、分離され、異なるクラスに分類される場合、参照シーケンス上のマッピングの結果と、別々のデータブロックにコード化されるエントロピーに基づいて、それぞれのクラスまたはリードまたはリードペアを表すために、異なるサブセットの記述子が使用される。したがって、アクセスユニットは、参照シーケンスまたはその一部、または同一クラスに属するリードまたはリードペアのいずれかを表すのに必要なエントロピーコード化記述子のみを含む。これは、可変長リードに関して図１２に示されており、および固定長リードペアに関して図１１、図１３、図１４および図１５に示す。
【００８２】
本開示を通して、アクセスユニット開始位置は、アクセスユニットに含まれるすべてのゲノムレコードのうち最も左のゲノムレコード位置として定義される。
【００８３】
本開示全体を通して、アクセスユニット終了位置は、アクセスユニットに含まれる全ゲノムレコードの全マッピング塩基の中で最も右にマッピングされた塩基位置として定義される。
【００８４】
本開示を通して、アクセスニット範囲は、アクセスニットに含まれるすべてのゲノムレコードのうち、ＡＵ開始位置と最も右のゲノムレコード位置との間に含まれるゲノム範囲として定義される。ゲノム範囲に含まれる位置（または座標）の数は、ＡＵの終了位置からＡＵの開始位置を引いて「１」を加えることで計算できる。
【００８５】
本開示を通して、アクセスユニットカバー領域は、ＡＵ開始位置とＡＵ終了位置との間に含まれるゲノム範囲として定義される。
【００８６】
本開示を通して、アクセスユニットはその開始位置とその終了位置の間のゲノム領域をカバーするとも言われる。
【００８７】
ＡＵに含まれるゲノムレコードは、ゲノムレコード長よりも小さいＡＵ末端位置からの距離でのマッピング位置のみを有することができる。しかしながら、ゲノムレコード結果においてコード化されたリードまたはリードペアに属する塩基が、異なるＡＵｓで覆われたゲノム領域にマッピングされることが起こり得る。このような場合の発生を図８に示す。
【００８８】
リードまたはリードペアの一部、またはペアの完全なリード２が、それらの圧縮表現を含むアクセスユニットの範囲に属さないゲノム領域（すなわち、関連するエントロピーコード化）にマッピングされ得るという事実は、特定のゲノム領域にマッピングされる全てのリードまたはリードペアを取得する必要がある場合は常に問題になる。そのような操作は多くのゲノム分析用途において非常に一般的であり、そしてデータセットを構成する全てのアクセスユニットを検査して要求された全てのリードを確実に回収する必要性を回避するために非常に高い効率で実行される必要がある。本発明の開示は、最小量のデータに相当する最小数のアクセスユニットにアクセスしてデコードすることによって、リードおよびリードペアに対して高い圧縮性能をもたらす方法を提供するという問題に対処し、また任意の関心のあるゲノム領域上の少なくとも１つの塩基でマッピングされるすべてのリードにアクセスすることも保証するという問題に対する新しい解決法を提供する。
【００８９】
上記の定義によれば、アクセスユニットを構築するための２つの有用な方法を識別することができる。
１.  同じデータクラスのアクセスユニットのゲノム範囲が重複しない「非重複モード」
２.  同じデータクラスのアクセスユニットのゲノム範囲が重複する「重複モード」
【００９０】
「非重複モード」は、ゲノムデータが圧縮されてファイルとしてメモリに記憶されるシナリオにおいて、および記憶されたファイルが１つの記憶装置から別の記憶装置にストリーミングされるストリーミングシナリオにおいて、それはより効率的な選択的アクセス手順の実施を可能にするから好ましい。「重複モード」は、ゲノムデータセットの一部がアクセスユニットへのコーディングおよび送信のために利用可能になったときに、ゲノムシーケンスデータの全体が送信デバイスで利用可能になる前にストリーミングシナリオをサポートする。
【００９１】
ゲノムシーケンスリードと参照シーケンスの圧縮表現
ゲノムシーケンスへの効率的なアプローチの一般的な要素は、参照シーケンスに対するシーケンスデータの相関の利用である。人間集団の体性プロファイルが非常に多様化した場合であっても、人とは異なるヌクレオチド数の実際の部分は、ゲノム全体を構成するヌクレオチドの総数の約０．１％程度である。したがって、各個体を特徴付ける特定のゲノム情報は、ゲノム全体に担持された情報全体に対して非常に限定される。既存の参照ゲノムが利用可能である場合、以前のシーケンシングのために、または公開された"平均"コンセンサス参照として使用可能である、実際の情報をコード化する最も効率的な方法は、参照ゲノムとの差異のみを識別し、コード化することである。
【００９２】
ＦＡＳＴＱデータの形で生シーケンスリードでそれを実現するために、利用可能な参照ゲノム上でマッピングする予備的な前処理ステップを実行する。参照ゲノムが利用可能でない場合、または特定の参照の使用によって導入されたバイアスが望ましくない場合には、利用可能なシーケンスのリードをより長いシーケンスにアセンブルすることによる新しい参照シーケンスの構築は、可能な代替である。
【００９３】
既存のまたは構築された参照シーケンスに対して、シーケンスのリードがマッピングされている場合、各シーケンスのリードは、この開示では「リード記述子」または単に「記述子」として示される多くの要素によって完全に表現することができる。
【００９４】
例えば、参照シーケンスのセグメントと完全に一致するシーケンスリードの場合、シーケンスリードを表すのに必要な記述子の唯一のサブセットは、参照上のマッピング位置の座標（通常はシーケンスリードの左端の塩基のマッピング位置）、シーケンスリードの長さ自体、およびリードが参照シーケンス鎖に対して直接または逆ＤＮＡ鎖にマッピングされているかどうかを示す情報である。
【００９５】
シーケンスリードのすべての塩基が参照シーケンスのすべての塩基と一致するマッピング位置を見つけることができない場合、最小数のミスマッチを有するマッピング（またはマッピング）が保持される。そのような場合、マッピング位置と最小数または最小数に近いミスマッチとの対応で起こり得る置換、挿入、削除、およびクリップされた塩基も表現するために、異なるサブセットの記述子が必要とされる。そのような記述子のサブセットを用いて、記述子によって運ばれる情報および参照シーケンスによって運ばれる情報を使用して、シーケンスリードを再構築することができる。
【００９６】
マッピングプロセスは、他のタイプの情報を生成することもできる：複数の可能なマッピング位置および関連スコア、マッピングの品質、スプライシングされたリードの仕様、ペアに属するリードの２つの異なる基準(通常染色体)へのマッピング、シーケンスプロセスの特徴（例えば、ポリメラーゼ連鎖反応複製または光学的複製）。このようなすべての情報は、各サブセットを拡張する特定の付加的な記述子を必要とし、各サブセットは、各サブセットの記述子の適切なエントロピーコード化アルゴリズムに適用することによって圧縮される。
【００９７】
ゲノムシーケンスプロセスは、以下の理由により、リード重複（すなわち、同じゲノムシーケンスの２つ以上の正確なコピー）を生成することができる。
・ゲノムシーケンスプロセス(ポリメラーゼ連鎖反応複製)の化学的性質。
・データ取得処理(光学的複製)。リードのペアが両方とも同じタイル上にあり、実験に応じてリード間の距離が所定の構成パラメータより小さい場合、リードは光学的複製と呼ばれる。
【００９８】
したがって、各リードまたはリードペアは、マッピングプロセスの結果にしたがって、特定のサブセットの記述子によって一意に表現することができる。
【００９９】
ＳＡＭおよびＣＲＡＭのような一般に使用されるアプローチは、それらのマッピング情報を表すために必要とされる記述子の特定のサブセットに従って、リードまたはリードペアをコード化しない（つまり、シーケンスリードをデータクラスに分類せず、アクセスユニットに別々にコーディングしない）。圧縮形式では、単一のデータクラスに属するシーケンスリードのみを含む。ペアで生成されたシーケンスリードの場合、先行技術の手法は、本開示で説明されている本発明によって行われるようにクラスに分割された単一の要素としてそれらをコーディングしない。そのような先行技術の手法は、以下の制限および欠点によって特徴付けられる。
１.  参照シーケンスに対するマッピング結果に従ってシーケンスリードを別々のデータクラスに分類し、独自の記述子のスーパーセットを使用することなく、リードまたはリードペアをコーディングすることは、不十分な圧縮性能をもたらす非効率的な手法である。
２.  別々のシーケンスリードとしてのリードペアのコード化は、同じ情報を運ぶいくつかの記述子の重複を必要とし、従って非効率的でありそして劣った圧縮性能をもたらす。
３.  プロセスは、おそらく次世代シーケンシング（ＮＧＳ）技術の場合のように非常に大きくなり得る全データセットにおいてブルートフォースシーケンシャルサーチを必要とするので、リードペアを再構築するのに必要な情報の検索は複雑で非効率的になる。
４．  特定のゲノム領域にマッピングされたリードまたはリードペアへの選択的アクセスは、すべてのリードまたはリードペアが検索されるという保証を得るためにデータセット全体を検索することを必要とする。
【０１００】
単一のサブセットの記述子によってリードペアをコード化する場合、当業者には、以下の技術的利点が明らかである。
１.  明らかに冗長である両方のリードに共通の情報は、ペアを単一の要素としてコーディングすることによっては再現されない（例えば、リードペア識別子、マッピング距離、マッピング参照識別子、ＳＡＭファイルフォーマットの特定のフラグによって現在エンコードされる様々なマッピング品質情報）。
２.  相互ペアリング情報（すなわち、どのリードが手にしているリードのメイトであるかを提供する情報）の検索は簡単であり、さらなる処理を必要としない。逆に、先行グ術の手法では、全データ量を解析する必要がある。
【０１０１】
シーケンスデータの特定の部分への効率的な選択的アクセスを可能にし、それらをデジタルデータネットワーク上で輸送することを可能にするために、参照に対してアラインされたシーケンスリードを表すために使用される記述子のセットはアクセスユニット（ＡＵ）と呼ばれる論理的に別々の独立したデータブロックで構成される。各アクセスユニットは、単一のデータクラスの圧縮表現のみを含み、他のアクセスユニットとは無関係に、またはマッピングに使用される参照シーケンス領域のコード化表現を搬送するアクセスユニットのみを使用してデコードすることができる。これにより、選択的アクセスと順序外転送機能が可能になる。
【０１０２】
圧縮効率を向上させるために、本発明は、同じ参照シーケンス上にマッピングされた両方のペアを有する各リードペアについて「マッピング参照識別子」記述子を特定する必要性を排除する。各アクセスユニットは、同じ参照上にマップするリードまたはペアのみを含むことができる。このような解決策を使用して、参照シーケンス識別子を表す記述子は、各アクセスユニットまたはアクセスユニットのセットごとに１回だけコード化される必要がある(ＳＡＭ／ＢＡＭフォーマットで現在行われている各リード毎に繰り返さない)。
【０１０３】
上で表現された規則の唯一の例外は、異なる参照シーケンス（例えば染色体）上にマッピングされた２つのリードを有するリードペアの場合である。この場合、ペアは分割され、２つのリードは２つのの別個のゲノムレコードとしてコード化され、各エンコードされたリードは、その結合がマッピングされる参照シーケンスの識別子を含む。
【０１０４】
当業者であれば、均質な統計的性質を有する要素のグループに情報を分類することは、異種データセットに適用される汎用のコンプレッサ（例えば、ＬＺ型アルゴリズム）の使用に関してより良い圧縮性能を提供することを知っている。
結果として、特定の記述子のサブセットを用いてゲノムシーケンスリードをペアとしてコード化する場合、各エントロピーの個々のサブセットを特徴付けるより低いエントロピー、およびリードペアを再構築および検索するときのより高い処理効率のおかげでより高い圧縮が達成される。
【０１０５】
シーケンスリード記述子
このセクションは、参照シーケンスにマップされたゲノムシーケンスリードを表すために指定された記述子を導入する。各リード／リードペアを表すために使用される記述子の特定のサブセットは、参照シーケンスに対するマッピングの結果に依存する（すなわち、リードとリードペアと参照シーケンスとの間のミスマッチの有無）。
【０１０６】
位置
リードまたはリードペア位置は、リードまたはリードペアにおける最も左の塩基の参照シーケンス上のマッピング位置として定義される。「位置」タイプの記述子は、各リードまたはリードペア毎に必要である。「位置」記述子の値は、以下を表すことができる。
・参照シーケンス上のリードまたはリードペアにおける最も左の塩基の座標の値
・同一のアクセスユニットでコード化された以前のリードまたはリードペアの座標に対する差分
「位置」記述子は、各コード化されたリードまたはリードペアを表すために必要とされる。
本発明では、このような記述子はｐｏｓ記述子と呼ばれる。
【０１０７】
リードペアリング
リードペアの場合、各リードがどのようにしてメイトと関連付けられるかを表す記述子は、以下のように、いくつかの構文要素によって表現することができる。
・リードのベースと、メイト内の対応するベースとの間の座標の差（最も左にマップされたベースと、メイト内の最も左にマップされたベースなど）。本発明の開示において、そのような記述子はペア記述子と呼ばれる。
・メイトがマッピングする参照配列の識別子を含む参照シーケンス上のメイトの絶対座標。そのような表現オプションは次の場合に使用される。
・ペアの２つのリードが異なる参照シーケンス（例：染色体）にマッピングされている、または
・ペアの２つのリードが同じ参照にマッピングされているが、許容ペアリング距離の最大値として指定された値を超える塩基数で区切られている場合。
本発明では、このような記述子をａｂｓｐａｉｒ記述子と呼ぶ。異なる参照シーケンス上にマッピングされたメイトの場合、参照シーケンスを識別する記述子をｒｅｆｉｄと呼ぶ。
・ペアリードの場合、そのメイトのリードと分離されたコード化されたリードの数。本発明では、このような記述子をｐｃｏｕｎｔ記述子と呼ぶ。
【０１０８】
最大ペアリング距離
既に述べたように、２つのリードの間の関連付けはシーケンスプロセスによって生成された情報であり、参照シーケンスを用いたマッピング処理によりペアリング距離は決定される。シーケンシング過程を経ている可能性のあるＤＮＡ断片のサイズよりはるかに大きい値が存在する場合、本開示の以下で論じる多くの理由から、コーディングを２つの単一リードに分割し、それらを別々のアクセスユニットにコーディングする方がより適切で便利である。明らかに、２つのリードがペアとして生成されたという情報は維持される。これは、カバーされているゲノム領域に応じて（すなわち各染色体について）記述子「ペア」が全体のデータセットまたは各アクセスユニットについて想定することができる最大値を定義することによって得られる。言い換えれば、パラメータＭａｘＤは、記述子「ペア」が取り得る最大値として指定される。ＭａｘＤの値は、塩基の数（または参照シーケンス内の座標）として表され、それは、同じアクセスユニット内で単一のユニットとして、または異なるアクセスユニット内の個別のリードとしてリードペアをコード化するために使用されるべき記述子の特定のサブセットを決定するためにエンコーダによって使用される。
【０１０９】
リードペアは、３つの可能なケースに従って、記述子値のサブセットを使用してコード化される。
１.  ２つのリードは同じ参照シーケンス上にマップされ、最も左のベースの座標間の差はパラメータＭａｘＤより小さいかまたは等しい
２.  ２つのリードは同じ参照シーケンス上にマップされ、最も左のベースの座標の差はパラメータＭａｘＤより大きい
３.  ２つのリードは、異なる参照シーケンス（例えば、異なる染色体)にマッピングされる
【０１１０】
リードが単一のエンティティとしてコード化されていない場合、ペアリング距離の特別な予約値が、そのような情報を表すために使用される。これらの記述子は「距離フラグ」と呼ばれ、表２にリストされ説明される。
【０１１１】
上述のケースをカバーするために、ペア記述子が以下のように指定される。
【表１】
2020500382.tif 000003
テーブル１  各マッピングケースに対する、およびパラメータMaxDの関数におけるペアリング距離記述子の値。
【０１１２】
距離フラグおよび関連するセマンティクスの許容可能な値は、以下の表に提供される。
【表２】
2020500382.tif 000004
テーブル２  距離フラグ定義および関連するセマティック
【０１１３】
リードペアをコード化するためのペアリング距離記述子の使用の例は、以下のセクションにおいて提供される。
１．  同じペアのリード１とリード２とが、Ｘ染色体（ＩＤ＝＝２）にマッピングされ、Ｘ染色体上のリード２の絶対座標が１５５２４９５９４である。
【表３】
2020500382.tif 000005
【０１１４】
２．  同じペアのリード１とリード２は、ペアリング距離が１５４８９６１で同じ参照シーケンスにマッピングされる（「ｐａｉｒ」＞ＭａｘＤ）。リード２は、参照シーケンス上の座標３２５６７４９９にマップされる。
【表４】
2020500382.tif 000006
【０１１５】
３．  同一のペアのリード１とリード２を、同じ参照シーケンス上に353のペア距離を用いて同じ参照配列にマッピングされる（「ｐａｉｒ」＜ＭａｘＤ）。
【表５】
2020500382.tif 000007
【０１１６】
４．  リード１はペアではない。
【表６】
2020500382.tif 000008
【０１１７】
本開示では、ペアリング距離の形態を表す記述子のセットは、ペア記述子とも呼ばれる。ペアリング距離が特定の値を超える度に、リードペアを分割し、それらを別々のリードとしてコード化することは、高い圧縮性能を達成するという上記の目的と矛盾するように見えるかもしれないことを強調しなければならない。実際には、現在のシーケンシング技術によって得られた大きくて統計的に意味のある一連の実験データによって得られたペアリング距離の値は、数百塩基の値を中心とするガウス分布を表す。数シグマのペアリング距離の値を示すペアの数は、全体のデータの1％の割合である。したがって、そのような小さな割合のペアの分割は、コード化効率の無視できる程度の低下をもたらすが、特定のゲノム領域への選択的アクセス操作のための非常に大きな要因のアクセス帯域幅の減少および非常に高い全体の速度の増加を可能にする。
【０１１８】
リード長
可変長リードの場合、リードを構成するヌクレオチドの数として表される長さを表すために、リードごとに記述子を使用する。明らかに、可変リード長の場合には、各リードごとにリード長記述子が必要とされる。
この開示では、この記述子はｒｌｅｎ記述子とも呼ばれる。
【０１１９】
逆相補体
アデニン（Ａ）はチミン（Ｔ）のみと結合し、シトシン（Ｃ）はグアニン（Ｇ）のみと結合することから、ＤＮＡは各鎖が他方の鎖の相補鎖である二重らせんによって構成されている。したがって、一方のヌクレオチド組成を知るためには、もう一方の鎖を表すだけで十分である。これが、参照シーケンスが常に単一のシーケンスによって表される理由であり、マッピングツールは両方の鎖に属するリードについてマッピング位置を見つけることができる。リードがＤＮＡヘリックスの相補鎖にマッピングされる場合、それは「逆相補的」であると言われる。記述子は、そのような情報を運ぶために必要であり、オリジナルのリードがそれがマッピングされる参照シーケンスの逆相補であるかどうかを示す情報を運ぶ。この開示では、このような記述子はｒｃｏｍｐ記述子とも呼ばれる。
【０１２０】
未知の塩基位置
シーケンス化プロセスの間、装置は、ペアを構成するリードまたはリードの所与の位置で任意の塩基を呼び出すことができないことが生じる可能性がある。このようなイベントは、対応するリード位置における特別なシンボル「Ｎ」によって識別される。したがって、リードにおけるシンボル「Ｎ」の各々の発生を識別する記述子が必要とされる。
記述子は、以下を表すことができる。
・参照シーケンスの座標として表現されるペアリード又はリードにおける「Ｎ」シンボルの絶対位置、及び、参照シーケンスの座標として表現されたペアリード又はリードにおける「Ｎ」シンボルの絶対位置
・ペアリードまたはリードにおける前の「Ｎ」との相対的な位置
この開示では、このような記述子は、ｎｍｉｓ記述子とも呼ばれる。
【０１２１】
ミスマッチ位置およびタイプ
参照シーケンス上にマップされたシーケンスリードは、それらがマッピングされる参照シーケンスセグメントに関してミスマッチを提示することができる。これらのミスマッチは、以下のケースに従って、分類され、置換、削除または挿入として示される。
・参照シーケンスに対する異なるヌクレオチド(塩基)の存在(置換)
・マッピングされたリードにヌクレオチドが存在しない(欠失)
・参照に存在しないリード中のヌクレオチドの存在(挿入)
【０１２２】
各ミスマッチタイプの表現は、３つの記述子の使用を意味し、１つはリードまたはリードペアのミスマッチ位置（ｍｍｐｏｓとも呼ばれる）、もう1つは置換のみが存在する場合のミスマッチのタイプ（ｓｕｂｔｙｐｅとも呼ばれる）もう1つは、置換、挿入、および欠失が存在する場合のミスマッチのタイプを表す（ｍｍｔｙｐｅとも呼ばれる）。
【０１２３】
ソフトクリップ
参照シーケンス上にマッピングされたゲノムシーケンスリードは、マッピング位置において参照シーケンス上に存在するもののうちのいずれかまたはわずかに一致しないヌクレオチドの配列のそれらのエッジ部分に存在し得る。これらのシーケンス部分はソフトクリップと呼ばれ、シーケンス部分の塩基を表すシンボルのストリングによって単純に構成される記述子によって表すことができる。
リードは、リードの開始および／または終了位置に、１または２つのソフトクリップのみを許容することができる。
この明細書では、このような記述子は、ｓｃｌｉｐ記述子とも呼ばれる。
【０１２４】
マッピングフラグ
マッピングフラグは、以下のようなアライメントプロセスに関する特定の情報を搬送するために使用される。
・リードまたはリードペアのための複数のマッピング位置の存在
・スプライスされたリードの存在
・ＰＣＲ(ポリメラーゼ連鎖反応)または光学的複製の存在
・補助アライメント(露光装置が同じリードまたはリードペアに対していくつかの可能なマッピング位置を生成した場合に使用される)
・リードが品質チェック（すなわち、シーケンスプロセスの品質を測定するための技術ベンダ固有の手順）に不合格
この明細書では、このような記述子はｆａｇｓ記述子とも呼ばれる。
【０１２５】
マッピングされていないリード
リードまたはリードペアが参照シーケンスのいずれの位置にもマップされていない場合、リードまたはリードペアはマッピングされていないものとして分類される。このような場合、リードは、リードを表すシンボルの逐語的シーケンスによって構成される記述子によって表される。リードは、ゲノム領域を特定することによって、明らかに選択的にアクセスすることができない別個のクラスのデータに属するアクセスユニットに分割される。
【０１２６】
ミスマッチなしでリードまたはリードペアをコード化する方法
リードまたはリードペアが参照シーケンス上で完全にマップされる（すなわち、いかなるミスマッチもない）場合、以下の記述子のサブセットが、リードおよび関連するマッピング情報を再構成するために必要とされる。
・リードまたはリードペアごとの位置記述子（ｐｏｓ）
・リードまたは２つのリードペアごとの逆相補記述子（ｒｃｏｍｐ）
・リードごとの長さの記述子(可変長読み出しの場合)（ｒｌｅｎ）
・リードペアごとのペアリング記述子(ｐａｉｒ)
・セットのマッピングフラグ（ｆｌａｇｓ）
【０１２７】
本発明では、このようなリードまたはリードペアはクラスＰに属するものとして分類される。
位置記述子ｐｏｓは、リードまたはリードペアの最も左のマッピングベースの参照ゲノム上の位置を表す。
逆相補記述子ｒｃｏｍｐは、リードが参照シーケンスの直接または逆の鎖にマップされているかどうかを示す。
可変長の場合、記述子ｒｌｅｎは、リード長さを提供する。
ｐａｉｒ記述子は、ペア全体を再構築するために必要な情報を搬送する。記述子の構文はテーブル１に示す。
【０１２８】
クラスＰに属するリードペアのコード化の一例を、図１１に示し、図１２には、可変長の単一のリードのための例が示されている。
【０１２９】
未知の塩基によって表されるミスマッチのみを有するリードまたはリードペアをコード化する方法
リードまたはリードペアが参照シーケンス上でマップするが、少なくとも１つの未知のベースを含む場合、以下の記述子のサブセットが、リードおよび関連するマッピング情報を再構成するために必要とされる。
・リードまたはリードペアごとの位置記述子（ｐｏｓ）
・リードまたは２つのリードペアごとの逆相補記述子（ｒｃｏｍｐ）
・各未知の塩基ごとの位置（ｎｍｉｓ）
・リードごとの長さの記述子(可変長読み出しの場合)（ｒｌｅｎ）
・リードペアごとのペアリング記述子(ｐａｉｒ)
・セットのマッピングフラグ（ｆｌａｇｓ）
【０１３０】
クラスＰのサブセットに既に存在する記述子は、同じ構文および意味を有する。追加の記述子ｎｍｉｓは、シーケンスプロセスによって「未知」と呼ばれるベースのリード(ペア)内の位置を提供する(シンボル「Ｎ」)。
【０１３１】
本発明では、このようなリードまたはリードペアは、クラスＮに属するものとして分類される。
【０１３２】
クラスＮのリードペアのコード化の一例を図１３に示す。
【０１３３】
未知のベースおよび置換を有するリードまたはリードペアをコード化する方法
リードまたはリードペアが参照シーケンス上でマップされ、少なくとも1つの置換を示すが、欠損や挿入はない場合、リードおよび関連するマッピング情報を再構築するに、次の記述子のサブセットが必要とされる。
・リードまたはリードペアごとの位置記述子（ｐｏｓ）
・リードまたは２つのリードペアごとの逆相補記述子（ｒｃｏｍｐ）
・各置換の位置ごとの記述子（ｍｍｐｏｓ） 
・各置換タイプごとの記述子（ｓｕｂｔｙｐｅ）
・各未知の塩基ごとの位置（ｎｍｉｓ）
・リードごとの長さの記述子(可変長読み出しの場合)（ｒｌｅｎ）
・リードペアごとのペアリング記述子(ｐａｉｒ)
・セットのマッピングフラグ（ｆｌａｇｓ）
【０１３４】
クラスＰのサブセットに既に存在する記述子は、同じ構文および意味を有する。このようなシーケンスリードデータクラスに使用される追加の記述子は、置換のタイプを表すための置換の位置およびサブタイプを表すｍｍｐｏｓである。
【０１３５】
このタイプのリードペアのコード化の一例は図１４に提供される。
本発明では、このようなリードまたはリードペアはクラスＭに属すると言う。
【０１３６】
少なくとも１つの挿入、欠損またはソフトクリップを有するリードまたはリードペアのコード化
リードまたはリードペアが、少なくとも１つの挿入、欠損またはソフトクリップを含み参照シーケンス上でマップされる場合、以下の記述子のサブセットが定義される。
・リードまたはリードペアごとの位置記述子（ｐｏｓ）
・リードまたは２つのリードペアごとの逆相補記述子（ｒｃｏｍｐ）
・各ミスマッチ(挿入、欠失、置換)の位置ごとの記述子（ｍｍｐｏｓ）
・各ミスマッチ(挿入、削除、置換)のタイプごとの記述子（ｍｍｔｙｐｅ）
・各シーケンスのソフトクリップごとの記述子（ｓｃｌｉｐｓ）
・各未知の塩基ごとの位置（ｎｍｉｓ）
・リードごとの長さの記述子(可変長読み出しの場合)（ｒｌｅｎ）
・リードペアごとのペアリング記述子(ｐａｉｒ)
・セットのマッピングフラグ（ｆｌａｇｓ）
【０１３７】
クラスＭのサブセットに既に存在する記述子は、同じ構文および意味を有する。この場合に使用される追加の記述子は、置換，挿入および欠失の位置を表すｍｍｐｏｓ、ミスマッチ（置換，挿入および欠失）のタイプを示すｍｍｔｙｐｅと、ソフトクリップされたベースを示すｓｃｌｉｐｓとを含む。
【０１３８】
本発明では、そのようなリードまたはリードペアの開示は、クラスＩに属すると言われる。クラスＩに属するリードペアのコード化の例は、図１５に提供される。
【０１３９】
参照シーケンスに１つのリードのみがマッピングされるリードペア
リードペアがマップリード（クラスＰ、Ｎ、ＭまたはＩのいずれかに属する）およびアンマップリードによって構成されている場合、ペアはクラスＨＭ（Ｈａｌｆ  Ｍａｐｐｅｄ）と呼ばれる別のクラスに属するものとして分類される。
参照シーケンスにマッピングされたリードは、上記のクラス（Ｐ、Ｎ、Ｍ、Ｉ）のいずれかであり得、各クラスについて既に説明された記述子のサブセットを使用してコード化される。マッピングされていないリードは、適切なエントロピーコーダを使用してそれを表す一連のシンボルを圧縮することによってエンコードされる。
【０１４０】
参照シーケンス記述子
参照シーケンスは、対応する生物学的サンプル中に見出され得るヌクレオチドを表すシンボルのストリングとして一般に表される。ＤＮＡの場合、ヌクレオチドは４つであり、シンボルＡ、Ｃ、ＧおよびＴによって表される。ＲＮＡの場合には、ＴはＵに置き換えられる。５番目のシンボルは、シーケンシング装置が実験によって要求された信頼度に従ってヌクレオチドの種類を決定することができなかったシーケンス中の座標を表すために付加される。本開示では、参照シーケンスは、完全に１つのアクセスユニットにコード化することも、２つ以上のサブシーケンスに分割することもできる。
【０１４１】
エントロピーコード化される参照シーケンスまたはサブシーケンスを表すために使用される記述子は、それぞれのアルファベットの許容されたシンボルに関するシーケンスまたはサブシーケンスの逐語的表現である。
【０１４２】
マッチングルールに従ったシーケンスリードの分類
シーケンシング装置によって生成されたシーケンスリードは、開示された発明によって、１つ以上の既存の参照シーケンスに関するアラインメントのマッチング結果に従って５つの異なる「クラス」に分類される。
【０１４３】
参照シーケンスに対してヌクレオチドのＤＮＡ配列をアライメントさせる場合、以下のケースが同定されうる。
１．  参照シーケンス内の領域が、エラーなしに（すなわち、完全なマッピング)シーケンスリードと一致することが判明する。このようなヌクレオチド配列は、「完全に一致するリード」と呼ばれ、または「クラスＰ」として示される。
【０１４４】
２．  参照シーケンス内の領域は、リードを生成するシーケンシング装置がいずれの塩基（またはヌクレオチド）ももたらせなかった位置の数によってのみ決定されるタイプおよび数のミスマッチを有するシーケンスリードと一致することが判明する。このようなタイプのミスマッチは、未定義のヌクレオチド塩基を示すのに使用される「Ｎ」の文字で表される。この明細書では、このタイプのミスマッチを「nタイプ」ミスマッチと呼ぶ。このような配列は、「Ｎミスマッチリード」または「クラスＮ」と呼ぶ。リードが「クラスＮ」に属すると分類されたら、一致の不正確さの程度を所定の上限に制限し、有効な一致と見なされるものとそうでないものとの間に境界を設定することが有用である。したがって、クラスＮに割り当てられたリードは、リードに含めることができる未定義の塩基（つまり「Ｎ」と呼ばれる塩基）の最大数を定義する閾値（ＭＡＸＮ）を設定することによっても制約を受ける。そのような分類は、対応する参照シーケンスを参照したときにクラスＮ共有に属するすべてのリードが圧縮データに選択的データ検索を適用するための有用な基準を構成する要求最小マッチング精度（または最大ミスマッチ度）を暗黙的に定義する。
【０１４５】
３．  参照シーケンス内の領域は、存在する場合、リードを生成するシーケンシング装置がいかなるヌクレオチド塩基ももたらすことができなかった位置の数によって決定されるタイプおよび数のミスマッチ（すなわち「ｎタイプ」ミスマッチ）に加えて、参照に存在するものとは異なる塩基がもたらされた数のミスマッチとを有するシーケンスリードと一致することが判明する。「置換」として示されるそのようなタイプのミスマッチはまた、一塩基変異（ＳＮＶ）または一塩基変異多型（ＳＮＰ）とも呼ばれる。この明細書では、このタイプのミスマッチは「sタイプ」のミスマッチとも呼ばれる。次いで、シーケンスリードを「Ｍミスマッチリード」と呼び、そして「クラスＭ」に割り当てる。「クラスＮ」の場合と同様に、「クラスＭ」に属するすべてのリードについても、一致の不正確さの程度を所定の上限に制限し、有効な一致と見なされるものとそうでないものとの間に境界を設定することが有用である。したがって、クラスＭに割り当てられたリードは、1つは存在する場合「ｎタイプ」のミスマッチである「ｎ」の数（ＭＡＸＮ）、もう1つは置換「ｓ」の数（ＭＡＸＳ）の閾値のセットを定義することによっても制約を受ける。第３の制約は、数値「ｎ」と「ｓ」の両方の関数ｆ（ｎ、ｓ）によって定義される閾値である。そのような第３の制約は、任意の意味のある選択的アクセス基準に従ってマッチングの不正確さの上限を有するクラスを生成することを可能にする。例えば、限定するわけではなく、ｆ（ｎ、ｓ）は、（ｎ＋ｓ）１／２または（ｎ＋ｓ）、あるいは「クラスＭ」に属するリードに対して認めらる最大マッチング不正確レベルに境界を設定する任意の線形または非線形の式とすることができる。そのような境界は、一方または他方に適用される単純な閾値を超えて「ｎタイプ」のミスマッチ「ｎ」の数および「ｓタイプ」のミスマッチ（置換）「ｓ」の数の任意の可能な組み合わせに対するさらなる境界を設定することを可能にするので、様々な目的のためのシーケンスリードの分析時に所望の選択的データ検索を圧縮データに適用するための非常に有用な基準を構成する。
【０１４６】
４．  第４のクラスは、「挿入」、「欠失」（別名「インデル」）および「切り取られた」のうちのいずれかのタイプの少なくとも１つのミスマッチ、さらに存在する場合はクラスＮまたはＭに属する任意のミスマッチタイプを提示するシーケンスリードによって構成される。そのような配列は、「Ｉミスマッチリード」と称され、そして「クラスＩ」に割り当てられる。挿入は、参照には存在しないがリードシーケンスには存在する1つまたは複数のヌクレオチドのさらなるシーケンスによって構成される。この明細書では、このタイプのミスマッチを「iタイプ」ミスマッチと呼ぶ。挿入されたシーケンスがシーケンスの端にある場合、参照では「ソフトクリップ」とも呼ぶ（すなわち、ヌクレオチドは参照と一致しないが、廃棄される「ハードクリップ」ヌクレオチドとは対照的にアラインされたリードに保持される）。この明細書では、このタイプのミスマッチを「ｃタイプ」のミスマッチと呼ぶ。ヌクレオチドの保持または廃棄はアライナ段階によって行われる決定であり、シーケンシング装置または次のアライメント段階によって決定されるリードを受け取りそして処理する本発明に開示されるリードの分類子によっては行われない。欠失は、参照に対してリードにある「ホール」（欠けているヌクレオチド）である。この明細書では、このタイプのミスマッチを「ｄタイプ」ミスマッチと呼ぶ。クラス「Ｎ」および「Ｍ」の場合と同様に、マッチングの不正確さに対する制限を定義することは可能であり適切である。「クラスＩ」に対する制約のセットの定義は、「クラスＭ」に対して使用されたのと同じ原理に基づいており、そしてテーブル１の表の最後の行に報告する。クラスＩデータに許容される各タイプのミスマッチについての閾値に加えて、さらなる制約は、ミスマッチの数「ｎ」、「ｓ」、「ｄ」、「ｉ」および「ｃ」の任意の関数ｗ（ｎ、ｓ、ｄ、ｉ、ｃ）によって決定される閾値によって定義される。そのような追加の制約は、任意の意味のあるユーザ定義の選択的アクセス基準に従って、マッチングの不正確さの上限を有するクラスを生成することを可能にする。例えば、限定するわけではなく、ｗ（ｎ、ｓ、ｄ、ｉ、ｃ）は、（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）１／５または（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）または「クラスI」に属するリードに対して認められる最大マッチング不正確レベルに境界を設定する任意の線形または非線形の式とすることができる。そのような境界は、「クラスＩ」のリードで許容されるミスマッチの数のあらゆる可能な組み合わせに対して、各タイプの許容されるミスマッチに適用される単純な閾値を超えてさらなる境界を設定することを可能にするので、様々な目的のためのシーケンスリードの分析時に所望の選択的データ検索を圧縮データに適用するための非常に有用な基準を構成する。
【０１４７】
５．  第５のクラスは、参照を参照するときに各データクラスについて有効であると見なされる（すなわち、テーブル１に規定される最大マッチング不正確さに対する上限を定義するマッチングルールのセットを満たさない）マッチングを見出すすべてのリードを含む。そのようなシーケンスは、参照シーケンスを参照するとき「マッピングされていない」と言われ、「クラスＵ」に属すると分類される。
【０１４８】
マッチングルールに従ったリードペアの分類
前のセクションで指定された分類はシングルシーケンスリードに関するものである。２つのリードが可変長の未知のシーケンスで区切られていることがわかっている、ペアでリードを生成するシーケンステクノロジ（例：Ｉｌｌｕｍｉｎａ Ｉｎｃ.）の場合、ペア全体を単一のデータクラスに分類することを検討するのが適切である。互いに結合されているリードは、その「メイト」と呼ばれる。
【０１４９】
両方のペアのリードが同じクラスに属する場合、ペア全体のクラスへの割り当ては明白であり、ペア全体は任意のクラスに対して同じクラスに割り当てられる（すなわち、 Ｐ、Ｎ、Ｍ、Ｉ、Ｕ）。２つのリードが異なるクラスに属しているが、どちらも「クラスＵ」には属していない場合、ペア全体が次の式に従って定義される最も高い優先順位を持つクラスに割り当てられる。
Ｐ<Ｎ<Ｍ<Ｉ
「クラスＰ」が最も低い優先順位を有し、「クラスＩ」が最も高い優先順位を有する。
【０１５０】
リードのうちの1つのみが「クラスＵ」に属し、そのメイトがクラスＰ、Ｎ、Ｍ、Ｉのいずれかに一致する場合、第６のクラスは「ハーフマップ」を表す「クラスＨＭ」として定義される。
【０１５１】
そのような特定のクラスのリードの定義は、それが参照ゲノムに存在するギャップまたは未知の領域（別名、ほとんど知られていないまたは未知の領域）を決定することを試みるために使用されるという事実によって動機付けられる。そのような領域は、既知の領域にマッピングすることができるペアリードを使用して、エッジでペアをマッピングすることによって再構築される。図２０に示すように、それからマッピングされていないメイトを使用して、未知の領域のいわゆる「コンティグ」を構築する。したがって、そのようなタイプのリードペアのみへの選択的アクセスを提供することにより、先行技術の解決策を使用することは完全に検査されることを必要とするであろう大量のデータセットによって生じるそのようなデータの非常に効率的な処理を可能にする関連する計算の負担を大幅に減らす。
【０１５２】
以下のテーブルは、各リードが属するデータのクラスを定義するために、リードに適用されるマッチングルールを要約する。ルールは、ミスマッチのタイプ（n、s、d、i、およびcタイプミスマッチ）の有無によって、表の最初の５列に定義される。第６列は、各ミスマッチタイプおよび可能性のあるミスマッチタイプの任意の関数f(n、s)およびｗ(n、s、d、i、c)についての最大閾値に関するルールを提供する。
【表７】
2020500382.tif 000009
2020500382.tif 000010
テーブル３  本発明の開示において定義される、各シーケンスリードがデータクラスに分類されるために満たさなければならないミスマッチのタイプと制約のセット。
【０１５３】
定義のまとめ
【表８】
2020500382.tif 000011
2020500382.tif 000012
2020500382.tif 000013
2020500382.tif 000014
テーブル４  アクセスユニットに関連する要素および特徴の定義のまとめ
【０１５４】
圧縮記述子サブセットのアクセスユニットへの分割およびファイルシステムへのアクセスユニットの格納またはクライアントへのストリーミングのためのモード
リードまたはリードペアが記述子の適切なサブセットによってゲノムレコードに分類およびコード化されると、エントロピーコード化記述子のストリームは、それらの相対的アクセスユニット範囲によって特徴付けられるアクセスユニットに分割される。言い換えれば、アクセスユニットは、各アクセスユニットに関連付けられているアクセスユニット範囲内の最も左側の塩基をマッピングするゲノムレコードのみを収集する。ゲノムデータセットのアクセスユニット範囲の定義は、非重複または重複の２種類である。
【０１５５】
アクセスユニットがファイルシステムに格納されるとき、物理的な記憶媒体上のアクセスユニットをマッピングするための２つの有用なモードが定義され実行されることができる。
ａ）異なる記述子ストリームからの、しかし同じアクセスユニットに属するデータのブロックが連続して格納されるアクセスユニット連続（ＡＵＣ）モード。
ｂ）同一の記述子に属するが異なるアクセスユニットに属するデータブロックがファイルシステムの連続領域に記憶される記述子ストリーム連続（ＤＳＣ）モード。
【０１５６】
ＡＵＣモードはファイルシステムアクセスの最小化にとって特に興味深い。ゲノム領域に基づく選択的アクセスの場合は、同じアクセスユニットに属するデータを記憶装置の連続領域に記憶することが可能になるからである。
【０１５７】
ＤＳＣモードは、記憶装置の隣接領域内の同じ記述子に属するすべてのデータブロックをグループ化する異なるデータ編成を実施する。このため、ＤＳＣモードは、例えば、１つまたは任意のサブセットの記述子ストリームのみを暗号化する必要がある場合など同じタイプの記述子のデータ連続性は動作をより効率的にすることができ、ゲノム領域ベースの選択的アクセス以外の他の使用例にも興味深く効率的である。
【０１５８】
ＡＵＣおよびＤＳＣストレージマッピングモード用に定義されたデータマッピング構成の図を図１６に示す。
【０１５９】
さらに、ＡＵＣモードは、記憶媒体上のＡＵ順序付けに関して２つの異なる方法で実施することができる。記憶装置内のアクセスユニットの順序は、同じデータクラスのすべてのアクセスユニットが記憶装置の同じ領域に記憶されている（クラス連続モードＣＣ）クラスベース、または記憶装置の同じ領域に記憶されている同じまたは最も近いゲノム領域へのマッピングするすべてのアクセスユニットを含むゲノム領域ベース（ゲノム領域連続モードＧＲＣ）のいずれかであり得る。ＡＵＣ／ＣＣモードは単一クラスのデータにのみアクセスするときより効率的になり、ＡＵＣ／ＧＲＣモードは同じゲノム領域にマッピングする異なるクラスのデータにアクセスするときより効率的になる。ＣＣおよびＧＲＣストレージマッピングモードによって定義されているデータマッピング構成の説明を図１７に示す。
【０１６０】
ＡＵのセグメントを搬送するトランスポートパケットを用いてクライアントにＡＵをストリーミングする場合、明らかにＡＵＣモードのみを採用することができる。
【０１６１】
アクセスユニットに含まれるデータに関連するゲノム領域を特徴付ける情報（すなわち、アクセスユニット範囲およびアクセスユニットが格納され、構造化され、以下の情報を含むマスターインデックステーブルと呼ばれる多次元データ構造に利用可能である。
１.  参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も左にマッピングされた塩基の、ヌクレオチド数として表される位置。
２．  参照シーケンスに関して、アクセスユニットに含まれるすべてのリードまたはリードペアの中で最も右にマッピングされた塩基の、ヌクレオチド数として表される位置。
３．  アクセスユニットサイズの一覧（ＡＵＣモード使用時） 
４．  データセットペイロードの第１のバイトを基準とした、各アクセスユニットの各記述子データブロックの第１のバイトのオフセット数のリスト（バイト数）。
【０１６２】
データをアクセスユニットに分割する方法、およびアクセスユニットをファイルシステムに格納する方法に関する情報は、データアクセスプロセスを最適化できるようにするために必要である。これが、そのような情報がデータセットヘッダに登録され、選択的データアクセスがデコード化ユニットによって実行されるときに利用可能にされる理由である。
【０１６３】
ＡＵＣとＤＳＣモードの技術的な利点
【表９】
2020500382.tif 000015
テーブル５  ＡＵＣとＤＳＣモードの技術的な利点
【０１６４】
選択的データアクセスによるゲノム領域の最適化
特定のゲノム領域への選択的なアクセスは、以下のように行われる１）参照シーケンス上の指定された領域をカバーするアクセスユニットを識別するステップと、２）適切なデータにアクセスするステップとを含む。次のセクションは、選択的データアクセス要求に応答して識別されたＡＵのデータへのアクセスを最適化することができる使用される記憶モード（ＡＵＣまたはＤＳＣ）を知る方法を説明する。
【０１６５】
ＤＳＣモードを使用してＡＵが記憶されるときのデータアクセス
図１６を参照すると、Blocks B_0_M to B_N_Mで構成されるアクセスユニットＭにアクセスするとき、マスタインデックステーブルのBlock_Byte_Offset[Sequence_ID] [Class_I D] [M] [0]エントリは、アクセスユニットの最初のバイトを探すために使用される。
１）fseek(FILE, Block_Byte_Offset[Sequence_ID][Class_ID][M][0], Dataset_Payload_First_Byte_Offset)
【０１６６】
次に、ブロックのサイズを知り、それに応じてペイロードを読み取るために、Block_Byte_Offset[Sequence_ID][Class_ID][M+1][0] と Block_Byte_Offset[Sequence_ID][Class_ID][M][0]の差が計算される。
２）fread(payload_buffer, Block_Byte_Offset[Sequence_ID][Class_ID][M+1][0] -Block_Byte_Offset[Sequence_ID][Class_ID][M][0], 1, FILE)
【０１６７】
ステップ１と２は、アクセスユニット内のすべてのブロックに対して、最後のブロックがindex N = Num_Descriptors[Sequence_ID][Class_ID] - 1になるまで繰り返される。
2xN+1) fseek(FILE, Block_Byte_Offset[Sequence_ID][Class_ID][M][N], Dataset_Payload_First_Byte_Offset)
2xN+2) fread(payload_buffer, Block_Byte_Offset[Sequence_ID][Class_ID][M+1][N+1] -Block_Byte_Offset[Sequence_ID][Class_ID][M][N], 1, FILE)
【０１６８】
ＡＵＣモードを使用してＡＵが記憶されるときのデータアクセス
図１６を参照すると、Blocks B_0_M to B_N_Mで構成されるアクセスユニットＭにアクセスするとき、マスタインデックステーブルの Block_Byte_Offset[Sequence_ID][Class_ID][M][0] エントリは、アクセスユニットの最初のバイトを探すために使用される。
１）fseek(FILE, Block_Byte_Offset[Sequence_ID][Class_ID][M][0], Dataset_Payload_First_Byte_Offset)
次に、マスターインデックステーブルのAU_Size[Sequence_ID][Class_ID][M]エントリを使用して、アクセスユニットをモノリシックなデータチャンクとして読み取る。
２）fread(payload_buffer, AU_Size[Sequence_ID][Class_ID][M], 1, FILE)
【０１６９】
ゲノム領域ベースの選択的アクセスによるＡＵＣおよびＤＳＣモードに対するデータアクセス効率の比較
選択的アクセス要求に関連する特定のゲノム領域をカバーすると識別されたＡＵに属するデータを検索することは、１回のシークと１回の読み取りのみであるのでＡＵＣモードが使用されるときより効率的であり、ＤＳＣモードで必要な２×Ｎ＋２シーク＋読み取りの操作と比較してＡＵ当たりのディスクへのアクセス数が大幅に最小化される。物理的記憶装置は一般にそれらのスループットと比較して比較的高いシーク時間を有する。つまり、読み取りを開始するのに比較的時間がかかるが、開始すると、連続したバイトを比較的速く読み取ることができる。これが、シークを最小限に抑え、モノリシックな読み取りを優先することが常に望ましい理由でである。データセットヘッダで利用可能なＡＵＣモードが採用されているという保証に関する情報は、効率的なモノリシックな読み取りを実装できるようにするために必要である。
【０１７０】
記述子ストリーム選択的データアクセスの最適化
一部のディスクリプタのみに別々にアクセスすることや、1つまたは複数のディスクリプタストリームのサブセットに別々に暗号化／デコード化を適用することなど、使用例によっては、ＤＳＣモードのほうがはるかに効率的である。ファイルシステム内のＤＳＣデータ格納モードがデータセットヘッダ内の適切なシグナリングによって使用されることを知っていることで、以下のセクションで説明するように、ゲノム情報のそのような処理ははるかに効率的になる。
【０１７１】
ＤＳＣモードを使用してＡＵが記憶されるときのデータアクセス
Error! Reference source not found.を参照すると、Blocks B_N_0 to B_N_Mで構成される記述子ストリームＮ(Class_ID=C, Descriptor_ID=D)にアクセスするとき、マスタインデックステーブルのBlock_Byte_Offset[0][C][0][D]エントリは、記述子ストリームの最初のバイトを探すのに使用される。
１） fseek(FILE, Block_Byte_Offset[0][C][0][D], Dataset_Payload_First_Byte_Offset)
【０１７２】
次に、マスタインデックステーブルのDescriptors_Stream_Size[C][D]エントリを使用して、Descriptors_Streamをモノリシックなデータのまとまりとして読み出す。
２） fread(payload_buffer, Descriptors_Stream_Size[C][D], 1, FILE)
これに限定されるものではないが、例えば暗号化などのデータアクセスおよび／または他の処理操作が、その後、payload_bufferに対して実行される。
【０１７３】
ＡＵＣモードを使用してＡＵが記憶されるときのデータアクセス
Error! Reference source not found.を参照すると、Blocks B_N_0 to B_N_Mで構成される記述子ストリームＮ(Class_ID=C, Descriptor_ID=D)にアクセスするとき、マスタインデックステーブルのBlock_Byte_Offset[0][C][0][D]エントリは、記述子ストリームの最初のバイトを探すのに使用される。
１） fseek(FILE, Block_Byte_Offset[0][C][0][D], Dataset_Payload_First_Byte_Offset)
【０１７４】
次に、ブロックのblock_headerが読み出される
２） fread(header_buffer, Block_Header_Size, 1, FILE)
その後、Block_HeaderのＢＳフィールドを使用してブロックペイロードを読み取る。
３） fread(payload_buffer[0], BS, 1, FILE)
記述子ストリームを構成する全てのブロック（Ｎ）について、ステップ１から３を繰り返す。
3xN+0) fseek(FILE, Block_Byte_Offset[Seq_Count][C][N][D], Dataset_Payload_First_Byte_Offset)
3xN+1) fread(header_buffer, Block_Header_Size, 1, FILE)
3xN+2) fread(payload_buffer[N], BS, 1, FILE)
【０１７５】
記述子ストリームベースの選択的アクセスによるＡＵＣモードおよびＤＳＣモードに対するデータアクセス効率の比較
記述子ストリームアクセスおよび処理は、ＡＳＣモードでの３×Ｎ＋２アクセスと比較して、Descriptors_Stream当たり記憶装置への２回のアクセスしか必要とされないので、ＤＳＣモードを使用することによってより効率的である。
【０１７６】
ＤＳＣモードがデータを格納するための使用であるという情報がデータセットヘッダで利用可能である場合、最適化された（最小）数のストレージアクセスの実行が可能である。
データの検索およびデコード化側では、アクセスユニットへのデータのどの区分化が実施され（重複または非重複）、選択的アクセスプロセスを最適化するためにＤＳＣ、ＡＵＣ／ＣＣまたはＡＵＣ／ＧＲＣが使用される。次に、選択されたゲノム領域にマッピングされているすべてのリードが確実に回復されるように、どのアクセスユニットをデコード化する必要があるかを識別することだけが必要である。アクセスユニットの範囲とアクセスユニットのカバーする領域に関する情報、およびリードペアを単一のエンティティとしてコーディングするか、単一のリードに分割するかを決定する閾値は、それぞれデータセットヘッダーのマスターインデックステーブルで利用できる。このような情報は、次のセクションで詳しく説明する。
【０１７７】
リードペアおよび選択的アクセス
単一エンティティとしてのリードペアのコード化表現は、ペアを構成する２つのリードの参照上のマッピング位置の座標差として「ペア距離」を表すことによって特徴付けられる。そのような記述子は、原則として、ゼロから参照シーケンス全体のサイズまでの任意の数の間の任意の可能な値（例えば、ヒト第１染色体について約２億５０００万塩基）を想定することができる。そのような可能性は、そのような特定の領域に属する全てのリードが全ての関連する情報で正しくデコードされ、データアクセス要求の結果として提供されることを保証することが要求されるときに特定のゲノム領域のみに属するアラインシーケンスデータへの選択的アクセスをデータ量アクセスと処理の両方に関して計算的に拡張的にする。この問題は、解決するのがさらに困難であり、そしてペアにおける２つのリードが２つの異なる参照シーケンスにマッピングされるとき、はるかに多くの帯域幅および処理リソースを必要とする。次のセクションでは、本発明の開示が、独立したアクセスユニットに分類された記述子を使用してコード化されたゲノムシーケンスリードペアを選択的にアクセスする問題をどのように解決するかを説明する。
【０１７８】
アラインされたシーケンスリードへの選択的アクセス
１つまたは複数の参照シーケンスにマッピングされたゲノムデータへの選択的アクセスは、通常、参照シーケンス（例えば染色体）の選択されたゲノム領域の最初（最後）および最後（最後）の座標を特定することによって行われる。
【０１７９】
開始座標および終了座標によって定義されるゲノム領域上にマッピングされたリードまたはリードペアを検索するために選択的アクセスが実行されるとき、検索およびデコードプロセスの２つの動作は、問題に対する有用な解決策として考慮される。
１  デコーダは、特定のゲノム領域と重複する全ゲノムリードまたはゲノムセグメント(単一の塩基まで)のみを検索する。検索操作は、全リード(指定されたゲノム領域に完全に含まれる場合)を含むまたは指定されたゲノム領域にマッピングされたリード部分のみをマッピングするように構成されている。
２  デコーダは、指定されたゲノム領域上にマップされた少なくとも１つのベースを有する全てのリードまたはリードペアを返す。
【０１８０】
図１０は、アイテム１に記載されているようなデコード化動作の場合、リード７０１、７０２、７０３および７０４が部分的にのみ返される（指定されたゲノム領域と重なるそれらのセグメント）のに対し、記載された検索動作およびデコード化動作の場合、アイテム２では、それらは完全に返される。所望の結果を得るための両方の動作の場合において、アクセスユニットｉおよびｉ＋１はデコードされなければならない。
【０１８１】
ケース１およびケース２は、デコード化アプリケーションによって返されるデータ量のみが異なるが、特定のゲノム領域に対応するデータへの所望のアクセスを提供するためにどのアクセスユニットをデコード化する必要があるかを決定する必要性を共有する。本発明は、ポイント１および２で箇条書きされた動作ケースをサポートし、必要なデータアクセス帯域幅および処理（すなわちデコード）の複雑さを最小限に抑えることと等価である同時にデコードおよび検査を必要とするアクセスユニットの数を最小限に抑えることができる新しいアルゴリズムを定義する。デコード化する必要があるアクセスユニットの識別は、データセットヘッダで利用可能な情報にアクセスして解析すること、特定の場合には部分的にもマスタインデックステーブル、圧縮ドメインで容易にアクセス可能なすべての情報にアクセスすることだけでできる。
【０１８２】
アクセスユニットに圧縮されたシーケンスデータへの選択的アクセス
ゲノムデータがアクセスユニットに圧縮され、各アクセスユニットが特定のゲノム領域をカバーする場合、いくつかのリードはアクセスユニット範囲の端にまたがってマッピングされ、リードの一部は１つのアクセスユニット範囲に属するゲノム位置にマッピングされ、他のリードの一部は前後のアクセスユニットに属するゲノム領域にマッピングされる（それぞれアクセスユニット範囲の境界についての参照シーケンス上のより小さな座標またはより大きな座標に関して）。この可能性の発生は、図７に明確に示されている。
【０１８３】
イルミナシーケンシング技術の非常に一般的な場合のように、リードペアの存在は、一貫性のある効率的な選択的データアクセスメカニズムの実施に対してさらに大きな挑戦をもたらす。これは、圧縮効率を確実にするために、各リードペアを単一の実体として表す情報は、特定のゲノム領域のみをカバーする単一のアクセスユニットでのみコード化することができるという事実によるものである。そのため、特定のゲノム領域にマッピングされているすべてのリードペアにアクセスする必要がある場合は、そのような領域をカバーするすべてのアクセスユニットをデコードするだけでは不十分である。ペアのいずれのリード２も、選択的アクセスが必要とされるゲノム領域にマッピングされ得る。当業者には容易に理解され得るように、このような手順は、特定のゲノム領域をカバーするアクセスユニットに記憶された圧縮シーケンスデータの選択的アクセスが提供し得るおよび提供すべき全ての利点を帯域幅および処理複雑性の低減に関して危険にさらす。
【０１８４】
要約すると、単一のエンティティとして表現され（高い圧縮性能のために）、そして特定のゲノム領域をカバーするアクセスユニット内に圧縮された形で含まれるペアを読み取るための効率的な選択的アクセス手順を達成することの障害は特に困難である。
１.アクセスユニット範囲の端の近くにマッピングされたリードペアは、アクセスユニット範囲の外側にマッピングされたリードの一部または全体を持つことができる。
２．リードとそのメイトとの間の距離が大きくなる可能性があり、リード２は他のアクセスユニットによってカバーされる領域にマッピングされることになる可能性があるが、リード１がコード化されるアクセスユニット内の単一エンティティとしてコード化される。
【０１８５】
この２つの可能性が図８に示されており、そこでは全てのリードペアがＡＵ１でコード化されているが、ペアのいくつかのセグメントは他のアクセスユニットによってカバーされるゲノム領域をマッピングする。
【０１８６】
本開示において提供される選択的アクセス問題の効率的な解決策は、ケース１とケース２の両方を解決し、所望のゲノム領域にマッピングするすべてのリードにアクセスすることを保証する特定のコード化およびデコード化技術を定義することに基づく。
【０１８７】
デコード化する必要があるアクセスユニットの最小数を決定する。そのような最適化制約は、データの任意の所与の区分化について重複または非重複アクセスユニット範囲へと検索されるゲノム領域に関連する最小量のデータにアクセスし、それをデコードすることと等価である。
【０１８８】
単一のデータ構造を使用することによってリードペアが圧縮され、そのようなコーディング手法が本開示に記載されているアクセスユニット分割手法と組み合わされると、以下のケースが起こり得る（図８参照）。
・アクセスユニット内のリードの一部であって、そのリードがマッピングされているゲノム領域と部分的にのみ重複する範囲を有する（２０１）。これはシングルリードの場合も同様であるが、平均距離が平均リード長よりもはるかに大きいペアエンドリードを扱う場合、問題はより頻繁に発生する。
・アクセスユニットの完全なリードが、リードがマッピングされているゲノム領域をカバーしていない（２０２及び２０３）
・上記で指定された２つの可能性の組み合わせ（２０４）
【０１８９】
ペアリング距離とリードマッピング位置の値が異なる場合の、上記の３つのケースの図解を図８に示す。図８の例では、リードペアＲＰ２およびＲＰ４は、アクセスユニット１によって完全にカバーされる領域にマッピングされ、ペアＲＰ１、ＲＰ３およびＲＰ５内のヌクレオチドの一部は、アクセスユニット２によってカバーされる位置にマッピングされ、そしてＲＰ６ｈｓアクセスユニット１および２から遠く離れているメイトをもつ。
【０１９０】
アラインシーケンスリードデータとアクセスユニットへの選択的アクセス
以下のセクションでは、参照シーケンス上にマッピングされ、アクセスユニットでコード化されたリードまたはリードへの効率的な選択的アクセスを実施するための方法について説明する。本発明に開示された方法は、全ての単一リードまたはペアに属するリードが選択的アクセスが必要なゲノム領域Ｒ上の少なくとも１つの塩基とマッピングするという保証を得るためにデコードされるべき最小数のアクセスユニットを決定および識別する利点を提供する。
【０１９１】
参照シーケンス上の座標ｓおよびｅによって識別されるゲノム領域に属するコード化（圧縮）データへのアクセスが必要とされる場合、本発明で開示される手順は、アクセスおよびデコードに必要なアクセスユニットがどれであるかを識別する。アクセスが要求されている選択されたゲノム領域Ｒ上にマッピングされた少なくとも１つのヌクレオチドを有する全てのリードが検索されるという保証を有する。
所与の１組のアクセスＵについて、開始位置ｓおよび終了位置ｅに関して指定された参照シーケンスの任意のゲノム領域Ｒ、ならびに開始座標ｓおよび終了座標ｅによって定義される関連するカバーされた領域を考える。「アクセスされ、デコードされ、検査される必要があるアクセスユニットの最小セットは、関連する開始座標ｓまたは終了座標ｅ」が以下の式のうちの１つを満たすすべてのアクセスユニットＡＵを識別することによって決定できる。
・ｓ≦ｓｉ≦ｅ
または
・ｓ≦ｅｉ≦ｅ
または
・ｓｉ≦ｓおよびｅｉ≧ｅ
【０１９２】
コード化プロセス中に各アクセスユニットについてｓｉおよびｅｉの値が決定されると、それらは、格納シナリオの場合はマスターインデックステーブルと呼ばれるインデックスデータ構造に、またはストリーミングシナリオの場合は各トランスポートブロックのヘッダに格納できる。マスターインデックステーブルに含まれるかまたは各トランスポートブロックヘッダによって運ばれるｓｉおよびｅｉの値を検査し、それらを選択的アクセスが要求されるゲノム領域を決定するｓおよびｅと比較することによって、ことによって、選択的アクセス要求を満たすためにアクセスされデコードされる必要がある最小セットのアクセスユニットＡＵｉを識別することができる。
【０１９３】
可変長シングルリードのデコード処理
以下のセクションでは、コード化シーケンスリードが可変長を有する場合に圧縮ゲノムデータのゲノム領域に選択的にアクセスすることに関与する工程を説明する。
１．分析者またはゲノムデータ処理アプリケーションは、参照シーケンス上の座標ｓ（開始）およびｓ＜ｅである座標ｅ（終了）によって定義されるゲノム領域にマッピングされたすべてのコード化シーケンスデータにアクセスする必要がある。
２．デコーダは、すべてのアクセスユニットＡＵｉにアクセスしてデコードする。ただし、Ｋ≦ｉ≦Ｋ＋Ｎ（ＡＵＫからＡＵＫ＋Ｎ）。
ａ．    ｓ∈ＡＫ（すなわち、開始座標sはＡＫがカバーされるゲノム領域に属する）
ｂ．    ｅ∈ＡＫ＋Ｎ（すなわち、末端座標ｅは、ＡＫ＋Ｎによってカバーされるゲノム領域に属する）
ｃ．
３．デコーダは、参照シーケンス上の位置Ｐ＞ｓにマッピングされた少なくとも１つの塩基を有するすべてのリードが検索されることを保証するために、ｉ＜Ｋで、何個のアクセスユニットＡｉをデコードしなければならないかを決定しなければならない。探索は、ｓ≦ｅｉ≦ｅであるすべてのＡＵをデコードすることを選択し、選択されたクラスのＡＵについてＭＩＴに存在するｅｉのすべての値が解析されたときに停止する。開始位置ｓｉ＞ｅを有するアクセスユニットは、アクセスのために選択されたゲノム領域内にマッピングされた少なくとも１つの塩基を有するいかなるリードも含まないので、スキップすることができる。
【０１９４】
ペアリードへの選択的アクセス
本発明において特定された新しいアルゴリズムは、シーケンスリードへの一貫したそして効率的な選択的アクセスを実施することを可能にしそして以下の工程からなる： 
１．リードペアが別々のアクセスユニット内の２つの別々のリードとしてエンコードされ、それより下でリードが同じアクセスユニット内の単一のゲノムレコードにエンコードされるペアリング距離に対する閾値を設定するパラメータＭａｘＤの定義。そのようなメカニズムは、それらのメイトから遠く離れてマッピングされるリードが、そのカバーされる領域がマッピング座標から遠くなるであろうアクセスユニットにおいてコード化されるのを防止する。
２．パラメータＭａｘＤは、ペアが単一のエンティティとしてコード化されるか、または２つの別々のリードとしてコード化されるかを決定するためにエンコーダによって設定および使用されるように、ファイルの「データセットヘッダ」に格納されるか、またはトランスポートブロックヘッダに送信される。これにより、ＭａｘＤは、選択されたゲノム領域にマッピングされた各ペアのすべてのリードを検索するのに必要な最小数のアクセスユニットをデコードすることによって選択的アクセスプロセスを実行するためにデコーダにおいて利用可能である。
【０１９５】
所与のアクセス単位ＡＵｉの集合ｉについて、開始位置ｓおよび終了位置ｅに関して指定された参照シーケンスのゲノム領域、ならびにアクセスされ、デコードされ、検査される必要があるアクセスユニットの最小セットである開始座標ｓｉおよび終了座標ｅｉによって定義される関連するカバー領域は、以下によって決定することができる。関連する開始座標ｓｉまたは終了座標ｅｉが以下の式を満たすすべてのアクセスユニットＡＵを識別すること。
ｓ−ＭａｘＤ≦ｓｉ≦ｅ
【０１９６】
ＡＵを決定し、対応するアクセスユニットを識別する例が図９に報告される。コード化プロセス中に各アクセスユニットについてｓｉおよびｅｉの値が決定されると、それらはマスタインデックステーブルと呼ばれる保管シナリオ用インデックスデータ構造に格納される。マスターインデックステーブルに含まれるｓｉ、およびｅｉの値を調べ、それらをｓ−ＭａｘＤおよびｅと比較し、そして選択的アクセスが要求されるゲノム領域を決定することによって、アクセスユニットＡＵｉの最小セットを同定することが可能である。要求されたゲノム領域にマッピングされた少なくとも１つの塩基を有する全てのリードが検索されることを保証しながら、選択的アクセス要求を満たすためにアクセスされデコードされる必要がある。
【０１９７】
固定長のリードを成すリードのためのデコード化プロセス。
以下のテキストは、コード化ゲノムシーケンスが一定長さでマップされたデータを読み取る参照シーケンスのゲノム領域への選択的アクセス手順に含まれる工程を記載する。
１．分析者またはゲノムデータ処理アプリケーションは、座標ｓ（開始）およびｓ＜ｅである座標ｅ（終了）によって定義されるゲノム領域にマッピングされたすべてのコード化シーケンスデータにアクセスする必要がある。
２．指定された間隔内にマッピングされた少なくとも１つのベースを有するコード化されたリードを含むＡＵを見つけるために、本開示に記載された選択的アクセス方法を実施するデコード装置はＭＩＴを構文解析し、
ａ．    最大のｓＫ≦ｓおよびｅＫ＞ｓを有するＡＵＫをデコードする。
ｂ．    ｉ＞Ｋでｓｉ≦ｅである全てのアクセスユニットＡＵｉをデコードする。
ｃ．    開始位置sｉ＜sと終了位置eｉ＞sを持つ追加のアクセスユニットＡＵｉを検索する
ここで、ｓｉとｅｉはＡＵｉの開始位置と終了位置である。
【０１９８】
ポイント２．ｃで説明された探索は、次の場合に停止するものとする。ここで、ＭａｘＤは、リードペアを２つの別個のゲノムレコードに分割してコード化する必要があるときを決定するための上記ペアリング距離に対する閾値である。
【０１９９】
ＭａｘＤのスカラーおよびベクトルパラメーター
上述のパラメータＭａｘＤは、エンコードされたゲノムデータセット全体に対して有効な定数であり得るか、または異なるゲノム領域に対して異なる値が定義され得る。適切なアプローチは、各参照シーケンス（例えば染色体）ごとに異なるパラメーター値を定義することである。そのようなアプローチが技術的利点を提示し得る理由は、シーケンシング実験が、生成されたシーケンスリードの密度がゲノム領域（例えば染色体）ごとに異なることを必要とし得ることである。圧縮効率を高め、同時に選択的アクセス動作の効率を最大にするために、生成されたシーケンシングリードの密度に従って選択的アクセスの特徴を適合させることが適切である。したがって、異なる参照シーケンスごとにＭａｘＤの値に異なる値を使用すると便利である。そのような選択的アクセスアルゴリズムを実行するために、各コード化ゲノムデータセットは、異なる参照シーケンスに関連するベクトルの各要素と共にＭａｘＤ値のベクトルを搬送することを必要とする。これは図１９に示されており、ここでは、閾値のベクトル（１６０１）が、本開示に記載された方法を実施するコード化装置によってコード化されたグローバルパラメータセットコンテナ（１６０４）内で移送される。
【０２００】
そのような手法は、異なる（のクラスタの）処理ユニットが異なる参照シーケンスにマッピングされたシーケンスデータを処理する場合にコード化データの最適な並列処理をサポートすることができるというさらなる利点を有する。
【０２０１】
データセットヘッダーとマスターインデックステーブル
上述したインデックスメカニズムおよび選択的アクセス手順をサポートするために、ここでは２つのデータ構造が本発明の不可欠な部分として説明されている。
・グローバルパラメータを運ぶデータセットヘッダ（１６０２）。データセットヘッダの構文は、テーブル６に示す。
・マスターインデックステーブル（ＭＩＴ）と呼ばれるインデックス作成ツールが本発明に開示されている。ＭＩＴ構文は、マッピングされたリード（すなわち、クラスＰ、Ｎ、Ｍ、ＩまたはＨＭに属すると分類されたリード）に関してテーブル４に提供され、各アクセスユニット開始位置および終了位置を表す２つの座標ＣｓｊｋおよびＣｅｊｋによって構成される。
・Ｃはリードクラスを表す（すなわちＣ∈｛Ｐ、Ｎ、Ｍ、Ｉ、ＨＭ｝）
・jは参照シーケンス識別子を表す
・kは各参照シーケンス内のＡＵ識別子を表す
図１８は、アクセスユニットの開始位置（Ｃｓｋ）および終了位置（Ｃｅｊｋ）を含む、上で定義されたマスターインデックステーブルの一例を示す。
【０２０２】
上で定義された座標を含むマスターインデックステーブル（１６０３）は、図１４に示されるように、圧縮されたゲノムコンテンツのデータセットヘッダ（１６０２）と共にデータ構造にコード化される。そのようなデータ構造の例はテーブル４に提供される。
【０２０３】
【表１０】
2020500382.tif 000016
2020500382.tif 000017
2020500382.tif 000018
2020500382.tif 000019
【０２０４】
データセットヘッダーの構文
データセットヘッダは、コード化されたゲノム情報を操作するためにエンコーダおよびデコーダによって使用されるグローバルパラメータを搬送するデータ構造である。データセットヘッダの各要素の構成要素と意味を以下のテーブル４に示す。
【０２０５】
【表１１】
2020500382.tif 000020
2020500382.tif 000021
2020500382.tif 000022
2020500382.tif 000023
テーブル６  データセットヘッダ
【０２０６】
マスタインデックステーブルの構文
マスターインデックステーブル（ＭＩＴ）と呼ばれるインデックス作成ツールが本発明に開示されている。
テーブル５は、本開示で定義されたマスタインデックステーブルの構文を提供し、ここで、Ｃｌａｓｓ＿ＩＤは、本開示で定義されたマッピングされたリードのクラス、Ｐ、Ｎ、Ｍ、ＩおよびＨＭクラスに対する一意の識別子である。たとえばＣｌａｓｓ＿ＩＤは次のように定義できる。
【０２０７】
【表１２】
2020500382.tif 000024
【０２０８】
マスターインデックステーブル（ＭＩＴ）は、次の要素を含む多次元配列に基づくデータ構造
・参照シーケンスに関して、異なる記述子ストリームからのブロックのセットとしての、アクセスユニットに含まれるすべてのリードまたはリードペアの一次アライメントの中で最も左に一致する塩基のヌクレオチド数としての位置。これは、テーブル７においてStart_AU_Ref_Position [Sequence_ID] [Class_ID] [AU_ID]によって表される。
【０２０９】
・参照シーケンスに関して、異なる記述子ストリームからのブロックのセットとしての、アクセスユニットに含まれるすべてのリードまたはリードペアの一次アラインメントの中で最も右に一致する塩基のヌクレオチド数としての位置。これは、テーブル７において、End_AU_Ref_Position [Sequence_ID] [Class_ID] [AU_ID]によって表される。
【０２１０】
・各アクセスユニットが連続したデータブロックとして記憶媒体に格納されている場合に、各アクセスユニットが連続したデータブロックとして記憶媒体に格納されている場合の各アクセスユニットのサイズのバイト
【０２１１】
・各参照シーケンスに関してコード化された各クラスの各ＡＵを構成する記述子の各コード化ブロックの最初のバイトのバイトオフセット。オフセットは、データセットペイロードの最初のバイト（０ベース）を基準にして計算される。ブロックが空であり、（1）Block_Header_Flagが設定されている場合、それは0xFFFFFFFFに等しい。ブロックが空で、（2）Block_Header_Flagが設定されていない場合、それは記述子ストリーム内の次のブロックのBlock_Byte_Offset値、 または 記述子ストリーム内の最後のブロックの場合は記述子ストリームペイロードサイズに等しい。これは、テーブル７のBlock_Byte_Offset [Sequence_ID] [Class_ID] [AU_ID] [Descriptor_ID] によって表される。 
【０２１２】
２つのコーディング方法の間の代替は、テーブル７の Block_Header_Flagと呼ばれるフラグによってコールされる。
【０２１３】
【表１３】
2020500382.tif 000025
2020500382.tif 000026
2020500382.tif 000027
2020500382.tif 000028
2020500382.tif 000029
テーブル７  マスターインデックステーブル
【０２１４】
トランスポートブロックヘッダの構文
ストリーミングシナリオでは、ファイルシステムまたはストレージシナリオで利用可能なマスターインデックステーブルによって運ばれる情報は、トランスポートブロックヘッダによって運ばれ、以下の構文に従って任意のアクセスユニットに属する各データブロックに関連付けられる。
【０２１５】
【表１４】
2020500382.tif 000030
2020500382.tif 000031
テーブル８  トランスポートブロックヘッダーの構文
【０２１６】
ブロックヘッダーの構文
【０２１７】
【表１５】
2020500382.tif 000032
テーブル９  ブロックヘッダーの構文
【０２１８】
トランスポートフォーマットからファイルフォーマットへの変換プロセス 
このセクションでは、トランスポートブロックヘッダにある構文要素から、上で定義したデータセットヘッダのパラメータSeq_CountとSeq_Blocks [seq]の更新、および前のセクションで定義したマスタインデックステーブルの編集を可能にするプロセスについて説明する。
【０２１９】
そのようなプロセスは、結果のファイルが元のトランスポートフォーマットによって運ばれる同等の情報をデータセットヘッダーとマスターインデックステーブルに保持することを保証するために定義される。そのような変換プロセスは、結果として得られるファイルがトランスポートセッションによって運ばれるすべての情報を保持し、そのような情報が適切なファイルアクセスのためにフォーマットされるために、トランスポートセッションを介して受信したデータをローカル記憶装置に格納する必要があるときに使用される。
【０２２０】
プロセスは次のように定義される。
１．  Seq_Countは０に初期化され、ＳＥＱＩＤが以前に受信されたいずれのＳＥＱＩＤとも異なるたびに１ずつ増加する。
２．  Seq_Blocks[SEQID]は、（ＳＥＱＩＤ、ＡＵＩＤ）ベクトルが以前の（ＳＥＱＩＤ、ＡＵＩＤ）ベクトルと異なる度に１ずつ増加する。
【０２２１】
３．  ６．４．３．１セクションで定義されているマスターインデックステーブルの座標は、次のように計算される。
ａ.    Sequence_ID = Seq_Count
ｂ.    ６．３．８セクションで定義されているブロックヘッダ内のClass_ID = Class_ID 
ｃ.    AU_ID = Seq_Blocks[SEQID]
ｄ.    Block_Header_Flagが設定されていない場合、６．３．８．１セクションで定義されているブロックヘッダのDescriptor_ID = Descriptor_ID, そうでない場合（BlockJHeader_Flagが設定される）  Descriptor_ID = 0.
４.  Start_AU_Ref_Position [Sequence_ID] [Class_ID] [AU_ID]という名前のマスターインデックステーブルエントリは、次のように計算される。
ａ.    Start_AU_Ref_Position[Sequence_ID][Class_ID][AU_ID] = Start_POS
５．  End_AU_Ref_Position [Sequence_ID] [Class_ID] [AU_ID]という名前のマスターインデックステーブルエントリは、次のように計算される。
ａ.    End_AU_Ref_Position[Sequence_ID][Class_ID][AU_ID] = End_POS
６．  データセットヘッダーフィールドBlock_Header_Flagはユーザー定義です。
７．Block_Header_Flagが設定されていない場合：
ａ.    新しい（Class_ID、Descriptor_ID）ベクトルによって識別されるトランスポートブロックが受信されるたびに、DSCN [Class_ID] [Descriptor_ID]という名前の新しい記述子ストリームコンテナ（ｄｓｃｎ）が作成され、Block_Ptr [Class_ID] [Descriptor_ID]という変数が定義され０に初期化される。
ｂ.    Block_Ptr [Class_ID] [Descriptor_ID]は、sizeof(gen_info) + Length of any gen_info child of DSCN[Class_ID][Descriptor_ID]だけ増加する。
ｃ.    ブロックヘッダのClass_IDとDescriptor_IDで識別されるすべてのブロックのペイロードは、DSCN [Class_ID] [Descriptor_ID]のValue []フィールドにコピーされる。
ｄ.    上記の各ブロックについて、Block_Ptr [Class_ID] [Descriptor_ID] [AU_ID]という名前の新しい変数が定義され、Block_Ptr [Class_ID] [Descriptor_ID]の現在の値が割り当てられる。
ｅ.    各ブロックについて、Block_Ptr [Class_ID] [Descriptor_ID]は、Block_size - Transport_Block_Header_Sizeによって増分され、Transport_Block_Header_Sizeは、転送ブロックヘッダーのサイズ（バイト単位）。
ｆ.    セッションが終了し、結果のデータを出力ファイルに書き込む前に、DS_Offsetという名前の変数が定義され、０に初期化される。
ｇ.    各DSCN [Class_ID] [Descriptor_ID]を出力ファイルに書き込んだ後、DS_Offsetはsizeof(gen_info header) + Length(DSCN[Class_ID][Descriptor_ID])だけ増加する。
ｈ.    出力ファイルに書き込まれるDSCN [Class_ID] [Descriptor_ID]ごとに、Block_Byte_Offset [Sequence_ID] [Class_ID] [AU_ID] [Descriptor_ID]という名前のマスターインデックステーブルエントリが次のように更新される。
Block_Byte_Offset [Sequence_ID] [Class_ID] [AU_ID] [Descriptor_ID] = DS_Offset + Block_Ptr [Class_ID] [Descriptor_ID] [AU_ID]
８．そうでない場合、BlockJHeader_Flagが設定されている場合：
ａ.    DatasetPayloadという名前のバッファが作成される。
ｂ.    各ブロックについて、ブロックヘッダはトランスポートブロックヘッダから抽出され格納される。
ｃ.    以前に抽出されたブロックヘッダーとブロックペイロードを含む各ブロックは、DatasetPayloadに書き込まれる。
ｄ.    各ブロックについて、Block_Byte_Offset [Sequence_ID] [Class_ID] [AU_ID] [Descriptor_J]は、DatasetPayload内のブロックのバイトオフセットに等しい。
ｅ.    AU_Size[Sequence_ID][Class_ID][AU_ID]と名付けられたマスターインデックステーブルエントリは、同じSequence_ID, Class_ID and AU_IDを有する各受信トランスポートブロックについての(Block_size - Transport_Block_Header_Size)の累積合計として計算される。
ｆ．   セッションの終わりに、データペイロードは、５．４セクションで定義されているように、データペイロードとして出力ファイルにダンプされる。
プロセスの終了時、通常はエンドユーザーがトランスポートプロセスの実行を停止したときは、マスターインデックステーブルの３番目のループ、つまり（AU_ID = 0; AU_ID <Seq_Blocks [Sequence_ID]; AU_ID ++）を再実行する必要がありる。 Sequence_IDインデックスとClass_IDインデックスの組み合わせごとに、Start_AU_Ref_Position [Sequence_ID] [Class_ID] [AU_ID]の値を大きくすることによって順序付けられる。
【図１】
2020500382.tif 000033
【図２】
2020500382.tif 000034
【図３】
2020500382.tif 000035
【図４】
2020500382.tif 000036
【図５】
2020500382.tif 000037
【図６】
2020500382.tif 000038
【図７】
2020500382.tif 000039
【図８】
2020500382.tif 000040
【図９】
2020500382.tif 000041
【図１０】
2020500382.tif 000042
【図１１】
2020500382.tif 000043
【図１２】
2020500382.tif 000044
【図１３】
2020500382.tif 000045
【図１４】
2020500382.tif 000046
【図１５】
2020500382.tif 000047
【図１６】
2020500382.tif 000048
【図１７】
2020500382.tif 000049
【図１８】
2020500382.tif 000050
【図１９】
2020500382.tif 000051
【図２０】
2020500382.tif 000052
【国際調査報告】
2020500382.tif 000053
2020500382.tif 000054