(57)【要約】１つまたは複数のリファレンスシーケンス上に整列されたときに、ゲノムシーケンシング装置によって生成されたゲノムシーケンスデータの表現及び処理のための方法および装置。シーケンスリードは、既存のまたは構築されたリファレンスシーケンスに対してそれらを整列させることによってコード化される。アライメント後、符号化プロセスは、リードをデータクラスに分類し、続いて複数の記述子層に関して各データクラスを符号化することからなる。各データクラスを表すのに使用される記述子のサブセットの符号化には、特定のソースモデル及びエントロピーコーダが使用される。【選択図】図１
2020500383.tif 000002
【特許請求の範囲】
【請求項１】
ゲノムシーケンスデータをコード化するための方法であって、前記ゲノムシーケンスデータはヌクレオチドのシーケンスのリードを含み、前記方法は、
・前記リードを１つ以上のリファレンスシーケンスと整列させて、整列されたリードを作成するステップ、
・前記整列されたリードを前記１つ以上のリファレンスシーケンスとの特定のマッチングルールに従って分類して、整列されたリードのクラスを作成するステップ、
・前記分類され整列されたリードを構文要素の多数のストリームとしてコード化するステップを備え、
・前記分類され整列されたリードを多数の構文要素のストリームとしてコード化することは、前記クラスの整列されたリードに従って前記構文要素を選択することを含み、
・前記構文要素のストリームにヘッダ情報を提供して、前記ゲノムデータブロックを別々にアクセス可能なデータユニットにエントロピーコード化するために連続したデータブロックを作成するゲノムシーケンスデータをコード化するための方法。
【請求項２】
・前記指定されたマッチングルールを満たさない前記リードを、マッピングされていないリードのクラスに分類し、
・前記分類されたマッピングされていないリードを多数の構文要素のストリームとしてコード化し、
・前記構文要素のストリーム及び前記コード化されたリファレンスシーケンスにヘッダ情報を提供して、連続するアクセスユニットを作成すること、
をさらに含む、請求項１に記載のコード化方法。
【請求項３】
前記分類が、アラインメントに使用されるリファレンスシーケンス上に複数のアラインメント位置を有するゲノムリードを同定することを含む、請求項２に記載の方法。
【請求項４】
前記分類することが、アラインメントのためのマッチングルールを満たすためにスプライスと名付けられた複数のセグメントに分割される必要があるゲノムリードを識別することを含む、請求項３に記載の方法。
【請求項５】
コード化されるゲノムシーケンスのリードがペアになっている、請求項４に記載のコード化方法。
【請求項６】
・リードのアライメントの数を識別し、この数を特定の構文要素で表すステップ、
・アライメントごとに対応するマッピング位置を識別し、各マッピング位置を特定の構文要素で表すステップ、
・一次及び二次アラインメントを同定するために各アラインメントにアラインメントスコアを割り当てるステップ、
・一次アライメントとして最高スコアのアライメントを識別するステップ、
・プライマリとは異なるリファレンスでアライメントが見つかるかどうかを識別し、特定の記述子を使用してこの情報を表すステップ、及び
一次アラインメントのリファレンスシーケンス上でアラインメントが別の連続を保存していないかどうかを識別し、この情報を特定の構文要素を使用して表すステップ、
以下のステップをさらに含む、請求項５に記載のコード化方法。
【請求項７】
前記１つ以上のリファレンスシーケンスとのマッチングを定義する所定のマッチングルールに従ってリファレンスシーケンス上に整列させるために２つ以上のスプライスに分割する必要があるリードを識別するステップ、
グローバル構成パラメータを使用して、スプライスされたリードの存在を通知するステップ、
特定の構文要素を使用してスプライスの数を表すステップ、及び
特定の構文要素を使用して各スプライスの長さを表すステップ、
をさらに含む、請求項６に記載のコード化方法。
【請求項８】
・ペア内の各リードのアライメントの数を識別し、この数を特定の構文要素で表すステップ、
・ペアにおいて最も左のリードのアラインメントごとに、対応するマッピング位置を識別し、各マッピング位置を特定の構文要素で表すステップ、
・最も左のリードのそれぞれのアライメントごとに、前記ペアにおける最も右のリードの関連するアライメントを識別し、特定の構文要素との関連を表すステップ、
・一次アライメント及び二次アライメントを識別するために、アライメントの各ペアにアライメントスコアを割り当てるステップ、
・最も高いスコアを有する一組のアラインメントを一次アラインメントとして同定するステップ、
・プライマリとは異なるリファレンスにアライメントが見つかるかを識別し、特定の記述子を使用してこの情報を表すステップ、及び
・アラインメントが一次アラインメントとは異なる連続をリファレンスシーケンス上に示すかを識別し、特定の構文要素を使用してこの情報を表すステップ、
をさらに含む、請求項７に記載のコード化方法。
【請求項９】
・予め定義されたマッチングルールに従ってリファレンスシーケンスに整列させるために、２つ以上のスプライスに分割する必要があるリードを同定するステップ、
・グローバル構成パラメータを使用して、スプライスされたリードの存在を通知するステップ、
・特定の構文要素を使用して、ペアで最も左のリードのスプライスの数を表すステップ、
・左端のリードの各アライメントに関連付けられた右端のリードのスプライス数を特定の構文要素のベクトルで表すステップ、及び
・特定の構文要素を使用して各スプライスの長さを表すステップ、
をさらに含む、請求項８に記載のコード化方法。
【請求項１０】
前記構文要素のストリームが、ゲノムデータセットヘッダを含み、
・各データセットグループを一意的に識別するために使用されるデータセットグループ識別子、
・各データセットを一意的に識別するために使用されるゲノムデータセット識別子、
・データセットが準拠しているデータ形式の仕様を識別するために使用されるブランド識別子、
？データセットが準拠しているデータフォーマット仕様を識別するために使用されるマイナーバージョン番号、
・固定長のリードを通知するために使用されるヌクレオチド中のコード化されたゲノムリードの長さ、
？ペアエンドリードの存在を通知するフラグ、
・ブロックヘッダの存在を通知するフラグ、
・前記アクセスユニットを復号化するときにデータアクセスを容易にするためにアクセスユニットが記憶媒体に記憶されるモードを通知するフラグ、
・リファレンスシーケンスに関してシーケンスリードのミスマッチをコード化するために使用されるアルファベットのタイプ、
・データセットのコードするために使用されたリファレンスシーケンスの数、
・各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの数値識別子、
・各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの文字列識別子、
各リファレンスシーケンスに関連するアクセスユニットを数えるために使用される、リファレンスシーケンスあたりのコード化されたアクセスユニットの数、
・整列されたリード、整列されていないリード、マッピングされていないリード及びリファレンスシーケンスを区別するために使用されるコード化されたゲノムデータのタイプ、
・データセットにコーディングされているデータクラスの数、
復号化処理中に使用されるデータセット内でコードされたデータクラスごとに使用される記述子の数、
・コード化されたマッピングされていないリードのインデックス付けに使用されたクラスタの総数、
・コード化されたクラスタシグネチャを復号化するのに使用されるクラスタシグネチャをコード化するのに使用される整数値を表すのに使用されるビット数、
・全てのクラスタシグネチャがヌクレオチドの数に関して同じ長さを有するかを通知するフラグ、
・クラスタシグネチャの長さ
を含む、請求項９に記載の方法。
【請求項１１】
前記構文要素のストリームは、整列されたリードの各クラス及びサブクラスごとに１つのセクションを含むマスタインデックステーブル含み、
前記セクションが、
・各クラス又はサブクラスのデータの各アクセスユニットの最も左のリードの一次アライメントの前記１つ以上のリファレンスシーケンス上のマッピング位置、
・各クラス又は各データのサブクラスの各アクセスユニットのすべての一次アラインメントの中の最も右にマッピングされた塩基の前記１つ以上のリファレンスシーケンス上の位置、
・各アクセスユニットを構成するコード化された構文要素の各ブロックのバイト単位のオフセット、
を含む、請求項１０に記載の方法。
【請求項１２】
前記マスタインデックステーブルは、各コード化された記述子ストリームのサイズと各アクセスユニットのサイズとをさらに含む、請求項１１に記載の方法。
【請求項１３】
ゲノムリードが複数のアライメントを有し、前記マスタインデックステーブルが、
・各クラス又は各データのサブクラスの各アクセスユニットのすべてのリードの中で最も左にアライメントされている前記１つ以上のリファレンスシーケンス上のマッピング位置、
・各クラス又は各データのサブクラスの各アクセスユニットのすべてのアラインメントの中で最も右にマッピングされた塩基の前記１つ以上のリファレンスシーケンス上の位置、及び
・各アクセスユニットを構成するコード化された構文要素の各ブロックのバイト単位のオフセット、
を含む、請求項１２に記載の方法。
【請求項１４】
前記アクセスユニットがコード化されたリードペアを含む、請求項１３に記載の方法。
【請求項１５】
前記マスタインデックステーブルは、前記アクセスユニットデータと一緒にコード化される、請求項１４に記載の方法。
【請求項１６】
前記ゲノムデータセットヘッダが前記アクセスユニットデータと一緒にコード化される、請求項１５に記載の方法。
【請求項１７】
前記構文要素のストリームは、使用されるリファレンスのタイプ（既存又は構築されたもの）及びリファレンスシーケンスと一致しないリードのセグメントに関する情報をさらに含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
前記分類され整列されたリードを多数の構文要素のストリームとしてコード化することは、特定のソースモデル及び特定のエントロピーコーダを各記述子ストリームに関連付けるステップを含む、請求項１７に記載の方法。
【請求項１９】
前記エントロピーコーダは、コンテキスト適応算術コーダ、可変長コーダ、又はゴロムコードのうちの１つである、請求項１８に記載の方法。
【請求項２０】
・ヘッダ情報を使用することによって構文要素の複数のストリームを抽出するために、前記コードされた化ゲノムデータを含むアクセスユニットを解析するステップ、及び
・１つ以上のリファレンスシーケンスに関してそれらの分類を定義する特定のマッチングルールに従って整列されたリードを抽出するために構文要素の前記多数のストリームを復号化するステップ、
を含む、コードされた化ゲノムデータを復号化するための方法。
【請求項２１】
請求項２に記載のようにコードされたマッピングされていないゲノムリードの復号化をさらに含む、請求項２０に記載の復号化方法。
【請求項２２】
グローバル構成パラメータを含むゲノムデータセットヘッダを復号化することをさらに含む、請求項２１に記載の復号化方法。
【請求項２３】
各クラスのリードについて１つのセクションと、関連する関連マッピング位置と、コードしたブロックオフセットとを含むマスタインデックステーブルを復号化することをさらに含む、請求項２２に記載の復号化方法。
【請求項２４】
使用される、既存の、変更さた又は構成されたリファレンスのタイプに関する情報を復号化することをさらに含む、請求項２３に記載の復号化方法。
【請求項２５】
前記ゲノムリードが対になっている、請求項２４に記載の復号化方法。
【請求項２６】
前記ゲノムデータがエントロピー復号化されている、請求項２５に記載の復号化方法。
【請求項２７】
・各リードのアライメント数を復号化するステップ、
・各アライメントの位置を復号化するステップ、
・各アラインメントに関連するスコアを復号化することによって一次アラインメントを識別するステップ、及び
・二次アラインメントが、対応する構文要素を復号化することによって一次アラインメントとはリファレンスシーケンスに関して異なる隣接性を有するかどうかを識別するステップ、
を含む複数のアライメント情報の復号化をさらに含む、請求項２６に記載の復号化方法。
【請求項２８】
・コード化されたリードが２つ以上のスプライスに分割されているかどうかを識別するステップ、
・各スプライスの長さを復号化するステップ、及び
・各スプライスのマッピング位置を復号化するステップ、
をさらに含む、請求項２７に記載の復号化方法。
【請求項２９】
前記コード化されたゲノムリードがペアエンドリードであり、
・左端のリードの各アライメントに関連付けられた右端のリードのアライメントの数を復号化するステップ、
・最も左側のリードの各アライメントを最も右側のリードの１つ以上のアライメントと関連付けるペアリング情報を復号化するステップ、
を含む、請求項２８に記載の復号化方法。
【請求項３０】
前記コード化されたゲノムリードが、２つ以上のスプライスに分割され、
・各コード化されたスプライスの長さを復号化するステップ、
・各スプライスのマッピング位置を復号化するステップ、
をさらに含む、請求項２９に記載の復号化方法。
【請求項３１】
ゲノムシーケンスデータ２８９の圧縮のためのゲノムエンコーダ（２８１０）であって、前記ゲノムシーケンスデータ２８９は、ヌクレオチドのシーケンスのリードを含み、前記ゲノムエンコーダ（２８１０）は、
・前記リードを１つ以上のリファレンスシーケンスに整列させ、それによって整列されたリードを作成するように構成される、アライナユニット（２８１）、
・構築されたリファレンスシーケンスを生成するように構成された、構築リファレンス生成ユニット（２８２）、
・１つ以上の既存のリファレンスシーケンス又は構築されたリファレンスシーケンスとの指定されたマッチングルールに従って前記整列されたリードを分類し、それによって整列されたリードのクラス（２８８）を作成する、データ分類ユニット（２８４）
・整列されたリードの前記クラスに従って前記構文要素を選択することによって、前記分類された整列されたリードを構文要素のストリームとしてコード化するように構成された、１つ以上の記述子コード化ユニット（２８５〜２８７）、
・それらの統計的特性に従って構文要素の前記ストリームを圧縮してゲノムストリーム（２８１５）を生成するように構成された１つ以上のエントロピーコード化ユニット（２８１２〜２８１４）、及び
圧縮されたゲノムデータ及びメタデータを多重化するためのマルチプレクサ（２８１６）、
を備えるゲノムエンコーダ。
【請求項３２】
請求項１に記載のコード化方法を実行するのに適したコード化手段をさらに備える、請求項３１に記載のゲノムエンコーダ。
【請求項３３】
圧縮されたゲノムストリーム（２９１）を解凍するためのゲノムデコーダ（２９８）であって、前記ゲノムデコーダ（２９８）は、
・圧縮されたゲノムデータ及びメタデータを逆多重化するためのデマルチプレクサ（２９０）、
・前記圧縮されたゲノムストリームを構文要素（２９５）のゲノム層に解析するように構成された解析手段（２９２〜２９４）、
・ゲノム層をヌクレオチドのシーケンスの分類されたリード（２９１１）に復号化するように構成された、１つ以上の層のデコーダ（２９６〜２９７）、
・１つ以上のリファレンスシーケンス上のヌクレオチドのシーケンスの前記分類されたリードを選択的に復号化して、ヌクレオチドのシーケンスの圧縮されていないリードを生成するように構成された、ゲノムデータクラスデコーダ（２９９）、
を備えるゲノムデコーダ。
【請求項３４】
前記１つ以上のリファレンスシーケンスは、圧縮されたゲノムストリーム（２９１）に格納されている、請求項３３に記載のゲノムデコーダ。
【請求項３５】
前記１つ以上のリファレンスシーケンスは、帯域外メカニズムを介して前記デコーダに提供される、請求項３４に記載のゲノムデコーダ。
【請求項３６】
前記１つ以上のリファレンスシーケンスがデコーダで構築される、請求項３５に記載のゲノムデコーダ。
【請求項３７】
実行されると少なくとも１つのプロセッサに請求項１に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項３８】
実行されると少なくとも１つのプロセッサに請求項２に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項３９】
実行されると少なくとも１つのプロセッサに請求項３に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４０】
実行されると少なくとも１つのプロセッサに請求項６に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４１】
実行されると少なくとも１つのプロセッサに請求項７に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４２】
実行されると少なくとも１つのプロセッサに請求項８に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４３】
実行されると少なくとも１つのプロセッサに請求項９に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４４】
実行されると少なくとも１つのプロセッサに請求項２７の復号化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４５】
実行されると少なくとも１つのプロセッサに請求項２８に記載の復号化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４６】
実行されると少なくとも１つのプロセッサに請求項２９に記載の復号化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４７】
実行されると少なくとも１つのプロセッサに請求項３０に記載の復号化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項４８】
請求項１に記載の方法に従ってコード化されたゲノムを保存するサポートデータ。
【請求項４９】
請求項２に記載の方法に従ってコード化されたゲノムを保存するサポートデータ。
【請求項５０】
請求項３に記載の方法に従ってコード化されたゲノムを保存するサポートデータ。
【請求項５１】
請求項６に記載の方法に従ってコード化されたゲノムを保存するサポートデータ。
【請求項５２】
請求項７に記載の方法に従ってコードされたゲノムをコードするサポートデータ。
【請求項５３】
請求項８に記載の方法に従ってコード化されたゲノムを保存するサポートデータ。
【請求項５４】
請求項９に記載の方法に従ってコード化されたゲノムを保存するサポートデータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、複数のアライメント座標又はリードのより小さなセグメントへの断片化（「スプライスドリード」としても知られる）を必要とするアライメントを有する１つ以上のリファレンスシーケンスに関してアライメントされたゲノムシーケンスデータの新規表現方法を提供する。開示された表現は、公知の従来技術の表現方法では利用できない新しい機能を提供することによって利用される記憶スペースを減らし、アクセス性能を改善する。
【背景技術】
【０００２】
ゲノムシーケンスデータの適切な表現は、ゲノム変異型の呼び出しやゲノムシーケンスデータ及びメタデータを処理することによって様々な目的で行われる他のすべての分析のような効率的なゲノム分析用途を可能にするために不可欠である。
【０００３】
ヒトゲノムシーケンシングは、ハイスループット低コストシーケンシング技術の出現によって手頃な価格になった。このような機会は、癌の診断及び治療から遺伝子疾患の同定まで、抗体の同定のための病原体サーベイランスから新しいワクチン、薬物の創製及び個別化された治療のカスタマイズに至るまでのいくつかの分野に新しい展望を開く。
【０００４】
病院、ゲノム解析プロバイダー、バイオインフォマティクス及び大規模な生物学データストレージセンターは、ゲノム医療を世界規模に拡大することを可能にする、手頃な価格、迅速、信頼性及び相互接続されたゲノム情報処理ソリューションを探している。シーケンシング処理におけるボトルネックの１つがデータ記憶となったため、ゲノムシーケンシングデータを圧縮形式で表すための方法がますます研究されている。
【０００５】
シーケンシングデータの最も使用されているゲノム情報表現は、ＦＡＳＴＱ及びＳＡＭフォーマットの圧縮に基づいている。目的は、伝統的に使用されているファイルフォーマット（それぞれ、整列されていないデータと整列されたデータ用のＦＡＳＴＱとＳＡＭ）を圧縮することである。このようなファイルは標準文字で構成されており、前述のようにＬＺ（ＬｅｍｐｅｌとＺｉｖ、最初のバージョンを公開した作者）スキーム（有名なｚｉｐ、ｇｚｉｐなど）などの汎用アプローチを使用して圧縮されている。ｇｚｉｐなどの汎用コンプレッサが使用されると、圧縮の結果は通常バイナリデータの単一のｂｌｏｂである。このようなモノリシック形式の情報は、特にハイスループットシーケンシングの場合のようにデータ量が非常に大きい場合には、アーカイブ、転送、及び詳述が非常に困難である。ＢＡＭフォーマットは、ＳＡＭファイルによって伝達される実際のゲノム情報を抽出するのではなく、非効率的で冗長なＳＡＭフォーマットの圧縮に重点が置かれており、また、各データソースの特定の性質（ゲノムデータ自体）を利用するよりも、ｇｚｉｐのような汎用テキスト圧縮アルゴリズムを採用するため、圧縮性能の低さが特徴である。
【０００６】
ＳＡＭの別の重要な制約は、ゲノムシーケンスのリード又はリードペアに関連した複数のアライメント（マルチプルマッピングとしても知られる）の表現の適切なサポートの欠如である。ゲノムシーケンスリードアラインメントは、次世代シークエンシング技術によって生成されたシーケンスリードから配列決定されたサンプルのゲノム情報を再構成することからなる処理である。再構成は、由来するゲノムについての事前の知識なしに、又はリファレンスとして既存のゲノムを使用してのいずれかで行うことができる。後者の手法は、当分野において「リファレンスに基づくアラインメント」として知られている。リファレンスに基づくアラインメントでは、配列決定されたサンプルから生成されたゲノムシーケンスリードを既存のリファレンスシーケンスと比較して（もしあれば）、シーケンスリードに関して最小数の差異を示すリファレンスシーケンスの領域を検索する。この処理は、リファレンスシーケンスに対するシーケンスリードの「整列（アライメント）」又は「マッピング」と呼ばれる。
【０００７】
いくつかのゲノム領域の反復性のために、シーケンスリードは同じ精度でいくつかの位置に整列させることができる。例えば、同じシーケンスのリードは、リファレンスシーケンス上の同じ長さの２つ以上のセグメントと完全に（すなわち、ミスマッチなしに）一致し得る。この場合、２つ以上のアラインメントは同等であると考えられ、そしてシーケンスのリードは「マルチプルアラインメント」を有すると言われる。この場合を図１５に示す。他の状況では、異なるアラインメントは異なる精度を有することができ、例えば１つのアラインメントはミスマッチを全く有さず（完全一致）、もう一方は１つ以上のミスマッチを有し得る。この場合、スコアリングシステムを使用してマルチプルアラインメントをランク付けする。
【０００８】
場合によっては、最大数のミスマッチなどの事前に確立されたマッチング基準を満たすアラインメント位置を見つけるために、シーケンスリードを２つ以上のサブセグメントに分割する必要がある。この場合、リードは「スプライスドリード」と呼ばれ、各サブセグメントは「スプライス」と呼ばれる。この場合を図１６に示す。
【０００９】
ＳＡＭの現在の仕様は、１１個の必須フィールドを使用したマルチプルアラインメント及びスプライスの表現をサポートしていないが、シーケンスリードアラインメントに使用されるツールの異なる実装によって異なる、したがって非効率的な方法で使用されるオプションフィールドの使用を必要とする。この書面に記載されている発明は、マルチプルアライメント及びスプライスドリードを表すこと、ならびに圧縮効率及びアクセス効率を維持することの両方の問題に対する解決策を提供する。
【００１０】
あまり使用されていないが、圧縮に関してＢＡＭよりも効率的なゲノムデータ圧縮へのより洗練されたアプローチが、ＣＲＡＭである。ＣＲＡＭは、リファレンスに関して差分コード化を採用するためのより効率的な圧縮を提供する（部分的にデータソースの冗長性を用いる）が、それでも増分の更新、ストリーミングのサポート、特定クラスの圧縮データへの選択的アクセス、及びマルチプルアライメントとスプライスリードの適切な表現などの機能に欠ける。
【００１１】
これらの手法では、低い圧縮率や、一度圧縮するとナビゲートや操作が困難になるデータ構造を生じる。単純な操作を実行するため、又はゲノムデータセットの選択された領域にアクセスするためであっても、大きくて厳格なデータ構造を取り扱う必要があるため、下流の分析は非常に遅くなり得る。ＣＲＡＭは、ＣＲＡＭレコードの概念に依存する。各ＣＲＡＭレコードは、それを再構成するのに必要なすべての要素をコード化することによって単一のマッピングされた又はマッピングされていないリードを表す。
【００１２】
ＣＲＡＭは、この書面に記載された発明によって解決され、除去される以下の欠点及び制限を示す。
１．ＣＲＡＭは、特定の機能を共有するデータのインデックス作成及びデータサブセットへのランダムアクセスをサポートしない。データのインデックス付けは、仕様（ＣＲＡＭ仕様ｖ３．０のセクション１２を参照）の範囲外であり、それは別のファイルとして実装されている。反対に、この文書に記載されている本発明のアプローチは、コード化プロセスと統合され、インデックスがコード化された（すなわち、圧縮された）ビットストリームに埋め込まれているデータインデックス方法を使用する。
２．ＣＲＡＭは、あらゆるタイプのマッピングされたリード（完全一致するリード、置換たけがあるリード、挿入又は欠失があるリード（「インデル（ｉｎｄｅｌｓ）」とも呼ばれる））を含むことができるコアデータブロックによって構築される。リファレンスシーケンスに関するマッピングの結果に従った、データの分類及びクラス内のリードのグループ化の概念はない。つまり、特定の機能を持つリードのみが検索された場合でも、すべてのデータを検査する必要がある。そのような制限は、コード化の前にデータをクラスに分類し区分することによって本発明によって解決される。
３．ＣＲＡＭは、各リードを「ＣＲＡＭレコード」にカプセル化するという概念に基づいている。これは、特定の生物学的特徴に特徴付けられたリード（例えば、置換はあるが「インデル」は含まないリード、又は完全にマッピングされたリード）を検索するときに、それぞれの完全な「記録」を調査する必要があることを意味する。
逆に、本発明では、別々の情報層で別々にコード化されたデータクラスの概念があり、各リードをカプセル化するレコードの概念はない。これは、その特徴を検査するために各（複数の）ブロックのリードを必要とせずに、特定の生物学的特性を有する一連のリード（例えば、置換はあるが「インデル」なしのリード、又は完全にマッピングされたリード）へのより効率的なアクセスを可能にする。
４．ＣＲＡＭレコードでは、各レコードフィールドは特定のフラグに関連付けられており、各ＣＲＡＭレコードにはさまざまなタイプのデータを含めることができるため、各フラグは常にコンテキストという概念がなく、同じ意味を持つ必要がある。このコード化メカニズムは冗長な情報を導入し、効率的なコンテキストベースのエントロピーコード化の使用を妨げる。
代わりに本発明では、データが属する情報「レイヤ」によって本質的に定義されるので、データを表すフラグという概念はない。これは、使用されるシンボル数が大幅に減少し、その結果として情報源エントロピーが減少し、その結果、より効率的な圧縮が行われることを意味する。異なる「層」の使用が状況に応じて異なる意味で各層にわたって同じシンボルを再使用することをエンコーダに可能にするので、そのような改善が可能である。ＣＲＡＭでは、各フラグはコンテキストという概念がないため常に同じ意味を持つ必要があり、各ＣＲＡＭレコードには任意のタイプのデータを含めることができる。
５．ＣＲＡＭ置換では、挿入と欠失はさまざまな構文要素、情報ソースのアルファベットのサイズを大きくし、より高いソースエントロピーを生成するオプションを使用して表される。逆に、開示された発明のアプローチは、置換、挿入及び欠失のために単一のアルファベット及びコード化を使用する。これはコード化及び復号化処理をより簡単にし、そしてコード化が高い圧縮性能によって特徴付けられるビットストリームをもたらすより低いエントロピーソースモデルを生成する。
６．ＣＲＡＭは、シングルリードとペアエンドリードの両方について、マルチプルアラインメントとスプライスドリードの適切な表現をサポートしていない。
【００１３】
リファレンスシーケンス上の１つ以上の位置にマッピングされると、ゲノムシーケンスリードはそれらがマッピングされているリファレンスシーケンスセグメントと完全に一致するか、又はいくつかのミスマッチを示すことができる。
ミスマッチのタイプは以下のとおりである。
・置換：マッピングされたリードの１つのヌクレオチドが、リファレンスシーケンスの対応するヌクレオチドと異なる
・挿入：マッピングされたリードはリファレンスに存在しないヌクレオチドを含む。シーケンスアラインメント処理後、それらはマッピングされたヌクレオチド間に「挿入」される結果となる
・欠失：リファレンスシーケンス中に存在する１つ以上のヌクレオチドが、マッピングされたシーケンスリードの対応する位置に存在しない
・ソフトクリップ：シーケンスリード又はリードペアの端にある１つ以上のヌクレオチドが、リファレンスシーケンスにマッピングされないが、アライメントツールによって保持される。
・ハードクリップ：シーケンスリード又はリードペアの端にある１つ以上のヌクレオチドが、リファレンスシーケンスにマッピングされず、マッピングされたリードの一部としてアライメントツールによって保存されない。この場合、マッピングされたリードは、マッピングされていないリードよりも短くなる。
【００１４】
本発明は、シーケンスリードアラインメント処理の結果に従ってデータを分類し、シーケンスデータを分割することによってゲノムシーケンスを圧縮し、それによってコード化される冗長情報が最小限にされ、選択的アクセス及び増分更新のサポートなどの機能が圧縮されたドメインで直接可能である。
【００１５】
ゲノムデータがアラインメント処理の結果に従って分類されると、本発明において開示される構文要素に関する表現は、より効率的なエントロピーコーディング、データへの選択的アクセス及び増分更新を可能にする。強化された圧縮は、データが均質な統計的性質を持つ独立したデータブロックに分割されるという事実によるものである。データが独立して解凍されることができるそのようなブロックに構造化されると、選択的アクセスはより少ない計算力及び帯域幅を必要とし、データセット全体を再コード化する必要なしに新しいコード化データブロックを追加することによる増分更新が可能である。
【００１６】
提示されたアプローチの１つの態様は、異なる層に構造化され別々にコード化されたデータのクラス及びメタデータの定義である。既存の方法に関するそのようなアプローチのより関連性のある改善は以下のものからなる。
１．各クラスのデータ又はメタデータに対して効率的なソースモデルを提供することによって構成される情報ソースエントロピーの減少による圧縮性能の向上、
２．圧縮ドメイン内で直接さらなる処理目的のために、圧縮データ及びメタデータの部分への選択的アクセスを実行する可能性、
３．シーケンスリードの特定のセットに関連する新しいシーケンスデータ及び／又はメタデータ及び／又は新しい分析結果を用いて、圧縮データ及びメタデータを追加的に（すなわち、復号化及び再コード化を必要とせずに）更新する可能性。
【００１７】
本発明において開示されるゲノムシーケンスデータの表現は、「記述子」の概念に依拠している。記述子は、エントロピーコーダを使用して圧縮されるゲノムシーケンスデータを表すのに使用される構文の要素として定義される。異なる記述子による元のゲノムシーケンスデータの表現は、より効率的な圧縮及びデータへの強化された選択的アクセスを可能にする。より効率的な圧縮は、各タイプの記述子又は同じ統計的性質を共有する記述子のサブセットごとに異なるエントロピーコーダを使用することによって達成される。異なる生物学的意味に従ってデータのサブセット中のゲノム情報を分割することを可能にする記述子の定義によって、より効率的な選択的アクセスが可能になる。データの各サブセットは他のデータとは無関係に復号化することができるので、必要な処理能力は減少し、復号化時間はより短い。
【００１８】
本発明の開示において定義される記述子は、同じタイプの圧縮された構文要素のブロックである多数の「記述子ストリーム」に構造化されている。
【発明の概要】
【発明が解決しようとする課題】
【００１９】
以下の特許請求の範囲の特徴は、以下を提供することによって既存の従来技術の解決法の問題を解決する。
【課題を解決するための手段】
【００２０】
ゲノムシーケンスデータをコード化するための方法であって、前記ゲノムシーケンスデータはヌクレオチドのシーケンスのリードを含み、前記方法は、
前記リードを１つ以上のリファレンスシーケンスと整列させ、それによって整列させたリードを作成するステップ、
前記整列リードを前記１つ以上のリファレンスシーケンスとの特定のマッチングルールに従って分類して、それによって整列リードのクラスを作成するステップ、
前記分類され整列されたリードを構文要素の多数のストリームとしてコード化するステップ、を備え、
前記分類された整列されたリードを構文要素の多数のストリームとしてコード化することは、前記整列されたリードのクラスに従って前記構文要素を選択することを含み、
前記構文要素のストリームにヘッダ情報を提供して、それによって前記ゲノムデータブロックを別々にアクセス可能なデータユニットにエントロピーコード化するために連続したデータブロックを作成する。
【００２１】
別の態様では、コード化方法は、
指定されたマッチングルールを満たさない前記リードを、分類されたマッピングされていないリードを多数の構文要素のストリームとしてコード化するマッピングされていないリードのクラスに分類し、
構文要素のストリーム及び前記コード化されたリファレンスシーケンスにヘッダ情報を提供し、それによって連続するアクセスユニットを作成することを、
さらに含む。
【００２２】
別の態様において、コード化方法はさらに、前記分類が、アラインメントに使用されたリファレンスシーケンス上に複数のアラインメント位置を有するゲノムリードを識別することを備えることを備える。
【００２３】
別の態様では、前記コード化方法は、前記分類することが、アライメントのためのマッチングルールを満たすためにスプライスと呼ばれる複数のセグメントに分割する必要があるゲノムリードを識別することを備えることをさらに備える。
【００２４】
別の態様において、前記コード化方法は、コード化されるゲノムシーケンスのリードがペアになっていることをさらに備える。
【００２５】
別の態様では、コード化方法は、
リードのアライメントの数を識別し、この数を特定の構文要素で表すステップ、
アライメントごとに対応するマッピング位置を識別し、各マッピング位置を特定の構文要素で表すステップ、
一次アライメント及び二次アライメントを識別するために各アライメントにアライメントスコアを割り当て、一次アライメントとして最も高いスコアを有するアライメントを識別するステップ、
プライマリとは異なるリファレンスでアライメントが見つかったかを識別し、この情報を特定の記述子を使用して表すステップ、
あるアラインメントが一次アラインメントのリファレンスシーケンス上の異なる隣接性を保存しないかを識別し、特定の構文要素を使用してこの情報を表すステップ、
をさらに備える。
【００２６】
別の態様では、コード化方法は、
前記１つ以上のリファレンスシーケンスとのマッチングを定義する所定のマッチングルールに従って、リファレンスシーケンス上に整列させるために２つ以上のスプライスに分割する必要があるリードを同定するステップ、
グローバル構成パラメータを使用してスプライスされたリードの存在を通知するステップ、
特定の構文要素を使用してスプライスの数を表すステップ、
特定の構文要素を使用して各スプライスの長さを表すステップ、
をさらに備える。
【００２７】
別の態様では、コード化方法は、
ペア内の各リードのアライメントの数を識別し、この数を特定の構文要素で表すステップ、
ペアにおいて最も左のリードのアラインメントごとに、対応するマッピング位置を識別し、各マッピング位置を特定の構文要素で表すステップ、
最も左のリードのアラインメントごとに、ペアにおいて最も右のリードに関連するアラインメントを識別し、特定の構文要素との関連を表すステップ、
一次及アライメント及び二次アライメントを識別するために、アライメントの各ペアにアライメントスコアを割り当てるステップ、
最も高いスコアを有するペアのアラインメントを一次アラインメントとして識別するステップ、
プライマリとは異なるリファレンスでアライメントが見つかったかを識別し、この情報を特定の記述子を使用して表すステップ、
一次アラインメントのリファレンスシーケンス上でアラインメントが別の連続を保存していないかどうかを識別し、特定の構文要素を使用してこの情報を表すステップ、
をさらに備える。
【００２８】
別の態様では、コード化方法は、
予め定義されたマッチングルールに従ってリファレンスシーケンス上に整列させるために２つ以上のスプライスに分割する必要があるリードを識別するステップ、
グローバル構成パラメータを使用してスプライスされたリードの存在を通知するステップ、
特定の構文要素を使用してペアで最も左のリードのスプライスの数を表すステップ、
特定の構文要素のベクトルを持つ最も左のリードの各アラインメントに関連付けられた最も右のリードのスプライス数を表すステップ、
特定の構文要素を使用して各スプライスの長さを表すステップ、
をさらに備える。
【００２９】
別の態様では、コード化方法は、
各データセットグループを一意的に識別するために使用されるデータセットグループ識別子、
各データセットを一意的に識別するために使用されるゲノムデータセット識別子、
データセットが準拠するデータフォーマット仕様を識別するために使用されるブランド識別子、
データセットが準拠するデータフォーマット仕様を識別するために使用されるマイナーバージョン番号、
固定長リードの通知に使用されるヌクレオチドのコード化されたゲノムリードの長さ、
ペアエンドリードの存在を通知するフラグ、
ブロックヘッダの存在を通知するフラグ、
前記アクセスユニットを復号化するときに、データアクセスを容易にするためにアクセスユニットが記憶媒体に記憶されるモードを通知するフラグ、
リファレンスシーケンスに関してシーケンスリードのミスマッチをコード化するために使用されるアルファベットのタイプ、
データセットのコーディングに使用されたリファレンスシーケンスの数、
各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの数値識別子、
各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの文字列識別子、
各リファレンスシーケンスに関連するアクセスユニットを数えるために使用されるリファレンスシーケンスごとのコード化アクセスユニットの数、
整列されたリード、整列されていないリード、マッピングされていないリード及びリファレンスシーケンスを区別するために使用されるコード化されたゲノムデータのタイプ、
データセットにコーディングされたデータクラスの数、
復号化処理中に使用されるデータセット内でコード化されたデータクラスごとに使用される記述子の数、
コード化されたマッピングされていないリードのインデックス付けに使用されたクラスタの総数、
コード化されたクラスタシグネチャを復号化するために使用されるクラスタシグネチャをコード化するために使用される整数値を表すために使用されるビット数、
すべてのクラスタシグネチャが、ヌクレオチド数に関して同じ長さを有する場合に、クラスタシグネチャの長さを通知するフラグ、
を備えるゲノムデータセットヘッダを備える前記構文要素のストリームを、さらに備える。
【００３０】
別の態様では、コード化方法は、
前記構文要素のストリームは、整列されたリードのクラス及びサブクラスごとに１つのセクションを含む、マスタインデックステーブルを備え、前記セクションは、
各クラス又はサブクラスのデータの各アクセスユニットの最も左のリードの一次アライメントの前記１つ以上のリファレンスシーケンス上のマッピング位置、
各クラス又は各データのサブクラスの各アクセスユニットのすべての一次アライメントの中で最も右にマッピングされた塩基の前記１つ以上のリファレンスシーケンス上の位置、
各アクセスユニットを構成するコード化された構文要素の各ブロックのバイト単位のオフセット、
をさらに備える。
【００３１】
別の態様では、コード化方法は、前記マスタインデックステーブルが各コード化された記述子ストリームのサイズを含むことをさらに備える。
【００３２】
別の態様では、コード化方法は、前記マスタインデックステーブルが各アクセスユニットのサイズをさらに含むことをさらに備える。
【００３３】
別の局面において、コード化方法は、ゲノムリードが複数のアライメントを有することをされに備え、上記マスタインデックステーブルが、
各クラス又は各データのサブクラスの各アクセスユニットのすべてのリードの中で最も左のアライメントの前記１つ以上のリファレンスシーケンス上のマッピング位置、
各クラス又は各データのサブクラスの各アクセスユニットのすべてのアラインメントの中で最も右にマッピングされた塩基の前記１つ以上のリファレンスシーケンス上の位置、
各アクセスユニットを構成するコード化された構文要素の各ブロックのバイト単位のオフセット、
を含む。
【００３４】
別の態様では、コード化方法は、前記アクセスユニットがコード化されたリードペアを含むことをさらに備える。
【００３５】
別の態様では、コード化方法は、前記マスタインデックステーブルが前記アクセスユニットデータと一緒にコード化されることをさらに備える。
【００３６】
別の態様では、コード化方法は、前記ゲノムデータセットヘッダが前記アクセスユニットデータと一緒にコード化されることをさらに備える。
【００３７】
別の態様では、コード化方法は、使用されるリファレンスのタイプ（既存又は構築された）及びリファレンスシーケンスと一致しないリードのセグメントに関する情報を構文要素のストリームがさらに備えることをさらに備える。
【００３８】
別の態様では、コード化方法は、構文要素の複数のストリームとして前記分類され整列されたリードが、特定のソースモデル及び特定のエントロピーコーダを各記述子ストリームに関連付けるステップを備えることをさらに備える。
【００３９】
別の態様では、コード化方法は、前記エントロピーコーダがコンテキスト適応算術コーダ、可変長コーダ又はゴロムコーダのうちの１つであることをさらに備える。
【００４０】
ヘッダ情報を使用することによって構文要素の複数のストリームを抽出するためにコード化されたゲノムデータを含むアクセスユニットを解析するステップ、
１つ以上のリファレンスシーケンスに関してそれらの分類を定義する特定のマッチングルールに従って整列されたリードを抽出するために構文要素の前記複数のストリームを復号化することステップ、
を備えるコード化ゲノムデータを復号化するための方法。
【００４１】
別の態様では、復号化方法は、マッピングされていないゲノムリードを復号化することをさらに備える。
【００４２】
別の態様では、復号化方法は、グローバル構成パラメータを含むゲノムデータセットヘッダを復号化することをさらに備える。
【００４３】
別の態様では、復号化方法は、リードのクラスごとに１つのセクションと、関連する関連マッピング位置と、コード化されたブロックオフセットとを含むマスタインデックステーブルを復号化することをさらに備える。
【００４４】
別の態様では、復号化方法はさらに、既存の、変換された又は構築された、使用されるリファレンスのタイプに関する情報を復号化することを備える。
【００４５】
別の態様では、復号化方法は、前記ゲノムリードがペアであることをさらに備える。
【００４６】
別の態様では、復号化方法は、前記ゲノムデータがエントロピー復号化されていることをさらに備える。
【００４７】
別の態様では、復号化方法は、
各リードのアライメント数を復号化するステップ、
各アライメントの位置を復号化するステップ、
各アライメントに関連するスコアを復号化することによってプライマリアライメントを識別するステップ、
対応する構文要素を復号化することによって、いずれかかのセカンダリアライメントがリファレンスシーケンスに対してプライマリアライメントと異なる隣接性を有するかを識別するステップ、
を備える複数のアライメント情報の復号化をさらに備える。
【００４８】
別の態様では、復号化方法は、
コード化されたリードが２つ以上のスプライスに分割されているかどうかを識別するステップ、
各スプライスの長さを復号化するステップ、
各スプライスのマッピング位置を復号化するステップ、
をさらに備える。
【００４９】
別の態様では、復号化方法はさらに、コード化されたゲノムリードがペアエンドリードであることをさらに備え、
最も左のリードの各アライメントに関連付けられた最も右のリードのアライメントの数を復号化するステップ、
最も左のリードの各アライメントを最も右のリードの１つ以上のアライメントと関連付けるペアリング情報を復号化するステップ、
を備える。
【００５０】
別の態様では、復号化方法は、コード化ゲノムリードが２つ以上のスプライスに分割されることさらに備え、
各コード化スプライスの長さを復号化するステップ、
各スプライスのマッピング位置を復号化するステップ、
を備える。
【００５１】
本発明はさらに、ゲノムシーケンスデータ２８９の圧縮のためのゲノムエンコーダ（２８１０）を提供し、前記ゲノムシーケンスデータ２８９はヌクレオチドのシーケンスのリードを備え、前記ゲノムエンコーダ（２８１０）は、
前記リードを１つ以上のリファレンスシーケンスに整列させ、それによって整列されたリードを作成するように構成される、アライナユニット（２８１）、
構築されたリファレンスシーケンスを生成するように構成された、構築されたリファレンス生成器ユニット（２８２）、
１つ以上の既存のリファレンスシーケンス又は構築されたリファレンスシーケンスを用いて指定されたマッチングルールに従って前記整列されたリードを分類し、それによって整列されたリードのクラス（２８８）を作成するように構成された、データ分類ユニット（２８４）、
整列されたリードの前記クラスに従って、前記構文要素を選択することによって前記分類された整列されたリードを構文要素のストリームとしてコード化するように構成された、１つ以上の記述子ストリームコード化ユニット（２８５〜２８７）、
圧縮されたゲノムデータ及びメタデータを多重化するためのマルチプレクサ（２８１６）、
を含む。
【００５２】
別の態様では、ゲノムエンコーダは、
データ分類ユニット（２８４）は、データクラスＮ、Ｍ及びＩのサブクラスを生成する閾値のベクトルで構成されたデータクラスＮ、Ｍ及びＩのエンコーダを含むことをさらに備える。
【００５３】
別の態様では、ゲノムエンコーダは、前述のコード化方法のすべての態様を実行するのに適した機能をさらに備える。
【００５４】
本発明はさらに、圧縮ゲノムストリーム（２９１）を解凍するためのゲノムデコーダ（２９８）を提供し、前記ゲノムデコーダ（２９８）は、
圧縮されたゲノムデータ及びメタデータを逆多重化するためのデマルチプレクサ（２９０）、前記圧縮されたゲノムストリームを構文要素（２９５）のストリームに解析するように構成された解析手段（２９２〜２９４）、
記述子ストリームをヌクレオチドのシーケンスの分類されたリードに復号化するように構成された、１つ以上の構文要素ストリームデコーダ（２９６〜２９７）、
１つ以上のリファレンスシーケンス上のヌクレオチドのシーケンスの前記分類されたリードを選択的に復号化して、ヌクレオチドのシーケンスの圧縮されていないリードを生成するように構成された、ゲノムデータクラスデコーダ（２９９）、
を備える。
【００５５】
別の態様では、ゲノムデコーダは、１つ以上のリファレンスシーケンスが圧縮されたゲノムストリーム（２９１）に格納されることをさらに備える。
【００５６】
別の態様では、ゲノムデコーダは、１つ以上のリファレンスシーケンスが帯域外メカニズムを介してデコーダに提供されることをさらに備える。
【００５７】
別の態様では、ゲノムデコーダは、１つ以上のリファレンスシーケンスがデコーダで構築されることをさらに備える。
【００５８】
本発明は、実行されると少なくとも１つのプロセッサに前述のコード化方法のすべての態様を実行させる命令を備えるコンピュータ可読媒体をさらに提供する。
【００５９】
本発明は、実行されると少なくとも１つのプロセッサに前述の復号化方法の全ての態様を実行させる命令を備えるコンピュータ可読媒体をさらに提供する。
【００６０】
本発明はさらに、前述のコーディング方法の全ての態様に従って実行されるゲノムコードを保存するサポートデータを提供する。
【図面の簡単な説明】
【００６１】
【図１】図１は、リファレンスシーケンス上の座標系及びリファレンスシーケンス上のリード及びリードペアのマッピングを示す。
【図２】図２は、ゲノムレコード長が、リード又はリードペアの最も左にマッピングされた塩基から最も右にマッピングされた塩基を分離するリファレンスシーケンス上のゲノム位置の数として定義される方法を示す。リードペアの場合、これは、両方のリードが同じリファレンスシーケンスにマッピングされているときに、リード１の左端の塩基をそのメイトのリード２の右端の塩基から隔てるリファレンスシーケンス上のゲノム位置の数である。
【図３】図３は、ペアリードの場合のゲノムレコード長の計算例を示す。
【図４】図４は、整列されたリード又はリードペアが２つ以上のアクセスユニットにまたがることができる方法を示す。これは、それぞれのゲノムレコード長が、レコードを含むＡＵの末端からリード又はリードペアマッピング位置までの距離よりも大きい場合に発生する。たとえリードが特定のゲノム領域をカバーしていないアクセスユニットでコード化されていても、一貫した選択的アクセスアルゴリズムは、特定のゲノム領域と重なるすべての塩基を検索することができなければならない。
【図５】図５は、マッピングされた３つのリードペアのうちの最初のリードの位置がどのように「ｐｏｓ」記述子にコード化されるかを示す。
【図６】図６は、リード１がストランド１からの起点を有し、リード２がストランド２からの起点を有するリードペアの例を示す。
【図７】図７は、ストランド１をリファレンスとして使用した場合に、リード２のリバースコンプリメントがどのようにコードされるかを示す。
【図８】図８は、リードペアを構成するリードと、「ｒｃｏｍｐ」記述子内のそれぞれのコード化との４つの可能な組み合わせを示す。
【図９】図９は、３つのリードペアのペアリング距離を計算する方法を示す。
【図１０】図１０は、リファレンスシーケンス（クラスＰ）に完全にマッピングするペアの固定長リードをコード化するために使用される記述子を示す。
【図１１】図１１は、リファレンスシーケンス（クラスＰ）上に完全にマッピングする可変長のリードをコード化するために使用される記述子を示す。
【図１２】図１２は、リファレンスシーケンス（クラスＮ）に関して未知の塩基を有するペアの固定長リードをコード化するために使用される記述子を示す。
【図１３】図１３は、少なくとも１つの置換を有するリファレンスシーケンス（クラスＭ）上にマッピングするペアの固定長リードをコード化するために使用される記述子を示す。
【図１４】図１４は、少なくとも１つの挿入、欠失又はソフトクリップ塩基を有するリファレンスシーケンス（クラスＩ）上にマッピングするペアの固定長リードをコード化するために使用される記述子を示す。
【図１５】図１５は、一番左のリードにＮ個のアライメント、一番右のリードにＭ個のアライメントがあるリードペアを示す。
【図１６】図１６は、左端のリード（リード１）を２つのスプライスに分割し、右端のリード（リード２）を４つに分割するのに必要な所与の制約条件によるリードペアのマッピングの方法を示す。
【図１７】図１７は、スプライシングを伴わないマルチプルアラインメントを示す。各リード又はリードペアに対して、Ｎはｍｍａｐ記述子の最初の値であり、最初のリードのアライメント数を示す。ペアエンドリードの場合、２番目のリードのアライメントの数であるＰが計算するために、続いてｍｍａｐ記述子のＮ個の値を使用する。
【図１８】図１８は、スプライスのない複数のアライメントをコード化するために、ｐｏｓ、ｐａｉｒ、及びｍｍａｐ記述子を使用する方法を示す。
【図１９】図１９は、スプライスを用いたマルチプルアラインメントの一例を示す。Ｎは最初のリードのスプライス数を表し、ｍｍａｐ記述子の最初の値としてコード化さる。Ｐは２番目のリードのスプライス数を表し、ｍｍａｐ記述子の次のＮ個の値を使用して計算される。Ｎ１及びＮ２は、第１及び第２のリードのアラインメント数を表し、ｓｐｌｅｎ記述子のＮ＋Ｐ値を使用して計算される。
【図２０】図２０は、スプライスのある複数のアライメントを表すために、ｐｏｓ、ｐａｉｒ、ｍｍａｐ、及びｓｐｌｅｎ記述子を使用する方法を示す。
【図２１】図２１は、本発明の開示に従って記憶媒体上にコード化されたゲノム情報を書き込むために使用することができる２つのコード化モードを示す。アクセスユニット連続（ＡＵＣ）モードが採用されるとき、各アクセスユニットは記憶媒体の連続領域に記憶される。記述子ストリーム連続（ＤＳＣ）モードが採用されるとき、同じタイプのすべての記述子は単一のブロックとして記憶媒体の連続領域上に記憶される。結果として、各ＡＵは記憶媒体の異なるセグメント間に「分散」される。
【図２２】図２２は、アクセスユニットがコード化された記述子のブロックによってどのように構成されるかを示す。ネットワーク上での転送を可能にするために、ブロックはさらにパケットに分解される。
【図２３】図２３は、アクセスユニットがヘッダ及び異なるストリームのデータブロックの多重化（記述子毎に１つ）によって構成されることを示す。同じタイプのいくつかのパケットが１つのブロックにカプセル化され、多数のブロックが１つのアクセスユニットに多重化される。
【図２４】図２４は、リードをクラスタ化し、各クラスタから取得したセグメントを組み立てることによって、「内部」リファレンスを作成する方法を示す。各クラスタは、構築されたリファレンスの１つのセグメントに寄与する。
【図２５】図２５は、リファレンスを構築する戦略が、特定のソート（例えば辞書式順序）がリードに適用された後に、最新のリードを格納することからなることを示す。
【図２６】図２６は、マッピングされていないリードのクラス（クラスＵ）に属するリードが、対応するストリームに格納又はもたらされる６つの記述子を使用してコード化され得ることを示す。
【図２７】図２７は、符号付きｐｏｓ記述子を使用して、構成されたリファレンス上のリードのマッピング位置をコーディングする、クラスＵのリードの代替コーディングを示す。
【図２８】図２８は、本発明の開示を実施するゲノムエンコーダのアーキテクチャを示す。
【図２９】図２９は、本発明の開示を実施するゲノムデコーダのアーキテクチャを示す。
【図３０】図３０は、リード１について３つのアライメント及びリード２について４つのアライメントを有するリードペアを示す。リード１についての第３のアライメントはＣｈｒＸ上であるが、すべてのアライメントは同じ染色体（例えばＣｈｒ１）上にある。ペア記述子の最初の値は、あるアライメントが他のアライメントシーケンスとは異なるリファレンスシーケンスにあることを示すために使用される。
【図３１】図３１は、プライマリアライメントのマッピング連続性を維持しない１つのセカンダリアライメントを表すためのｍｍｓｃ記述子の使用例を示す
【図３２】図３２は、より長いシーケンス（「「コンティグ」としても知られる））をマッピングされていないリードと組み合わせることによって、リファレンスシーケンスの未知領域を埋めるために、ハーフマッピングされたリードペア（クラスＨＭ）を用いる方法を示す。
【発明を実施するための形態】
【００６２】
関連アプリケーションとの相互参照
本出願は、特許出願ＰＣＴ／ＥＰ２０１６／０７４３１１、ＰＣＴ／ＥＰ２０１６／０７４３０１、ＰＣＴ／ＥＰ２０１６／０７４３０７、ＰＣＴ／ＥＰ２０１６／０７４２９７、ＰＣＴ／ＵＳ２０１７／１７８４２、ＰＣＴ／ＵＳ２０１７／１７８４１の優先権及びその利益を主張する。
【００６３】
本発明において言及されるゲノム又はプロテオームシーケンスは、例えば、限定されるものではないが、ヌクレオチドシーケンス、デオキシリボ核酸（ＤＮＡ）シーケンス、リボ核酸（ＲＮＡ）、及びアミノ酸シーケンスを含む。本明細書中の記載はヌクレオチドシーケンスの形態のゲノム情報に関してかなり詳細であるが、圧縮のための方法及びシステムは、いくつかのバリエーションを伴うが、当業者によって理解されるように、他のゲノム又はプロテオームシーケンスについても同様に実施され得ることが理解される。
【００６４】
ゲノムシーケンス情報は、定義された語彙からの文字列によって表されるヌクレオチドのシーケンス（別名「塩基」）の形でハイスループットシークエンシング（ＨＴＳ）装置によって生成される。最小の語彙は５つの記号：｛Ａ、Ｃ、Ｇ、Ｔ、Ｎ｝で表され、ＤＮＡに存在する４種類のヌクレオチド、すなわちアデニン、シトシン、グアニン及びチミンを表す。ＲＮＡでは、チミンはウラシル（Ｕ）に置き換えられる。Ｎは、シークエンシング装置がいかなる塩基も呼び出せなかったことを示し、したがってその位置におけるヌクレオチドの実際の性質は決定されていない。ＩＵＰＡＣ  ａｍｂｉｇｕｉｔｙ  ｃｏｄｅｓが語彙としてシーケンシングマシンによって採用される場合、シンボルに使用されるアルファベットは以下の記号からなる：｛Ａ、Ｃ、Ｇ、Ｔ、Ｕ、Ｗ、Ｓ、Ｍ、Ｋ、Ｒ、Ｙ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎ又は−｝。
【００６５】
本発明の文脈において、「ゲノムデータセット」は、例えば、生物のゲノムデータ、１つ以上のシーケンス及び生物のゲノムシーケンシングによって、元のシーケンスデータに対して行われたゲノムデータ処理の他の任意のステップによって生成されるメタデータを含む、構造化されたゲノムデータのセットとして定義される。
【００６６】
シーケンシング装置によって生成されたヌクレオチドシーケンスは「リード」と呼ばれる。シーケンスリードは、数十から数千の範囲の数のヌクレオチドから構成され得る。いくつかのシーケンシング技術は、一方のリードが一方のＤＮＡ鎖から生じ、他方が他方の鎖から生じる「ペア」からなるシーケンスリードを生成する。ペアを生成するシーケンシング処理における別のリードに関連するリードは、その「メイト」であると言われる。
【００６７】
本開示を通して、リファレンスシーケンスは、各整数座標が単一のヌクレオチドに関連している一次元整数座標系に関連したヌクレオチドのシーケンスである。座標値は、ゼロ以上でなければならない。本発明のコンテキストにおけるこの座標系はゼロを基準とし（すなわち、最初のヌクレオチドは座標０を有し、それは位置０にあると言われる）、左から右へ直線的に増加する。
【００６８】
マッピングシーケンスリードがリファレンスシーケンス上にあるとき、前記リファレンスシーケンスは、最も左の位置が位置０として示される一次元座標系の軸として使用される。最小の座標番号によって識別されるリファレンスシーケンス位置にマッピングされたリードは、通常、「最も左の」ヌクレオチドと呼ばれ、最大の座標番号によって識別されるリファレンスシーケンス位置にマッピングされたリードを構成するヌクレオチドは、「最も右」のヌクレオチドと呼ばれる。これを図１に示す。本開示を通して、ヌクレオチドは「塩基」とも呼ばれる。
【００６９】
シーケンスリードがリファレンスシーケンスにマッピングされるとき、最も左にマッピングされた塩基の座標は、リファレンスシーケンス上のリードのマッピング位置を表すと言われる。
【００７０】
リファレンスゲノムは１つ以上のリファレンスシーケンスによって構成され、それは種の遺伝子セットの代表例として科学者によって集められる。例えば、ＧＲＣｈ３７、ゲノムリファレンスコンソーシアムのヒトゲノム（ｂｕｉｌｔ３７）は、ニューヨーク州バッファロー出身の１３人の匿名のボランティアに由来する。しかしながら、リファレンスシーケンスはまた、それらのさらなる処理を考慮してリードの圧縮性を改善するために考えられ、単に構築された合成シーケンスからなることもできる。
【００７１】
本開示を通して、ゲノムレコードは、以下のコード化表現として定義される。
・アライメント情報、リード識別子及び品質値にオプションで関連付けられた単一シーケンスリード又はペアシーケンスリード
・リファレンスシーケンス（例えば染色体）又はその一部。
【００７２】
本開示を通して、ゲノムレコード位置は、ゲノムレコードにおいてコード化されたリード又はリードペアの最も左にマッピングされた塩基のリファレンスシーケンス上の位置として定義される。
【００７３】
リード又はリードペアレコード内のマッピング塩基は、いかを含む。
・リファレンスシーケンス上の対応する塩基と一致する配列されたリードの塩基
・対応する塩基と一致しない配列されたリードの塩基（別名、一塩基多型）。
【００７４】
アラインメントされたリードに存在し、リファレンスシーケンスには存在しない塩基（別名、挿入）及びアラインメント処理によって保存されているがリファレンスシーケンスにはマッピングされない塩基（別名ソフトクリップ）は、マッピング位置を有さない。
【００７５】
本開示では、リファレンス上の最小座標上にマッピングされている塩基でリードペアを構成するリードを「リード１」と呼び、そのメイトを「リード２」と呼ぶ。
【００７６】
今日の技術を使用するシーケンシング装置によって、ペアとして生成された２つのリードを分離する、ヌクレオチド（又は塩基）の数として表される距離は未知であり、それはペアを構成する両方のリードをリファレンスシーケンスへマッピングする（すなわち適切なマッチング関数を最小にする）ことによって決定される。
【００７７】
本開示を通して、ゲノムレコード長は、レコード中にコード化された最も左にマッピングされた塩基とレコード中にコード化された最も右にマッピングされた塩基との間の座標位置の数として定義される。
【００７８】
本開示を通して、ペアリング距離は、レコードにコード化された最も左にマッピングされた塩基とレコードにコード化されたリード２の最も左にマッピングされた塩基との間の座標位置の数として定義される。ペアリング距離の例を図１に示す。
【００７９】
本開示を通して、シングルリードの場合、ゲノムレコード長（ＧＲＬ）は、最も右にマッピングされた塩基のマッピング位置から最も左の塩基のマッピング位置を減算し、「１」を加えることによって得られる整数として計算される。
ＧＲＬ＝（最も右の塩基の位置）−（最も左の塩基の位置）＋１
【００８０】
リードペアの場合、本開示全体を通して、ゲノムレコード長（ＧＲＬ）は、リファレンスシーケンス（リード１）上の最小位置におけるリードマッピングの最も左の塩基のマッピング位置を、そのメイトの最も右の塩基のマッピング位置の座標（リード２）から差し引き、「１」を加えることによって得られる整数として計算される。ゲノムレコード長のそのような定義は図３に示される。
【００８１】
本開示全体を通して、リファレンスシーケンス又はその一部をコードするゲノムレコードの場合、ゲノムレコード長は、コードされたシーケンスを構成するヌクレオチドの数として定義される。
【００８２】
本開示を通して、ゲノム範囲は、Ｓ＜Ｅであるように、開始座標Ｓ及び終了座標Ｅによって定義されるリファレンスシーケンス上の連続座標セグメントとして定義される。ゲノム範囲の開始位置及び終了位置は、範囲に常に含まれる。
【００８３】
本発明は、シーケンスリードがアクセスユニットと呼ばれる複数のデータブロックに含まれる記述子のセットによって圧縮される場合に、任意のゲノム領域にマッピングされた整列されたゲノムシーケンスリードへの効率的なアクセスを可能にする新しい方法を定義することを目的とする。
【００８４】
本開示を通して、アクセスユニット（ＡＵ）は、ビットストリームのアクセス及び操作を容易にするためにゲノム情報又は関連するメタデータのコード化表現を含む論理データ構造として定義される。本開示に記載の本発明を実施する復号化装置によって復号化することができるのは、これが最小のデータ構成である。
【００８５】
コード化された情報のタイプに応じて、ＡＵは他のＡＵとは無関係に、又は他のＡＵに含まれる情報を使用して復号化することができる。
【００８６】
ＡＵは、コード化されたデータの性質に応じて多様なタイプのものとすることができる。アクセスユニットは、リファレンスシーケンス、又はその一部、あるいは単一クラスのデータに属するコード化されたリード又はリードペアを含む。たとえば、アクセスユニットは、ゲノムリファレンスコンソーシアムのヒトゲノム（ｂｕｉｌｄ３７）であるＧＲＣｈ３７の１番染色体全体を含んでもよい。別のアクセスユニットは、座標５０００と１５０００の間に位置するＧＲＣｈ３７の第１染色体のヌクレオチドのコード化表現を含んでもよい。他のアクセスユニットは、ミスマッチなしにリファレンスシーケンスに完全にマッピングするリード又はリードペアのみを含んでもよい。別のアクセスユニットは、リファレンスシーケンスに関してミスマッチとして「Ｎ」の記号のみを含むリード又はリードペアを含んでもよい。別のアクセスユニットは、任意のタイプの置換（例えば、リード又はリードペアに存在する１つの塩基は、リファレンスシーケンス中の対応するマッピング位置の塩基とは異なる）を含むリード又はリードペアを含んでもよい。他のアクセスユニットは、ミスマッチ、挿入、欠失及びソフトクリップされた塩基を含むリード又はリードペアを含んでもよい。他のアクセスユニットは、リファレンスシーケンスにマッピングされていないリード又はリードペアのみを含んでもよい。他のアクセスユニットは、一方のリードがリファレンスシーケンスにマッピングされ、他方がマッピングされていないリードペアのみを含んでもよい。別のタイプのアクセスユニットは、１つ以上のリファレンスシーケンス（例えば、染色体）によって構成されるリファレンスゲノムのコード化されたセグメントのみを含んでもよい。
【００８７】
アクセスユニットの本質的な特徴は、それが表すゲノム情報（シーケンスリード又はリードペア、リファレンスシーケンス）、それを示すリード又はリードペアの関連するアラインメント情報及びメタデータを再構成するのに必要なすべての要素を圧縮形式で含むことである。言い換えれば、アクセスユニットによってもたらされるリード、リードペア又はリファレンスシーケンス及び関連情報を完全に再構成するためには、アクセスユニット自体、及び必要であれば、それが参照するリファレンスシーケンスを含むアクセスユニットを取り出すことだけが必要である。
【００８８】
各アクセスユニットにおいて、エントロピーコーディングがそれらを圧縮するために適用されるときに、それらの同種の統計的性質を活用するために、コード化されたリード又はリードペアを表す次のセクションにリストされた記述子は、タイプごとの別々のデータブロックに集約される。
【００８９】
各アクセスユニットは、リファレンスシーケンス上のゲノム領域にマッピングされた同じクラスに属するシーケンスリード又はリードペアを表す記述子の圧縮されたサブセットを含む。リファレンスシーケンス上のそのようなゲノム領域は、開始座標（又は開始位置）及び終了座標（又は終了位置）によって定義される。
【００９０】
アクセスユニットの一例が図２２に示される。アクセスユニットはコード化された記述子のブロックによって構成される（次のセクションで説明される）。ネットワーク上での転送を可能にするために、ブロックはさらにパケットに分解される。
【００９１】
記述子は、コード化されたリファレンスシーケンス、シーケンスリード及び関連するマッピング情報、又はシーケンスリードのペア及び関連するマッピング情報を再構成（すなわち復号化）するのに必要な情報の一部を表す構文要素である。表現するために異なるタイプの記述子が定義される。
・リファレンスシーケンス上のリードのマッピング位置、
・リードとメイトの距離、
・シーケンスリードの長さ
リファレンスシーケンスに対する整列されたリードのミスマッチの位置、
・関連する位置でのリファレンスシーケンスに対するミスマッチのタイプ、
・マッピング手順によってリファレンスシーケンスにマッピングできなかった塩基、及び「ソフトクリップ」塩基として分類された塩基、
シーケンスリード長、
・ＳＡＭ仕様で指定されているマッピングフラグ、
・マッピング手順によって単一のリード又はリードペアに関連付けられている複数のマッピング位置、
・スプライスされたリードの存在の識別（つまり、チャンクに分割されたときに、より高いマッチング精度でマッピング位置を認めるとき、そして、それらがリファレンスシーケンス上の単一位置にマッピングされた単一連結リードとしてマッピングされるときのリード）、
・使用されるリファレンスシーケンスの特定のタイプ：
○ゲノムリファレンスコンソーシアム（例えばＧＲＣｈ３７）、カリフォルニア大学サンタクルス校（例えばｈｇｌ９）のようなコンソーシアムによって公開されているものとしてのリファレンスゲノム、
○指定されたセットのリード及び指定されたセットのアセンブリルールを用いて構築されたリファレンスシーケンス。
・そのような変更されたリファレンスシーケンスにマッピングされたシーケンスリードのミスマッチを表すために使用される記述子のエントロピーを減少させる目的でリファレンスシーケンスに適用される変更の位置及びタイプ、
・指定された程度のマッチング精度でリファレンスシーケンスのどの位置にもマッピングできないシーケンスリードの表現、
・リファレンスシーケンス全体又はその一部の表現。
【００９２】
本開示において参照され、本発明によって使用される各記述子の完全なリスト及び正確な定義は、以下の節に提供される。
【００９３】
上述のように、それらがそれらの関連する情報で完全に再構成されることができるように、圧縮された形でリファレンスシーケンス、シーケンスリード又はリードペアを表すために本発明によって多数の記述子が使用される。リファレンスシーケンス上のマッピングの結果に従って、リード又はリードペアもまた異なるクラスに分類及び分離され、別々のデータブロックにエントロピーコード化される場合、記述子の異なるサブセットが各クラス又はリード又はリードペアを表すために使用される。したがって、アクセスユニットは、リファレンスシーケンス、又はその一部、あるいは同じクラスに属するリード又はリードペアのいずれかを表すために必要なエントロピーコード化された記述子のみを含む。これは、可変長のリードについては図１１に、固定長のリードペアについては図１２、図１３、図１４に示す。
【００９４】
本開示を通して、同じタイプのエントロピーコード化された記述子は記述子ストリームを構成すると言われる。
【００９５】
本開示を通して、アクセスユニット開始位置は、アクセスユニットに含まれるすべてのゲノムレコードのうち最も左のゲノムレコード位置として定義される。
【００９６】
本開示全体を通して、アクセスユニット終了位置は、アクセスユニットに含まれる全ゲノムレコードの全マッピングされた塩基の中で最も右にマッピングされた塩基位置として定義される。
【００９７】
本開示を通して、アクセスユニット範囲は、アクセスユニットに含まれるすべてのゲノムレコードのうち、ＡＵ開始位置と最も右のゲノムレコード位置との間に含まれるゲノム範囲として定義される。ポジション数の値は、ＡＵの終了位置からＡＵの開始位置を引いて「１」を加えることで計算できる。
【００９８】
本開示を通して、アクセスユニットカバー領域は、ＡＵ開始位置とＡＵ終了位置との間に含まれるゲノム範囲として定義される。
【００９９】
本開示を通して、アクセスユニットはその開始位置とその終了位置の間のゲノム領域をカバーするとも言われる。
【０１００】
ＡＵでコード化されたいくつかのゲノムレコードは、ゲノムレコード長よりも小さいＡＵ末端位置からの距離でマッピング位置を有することができる。これは、ゲノムレコードにコードされているリード又はリードペアに属するいくつかの塩基が、以下のＡＵのうちの１つによってカバーされるゲノム領域にマッピングされることを意味する。これを図４に示す。
【０１０１】
上記の定義によると、アクセスユニットを構築するための２つの便利な方法が識別できる。
１．同じデータクラスのアクセスユニットのゲノム範囲が決して重複しない、いわゆる「非重複モード」、
２．同じデータクラスのアクセスユニットのゲノム範囲が重複してもよい、いわゆる「重複モード」。
【０１０２】
「非重複モード」は、ゲノムデータが圧縮されてファイルとしてメモリに記憶されるシナリオにおいても、記憶されたファイルが１つの記憶装置から別の記憶装置にストリーミングされるときにもストリーミングシナリオにおいて好ましい。「重複モード」は、ゲノムデータセットの一部がアクセスユニットへのコーディング及び送信のために利用可能になったとき、及びゲノムシーケンスデータの全体が送信デバイスで利用可能になる前にストリーミングシナリオをサポートする。
【０１０３】
開示された発明の革新的な態様は以下の通りである。
１．ゲノムシーケンスへの各シーケンスリード又はリードペアのコード化は、コード化シーケンスリード又はリードペアがリファレンスシーケンスにマッピングする方法、及びその圧縮された表現から完全に再構成することができる方法を表す記述子のサブセットによって実施される。
２．各クラスのデータに属するシーケンスリード又はリードペアを表すために、記述子の特定のサブセットを使用され、リード又はリードペアは、リファレンスシーケンスへのマッピングの結果に従って分割される。この表現は、複数のマッピング位置とスプライスされたリードをサポートする。
３．記述子の特定のサブセットは、リファレンスシーケンス又はその一部を表すために使用される。
４．各リードが同じ長さを有するシーケンスリードペアの場合、各ペアは単一の記述子のサブセットに関連するゲノムレコード内の単一の実体としてエントロピーコード化されて、コーディング性能を最大にする。
５．ゲノムレコードにコード化された圧縮形式（すなわちエントロピーコード化）の記述子のサブセットは、リードの最も左にマッピングされた塩基、又はリードペア用のリード１の最も左にマッピングされた塩基を含む範囲を有するアクセスユニットに含まれる。
６．１つのペアに属するリードを単一のエンティティとしてコード化する必要があるかどうか、及びそのペアを表す記述子のサブセットを単一のアクセスユニットに圧縮形式で含める必要があるかどうか、又はペアが分割され、２つの異なるアクセスユニットに２つの別々のリードとして圧縮形式で表されるべきかを決定するコーディング方法。この方法は、ペアの２つのリード間の距離とアクセスユニットの範囲を入力パラメータとして使用して、分割規則を定義する。
７．エンコーダ側での新しいコード化方法の適用及び圧縮されたビットストリームでのコード化パラメータの送信は、デコーダ側で、すべてのシーケンスリード及び特定のゲノム領域にマッピングされた（すなわち、属する）リードペアにアクセスすることが要求されるときに復号化される必要がある最小数のアクセスユニットの最小数の識別を可能にする。８．コード化方法の定義、復号化器側でのコード化方法のパラメータの送信、最小アクセスユニット数の決定及び任意の所与のゲノム領域にマッピングするすべてのリードを検索するためのそれらの識別は、圧縮された形式で格納又は転送された（つまりストリーミングされた）シーケンスリード及びリードペアへの高性能の選択的アクセス実装を可能にする。
９．記述子を使用し、アクセスユニット内の同種のデータブロックに分割することにより、効果的なエントロピーコーディングを、ゲノム情報表現を圧縮することに適用することができる。
１０．マスタインデックステーブル（ＭＩＴ）と呼ばれるインデックス作成ツールの定義は、
ａ．データクラスごとに、ゲノムデータセットに含まれる各ＡＵの開始位置と終了位置を含むインデックス。各インデックスでは、ＡＵ開始位置は昇順でソートされる。
ｂ．データクラスごとに、各データクラスに属するコード化されたＡＵの記憶媒体上の物理的位置へのポインタのベクトル。各ベクトルは、ＡＵ開始位置の対応するインデックスとしてソートされる。
ＭＩＴは、リファレンスシーケンス上のゲノム領域を、前記リード又はリードペアの圧縮表現を含むアクセスユニットの記憶装置上の対応する位置と関連付けることによって、特定のゲノム領域にマッピングされたリード又はリードペアへの効率的なランダムアクセスを可能にする。
１１．可変長のシングルリード（つまり、任意の値を取り得る長さのリード）の場合、各アクセスユニットでコード化されたリードの長さの分布とそのマッピング座標を評価する新しいコード化方法が、アクセスユニットに含まれるリードに属する塩基のマッピング位置の座標（ＡＵ終了位置）を決定し、ＭＩＴにそのような値の表現を書き込むので、特定のゲノム領域に対して効率的な選択的アクセス動作を実施するためのデコーダによって利用可能である。デコーダは、特定の選択的アクセス領域をカバーする各ＡＵの終了位置の値を検索するためにＭＩＴのみを検査することによって、選択的アクセスを必要とするゲノム領域をカバーする全てのリードが検索されことを保証するために復号化される必要があるアクセスユニットの最小数を決定することができる。
【０１０４】
以下では、上記の革新的な態様のそれぞれをさらに詳細に説明する。
【０１０５】
マッチングルールに従ったシーケンスリードの分類
シーケンシング装置によって生成されたシーケンスリードは、開示された発明によって、１つ以上の「既存の」リファレンスシーケンスに関するアラインメントのマッチング結果に従って、６つの異なる「クラス」に分類される。
【０１０６】
リファレンスシーケンスに関してヌクレオチドのＤＮＡシーケンスを整列させる場合、以下の場合が識別され得る。
１．リファレンスシーケンス中の領域が、エラーのないシーケンスリードと一致することが見出された（すなわち、完全マッピング）。そのようなヌクレオチドシーケンスは、「完全に一致するリード」と呼ばれるか、又は「クラスＰ」と表される。
２．リファレンスシーケンス中の領域は、リードを生成するシーケンシング装置がいずれの塩基（又はヌクレオチド）も呼び出せなかった位置の数によってのみ決定されるミスマッチのタイプ及び数を有するシーケンスリードと一致することが見出される。そのようなタイプのミスマッチは、未定義のヌクレオチド塩基を示すために使用される文字、「Ｎ」によって表される。この文書では、このタイプのミスマッチを「ｎタイプ」のミスマッチと呼ぶ。そのようなシーケンスは「クラスＮ」リードに属する。リードが「クラスＮ」に属すると分類されると、一致の不正確さの程度を所定の上限に制限し、有効な一致と見なされるものとそうでないものとの間に境界を設定することが有用である。したがって、クラスＮに割り当てられたリードはまた、リードが含むことができる未定義の塩基（すなわち「Ｎ」と呼ばれる塩基）の最大数を定義する閾値（ＭＡＸＮ）を設定することによって制約される。そのような分類は、クラスＮに属するすべてのリードが対応するリファレンスシーケンスを参照したときに共有する必要最小マッチング精度（又は最大ミスマッチ度）を暗黙的に定義し、これは選択データ検索を圧縮データに適用するための有用な基準を構成する。
３．リファレンスシーケンス中の領域は、リードを生成するシーケンシング装置が存在するならば（すなわち「ｎタイプ」）、いずれのヌクレオチド塩基も呼び出せなかった位置の数によって決定されるタイプ及びミスマッチのタイプと数を有するシーケンスリードと一致すること、リファレンスに存在するものとは異なる塩基が呼び出されたミスマッチの数をプラスすることを検出する。「置換」として示されるようなタイプのミスマッチはまた、一塩基変異（ＳＮＶ）又は一塩基多型（ＳＮＰ）とも呼ばれる。この文書では、このタイプのミスマッチは「sタイプ」のミスマッチとも呼ばれる。次いで、シーケンスリードを「Ｍミスマッチリード」と呼び、そして「クラスＭ」に割り当てる。「クラスＮ」の場合と同様に、「クラスＭ」に属するすべてのリードについても、一致の不正確さの程度を所定の上限に制限し、有効な一致と見なされるものとそうではないものとの境界を設定すると便利である。したがって、クラスＭに割り当てられたリードは、１つは「ｎタイプ」の不一致数「ｎ」（存在する場合）、もう１つは置換数「ｓ」（ＭＡＸＳ）である、閾値のセットを定義することによっても制約される。第３の制約は、数値「ｎ」と「ｓ」の両方の関数ｆ（ｎ、ｓ）によって定義される閾値である。そのような第３の制約は、任意の意味のある選択的アクセス基準に従ってマッチングの不正確さの上限を有するクラスを生成することを可能にする。例えば、限定としてではなく、「クラス  Ｍ」に属するリードに対して認められる、ｆ（ｎ、ｓ）は、（ｎ＋ｓ）１／２又は（ｎ＋ｓ）、あるいは最大マッチング不正確レベルに境界を設定する以下のように任意の線形の式又は非線形の式とすることができる。このような境界は、一方のタイプ又はもう一方のタイプに適用された単純閾値を超える「ｎ型」ミスマッチの数と「ｓ型」（置換）ミスマッチの数との任意の可能な組み合わせにさらなる境界を設定することを可能にするので、様々な目的でシーケンスリードを分析するときに所望の選択データ検索を圧縮データに適用するための非常に有用な基準を構成する。
【０１０７】
第４のクラスは、「挿入」、「欠失」（「インデル」）及び「クリップド」の間のいずれかのタイプの少なくとも１つのミスマッチ、さらに存在する場合はクラスＮ又はＭに属する任意のミスマッチタイプを示すシーケンスリードによって構成される。「Ｉミスマッチリード」と呼ばれ、「クラスＩ」に割り当てられる。挿入は、リファレンスには存在しないがリードシーケンスには存在する１つ以上のヌクレオチドのさらなるシーケンスによって構成される。この文書では、このタイプのミスマッチを「ｉタイプ」ミスマッチと呼ぶ。挿入されたシーケンスがシーケンスの端にある場合、この文献では「ソフトクリップ」とも呼ばれる（すなわち、ヌクレオチドはリファレンスと一致しないが、廃棄される「ハードクリップ」ヌクレオチドとは対照的に整列されたリードに保持される）。この文書では、このタイプのミスマッチを「ｃタイプ」のミスマッチと呼ぶ。欠失は、リファレンスに関してリードにおける「穴」（欠けているヌクレオチド）である。この文書では、このタイプのミスマッチを「ｄタイプ」ミスマッチと呼ぶ。クラス「Ｎ」及び「Ｍ」の場合と同様に、マッチングの不正確さに対する制限を定義することは可能であり適切である。「クラスＩ」に対する制約のセットの定義は、「クラスＭ」に対して使用されたのと同じ原理に基づいており、そして最後の表の行の表１に報告されている。クラスＩデータに許容される各タイプのミスマッチについての閾値に加えて、さらなる制約は、ミスマッチの数「ｎ」、「ｓ」、「ｄ」、「ｉ」及び「ｃ」、「ｗ（ｎ、ｓ、ｄ、ｉ、ｃ）」の任意の関数によって決定される閾値によって定義される。そのような追加の制約は、任意の意味のあるユーザ定義の選択的アクセス基準に従って、マッチングの不正確さの上限を有するクラスを生成することを可能にする。例えば、限定としてではなく、ｗ（ｎ、ｓ、ｄ、ｉ、ｃ）は、（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）１／５又は（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）又は「クラスＩ」に属するリードについて認められる最大ミスマッチ不正確レベルに境界を設定する任意の線形又は非線形の式であり得る。このような境界は、許容されるミスマッチの各タイプに適用される単純な閾値を超えて、「クラスＩ」のリードで許容されるミスマッチの数のあらゆる可能な組み合わせに対してさらなる境界を設定することを可能にするので、様々な目的のためのシーケンスリードを分析するときに所望の選択的データ検索を圧縮データに適用するための非常に有用な基準を構成する。
【０１０８】
５．第５のクラスは、リファレンスを参照するときに、各データクラスについて、有効と見なされる（すなわち、表１に規定される最大マッチング不正確さに対する上限を定義するマッチングルールのセットを満たさない）いかなるマッピングも検出されない全てのリードを含む。シーケンスそのようなシーケンスは、リファレンスシーケンスを指すときに「マッピングされていない」と言われ、「クラスＵ」に属すると分類される。
【０１０９】
マッチングルールに従ったリードペアの分類
前のセクションで指定された分類は、単一シーケンスのリードに関するものである。２つのリードが可変長の未知のシーケンスで区切られていることがわかっている、ペアでリードを生成するシーケンステクノロジ（例：Ｉｌｌｕｍｉｎａ  Ｉｎｃ．）の場合は、ペア全体を単一のデータクラスに分類することを検討するのが適切である。互いに結合されているリードは、その「メイト」と呼ばれる。
【０１１０】
両方の対のリードが同じクラスに属する場合、全ペアのクラスへの割り当ては明らかであり、全ペアが任意のクラス（すなわちＰ、Ｎ、Ｍ、Ｉ、Ｕ）に対して同じクラスに割り当てられる。２つのリードが異なるクラスに属しているが、どちらも「クラスＵ」に属していない場合、ペア全体が次の式に従って定義された最高の優先順位を持つクラスに割り当てられる。
Ｐ＜Ｎ＜Ｍ＜Ｉ
ここで、「クラスＰ」が最も低い優先順位を持ち、「クラスＩ」が最も高い優先順位を持つ。
【０１１１】
リードのうちの１つのみが「クラスＵ」に属し、そのメイトがクラスＰ、Ｎ、Ｍのいずれかである場合、第６のクラスは「ハーフマップ」を表す「クラスＨＭ」として定義される。
【０１１２】
そのような特定のクラスのリードの定義は、それがリファレンスゲノムに存在するギャップ又は未知の領域（別名、ほとんど知られていない又は未知の領域）を決定することを試みるために使用されるという事実によって動機付けられる。そのような領域は、既知の領域にマッピングすることができるペアリードを使用して、エッジでペアをマッピングすることによって再構成される。次に、図３２に示すように、マッピングされていないメイトを使用して、未知の領域のいわゆる「コンティグ」を構築する。したがって、そのようなタイプのリードペアのみへの選択的アクセスを提供するデータは、最先端のソリューションを使用して完全に検査する必要があると思われる大量のデータセットによって生成されたデータの効率的な処理を可能にする関連したコンピュータの負荷を低減する。
【０１１３】
以下の表は、各リードが属するデータのクラスを定義するためにリードに適用されるマッチングルールをまとめる。ルールは、ミスマッチのタイプ（ｎ、ｓ、ｄ、ｉ、及びｃタイプのミスマッチ）の有無によって、表の最初の５列に定義される。第６列は、各ミスマッチタイプ及び可能なミスマッチタイプの任意の関数ｆ（ｎ、ｓ、ｄ、ｉ、ｃ）に対する最大閾値に関するルールを提供する。
【表１】
2020500383.tif 000003
表１．本発明の開示において定義されるデータクラスに分類されるために、各シーケンスリードが満たすべきミスマッチのタイプ及び制約のセット。
【０１１４】
ゲノムシーケンスリードとリファレンスシーケンスの圧縮表示
ゲノムシーケンスリード圧縮に対する効率的なアプローチの共通要素は、リファレンスシーケンスに対するシーケンスデータの相関関係の利用である。たとえヒト集団の体性プロファイルが非常に多様化したとしても、人によって異なるヌクレオチドの数の実際の部分は全ゲノムを構成するヌクレオチドの総数の約０．１％にすぎない。したがって、各個体を特徴付ける特定のゲノム情報は、全ゲノムによってもたらされる全情報に関して非常に限られている。以前のシーケンシングのため、又は公表された「平均的」コンセンサスリファレンスとしての既存のリファレンスゲノムが利用可能である場合、実際の情報をコード化する最も効率的な方法は、リファレンスゲノムに関する差異のみを識別しコード化することである。
【０１１５】
ＦＡＳＴＱデータの形態の生シーケンスリードを用いてそうするために、利用可能なリファレンスゲノム上にマッピングする予備的前処理工程が行われる。リファレンスゲノムが利用できない場合、又は特定のリファレンスの使用によって導入された偏りが望ましくない場合、利用可能なシーケンスリードをより長いシーケンスに組み立てることによる新しいリファレンスシーケンスの構築は可能な代替法である。
【０１１６】
シーケンスリードが既存の又は構築されたリファレンスシーケンスに関してマッピングされている場合、各シーケンスリードは、本開示において「リード記述子」又は単に「記述子」として示されるいくつかの要素によって完全に表すことができる。
【０１１７】
例えば、リファレンスシーケンスのセグメントと完全に一致するシーケンスリードの場合、シーケンスリードを表すのに必要な記述子の唯一のサブセットは、リファレンス上のマッピング位置の座標（通常はシーケンスの左端の塩基のマッピング位置の座標）、シーケンスリードの長さ自体、及びリードがリファレンスシーケンス鎖に対して直接又はリバースＤＮＡ鎖にマッピングされているかどうかを示す情報により構成される。
【０１１８】
シーケンスリードのすべての塩基がリファレンスシーケンスのすべての塩基と一致するマッピング位置を見つけることができない場合、最小数のミスマッチを有するマッピング（又はマッピング）が保持される。そのような場合、マッピング位置と最小数又は最小数に近いミスマッチとの対応で起こり得る置換、挿入、削除、及びクリップされた塩基も表現するために、異なるサブセットの記述子が必要とされる。記述子のそのようなサブセットを用いて、記述子によってもたらされる情報及びリファレンスシーケンスによってもたらされる情報を使用して、シーケンスリードを再構成することができる。
【０１１９】
マッピングプロセスは、複数の可能なマッピング位置と関連スコア、マッピングの質、スプライスリードの指定、ペアに属するリードの２つの異なるリファレンス（通常は染色体）へのマッピング、シークエンシング処理特徴（ＰＣＲ又は光学的複製）のような他のタイプの情報も生成することができる。全てのそのような情報は各サブセットを拡張する特定の追加の記述子を必要とし、それは次に記述子の各サブセットに対して適切なエントロピーコード化アルゴリズムを適用することによって圧縮される。
【０１２０】
ゲノムシークエンシング処理は、以下の理由により、リード重複（すなわち、同じゲノムシーケンスの２つ以上の正確なコピー）を生成し得る。
・ゲノムシークエンシングプロセスの化学的性質（ポリメラーゼ連鎖反応複製）、
・データ取得プロセス（光学的複製）。ペアのリードが両方とも同じタイル上にあり、リード間の距離が実験に応じて所定の構成パラメーターより小さい場合、リードは光複製と呼ばれる。
【０１２１】
したがって、各リード又はリードペアは、マッピングプロセスの結果に従って、特定の記述子のサブセットによって一意的に表すことができる。
【０１２２】
ＳＡＭ及びＣＲＡＭなどの一般的に使用される手法は、それらのマッピング情報を表すのに必要とされる記述子の特定のサブセットに従ってリード又はリードペアをコード化しない。ＳＡＭ及びＣＲＡＭは、それらがマッピングされているリファレンスシーケンスに関してそれらが含むミスマッチの数及びタイプに従ってシーケンスリードをデータクラスに分類しない。さらに、これらのフォーマットは、単一のデータクラスに属するシーケンスリードのみを圧縮形式で含むアクセスユニットにシーケンスリードを別々にコード化しない。ペアで生成されたシーケンスリードの場合、最新の手法では、リファレンスシーケンスに対するそれらのマッピング精度に従ってクラスに分割された単一の要素としてそれらをコード化しない。そのような最先端の手法は、以下の制限及び欠点によって特徴付けられる。
１．リファレンスシーケンスに対するマッピング結果に従ってシーケンスリードを別々のデータクラスに分類せず、独自の記述子のスーパーセットを使用せずにリード又はリードペアをコード化することは、不十分な圧縮性能をもたらす非効率的な手法である。
２．リードペアを別々のシーケンスリードとしてコード化することは、同じ情報をもたらすいくつかの記述子の複製を必要とし、従って非効率的でありそして劣った圧縮性能をもたらす。
３．このプロセスはおそらく次世代シーケンシング（ＮＧＳ）技術の場合のように非常に大きくなり得る全データセットにおいて力ずくのシーケンシャルサーチを必要とするので、リードペアを再構成するのに必要な情報の検索は複雑で非効率的になる。
４．特定のゲノム領域にマッピングされたリード又はリードペアへの選択的アクセスは、すべてのリード又はリードペアが検索されることを保証するためにデータセット全体を検索する必要がある。
【０１２３】
単一のサブセットの記述子を用いてリードペアをコード化するとき、以下の技術的利点が当業者に明らかである。
１．明らかに冗長である、両方のリードに共通の情報は、ペアを単一要素としてコード化することによって複製されない（例えば、リードペア識別子、マッピング距離、マッピングリファレンス識別子、ＳＡＭファイルフォーマットの特定のフラグによって現在コード化される様々なマッピング品質情報）。
２．相互ペアリング情報（すなわち、どのリードが現在のリードのメイトであるかを提供する情報）の検索は簡単であり、さらなる処理を必要としない。逆に、最先端の手法では、全データ量を解析する必要があるかもしれない。
【０１２４】
シーケンシングデータの特定の部分への効率的な選択的アクセスを可能にし、それらをデジタルデータネットワーク上で輸送することを可能にするために、リファレンスに対して整列されたシーケンスリードを表すために使用される記述子のセットはアクセスユニット（ＡＵ）と呼ばれる論理的に別々の独立したデータブロックで構成される。各アクセスユニットは、単一のデータクラスの圧縮表現のみを含み、他のアクセスユニットとは無関係に、又はマッピングに使用されるリファレンスシーケンス領域のコード化表現をもたらすアクセスユニットのみを使用して復号化することができる。これにより、選択的アクセスと順序外転送機能を可能にする。
【０１２５】
圧縮効率を向上させるために、本発明は、同じリファレンスシーケンス上にマッピングされた両方の対を有する各リードペアについて「マッピングリファレンス識別子」記述子を指定する必要性を排除する。各アクセスユニットには、同じリファレンスにマッピングされているリード又はペアのみを含めることができる。そのような解決策を使用すると、リファレンスシーケンス識別子を表す記述子は、各アクセスユニット又はアクセスユニットのセットごとに一度だけコード化される必要がある（及び、ＳＡＭ／ＢＡＭフォーマットで現在行われているように各リードに対して繰り返されない）。
【０１２６】
上記で表現された規則の唯一の例外は、異なるリファレンスシーケンス（例えば、染色体）上にマッピングされた２つのリードを有するリードペアの場合である。この場合、ペアは分割され、そして２つのリードは２つの別々のゲノムレコードとしてコード化され、そして各コード化されたリードはそのペアがマッピングされるリファレンスシーケンスの識別子を含む。
【０１２７】
同種の統計的性質を有する要素のグループに情報を分類することは、異種のデータセットに適用される汎用コンプレッサ（例えばＬＺタイプのアルゴリズム）の使用に関してより良い圧縮性能を提供することを当業者は知っている。結果として、ゲノムシーケンスリードを記述子の特定のサブセットを用いてペアとしてコード化する場合、各個別の記述子のサブセットを特徴付けるエントロピーがより低く、リードペアを再構成及び検索するときの処理効率が高いため、より高い圧縮が達成される。
【０１２８】
シーケンスリード記述子
このセクションでは、リファレンスシーケンスにマッピングされたゲノムシーケンスリードを表すために指定された記述子を紹介する。各リード又はリードペアを表すために使用される記述子の特定のサブセットは、リファレンスシーケンスに対するマッピングの結果（すなわち、リード又はリードペアとリファレンスシーケンスとの間のミスマッチの有無）に依存する。
【０１２９】
位置
リード又はリードペアの位置は、リード又はリードペアの左端の塩基のリファレンスシーケンス上のマッピング位置として定義される。「位置」タイプの記述子は、各リード又はリードペアごとに必要である。「位置」記述子の値は、次のとおりである。
・リファレンスシーケンス上のリード又はリードペアの左端の塩基の座標の値
・又は同じアクセスユニット内でコード化された前のリード又はリードペアの座標に関する差。
【０１３０】
「位置」記述子は、各コード化されたリード又はリードペアを表すために必要である。
【０１３１】
本発明の開示において、そのような記述子はｐｏｓ記述子と呼ばれる。
【０１３２】
ペアリング
リードペアの場合、各リードがペア内のそのメイトとどのように関連付けられているかを表す記述子は、次のように複数の構文要素で表すことができる。
・メイト内のそれぞれの塩基と、リードの塩基（例えば、メイト内の最も左にマッピングされた塩基との間にある最も左にマッピングされた塩基）との座標の差。本発明の開示において、そのような記述子はペア記述子と呼ばれる。
・メイトがマッピングするリファレンスシーケンスの識別子を用いたリファレンスシーケンス上のメイトの絶対座標。そのような表現オプションは次の場合に使用される。
○ペアの２つのリードが異なるリファレンスシーケンス（例：染色体）にマッピングされている、又は
○ペアの２つのリードが同じリファレンスにマッピングされているが、許容ペアリング距離のような最大値として指定された値を超える塩基数で区切られている場合。
【０１３３】
本発明の開示において、そのような記述子はａｂｓｐａｉｒ記述子と呼ばれる。メイトが異なるリファレンスシーケンスにマッピングされている場合、リファレンスシーケンスを識別する記述子はｒｅｆｉｄと呼ばれる。
・ペアのリードの場合にリードをそのメイトから分離するコード化されたリードの数。本発明の開示において、そのような記述子は、ｐｃｏｕｎｔ記述子と呼ばれる。
【０１３４】
リード長
可変長のリードの場合、リードあたりの記述子を使用して、リードを構成するヌクレオチドの数として表される長さを表す。明らかに、可変長リード長の場合には、リードごとにリード長記述子が必要である。
本開示では、この記述子は、ｒｌｅｎ記述子とも呼ばれる。
【０１３５】
リバースコンプリメント
アデニン（「Ａ」）はチミン（「Ｔ」）とのみ結合し、シトシン（「Ｃ」）はグアニン（「Ｇ」）と結合するだけなので、ＤＮＡは各鎖が他方の相補鎖である二重らせんによって構成される。したがって、もう一方のヌクレオチド組成を知るためには、一方の鎖を表すだけで十分である。これが、リファレンスシーケンスが常に単一のシーケンスによって表される理由であり、マッピングツールは両方の鎖に属するリードについてマッピング位置を見つけることができる。リードがＤＮＡヘリックスの相補鎖にマッピングされる場合、それは「リバースコンプリメント」であると言われる。記述子は、そのような情報をもたらすために必要であり、オリジナルのリードが、それがマッピングされるリファレンスシーケンスのリバースコンプリメントであるかどうかを示す情報をもたらす。
リバースコンプリメント記述子は、リードごとに必要である。
本開示では、そのような記述子は、ｒｃｏｍｐ記述子とも呼ばれる。
【０１３６】
未知の塩基の位置
シーケンシング処理の間に、装置は、リード又はリードを構成するリードの所与の位置にある塩基を呼び出すことができないことが起こり得る。そのようなイベントは、対応するリード位置にある特定の記号「Ｎ」によって識別される。したがって、リード位置中の記号「Ｎ」の発生を識別する記述子が必要である。
記述子は以下を表すことができる。
・リファレンスシーケンスの座標として表される、ペアのリード又はリードにおける「Ｎ」記号の絶対位置、又は
・同じリード又はペアのリードにおける前の「Ｎ」の相対位置。
【０１３７】
本開示では、そのような記述子は、ｎｍｉｓ記述子とも呼ばれる。
【０１３８】
位置とタイプの不一致
リファレンスシーケンスにマッピングされたシーケンスリードは、それらがマッピングされているリファレンスシーケンスセグメントに関してミスマッチを提示することがある。これらのミスマッチは分類され得、そして以下の場合に従って置換、欠失又は挿入として示される。
・リファレンスシーケンスに関して異なるヌクレオチド（塩基）の存在（置換）
・マッピングされたリードにヌクレオチドがない（欠失）
・リファレンスに含まれていないヌクレオチドがリード中に存在する（挿入）
【０１３９】
各不一致タイプの表現は、１つはリード又はリードペアの不一致位置（ｍｍｐｏｓとも呼ばれる）、もう１つは置換のみが存在する場合の不一致のタイプ（サブタイプとも呼ばれる）、もう１つは、置換、挿入、及び削除が存在する場合のミスマッチのタイプを表す（ｍｍｔｙｐｅとも呼ばれる）、３つの記述子の使用を意味する。
【０１４０】
ソフトクリップ
リファレンスシーケンス上にマッピングされたゲノムシーケンスリードは、マッピング位置でリファレンスシーケンス上に存在するヌクレオチドシーケンスのいずれにも一致しないヌクレオチドシーケンスのそれらのエッジ部分に存在し得る。これらのシーケンス部分はソフトクリップと呼ばれ、シーケンス部分の塩基を表す一連の記号によって単純に構成される記述子によって表すことができる。
リードの開始時及び／又は終了時に、リードで許可されるソフトクリップは１つ又は２つのみである。
この文書では、そのような記述子はｓｃｌｉｐｓ記述子とも呼ばれる。
【０１４１】
マッピングフラグ
マッピングフラグは、次のような整列プロセスに関する特定の情報を伝えるために使用される。
・リード又はリードペアに対する複数のマッピング位置の存在
・スプライスリードの存在
・ＰＣＲ（ポリメラーゼ連鎖反応）又は光学的複製の存在
・補助アラインメント（アライナが同じリード又はリードペアに対して複数の可能なマッピング位置を生成した場合に使用）
・リードが品質チェックに不合格となる（すなわち、シーケンシング処理の品質を測定するための技術ベンダ固有の手順）。
この文書では、そのような記述子はフラグ記述子とも呼ばれる。
【０１４２】
マッピングされていないリード
リードがリファレンスシーケンスのどの位置にもマッピングされていない場合、リードはマッピングされていないとして分類される。そのような場合、マッピングされていないリードはすべて、いくつかの共通の特性に従ってグループ化される。このプロセスは「クラスタリング」と呼ばれる。同じ特性を共有するリードのグループはクラスタと呼ばれる。本発明の開示を通して、同じクラスタに属するシーケンスリードの間で共有される特徴はクラスタシグネチャ又はシグネチャと呼ばれる。
【０１４３】
シグネチャは、２から数千までの任意の数のヌクレオチドで構成することができ、シグネチャはすべてのクラスタに対して固定長又は可変長のいずれかを持つことができる。シグネチャに属することができる記号のアルファベットは、処理されているシーケンスリードを生成するために配列決定された特定のゲノムサンプルに依存する。一例として、しかし限定としてではなく、以下のアルファベットを使用することができる。
・ＤＮＡ用
○｛Ａ、Ｇ、Ｃ、Ｔ、Ｎ｝
○｛Ａ、Ｇ、Ｃ、Ｔ、Ｒ、Ｙ、Ｓ、Ｗ、Ｋ、Ｍ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎ、．、−｝（ｌＵＰＡＣ表記）
・ＲＮＡ用
○｛Ａ、Ｇ、Ｃ、Ｕ、Ｎ｝
○｛Ａ、Ｇ、Ｃ、Ｕ、Ｒ、Ｙ、Ｓ、Ｗ、Ｋ、Ｍ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎ、．、−｝（ｌＵＰＡＣ表記）
・アミノ酸用
○｛Ａ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｋ、Ｌ、Ｍ、Ｎ、Ｐ、Ｑ、Ｒ、Ｓ、Ｔ、Ｖ、Ｗ、Ｙ｝
【０１４４】
クラスタシグネチャを計算するために使用されるアルファベットのタイプは、本開示で説明されるゲノムデータセットヘッダと呼ばれるデータ構造によってもたらされるパラメータＡｌｐｈａｂｅｔ＿ＩＤによって識別される。
【０１４５】
同じゲノムデータセットに属するクラスタのシグネチャは、固定長又は可変長であり得る。ゲノムデータセットのヘッダにコード化されたグローバルパラメータは、シグネチャの長さが固定か可変かを示すために使用される。シグネチャ長が固定の場合、第２のグローバルパラメータはクラスタシグネチャのシンボル単位の長さを表す。可変シグニチャ長の場合、この値は０である。マッピングされていないリードの各クラスタは、１つ以上のアクセスユニットにコーディングされる。
【０１４６】
ミスマッチのないリード又はリードペアのコード化
リード又はリードペアがリファレンスシーケンスに完全にマッピングされる場合（すなわち、ミスマッチがない場合）、リード及び関連マッピング情報を再構成するために、以下の記述子のサブセットが必要とされる。
・リード又はリードペアごとの位置記述子（ｐｏｓ）
・リードごとに１つ、又はリードペアごとに２つのリバースコンプリメント記述子（ｒｃｏｍｐ）
・リードごとの長さ記述子（可変長リード専用の場合）（ｒｌｅｎ）
・リードペア（ペア）ごとのペアリング記述子
・マッピングフラグ（｛ｆｌａｇｓ）のセット
【０１４７】
本発明では、そのようなリード又はリードペアはクラスＰに属するものとして分類される。
位置記述子ｐｏｓは、リード又はリードペアの左端のマッピング塩基のリファレンスゲノム上の位置を表す。その使用方法を図５に示す。
リバースコンプリメント記述子ｒｃｏｍｐは、リードがリファレンスシーケンスの直接鎖又は逆鎖のどちらにマッピングされるかを示す。この記述子の意味と構文は、図７と図８に示される。
可変長リードの場合、記述子ｒｌｅｎはリード長をコード化する。
ペア記述子は、ペア全体を再構成するために必要な情報をもたらす。記述子の構文は、図９に示される。
クラスＰに属するリードペアのコード化の例を図１０に提供し、可変長の単一リードの対応する例を図１１に提供する。
【０１４８】
未知の塩基によってのみ表されるミスマッチを有するリード又はリードペアのコード化
リード又はリードペアがリファレンスシーケンスにマッピングするが、少なくとも１つの未知の塩基を含む場合、リード及び関連マッピング情報を再構成するために、以下の記述子のサブセットが必要とされる。
・リード又はリードペアごとのポジション記述子｛ｐｏｓ）
・リードごとに１つ、又はリードペアごとに２つのリバースコンプリメント記述子｛ｒｃｏｍｐ）
・未知の塩基ごとの位置｛ｎｍｉｓ）
・リードごとの長さ記述子（可変長リード専用の場合）｛ｒｌｅｎ）
・リードペアごとのペアリング記述子（ｐａｉｒ）
・マッピングフラグ（ｆｌａｇｓ）のセット
【０１４９】
クラスＰサブセットにすでに存在する記述子は、同じ構文と動作を有する。追加の記述子ｎｍｉｓは、シーケンシング処理によって「未知」と呼ばれる塩基（記号「Ｎ」）のリード（ペア）における位置を提供する。
本発明では、そのようなリード又はリードペアはクラスＮに属するものとして分類される。
クラスＮのリードペアのコード化の一例を図１２に提供する。
【０１５０】
未知の塩基及び置換を有するリード又はリードペアのコード化
リード又はリードペアがリファレンスシーケンスにマッピングし、少なくとも１つの置換を示すが欠失又は挿入を示さない場合、リード及び関連マッピング情報を再構成するために、以下の記述子のサブセットが必要とされる。
・リード又はリードペアごとの位置記述子（ｐｏｓ）
・リードごとに１つ、又はリードペアごとに２つのリバースコンプリメント記述子（ｒｃｏｍｐ）
・置換位置ごとの記述子（ｍｍｐｏｓ）
・置換タイプ（サブタイプ）ごとの記述子
・未知の塩基ごとの位置（ｎｍｉｓ）
・リードごとの長さ記述子（可変長リード専用の場合）（ｒｌｅｎ）
・リードペア（ペア）ごとのペアリング記述子
・マッピングフラグ（ｆｌａｇｓ）のセット
【０１５１】
クラスＰサブセットにすでに存在する記述子は、同じ構文と意味を有する。このようなシーケンスリードデータクラスに使用される追加の記述子は、置換の位置を表すｍｍｐｏｓと置換のタイプを表すサブタイプである。
このタイプのリードペアのコード化の例を図１３に示す。
本発明の開示において、そのようなリード又はリードペアはクラスＭに属すると言われる。
【０１５２】
少なくとも１つの挿入、削除、又はソフトクリップを使用したリード又はリードペアのコード化
リード又はリードペアが少なくとも１つの挿入欠失又はソフトクリップを有するリファレンスシーケンスにマッピングするとき、以下の記述子のサブセットが定義される。
・リード又はリードペアごとの位置記述子（ｐｏｓ）
・リードごとに１つ、又はリードペアごとに２つのリバースコンプリメント記述子（ｒｃｏｍｐ）
・ミスマッチの位置（挿入、削除、置換）ごとの記述子（ｍｍｐｏｓ）
・ミスマッチのタイプ（挿入、削除、置換）ごとの記述子（ｍｍｔｙｐｅ）
・ソフトクリップ（スクリップ）のシーケンスごとの記述子
・未知の塩基ごとの位置（ｎｍｉｓ）
・リードごとの長さ記述子（可変長リード専用の場合）（ｒｌｅｎ）
・リードペア（ペア）ごとのペアリング記述子
・マッピングフラグ｛ｆｌａｇｓ）のセット
【０１５３】
クラスＭサブセットにすでに存在する記述子は、同じ構文と意味を有する。この場合に使用される追加の記述子は、置換、挿入及び削除の位置を表すｍｍｐｏｓ、ミスマッチのタイプを表すｍｍｔｙｐｅ（置換、挿入又は削除）、及びソフトクリップされた塩基を表すｓｃｌｉｐｓである。
本発明の開示において、そのようなリード又はリードペアはクラスＩに属すると言われる。クラスＩに属するリードペアのコード化の例が図１４に提供される。
【０１５４】
リファレンスシーケンスに１つのリードのみがマッピングされているリードペア
リードペアが（クラスＰ、Ｎ、Ｍ、又はＩのいずれかに属する）マッピングされているリード及びマッピングされていないリードによって構成されている場合、そのペアはクラスＨＭ（Ｈａｌｆ  Ｍａｐｐｅｄ）と呼ばれる別のクラスに属するものとして分類される。
リファレンスシーケンス上にマッピングされたリードは、上述のクラス（Ｐ、Ｎ、Ｍ、Ｉ）のいずれでもよく、各クラスについて既に説明した記述子のサブセットを使用してコード化される。マッピングされていないリードは、適切なエントロピーコーダを使用してそれを表す記号の文字列を圧縮することによってコード化される。
【０１５５】
マッピングされていないリード又はリードペアのコード化と「内部」リファレンスの作成
クラスＵに属するリード又はクラスＨＭに属するリードペアのマッピングされていないメイトは、指定されたマッチング精度の制約を満たす「既存の」リファレンスシーケンスにマッピングすることはできない。本発明は、これらのデータクラスに属するリードを整列及び圧縮するために使用されるべき１つ以上の「内部」リファレンスシーケンスを構築するための方法を開示する。
制限としてではなく、例えば適切な「内部」リファレンスを構築するためのいくつかのアプローチが可能である。
・マッピングされていないリードを、少なくとも最小サイズ（シグネチャ）の共通の連続ゲノムシーケンスを共有するリードを含むクラスタに分割すること。図２４に示すように、各クラスタはそのシグネチャによって一意的に識別できる。
・任意の意味のある順序（例えば、辞書順）でのリードのソート、及び最後のＮ番目のリードの、Ｎ＋１番目のコード化のための「内部」リファレンスとしての使用。この方法を図２５に示す。
・指定されたマッチング精度の制約又は新しい制約のセットに従って前記クラスに属する全てのリード又は関連するリードのサブセットを整列及びコード化することができるように、クラスＵのリードのサブセットに対していわゆる「デノボアセンブリ」を実行する。
【０１５６】
指定されたマッチング精度制約のセットを満たす「内部」リファレンスにコーディングされているリードをマッピングできる場合、圧縮後にリードを再構成するために必要な情報は、次のタイプの構文要素を使用してコーディングされる。
１．内部リファレンス（ｐｏｓ記述子）内のリード番号に関して、内部リファレンス上の一致部分の開始位置。この位置は、以前にコード化されたリードに関して絶対値又は微分値としてコード化することができる。
２．内部リファレンス（ペア記述子）内の対応するリードの先頭からの開始位置のオフセット。例えば。リード長が固定の場合、実際の位置はｐｏｓ*ｌｅｎｇｔｈ＋ｐａｉｒである。
３．ミスマッチ位置（ｓｎｐｐ記述子）及びタイプ（ｓｎｐｔ記述子）としてコーディングされた、可能なミスマッチの存在
４．内部リファレンスと一致しない（又は一致するが、定義済みの閾値を超えるミスマッチの数が多い）リードの部分（通常はｐａｉｒで識別されるエッジ）は、ｉｎｄｃ記述子にコード化される。図２６に示すように、ｉｎｄｃ記述子にコード化されたミスマッチのエントロピーを減らすために、使用されている内部リファレンスの一部のエッジに対してパディング操作を実行できる。最も適切なパディングの戦略は、処理中のゲノムデータの統計的特性にしたがってコード化することにより選択することができる。考えられるパディング戦略は次のとおりである。
ａ．パディングなし
ｂ．現在コード化データの頻度に応じて選択された固定のパディングパターン
ｃ．最新のＮ個のコード化されたリードに関して定義された現在のコンテキストの統計的特性に従った可変パディングパターン
特定のタイプのパディングストラテジーは、ｉｎｄｃ記述子ストリームヘッダーの特別な値によって通知される。
５．リードが、内部の自己生成、外部、又はリファレンスなし（ｒｔｙｐｅ記述子）のいずれを使用してコード化されているかを示すフラグ
６．逐語的にコード化されているリード（ｕｒｅａｄｓ記述子）。
【０１５７】
図２６は、そのようなコーディング手順の例を提供する。
【０１５８】
図２７は、ｐｏｓ＋ｐａｉｒ構文要素が符号付きｐｏｓに置き換えられている場合の、内部リファレンス上のマッピングされていないリードの代替コード化を示す。この場合、ｐｏｓは、リファレンスシーケンス上の位置に関して、リードｎ−１の最も左のヌクレオチドの位置に対するリードｎの最も左のヌクレオチド位置の距離を表す。
クラスＵのリードが可変長を示す場合、ｎ個の追加の記述子ｒｌｅｎが各リード長を格納するために使用される。
このコーディング手法は、リードごとにＮ個の開始位置をサポートするように拡張することができ、それによってリードを２つ以上の基準位置にわたって分割することができる。これは、シーケンシング技術においてループによって生成される繰り返しパターンを通常示す非常に長いリード（５０Ｋ＋塩基）を生成し、それらのシーケンシング技術（例えば、Ｐａｃｉｆｉｃ  Ｂｉｏｓｃｉｅｎｃｅからの）によって生成されるリードをコード化するのに特に有用であり得る。同じアプローチを同様に使用して、ほとんど又は全く重複することなくゲノムの２つの異なる部分に整列するリードとして定義されるキメラシーケンスリードをコードすることができる。
上記のアプローチは、単純なクラスＵ以外にも明確に適用でき、リード位置に関連する構文要素を含むすべてのストリーム（ｐｏｓストリーム）に適用できる。
【０１５９】
複数のマッピング位置を持つペアのリードとリード
リファレンスシーケンスの複数の座標にマッピングされている１つ以上のリードペアの場合は、コード化されたデータレコードを複製することによるＳＡＭ又はＣＲＡＭのような最先端の手法、及び冗長性が導入されているため、圧縮効率が明らかに低下することになるデータ内の散乱を生じる随意的なフィールドのアドホックな追加によってサポートされる。さらに、１つのリードがそれぞれのメイトの複数のマッピング位置に対にされるペアエンドリードのいくつかのマッピング構成は、ユーザ定義のオプションフィールドによってのみサポートされる。リファレンスシーケンス上で適切なマッピングを見つけるために２つ以上のサブシーケンスに分割される必要があるリード及びリードペアの表現についても同じことが言える。そのようなアプローチの主な結果は、データの再利用性に大きな影響を及ぼし、ある部分表現から別の部分表現に渡すときの情報の損失と共に、非効率的な表現の増殖である。
本開示に記載された方法は、複数のマッピング位置及びスプライスされたリードの両方の表現をサポートし、圧縮及び圧縮データのアクセス可能性の両方に関して、既存の解決策よりもはるかに効率的である。より良い圧縮は、均質な統計的性質を有する記述子と適切なコンテキストを有する異なるエントロピーコーダとをグループ化する可能性によって提供される。より良いファイルアクセシビリティは、コード化された情報全体を解凍してアクセスする必要なしに、特定のタイプのゲノムデータの解凍及び検索を可能にするインデックスメカニズムの定義によって提供される。例えば、本開示に記載されている発明は、スプライスされたリードの有無にかかわらず複数のマッピング位置を有するシーケンスリード又はリードペアの検索を可能にするインデックス付けメカニズムを提供する。これは、ＳＡＭ及びＣＲＡＭのような最先端のゲノム情報表示フォーマットでは現在不可能である。
複数のアライメントを持つリードペアをコード化する場合、ＳＡＭとＣＲＡＭは、他のリードのシングルアライメントに関連付けられたペアで、あるリードの複数アライメントの表現をサポートする可能性がない。当業者は、これがＲＮＡ＿ｓｅｑ及びＣｈｌＰ＿ｓｅｑなどの実験において頻繁に見られるケースであり、そして今日、ＳＡＭ及びＣＲＡＭは、ペアにおけるリードのマルチプルアラインメント間のカップリングのすべての可能な組み合わせをサポートする方法を有さない。本開示において提案される解決策は、ハイスループットシーケンシング（ＨＴＳ）装置によって生成されたゲノムデータにおいて今日見出される全ての可能な構成をサポートすることができる。
【０１６０】
ゲノムシーケンスリードをリファレンスシーケンスにマッピングするとき、以下の結果が考えられる。
１．確立された制約に従ってリファレンスシーケンスの単一領域にリードをマッピングする。この場合、マッピングは「一意的」であると言われる、
２．リードは、リファレンスシーケンスの２つ以上のゲノム領域に完全に一致する、
３．多数の可能なマッピング位置が位置合わせツールによって報告される。各マッピングはそれぞれの領域からの編集距離が異なるが、アライナはそれらのすべてが有効であると見なす。アライナは通常、完全に実装に依存する方法で各アライメントにスコアを割り当てる。割り当てられたスコアによると、「一次」アライメントには通常フラグが立てられる。アライメントが他のものとまったく同じ編集距離と同じミスマッチを示す可能性がある。
【０１６１】
ケース１は、アライメントの一意性がコード化されていることを単に要求する。
ケース２は、すべてのマッピングが等しい可能性であるため、「一次」又は「二次」アライメントが存在しないことを認識する必要がある。コード化される唯一の追加情報は、すべてのマッピング位置のベクトルである。
ケース３は、全てのマッピング位置がコード化されたリードのアレイとしてコード化されることを要求する。本発明に開示されているすべての必要な記述子は必要なときにマッピング位置ごとに複製されなければならない。マッピング位置が異なれば、リファレンスに関してさまざまなレベルのエラー（置換、インデル、切り捨てられた塩基）を示すことがある。
【０１６２】
スプライスリード
スプライスされたリードは、リファレンスシーケンス上の適切なマッピング領域を見つけるために２つ以上のサブリードに分割される必要があるシーケンスリードとして定義される。この場合、サブリード間の距離（「ジャンクション」と呼ばれる）は通常、欠失と見なすには大きすぎる。スプライスされたリードのマッピングは、リファレンスシーケンスの直接鎖又はリバース鎖を指すことができ、したがって、「絶対鎖」と呼ばれるこの情報は保存されそしてコード化されなければならない。
【０１６３】
スプライスされたリードのコード化は各スプライスのマッピング位置の保存を必要とし、それは可変長リードとして考慮されなければならず、固定長リードのみを含むゲノムデータセットにコード化される。
【０１６４】
マルチプルアライメントとスプライスリードの記述子
以下の説明において、テンプレートという用語はＳＡＭの明細書におけるように使用され、その一部がシーケンシング装置で配列決定されるか、又は生シーケンスから組み立てられるヌクレオチドシーケンスを識別する。使用されるシーケンシング技術によれば、鋳型の配列決定は、単一のヌクレオチドシーケンス（１回のリード）又は「ペア」と言われる２つの配列のいずれかを生成することができる。これに関連して、セグメントは連続したシーケンス又はサブシーケンスとして定義される。
【０１６５】
複数のアライメント位置を使用してリード又はリードペアをコード化する場合、コード化されたデータによって伝達される情報は次のとおりである。
・テンプレート内の各セグメントのすべてのマッピング位置（例：Ｒｅａｄ１とＲｅａｄ２）
・テンプレートに対する任意の一次マッピングの存在（すなわち、リード１及びリード２）。
【０１６６】
本発明の開示では、複数のマッピング位置及びスプライスされたリードのコーディングは以下によってサポートされる。
１．コード化データセットのレベルで定義され、データセットを構成するすべてのアクセスユニットに有効な２つのグローバルフラグ：
・ｍａ：設定すると、データセット内に複数のアライメントが存在することを示す。
・ｓｒ：設定すると、データセット内にスプライスリードが存在することを示す。
２．以下の記述子：
・ｍｍａｐ記述子は、ペアのリード又は左端のリードがいくつの位置に配置されたかを示すために使用され、最初の数字（Ｎ）は、単一のセグメントとしてのリード（ｓｒ  ｆｌａｇ＝０の場合）、又は複数の可能なアライメントのためにリードがスプライスされたすべてのセグメントを指す。Ｎの値は、このレコードのテンプレートに対してｐｏｓ記述子の値がいくつコーディングされているかを示す。スプライスがない場合及びスプライスがある場合について以下に説明するように、Ｎの後に１つ以上の数Ｍiが続く。
・スプライス記述子は、スプライスアライメントの場合に使用される。現在のレコードの各スプライスをいくつの塩基で構成するかを示す長さのリストである。各リードの長さは（固定リード長の場合はグローバルリード長さから、又は可変長リードの場合はｌｅｎ記述子から）既知であるため、この記述子は、アライメントごとに各セグメントに使用されたセグメント数を計算するためにデコーダによって使用される。
・ｍｍｓｃｏｒｅ記述子は、アライメントごとのスコアの値とプライマリアライメントの指標を提供する。スコアは、整列ツールによって各特定のマッピング構成に割り当てられた信頼性のレベルを示す。通常は浮動小数点値を想定する。例えば、一次アライメント（すなわち、最良の候補と考えられるもの）は、最も高いスコアを有するものであり得る。
・ｍｍｓｃ記述子は、プライマリアライメントのマッピングの同じ連続性を保持しない代替セカンダリアライメントをサポートする（最も一般的な例は、ＣＩＧＡＲ文字列にｉｎｄｅｌが含まれ、プライマリシーケンスにＭのみが含まれる場合である）。この場合、一次アラインメントと他のアラインメントとの間の隣接性の違いをコード化する必要がある。
【０１６７】
スプライスのないマルチプルアラインメント
データセットにスプライスが存在しない場合、グローバルのｓｒフラグは設定されず、ｓｐｌｅｎ記述子は使用されない。ペアエンドシーケンスでは、ｍｍａｐ記述子は、ｉが１から最初の（一番左の）リードアライメントの数（Ｎ1）までとなる、１つ以上の数（Ｍi）が続く１つの値Ｎで構成される。そのリードにスプライスが存在しない場合、Ｎ1＝Ｎである。スプライスされているかどうかにかかわらず、最初のリードアライメントごとに、１つの値Ｍiを使用して２番目のリードのアライメントに使用されるセグメント数（この場合はアライメント数）、最初のリードのアライメントのためにコーディングされるためのペア記述子の数を示す。
Ｍの値は、２回目のリードのアライメント数を示すＰ＝Σ＝１を計算するために使用され
ます。
この方法は図１７に示される。
【０１６８】
Ｍi＝０の特別な値は、一番左のリードのｉ番目のアライメントが、最も左のリードのｋ番目のアライメントとすでにペアになっている最も右のリードのアライメントとをペアであることを、ｋ＜ｉ（新しいアライメントは検出されず、これは上記の式と一致する）示す。
例として、最も単純なケースでは：
１．左端のリードに単一の位置合わせがあり、右端に２つの代替の位置合わせがある場合、Ｎは１の値を想定し、Ｍiは２の値を想定する。
２．左端のリードに対して２つの代替アライメントが検出され、右端のリードに対して１つのみが検出された場合、Ｎは２、Ｍiは１、Ｍ2は０と見なされる。
Ｍiが０に等しいとき、ペア記述子の関連する値は既存の第２のリードアラインメントを指す。
【０１６９】
図１７は、スプライスのないマルチプルアラインメントの場合のＮ、Ｐ、及びＭの意味を示し、図１８は、ｐｏｓ、ペア、及びｍｍａｐ記述子がマルチプルアラインメント情報をコード化するためにどのように使用されるかを示す。
【０１７０】
スプライスとのマルチプルアライメント
スプライスリードの場合は、ｓｐｌｅｎ記述子が使用される。Ｎ＋Ｐ値のシーケンスの各レコードに対して構成される。最初のＮ個の値は、単一のリード又はの最初の（例えば、最も左の）リードのペアの各整列されたセグメントの長さを示す。以下のＰ値は、ペアエンドシーケンシングの場合、２番目のリードの各整列セグメントの長さを示す。Ｐは、
【数１】
2020500383.tif 000004
で計算される。ここで、Ｍiの各値は、テンプレート全体のアライメントを構成するために、最初のリードの個々のアライメントに適用される。
レコードのｓｐｌｅｎ記述子の最初のＮ個の値により、Ｎｉの計算が可能になる。これは、最初のリードのアライメントの数を表す。Ｎ1＝Ｎの場合、最初のリードに対してスプライスは存在しない。
次のレコードのＳｐｌｅｎ記述子のＰ値により、Ｎ2の計算が可能にする。これは、２番目のリードのアライメント数を示す。Ｎ2＝Ｐの場合、２番目のリードにはスプライスが存在しない。
【０１７１】
定義されたｍｍａｐ及びｓｐｌｅｎ記述子は、いくつのリード又はリードペアが複数のマッピングを表すか、及びいくつのセグメントが各リード又はリードペアマッピングを構成しているかを一意的に識別することを可能にする。これを図１９と図２０に示す。
【０１７２】
アライメントスコア
ｍｍｓｃｏｒｅ記述子は、アライメントのマッピングスコアをシグナリングすることを可能にする。シングルエンドシーケンスでは、テンプレートごとにＮ1値があり、ペアエンドシーケンスでは、テンプレート全体のアライメントごとに値がある。言い換えれば、リード１の１つのアライメントとリード２の１つのアライメントによって構成されるすべてのペアが、関連するスコアを持つことができる。ペアエンドリードの場合、合計スコア数は次のように計算される。
Ｎ．スコア＝ＭＡＸ（Ｎ1，Ｎ2）＋Ｍ0
ここで、Ｎ1はリード１の合計アライメント数、Ｎ2はリード２の合計アライメント数、Ｍの数は０である。
シングルリードの場合、スコア数はＮ1に等しい。
【０１７３】
スプライス記述子のないマルチプルアライメント
以下の表は、スプライスされたリードのないマルチプルアラインメントの場合における本発明の開示において定義されたｍｍａｐ及びｍｍｓｃｏｒｅ記述子の使用の意味及び効果を要約している。
【表２】
2020500383.tif 000005
【０１７４】
スプライス記述子があるマルチプルアライメント
以下の表は、スプライス記述子があるマルチプルアライメントの場合の本発明の開示に定義されたｍｍａｐ及びｍｍｓｃｏｒｅ記述子の使用の意味と効果をまとめる。
【表３】
2020500383.tif 000006
【０１７５】
異なる染色体上のマルチプルアライメント
アライメントプロセスが、一次マッピングが配置されているものとは別のリファレンスシーケンスへの代替マッピングを見つけることが起こり得る。
この場合、アプリケーションに関しては、テンプレートの代替マッピングが複数コーディングされている２つ以上の必然的に異なるアクセスユニット間の（ランダムアクセスの複雑さに関して）高速リンクを維持することが最も重要である。
独自に整列されたリードペアについて、本発明の開示は、ペア中の２つのリードが異なる染色体上にマッピングされる場合のキメラアラインメントを表すために使用される、ペアと名付けられた記述子を定義する。この記述子は、リファレンスと、同じテンプレートに対するさらなるアライメントを含む次のレコードの位置を通知するために使用できる。これを図３０に示す。
【０１７６】
ペア内の一番左のリードのための１つ以上のアライメントが現在コード化されているＡＵに関連するものとは異なるリファレンスシーケンス上に存在する場合、ペア記述子の予約値が使用される（ユニークなアラインメントの場合、別のリファレンスに提示されるアラインメントに用いられるものと同じではない）。予約値の後には、次のＡＵに含まれるすべてのものの中で最も左側のアライメントのリファレンス及び位置（すなわち、そのレコードに対するｐｏｓ記述子の最初の復号化値）が続く。
【０１７７】
挿入、削除、マッピングされていない部分を含む複数のアライメント
場合によっては、複数のアラインメントが、一致及び不一致の塩基、挿入、欠失及びソフトクリップの異なる構成を提示することがある。例えば、一次アラインメントが一致又はミスマッチ塩基のみを有し、したがってそれが連続したヌクレオチドシーケンスとしてマッピングされる一方で、二次アラインメントが挿入、欠失、ソフトクリップ又はスプライスを提示することは稀ではない。本開示を通して、マッピングされたリードが挿入を含まない場合、欠失又はクリップされた塩基はマッピング隣接性を有すると言われる。本発明の開示は、二次アラインメントが一次アラインメントの同じマッピング隣接（Ｐ、Ｍ又はＮの場合のように）を保持するか否か（Ｉ、Ｕ、スプライス）をシグナリングする第３の記述子を定義する。この記述子、ｍｍｓｃ（マルチマッピングサブクラス用）は、原則として、アライメントごとのフラグにすぎない。ｍｍｓｃが設定されている場合は、マッピングされていないヌクレオチドを表す追加の記号「Ｕ」で拡張され、その後にマッピングされていないヌクレオチドの文字列が続く、アライナによって生成されたＳＡＭシガー文字列の逐語表現が続きく。図３１は、この記述子の使用例を示す。この記述子の構文は次のとおりである。
・すべての線形が同じマッピング隣接を共有する場合、単一の値が存在し、０に設定されます（Ｎ＝０）。
・少なくとも１つのセカンダリアライメントでマッピングの連続性が維持されない場合、記述子は次のように構成される。
○最初の値Ｎ＞０は、いくつセカンダリアライメントがマッピングの連続性を維持しないかを示す。
○次に、マッピングの連続性を維持しないで、次の要素を２次アライメントごとにＮ回繰り返す。
○１つの値は、マッピングの連続性を維持しないセカンダリアライメントに関連するペアリング値を示す。
○次の値は、ペアのどのリードがマッピングの連続性を維持しないかを示す。
○次の値は、マッピングの連続性を維持しないでリードのマッピング特性を表すシガー文字列を含む。
○シガー文字列がシンボル「Ｓ」を含む場合にのみ存在する任意の１つのフィールドは、クリップされたヌクレオチドの逐語的文字列を含む。
【０１７８】
リファレンスシーケンス記述子
リファレンスシーケンスは一般に、対応する生物学的試料中に見出すことができるヌクレオチドを表す一連の記号として表される。ＤＮＡの場合、ヌクレオチドは４であり、記号Ａ、Ｃ、Ｇ及びＴによって表される。ＲＮＡの場合、ＴはＵによって置換される。５番目の記号は、実験によって要求された信頼度に従ってヌクレオチドのタイプを決定することができなかった、シーケンシング装置がシーケンス中の座標を表すために付加される。本発明の開示では、リファレンスシーケンスは、完全に１つのアクセスユニットにコード化することも、２つ以上のサブシーケンスに分割することもできる。
エントロピーコード化されるリファレンスシーケンス又はサブシーケンスを表すために使用される記述子は、それぞれのアルファベットの許容されたシンボルに関するシーケンス又はサブシーケンスの逐語的表現である。
【０１７９】
ソースモデル、エントロピーコーダ、及びコーディングモード
本発明に開示されたゲノムデータ構造の各データクラス、サブクラス及び関連する記述子ストリームについて、各ストリームによってもたらされるデータ又はメタデータの特定の特徴及びその統計的性質に従って、異なるコード化アルゴリズムを採用することができる。「コード化アルゴリズム」は、記述子ストリームの特定の「ソースモデル」と特定の「エントロピーコーダ」との関連付けとして意図されなければならない。特定の「ソースモデル」は、ソースエントロピーの最小化に関してデータの最も効率的なコード化を得るために特定され選択され得る。エントロピーコーダの選択は、コード化効率の考慮事項及び／又は確率分布の特徴、ならびに関連する実装の問題によって促進され得る。「コード化モード」とも呼ばれる特定の「コード化アルゴリズム」の各選択は、データセット全体のデータクラス又はサブクラスに関連する全体の「記述子ストリーム」に適用することができ、又は異なる「コード化モード」は、アクセスユニットに分割された記述子の各部分に適用される。
コーディングモードに関連付けられている各「ソースモデル」は、次のような特徴がある。
・各ソースによって発行された構文要素の定義（すなわち、位置の読み取り、ペアリング情報の読み取り、表２で定義されたリファレンスシーケンスに対するミスマッチなどのデータのクラスを表すのに使用される記述子のセット）。
・関連する確率モデルの定義
・関連するエントロピーコーダの定義
【０１８０】
さらなる利点
定義されたデータクラス及びサブクラスへのシーケンスデータの分類は、単一の別々のデータソース（例えば距離、位置など）によって構文要素のシーケンスをモデル化することによって特徴付けられるより低い情報ソースエントロピーを利用する効率的なコーディングモードの実施を可能にする。
本発明の他の利点は、関心のあるタイプのデータのサブセットのみにアクセスすることが可能であることである。例えば、ゲノム学における最も重要な用途の１つは、リファレンス（ＳＮＶ）又は集団（ＳＮＰ）に対するゲノムサンプルの差異を見出すことにある。今日、そのようなタイプの分析は完全なシーケンスリードの処理を必要とするが、本発明により開示されたデータ表現を採用することにより、ミスマッチはすでに１〜３のデータクラスのみに分離される（「ｎタイプ」及び「ｉタイプ」ミスマッチとも考えられる利益に依存する）。さらなる利点は、新しいアライメントを取得するために、新しいリファレンスシーケンスが公開されるとき、又は既にマッピングされたものに対して再マッピングが実行されるときに、特定の「外部」リファレンスシーケンスを参照して圧縮されたデータ及びメタデータから別の異なる「外部」リファレンスシーケンスへの効率的なトランスコーディングを実行できることである（別のマッピングアルゴリズムを使用するなど）。
【０１８１】
図２８は、本発明の原理によるコード化装置２８７を示す。コード化装置２８７は、例えばゲノムシーケンシング装置２８０によって生成された生シーケンスデータ２８９を入力として受け取る。ゲノムシーケンシング装置２８０は、Ｉｌｌｕｍｉｎａ  ＨｉＳｅｑ  ２５００、Ｔｈｅｒｍｏ  Ｆｉｓｈｅｒ  Ｉｏｎ  Ｔｏｒｒｅｎｔデバイス又はＯｘｆｏｒｄ  Ｎａｎｏｐｏｒｅ  ＭｉｎｌＯＮのように当該技術分野において既知である。生シーケンスデータ２８９はアライナユニット２８１に供給され、アライナユニット２８１はリードをリファレンスシーケンス２８２０に整列させることによってコード化のためのシーケンスを準備する。あるいは、専用モジュール２８２を使用して利用可能なリードからリファレンスシーケンスを生成することができる。このドキュメントの「クラスＵのマッピングされていないリード用の内部リファレンスの構築」及び「クラスＨＭ」のセクションで説明されている方法基準発生器２８２によって処理された後、リードは得られたより長いシーケンス上にマッピングすることができる。次いで、整列されたシーケンスはデータ分類モジュール２８４によって分類される。データクラス２８８は次に記述子エンコーダ２８５〜２８７に供給される。次いで、ゲノム記述子ストリーム２８１１は、レイヤによって運ばれるデータ又はメタデータの統計的特性に従ってレイヤをコード化する算術エンコーダ２８１２〜２８１４に供給される。結果は１つ以上のゲノムストリーム２８１５である。
【０１８２】
図２９は、本開示の原理による復号化装置２９８を示す。復号化装置２９８は、ネットワーク又は記憶素子から多重化ゲノムビットストリーム２９１０を受け取る。多重化ゲノムビットストリーム２９１０は、デマルチプレクサ２９０に供給され、エントロピーデコーダ２９２〜２９４に供給される個別のゲノムビットストリーム２９１を生成し、ゲノム記述子ストリーム２９５を生成する。抽出されたゲノム記述子ストリームは、記述子デコーダ２９６〜２９７に供給される。記述子をさらにシーケンスリードのクラスに復号化する。クラスデコーダ２９９は、ゲノム記述子２９１１及び変換されたリファレンス２９１４をさらに処理し、その結果をマージしてシーケンスの圧縮されていないリードを生成し、次いでこれを当技術分野で公知のフォーマット、例えばテキストファイル又はｚｉｐ圧縮ファイル又はＦＡＳＴＱ又はＳＡＭ／ＢＡＭファイルにさらに格納できる。
クラスデコーダ２９９は、１つ以上のゲノムビットストリームによって運ばれる元のリファレンスシーケンスに関する情報を活用することによって元のゲノムシーケンスを再構成することができる。リファレンスシーケンスがゲノムストリームによって輸送されない場合、それらは復号化側で利用可能でなければならず、クラスデコーダによってアクセス可能でなければならない。
本明細書に開示されている本発明の技術は、ハードウェア、ソフトウェア、ファームウェア又はそれらの任意の組み合わせで実施することができる。ソフトウェアで実施されるとき、これらはコンピュータ媒体に格納され、ハードウェア処理装置によって実行されてもよい。ハードウェア処理ユニットは、１つ以上のプロセッサ、デジタル信号プロセッサ、汎用マイクロプロセッサ、特定用途向け集積回路、又は他の個別論理回路を備えることができる。
本開示の技法は、携帯電話、デスクトップコンピュータ、サーバ、タブレット及び類似の装置を含む様々な装置又は装置において実施することができる。
【０１８３】
アクセスユニットのタイプ
本発明の開示を通して、データクラスに分類され、圧縮層又は非圧縮層に構造化されたゲノムデータは、上で定義されたように異なるアクセスユニットに編成される。アクセスユニットは次のように区別される。
・それらが保有するゲノムデータ及びデータセットの性質及びそれらにアクセスすることができる方法を特徴付ける、タイプ、
・同じタイプに属するアクセスユニットに固有の順序を提供する順番。
【０１８４】
あらゆるタイプのアクセスユニットは、さらに異なる「カテゴリ」に分類できる。
以下に、異なるタイプのゲノムアクセスユニットの定義の非網羅的リストを示す。
１）タイプ０のアクセスユニットは、アクセス又は復号化及びアクセスされるために他のアクセスユニットから来る情報を参照する必要はない。データ又はそれらが含むデータセットによってもたらされる全情報は、復号化装置又は処理アプリケーションによって独立して読み取られ、処理されることができる。例として、しかし限定としてではなく、タイプ0のアクセスユニットは、染色体又は全リファレンスゲノム又はその一部のようなコード化されたリファレンスシーケンスをもたらすに使用され得る。
２）タイプ１のアクセスユニットは、タイプ０のアクセスユニットによってもたらされるデータを参照するデータを含む。
タイプ１のアクセスユニットに含まれるデータのリード又は復号化及び処理は、タイプ０の１つ以上のアクセスユニットにアクセスすることを必要とする。タイプ１のアクセスユニットは「クラスＰ」のシーケンスリードに関連するゲノムデータをコード化する。
３）タイプ２のアクセスユニットは、タイプ０のアクセスユニットによって運ばれるデータを参照するデータを含む。
タイプ２のアクセスユニットに含まれるデータのリード又は復号化及び処理は、タイプ０の１つ以上のアクセスユニットへのアクセスを必要とする。タイプ２のアクセスユニットは、「クラスＮ」のシーケンスリードに関連するゲノムデータをコード化する。
４）タイプ３のアクセスユニットは、タイプ０のアクセスユニットによってもたらされるデータを参照するデータを含む。
タイプ３のアクセスユニットに含まれるデータのリード又は復号化及び処理は、タイプ０の１つ以上のアクセスユニットへのアクセスを必要とする。タイプ３のアクセスユニットは、「クラスＭ」のシーケンスリードに関連するゲノムデータをコード化する。
５）タイプ４のアクセスユニットは、タイプ０のアクセスユニットによって運ばれるデータを参照するデータを含む。
タイプ４のアクセスユニットに含まれるデータのリード又は復号化及び処理は、タイプ０の１つ以上のアクセスユニットへのアクセスを必要とする。タイプ４のアクセスユニットは、「クラスＩ」のシーケンスリードに関連するゲノムデータをコード化する。
６）タイプ５のアクセスユニットは、利用可能なリファレンスシーケンス（「クラスＵ」）にマッピングすることができないリードを含み、再構成された内部リファレンスシーケンスを使用した。タイプ５のアクセスユニットは、タイプ０のアクセスユニットによってもたらされるデータを参照するデータを含む。タイプ５のアクセスユニットに含まれるデータのリード又は復号化及び処理は、タイプ０の１つ以上のアクセスユニットへのアクセスを必要とする。
７）タイプ６のアクセスユニットはリードペアを含み、一方のリードは４つのクラスＰ、Ｎ、Ｍ、Ｉのいずれにも属することができ、他方は利用可能なリファレンスシーケンス（「クラスＨＭ」）にマッピングできない。タイプ６のアクセスユニットは、タイプ０のアクセスユニットによってもたらされるデータを参照するデータを含む。タイプ６のアクセスユニットに含まれるデータのリード又は復号化及び処理は、タイプ０の１つ以上のアクセスユニットへのアクセスを必要とする。
８）タイプ７のアクセスユニットは、タイプ１のアクセスユニットに含まれるデータ又はデータセットに関連するメタデータ（例えば、品質スコア）及び／又は注釈データを含む。タイプ７のアクセスユニットは、異なる層に分類及びラベル付けされてもよい。
９）タイプ８のアクセスユニットは、注釈データとして分類されたデータ又はデータセットを含む。タイプ８のアクセスユニットは、層に分類されラベル付けされてもよい。
１０）追加のタイプのアクセスユニットは、ここで説明されている構造とメカニズムを拡張することができる。例として、しかし限定としてではなく、ゲノム変異体の呼び出し、構造的及び機能的分析の結果は、新しいタイプのアクセスユニットにコード化することができる。本明細書に記載されているアクセスユニット内のデータ編成は、アクセスユニット内にカプセル化されるいかなるタイプのデータを妨げるものではなく、コード化データの性質に関して完全に透明なメカニズムである。
【０１８５】
タイプ０のアクセスユニットは順序付けられている（例えば番号付けされている）が、それらは順序付けられた方法で格納及び／又は送信される必要はない（技術的利点：並列処理／並列ストリーミング、多重化）。
タイプ１、２、３、４、５及び６のアクセスユニットは、順序付けされる必要はなく、順序付けられた方法で格納及び／又は送信される必要もない（技術的利点：並列処理／並列ストリーミング）。
【０１８６】
図２２は、アクセスユニットが、ヘッダと、一つ以上の同種データのストリームとによってどのように構成されるかを示す。各ストリームは1つ以上のブロックで構成できる。各ブロックはいくつかのパケットを含み、リード位置、ペアリング情報、リバースコンプリメント情報、位置とタイプのミスマッチなどを示すパケットは上で紹介した記述子の構造化シーケンスである。
各アクセスユニットは各ブロック内に異なる数のパケットを持つことができるが、アクセスユニット内ではすべてのブロックは同じ数のパケットを持つ。
各データパケットは、３つの識別子ＸＹＺの組み合わせによって識別できる。
・Ｘは、それが属するアクセスユニットを識別する。
・Ｙは、それが属するブロック（すなわちそれがカプセル化するデータ型）を識別する。
・Ｚは、同じブロック内の他のパケットに対するパケットの順序を表す識別子である。図２３は、アクセスユニットとパケットラベリングの例を示す。ここで、ＡＵ＿Ｔ＿Ｎは、アクセスユニットのタイプに従った順番の通知を意味してもよく、意味しなくてもよい識別子Ｎを有するＴタイプのアクセスユニットである。識別子は、もたらされるゲノムデータを完全に解読するのに必要とされるあるタイプのアクセスユニットを他のタイプのアクセスユニットと一意的に関連付けるために使用される。
任意のタイプのアクセスユニットは、異なる順序付けプロセスに従って異なる「カテゴリ」にさらに分類及びラベル付けすることができる。例えば、限定としてではなく、分類及びラベリングは、
異なる時間に同じ生物を配列決定する（アクセスユニットは「時間的」含意を有するゲノム情報を含む）、
２．同一生物の異なる性質の臓器の試料（例えば、ヒト試料については皮膚、血液、髪）を配列決定する。これらは「生物学的」意味を持つアクセスユニットである。
【０１８７】
データ保存モード
コード化された記述子を記憶媒体に記憶するとき、２つは本発明の開示に記載されている手法である。
１．アクセスユニット連続（ＡＵＣ）モード
２．記述子ストリーム連続（ＤＳＣ）モード
ＡＵＣが適用されるとき、同じアクセスユニットに属する（しかし異なる記述子ストリーム）コード化データブロックは記憶媒体の隣接領域に格納される。
ＡＵＣモードは、データストレージに関して２つの異なる方法で実装できる。
ａ）記憶媒体上に隣接して記憶されたアクセスユニットの順序がクラスに基づくことができる、すなわち同じクラスのすべてのアクセスユニット（Ｃｌａｓｓ＿ＩＤ）が記憶媒体内に連続して記憶されるクラスの連続（ＣＣ）。
ｂ）リファレンス単位ベースのアクセスユニット、すなわち同じＡＵ＿ＩＤを有するすべてのアクセスユニットの順序（すなわち、同じゲノム領域へのマッピング）が連続して格納されているゲノム領域の連続（ＧＲＣ）。
【０１８８】
ＡＵＣ／ＣＣモード方法は、単一クラスのデータにアクセスするときにより効率的である。ＡＵＣ／ＧＲＣモードは、同じゲノム領域にマッピングされている任意のクラスのデータにアクセスするときにより効率的である。本開示に記載される発明及び関連する構文は、すべてのモードのＤＳＣ、ＡＵＣ／ＣＣ及びＡＵＣ／ＧＲＣ方法をサポートし、所望の選択的アクセス性能に従って任意のモードを選択する自由をエンコーダに残す。ＡＵＣ／ＣＣモード又はＡＵＣ／ＧＲＣモードが使用される場合、表２に列挙されるように、ゲノムデータセットヘッダによってもたらされるＣＣ＿Ｍｏｄｅ＿Ｆｌａｇという名前のフラグによって通知される。
ＤＳＣが適用されると、同じ記述子ストリームに属するブロックは記憶媒体の隣接領域に記憶される。ゲノムデータは実際には、エントロピーエンコーディングの観点から均質なデータを表す、（１つ以上のブロックで構成された）記述子ストリームごとに編成される。
コード化方法の間にゲノムデータセットで使用される記憶代替は、表２にリストされるようにゲノムデータセットヘッダに記憶されたＢｌｏｃｋ＿Ｈｅａｄｅｒ＿Ｆｌａｇと呼ばれるフラグによって合図される。
ＡＵＣモードとＤＳＣモードとの間の違いが図２１に示されており、そこではアクセスユニットは、垂直方向にデータブロックＢｎ＿ｍにコードされた記述子のタイプを識別する記述子＿ＩＤを、水平方向にアクセスユニットＩＤを有する座標系で構築される。データブロックＢｎ＿ｍは、アクセスユニットｍに対するタイプ（すなわち識別子）ｎのコード化された記述子を含む。
【０１８９】
効率的な選択的アクセスのための圧縮ゲノムデータのインデックス付け
本開示では、位置合わせされたデータの特定の領域への選択的アクセスをサポートするために、２つのデータ構造、すなわちグローバルパラメータをもたらすゲノムデータセットヘッダ、及びコード化及び復号化処理中に使用されるマスタインデックステーブル（ＭＩＴ）と呼ばれるインデックスツールが説明される。ゲノムデータセットヘッダの構文は表２に提供され、マスタインデックステーブルの構文は表３に提供される。
【０１９０】
ゲノムデータセットヘッダ
ゲノムデータセットヘッダは、コード化されたゲノム情報を操作するためにエンコーダ及びデコーダによって使用されるグローバルパラメータをもたらすデータ構造である。
ゲノムデータセットヘッダに含まれる情報には、次のものがある。
・各データセットグループを一意的に識別するために使用されるデータセットグループ識別子、
・各データセットを一意的に識別するために使用されるゲノムデータセット識別子、
・データセットが準拠しているデータフォーマット仕様を識別するために使用されるブランド識別子。
・データセットが準拠しているデータフォーマット仕様を識別するために使用されるマイナーバージョン番号、
・固定長のリードをシグナルするために使用されるヌクレオチド中のコード化ゲノムリードの長さ、
・ペアエンドリードの存在を通知するフラグ
・ブロックヘッダの存在を通知するフラグ、
・どのＡＵコード化モードがデータセットＡＵＣ／ＣＣ又はＡＵＣ／ＧＲＣで使用されるかを通知するフラグ、
・リファレンスシーケンスに関してシーケンスリードのミスマッチをコードするために使用されるアルファベットのタイプ、
・データセットをコード化するために使用されたリファレンスシーケンスの数、
・各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの数値識別子、
・各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの文字列識別子、
・各リファレンスシーケンスに関連するアクセスユニットを数えるために使用される、リファレンスシーケンスあたりのコード化されたアクセスユニットの数、
・整列されたリード、整列されていないリード、マッピングされていないリード及びリファレンスシーケンスを区別するために使用されるコード化ゲノムデータのタイプ、
・データセットにコーディングされているデータクラスの数、
・復号化プロセス中に使用されるデータセット内でコード化されたデータクラスごとに使用される記述子の数、
・コード化されたマッピングされていないリードを索引付けするために使用されたクラスタの総数、
・コード化されたクラスタシグネチャを復号化するのに使用されるクラスタシグネチャをコード化するのに使用される整数値を表すのに使用されるビット数、
・すべてのクラスタシグネチャがヌクレオチドの数に関しての同じ長さを有するかを通知するフラグ
・クラスタシグネチャの長さ。
【０１９１】
ゲノムデータセットヘッダの各要素の構文及び意味は、以下の表２に列挙されている。
【表４】
2020500383.tif 000007
2020500383.tif 000008
表２．ゲノムデータセットヘッダの構文
【０１９２】
マスタインデックステーブル
マスタインデックステーブル（ＭＩＴ）と呼ばれるインデックス作成ツールが本発明に開示されている。
マスタインデックステーブル（ＭＩＴ）は、次の要素を含む多次元シーケンスに基づく・リファレンスシーケンスに関して、異なる記述子ストリームからのブロックのセットとして、アクセスユニットに含まれるすべてのリード又はリードペアの一次アライメントの中で最も左の一致する塩基のヌクレオチド数としての位置。これは、表３のStart_AU_Ref_Position[Sequence_ID][Class_ID][AU_ID]によって表される。
・リファレンスシーケンスに関して、異なる記述子ストリームからのブロックのセットとして、アクセスユニットに含まれるすべてのリード又はリードペアの一次アラインメントの中で最も右の一致する塩基のヌクレオチドの数としての位置。これは、表３のEnd_AU_Ref_Position[Sequence_ID][Class_ID][AU_ID]によって表される。
【０１９３】
各リファレンスシーケンスに関してコード化された各Ｃｌａｓｓの各ＡＵを構成する記述子の各コード化されたブロックの最初のバイトのバイトオフセット。オフセットは、データセットペイロードの最初のバイト（０からは始まる）を基準にして計算される。ブロックが空で（１）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 set）、ＭＩＴは、各記述子ストリームのサイズをバイト単位で含む。ブロックヘッダが存在しない場合（Block_Header_Flag unset）、ＭＩＴは各アクセスユニットのサイズをバイト単位で含む。
【０１９５】
２つのコード化された方法の間の代替は、表２のBlock_Header_Flagと呼ばれるフラグによって通知される。
【表５】
2020500383.tif 000009
2020500383.tif 000010
2020500383.tif 000011
表３−マスタインデックステーブル
【０１９６】
マスタインデックステーブルと複数のアライメント
マルチプルアラインメントが存在する場合、上で紹介したＭＩＴは、アクセスユニットにコード化されたリード又はリードペアのマルチプルアラインメントを考慮に入れるインデックス作成ツールを提供するために複製される。拡張マスタインデックステーブルには、
・リファレンスシーケンスに関して、異なる記述子ストリームからのブロックのセットとしての、アクセスユニットに含まれるすべてのリード又はリードペアのすべてのアラインメントの中で最も左に一致する塩基のヌクレオチド数としての位置。これは、表３のStart_AU_Ref_Position[Sequence_ID][Class_ID][AU_ID]によって表される。
・リファレンスシーケンスに関して、異なる記述子ストリームからのブロックのセットとしての、アクセスユニットに含まれるすべてのリード又はリードペアのすべてのアライメントの中で最も右に一致する塩基の位置（ヌクレオチド数として）。これは、表３のEnd_AU_Ref_Position[Sequence_ID][Class_ID][AU_ID]によって表される。
【図１】
2020500383.tif 000012
【図２】
2020500383.tif 000013
【図３】
2020500383.tif 000014
【図４】
2020500383.tif 000015
【図５】
2020500383.tif 000016
【図６】
2020500383.tif 000017
【図７】
2020500383.tif 000018
【図８】
2020500383.tif 000019
【図９】
2020500383.tif 000020
【図１０】
2020500383.tif 000021
【図１１】
2020500383.tif 000022
【図１２】
2020500383.tif 000023
【図１３】
2020500383.tif 000024
【図１４】
2020500383.tif 000025
【図１５】
2020500383.tif 000026
【図１６】
2020500383.tif 000027
【図１７】
2020500383.tif 000028
【図１８】
2020500383.tif 000029
【図１９】
2020500383.tif 000030
【図２０】
2020500383.tif 000031
【図２１】
2020500383.tif 000032
【図２２】
2020500383.tif 000033
【図２３】
2020500383.tif 000034
【図２４】
2020500383.tif 000035
【図２５】
2020500383.tif 000036
【図２６】
2020500383.tif 000037
【図２７】
2020500383.tif 000038
【図２８】
2020500383.tif 000039
【図２９】
2020500383.tif 000040
【図３０】
2020500383.tif 000041
【図３１】
2020500383.tif 000042
【図３２】
2020500383.tif 000043
【国際調査報告】
2020500383.tif 000044
2020500383.tif 000045
2020500383.tif 000046