(57)【要約】ゲノムシーケンシング装置によって生成されたゲノム配列データのインデックス付けのための方法および装置。提案された方法は、シーケンシング装置によって生成された生シーケンスデータと、特定のマッチング基準に従って何れの参照シーケンスにもマッピングできないそれらのシーケンスリードの両方に適用することができる。 本発明は、ブラウジング及び効率的な選択的なアクセスを可能にするために、整列されていないシーケンスリードを分割及びインデックス付けする方法を説明する。【選択図】図１
2019537172.tif 000002
【特許請求の範囲】
【請求項１】
ゲノムシーケンスデータをコード化するための方法であって、前記ゲノムシーケンスデータはヌクレオチドシーケンスのリードを含み、前記方法が、
・前記リードを、「クラスタシグネチャ」と呼ばれるヌクレオチドの共通シーケンス又は部分シーケンスを共有するリードのクラスタに分割するステップ、
・クラスタ化されたリードを構文要素の多数のブロックとしてコード化するステップ、及び
・ヘッダ情報を用いて前記構文要素のブロックを構造化し、それによって連続的なアクセスユニットを作成するステップ
を含むゲノムシーケンスデータをコード化するための方法。
【請求項２】
前記クラスタシグネチャは、
・サポートされているアルファベットの各ヌクレオチドを一意的な２進法表示に関連付けること、及び
・コード化されたシグネチャを表すビット文字列を得るためにシグネチャ内の各ヌクレオチドの前記２進法表示を連結すること、
によってコード化される、請求項１に記載の方法。
【請求項３】
コード化されたシーケンスリードの各クラスタは前記コード化されたシグネチャによって識別される請求項２に記載の方法。
【請求項４】
前記構文要素のブロックは、請求項２によりコード化され、各クラスタに属するシーケンスリードを表すコード化された構文要素のブロックの記憶媒体上の位置を表す整数値のベクターに関連付けられたクラスタシグネチャを含むマスタインデックステーブルを備える請求項３に記載の方法。
【請求項５】
前記構文要素のブロックが、
・各データセットグループを一意的に識別するために使用されるデータセットグループ識別子、
・各データセットを一意的に識別するために使用されるゲノムデータセット識別子、
・前記データセットが準拠するデータフォーマット仕様を識別するために使用されるブランド識別子、
・データセットが準拠しているデータフォーマット仕様を識別するために使用されるマイナーバージョン番号、
・一定長さのリードを知らせるために使用されるヌクレオチド中のコード化されたゲノムリードの長さ、
・ペアエンドリードの存在を知らせるフラグ、
・ブロックヘッダの存在を知らせるフラグ、
・前記アクセスユニットを復号化するときにデータアクセスを容易にするために、アクセスユニットが記憶媒体に記憶される順序を知らせるフラグ、
・データセットをコード化するために使用されたリファレンスシーケンスの数、
・各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの数値識別子、
・各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの文字列識別子、
・各リファレンスシーケンスに関連するアクセスユニットを数えるために使用される、リファレンスシーケンスごとのコード化されたアクセスユニットの数、
・整列されたリード、整列されていないリード、マッピングされていないリード及びリファレンスシーケンスを区別するために使用されるコード化されたゲノムデータの種類、
・データセットにコード化されているデータクラスの数、
・復号化処理中に使用されるデータセット内でコード化されたデータクラスごとに使用される記述子の数、
・コード化されたマッピングされていないリードにインデックスを付けるために使用されるクラスタの総数、
・コード化されたクラスタシグネチャの復号化に使用されるクラスタシグネチャをコード化するために使用される整数値を表すために使用されるビット数、
・全てのクラスタシグネチャがヌクレオチドの数に関して同じ長さを有するかを知らせるフラグ、
・クラスタシグネチャの長さ
を備えるゲノムデータセットヘッダを含む、請求項４に記載の方法。
【請求項６】
前記ゲノムリードが対になっている、請求項５に記載の方法。
【請求項７】
前記ゲノムデータがエントロピーコード化されている、請求項６に記載の方法。
【請求項８】
・ヘッダ情報を使用することによって複数の構文要素のブロックを抽出するために前記コード化されたゲノムデータを含むアクセスユニットを解析するステップ、
・請求項１によりコード化された生リード、マッピングされていないリード及び整列されていないリードを抽出するために、前記複数の構文要素のブロックを復号化するステップ、
・コード化されたクラスタシグネチャを抽出するためにマスタインデックステーブルを構文解析するステップ、
・シグネチャの各２進法表示に対応するヌクレオチドシーケンスを関連付けることによって前記クラスタシグネチャを復号化するステップ、
・ゲノムデータのコード化された表現を含むアクセスユニットを記憶媒体上で検索するために各シグネチャに関連する整数のベクターを解析するステップ、及び
・ヘッダ情報を使用することによって、アクセスユニットから複数の構文要素のブロックを抽出するステップ
を含む、コード化されたゲノムデータの復号化方法。
【請求項９】
グローバルな設定パラメータを含むゲノムデータセットヘッダを復号化することをさらに備える、請求項８に記載の復号化方法。
【請求項１０】
コード化されたクラスタシグネチャ及びコード化されたブロックオフセットを含むマスタインデックステーブルを復号化することをさらに備える、請求項９に記載の復号化方法。
【請求項１１】
前記ゲノムリードが対になっている、請求項１０に記載の復号化方法。
【請求項１２】
前記ゲノムデータがエントロピー復号化される、請求項１１に記載の復号化方法。
【請求項１３】
生ゲノムシーケンスデータ（１１１）、マッピングされていないゲノムシーケンスデータ（１１１）及び整列されていないゲノムシーケンスデータ（１１１）を圧縮するためのゲノムエンコーダ（１１１５）であって、前記ゲノムシーケンスデータ（１１１）は、ヌクレオチドシーケンスのリードを備え、
・前記ゲノムエンコーダ（１１１５）は、
・クラスタシグネチャと呼ばれるヌクレオチドの共通シーケンス又は部分シーケンスを共有するリードのグループに前記リードを分割し、それによってリードのクラスタ（１１３）及びクラスタシグネチャ（１１４）を作成するように構成されたクラスタリングユニット（１１２）、
・前記クラスタ化されたリードを構文要素のブロックとしてコード化するように構成された、１つ以上の記述子コード化ユニット（１１５）、
・ゲノムアクセスユニット（１１１１）を生成するために、それらの統計的特性に従って構文要素の前記ブロックを圧縮してように構成された、１つ以上のエントロピーコード化ユニット（１１１０）、
・一意的な２進法表示をクラスタシグネチャの各記号に関連付けることによってクラスタシグネチャ（１１４）を２値化するように構成されたシグネチャコード化ユニット（１１６）、
・２値化された前記クラスタシグネチャ（１１７）を、前記ゲノムアクセスユニット（１１１１）に含まれるエントロピーコード化された記述子の記憶媒体上のオフセットを表す整数のベクターに関連付けるように構成されたゲノムデータセットヘッダ及びマスタインデックステーブルジェネレータ（１１９）、及び
・圧縮された前記ゲノムデータ及びメタデータを多重化するためのマルチプレクサ（１１１３）を備えるゲノムエンコーダ（１１１５）。
【請求項１４】
ゲノムシーケンスデータ（１２１）の圧縮のためのゲノムエンコーダ（１２１０）であって、前記ゲノムシーケンスデータ（１２１）は、ヌクレオチドのシーケンスのリードを備え、前記ゲノムエンコーダ（１２１０）は、
・前記リードを１つ以上のリファレンスシーケンスに整列させ、それによって整列させたリードを作成するように構成される、アライナユニット（１２２）、
・１つ以上の既存のリファレンスシーケンス又は構築されたリファレンスシーケンスで、指定されたマッチング規則に従って前記整列されたリードを分類し、それによって整列されたリード（１２８）のクラスを作成するように構成された、データ分類ユニット（１２４）、
・整列されたリードの前記クラスに従って前記構文要素を選択することによって、前記分類された整列されたリードを構文要素のブロックとしてコード化するように構成された、１つ以上の記述子コード化ユニット（１２５〜１２７）、
・ゲノムストリーム（１２１５）を生成するために、それらの統計的特性に従って構文要素の前記ブロックを圧縮するように構成された、１つ以上のエントロピーコード化ユニット（１２１２〜１２１４）、
・、請求項１２に従って構成された、マッピングされていないシーケンスリードコード化ユニット（１１１５）、及び
・圧縮された前記ゲノムデータ及びメタデータを多重化するためのマルチプレクサ（１２１６）を備えるゲノムエンコーダ。
【請求項１５】
請求項２に記載のコード化方法を実行するのに適したコード化手段をさらに備える、請求項１４に記載のゲノムエンコーダ。
【請求項１６】
圧縮したゲノムアクセスユニット（１３４）を解凍するためのゲノムデコーダ（１３１３）であって、前記ゲノムデコーダ（１３１３）は、
・圧縮したゲノムアクセスユニット（１３４）とゲノムデータセットヘッダとマスタインデックステーブル（１３３）を逆多重化するためのデマルチプレクサ（１３２）、
・前記ゲノムデータセットヘッダ及びマスタインデックステーブル（１３３）を解析するように構成された解析手段（１３５）
・コード化されたクラスタシグネチャ（１３７）へ、
・前記コード化されたクラスタシグネチャ（１３７）をクラスタシグネチャ（１３１１）に復号化するように構成されたシグネチャデコーダ（１３９）、
・前記圧縮されたゲノムアクセスユニットを、ゲノム記述子（１３８）と名付けられた構文要素のブロックに解凍するように構成されたエントロピーデコーダ（１３６）、及び
・ゲノム記述子をヌクレオチドシーケンスの圧縮されていないリードに復号化するように構成された、１つ以上の記述子デコーダ（１３１０）、
を備えるゲノムデコーダ。
【請求項１７】
圧縮されたゲノムストリーム（１４１０）を解凍するためのゲノムデコーダ（１４８）であって、前記ゲノムデコーダ（１４８）は、
・圧縮されたゲノムデータ及びメタデータをゲノムビットストリーム（１４１）及びマッピングされていないシーケンスリードのビットストリーム（１４５）に逆多重化するためのデマルチプレクサ（１４０）、
・前記圧縮されたゲノムストリームをゲノム記述子（１４５）と名付けられた構文要素のブロックに解析するように構成されたエントロピーデコーダ（１４２〜１４４）、
・前記ゲノム記述子をヌクレオチドのシーケンスの分類されたリードに復号化するように構成された１つ以上のゲノム記述子デコーダ（１４６〜１４７）、
・ヌクレオチドのシーケンスの圧縮されていないリードを生成するために、１つ以上のリファレンスシーケンス上のヌクレオチドのシーケンスの前記分類されたリードを選択的に復号化するように構成されたゲノムデータクラスデコーダ（１４９）、
・圧縮されていない生シーケンスリード、マッピングされていないシーケンスード及び整列されていないシーケンスリード（１４１４）とクラスタシグネチャ（１４１５）を生成するために、請求項１６により構成されたデコーダ（１３１３）
を備えるゲノムデコーダ（１４８）。
【請求項１８】
実行されると少なくとも１つのプロセッサに請求項２に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項１９】
実行されると少なくとも１つのプロセッサに請求項２に記載のコード化方法を実行させる命令を備えるコンピュータ可読媒体。
【請求項２０】
実行されると少なくとも１つのプロセッサに請求項７に記載の復号方法を実行させる命令を含むコンピュータ可読媒体。
【請求項２１】
請求項１に記載の方法に従ってコード化されたゲノムデータを保存するサポートデータ。
【請求項２２】
請求項２に記載の方法に従ってコード化されたゲノムデータを保存するサポートデータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、選択的アクセス及びパターンマッチングを可能にするためにゲノムシーケンスデータを分割及びインデックスを付ける新規な方法を提供する。開示されたインデックスを付ける方法は、整列されていないシーケンスリードの中から特定のヌクレオチドシーケンスを検索するときに必要な処理能力及びデータアクセス時間を低減する。開示された方法は、
・ゲノムシーケンシング装置によって生成された生のシーケンスデータ、
・指定された一致条件に従ってリードマッピングの処理中に１つ以上のリファレンスシーケンスの何れかの領域でマッピングできないマッピングされていないリード、
・指定された一致条件に従って、シーケンスリードアセンブリ（リファレンスなしのアライメントとも呼ばれる）の処理中に、長いシーケンス（「コンティグ（ｃｏｎｔｉｇｓ）」とも呼ばれる）を形成するために、他のリードと位置合わせできない整列されていないリード
に適用することができる。
【背景技術】
【０００２】
ゲノムシーケンスデータの適切なインデックス付けは、例えば、しかし限定としてではなく、遺伝子の発見などの効率的なゲノム分析適用を可能にするために基本的なことである。遺伝子の発見は、形質又は表現型の発達に関連する生物のゲノムの領域を同定するプロセスである。遺伝子の発見は、研究における１つ以上のゲノムサンプル中のヌクレオチドの特定のパターンの検索を必要とする。同様に、他のゲノム分析の応用は、目的のヌクレオチドの配置を同定するためのパターンマッチング技術の利用を必要とする。いくつかの場合において、パターンマッチングは、より長いゲノムシーケンスを構築するために、シーケンスデータが既存のリファレンスシーケンス上にマッピングされるシーケンスアラインメント技術の代替として見られる。シーケンスデータの最も使用されているゲノム情報表示は、生リードについてはＦＡＳＴＱフォーマット、整列されたリードについてはＳＡＭ及びＣＲＡＭに基づいている。これらの解決法は、生リード又はマッピングされていないリードのためのいかなる形式のインデックス付けもサポートせず、それらを順不同のレコードのシーケンスとして保管する。これらは、特定のパターンを検索するにはデータセット全体を復号化して解析する必要があることを意味する。
【０００３】
本発明は、生ゲノムシーケンスリード又はマッピングされていないゲノムシーケンスリードを以下によってインデックス付することを目的とする：
・共有されている共通の部分シーケンスによるリードのクラスタリング。クラスタに属する全てのリードが、定義されたクラスタリングの制約により、いくらかのミスマッチを有するヌクレオチドの特定のシーケンスを含む。本発明の開示を通して、共通のシーケンスはクラスタシグネチャと呼ばれる、
・シグネチャヌクレオチドを表す１つ以上の整数のシーケンスとしてクラスタシグネチャをコード化、
・コード化されたシグネチャを順番に並んだ又は順番に並んでいないベクターに格納、
・本開示で定義されるように、Ｃｌａｓｓ  Ｕに属する生リード、マッピングされていないリード又は整列されていないリードと共に、コード化されたシグネチャのベクターをコード化すること。
【０００４】
既存の方法に関するそのようなアプローチの最も関連性のある改善は以下のものからなる：
１．シングルリードの代わりにリードのクラスタ全体でパターンマッチングを実行する可能性、
２．同時にいくつかのクラスタに対して並列パターンマッチングを実行する可能性、
３．クラスタシグネチャの特性に関連する基準に従って、生リード又はマッピングされていないリードを順序付ける可能性
４．既知の遺伝子とクラスタシグネチャとの比較を可能にすることによる遺伝子発見性能の向上。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
以下の特許請求の範囲の特徴は、ゲノムシーケンスデータをコード化するための方法を提供することによって既存の従来技術の解決法の問題を解決する。
【課題を解決するための手段】
【０００６】
ゲノムシーケンスデータは、ヌクレオチドシーケンスのリードを含み、前記方法は、
「クラスタシグネチャ」と呼ばれるヌクレオチドの共通のシーケンス又は部分シーケンスを共有するリードのクラスタに前記リードを分割すること、
前記クラスタ化されたリードを構文要素の多数のブロックとしてコード化すること、
ヘッダ情報を用いて前記構文要素のブロックを構成し、それによって連続的なアクセスユニットを作成する。
【０００７】
別の態様では、コード化方法は、
サポートされたアルファベットの各ヌクレオチドを一意的な２進法表示に関連付け、
コード化したシグネチャを表すビット文字列を取得するために、シグネチャ内の各ヌクレオチドの２進法表示を連結すること、
によって前記クラスタシグネチャをコード化することをさらに含む。
【０００８】
別の態様では、コード化方法は、コード化したシーケンスリードの各クラスタが前記コード化したシグネチャによって識別されるステップをさらに含む。
【０００９】
別の態様では、前記構文要素のブロックは、サポートされたアルファベットの各ヌクレオチドを一意的な２進法表示に関連付けてコード化されたクラスタシグネチャを含み、コード化されたシグネチャを表すビットストリームを取得するために、シグネチャの各ヌクレオチドの２進法表示に連結させるマスタインデックステーブルを含み、各クラスタに属するシーケンスリードを表すコード化された構文要素のブロックの記憶媒体上の位置を表す整数値のベクターに関連付けられる。
【００１０】
別の態様では、前記構文要素のブロックは、各データセットグループを一意的に識別するために使用されるデータセットグループ識別子を含むゲノムデータセットヘッダ、
各データセットを一意的に識別するために使用されるゲノムデータセット識別子、
データセットが準拠するデータフォーマット仕様を識別するために使用されるブランド識別子、
データセットが準拠するデータフォーマット仕様を識別するために使用されるマイナーバージョン番号、
固定長リードを知らせるために使用されるヌクレオチドのコード化されたゲノムリードの長さ、
ペアエンドリードの存在の存在を知らせるフラグ、
ブロックヘッダの存在を知らせるフラグ、
アクセスユニットが記憶媒体に記憶される順序を知らせるフラグ、
データセットをコード化するために使用されるリファレンスシーケンスの数、
各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの数値識別子、
各リファレンスシーケンスを一意的に識別するために使用されるリファレンスシーケンスごとの文字列識別子、
各リファレンスシーケンスに関連するアクセスユニットを数えるために使用されるリファレンスシーケンスごとのコード化したアクセスユニットの数、
整列されたリード、整列されていないリード、マッピングされていないリード及びリファレンスシーケンスを区別するために使用されるコード化したゲノムデータの種類、
データセットにコード化されているデータクラスの数、
復号化処理中に使用されるデータセット内でコード化されたデータクラスごとに使用される記述子の数、
コード化されたマッピングされていないリードのインデックス付に使用されたクラスタの総数、
コード化されたクラスタシグネチャを復号化するのに使用されるクラスタシグネチャをコード化するのに使用される整数値を表すのに使用されるビット数、
すべてのクラスタシグネチャが、ヌクレオチド数に関して同じ長さを有する場合に、クラスタシグネチャの長さを知らせるフラグ、
を備える。
【００１１】
前記コード化方法の別の態様では、前記ゲノムリードは対合している。
【００１２】
前記コード化方法の他の態様では、前記ゲノムデータはエントロピーコード化されている。
【００１３】
コード化されたゲノムデータを復号化するための方法は、
ヘッダ情報を使用することによって構文要素の複数のブロックを抽出するために、前記コード化されたゲノムデータを含むアクセスユニットを解析するステップ、
前記方法としてコード化された生リードの、マッピングされていないリード及び整列されていないリードを抽出するために、前記多数の構文要素のブロックを復号化するステップ、
コード化されたクラスタのシグネチャを取得すために、マスタインデックステーブルを解析するステップ、
シグネチャの各２進法表示に対応するヌクレオチドシーケンスを関連付けることによりシグネチャシグネチャを復号化するステップ、
ゲノムデータのコード化された表現を含むアクセスユニットを記憶媒体上で取得するために、各シグネチャに関連付けられた整数のベクターを解析するステップ、
ヘッダ情報を用いてアクセスユニットから構文要素の複数のブロックを抽出するステップ
を備える。
【００１４】
別の態様では、前記復号方法は、グローバルな構成パラメータを含むゲノムデータセットヘッダを復号化することをさらに含む。
【００１５】
別の態様では、前記復号化方法は、コード化されたクラスタシグネチャとコード化されたブロックオフセットとを含むマスタインデックステーブルを復号化することをさらに含む。
【００１６】
前記復号化方法の他の態様では、前記ゲノムリードが対になっている。
【００１７】
前記復号化方法の別の態様では、前記ゲノムリードがエントロピー復号化されている。
【００１８】
生ゲノムシーケンスデータ（１１１）、マッピングされていないゲノムシーケンスデータ（１１１）、マッピングされていないゲノムシーケンスデータ（１１１）を圧縮するためのゲノムエンコーダ（１１１５）であって、前記ゲノムシーケンスデータ（１１１）は、ヌクレオチドのシーケンスのリードを備え、前記ゲノムエンコーダ（１１１５）は、
クラスタシグネチャと呼ばれるヌクレオチドの共通のシーケンス又は部分シーケンスを共有するリードのグループに前記リードを分割し、それによってリードのクラスタ（１１３）及びクラスタシグネチャ（１１４）を作成するように構成された、クラスタリングユニット（１１２）、
前記クラスタ化されたリードを構文要素のブロックとしてコード化するように構成された、１つ以上の記述子コード化ユニット（１１５）、
ゲノムアクセスユニット（１１１１）を生成するために、それらの統計的特性に従って構文要素の前記ブロックを圧縮するように構成された、１つ以上のエントロピーコード化ユニット（１１１０）。
一意的な２進法表示をクラスタシグネチャの各記号に関連付けることによってクラスタシグネチャ（１１４）を２値化するように構成された、シグネチャコード化ユニット（１１６）、
前記２値化されたクラスタシグネチャ（１１７）を、前記ゲノムアクセスユニット（１１１１）に含まれるエントロピーコード化された記述子の記憶媒体上のオフセットを表す整数のベクターに関連付けるように構成されたゲノムデータセットヘッダ及びマスタインデックステーブルジェネレータ（１１９）、
圧縮されたゲノムデータとメタデータを多重化するためのマルチプレクサ（１１１３）、
を備える。
【００１９】
ゲノムシーケンスデータ（１２１）の圧縮のためのゲノムエンコーダ（１２１０）であって、前記ゲノムシーケンスデータ（１２１）はヌクレオチドのシーケンスのリードを含み、
前記ゲノムエンコーダ（１２１０）は、
前記リードを１つ以上のリファレンスシーケンスに整列させ、それによって整列されたリードを作成するように構成された、アライナユニット（１２２）、
１つ以上の既存のリファレンスシーケンス又は構築されたリファレンスシーケンスで、指定されたマッチング規則に従って前記整列されたリードを分類し、それによって整列されたリードのクラス（１２８）を作成するように構成された、データ分類ユニット（１２４）、
整列されたリードの前記クラスに従って、前記構文要素を選択することにより、前記分類された整列されたリードを構文要素のブロックとしてコード化するように構成された、１つ以上の記述子コード化ユニット（１２５〜１２７）、
ゲノムストリーム（１２１５）を生成するために、統計特性に従って構文要素の前記ブロックを圧縮するように構成された、１つ以上のエントロピーコード化ユニット（１２１２〜１２１４）、
上述のように構成された、生リードシーケンスリード、マッピングされていないリードシーケンスリード及び整列されていないシーケンスリードコード化ユニット（１１１５）、
圧縮されたゲノムデータ及びメタデータを多重化するためのマルチプレクサ（１２１６）
を備える。
【００２０】
コード化方法を実行可能なコード化手段を備えるゲノムデコーダであって、サポートされているアルファベットの各ヌクレオチドを一意的な２進表現に関連付けることによって前記クラスタシグネチャをコード化し、コード化されたシグネチャを表すビット文字列を得るために、各ヌクレオチドの前記２進表現をシグネチャに連結することを備えるゲノムデコーダ。
【００２１】
圧縮されたゲノムアクセスユニット（１３４）を解凍するためのゲノムデコーダ（１３１３）であって、前記ゲノムデコーダ（１３１３）は、
圧縮されたゲノムアクセスユニット（１３４）と、ゲノムデータセットヘッダと、マスタインデックステーブル（１３３）とを逆多重化するためのデマルチプレクサ（１３２）、前記ゲノムデータセットヘッダ及びマスタインデックステーブル（１３３）をコード化されたクラスタシグネチャ（１３７）に解析するように構成された解析手段（１３５）、
前記コード化されたクラスタシグネチャ（１３７）をクラスタシグネチャ（１３１１）に復号化するように構成されていたシグネチャデコーダ（１３９）、
前記圧縮されたゲノムアクセスユニットを、ゲノム記述子（１３８）と名付けられた構文要素のブロックに解凍するように構成されたエントロピーデコーダ（１３６）、
ゲノム記述子をヌクレオチドのシーケンスの圧縮されていないリードに復号化するように構成された１つ以上の記述子デコーダ（１３１０）を備えるゲノムデコーダ。
【００２２】
圧縮されたゲノムストリーム（１４１０）を解凍するためのゲノムデコーダ（１４８）であって、前記ゲノムデコーダ（１４８）は、
圧縮されたゲノムデータ及びメタデータをゲノムビットストリーム（１４１）及びマッピングされていないシーケンスリードのビットストリーム（１４５）に逆多重化するためのデマルチプレクサ（１４０）、
前記圧縮されたゲノムストリームをゲノム記述子（１４５）と名付けられた構文要素のブロックに解析するように構成されたエントロピーデコーダ（１４２〜１４４）、
ゲノム記述子をヌクレオチドのシーケンスの分類されたリードに復号化するように構成された１つ以上のゲノム記述子デコーダ（１４６〜１４７）、
１つ以上のリファレンスシーケンス上のヌクレオチドのシーケンスの前記分類されたリードを選択的に復号化して、ヌクレオチドのシーケンスの圧縮されていないリードを生成するように構成されたゲノムデータクラスデコーダ（１４９）、
圧縮されていない生シーケンスリード、未マッピングされていないシーケンスリード及び整列されていないシーケンスリード（１４１４）及びクラスタシグネチャ（１４１５）を生成するために、上述のように構成されたマッピングされていないシーケンスリードデコーダ（１３１３）、
を備えるゲノムデコーダ。
【００２３】
本発明はさらに、実行されると、少なくとも１つのプロセッサに前述のコード化方法のすべての態様を実行させる命令を備えるコンピュータ可読媒体を提供する。
【００２４】
本発明はさらに、実行されると、少なくとも１つのプロセッサに前述のコード化方法のすべての態様を実行させる命令を備えるコンピュータ可読媒体を提供する。
【００２５】
本発明はさらに、実行されると、少なくとも１つのプロセッサに前述の復号化方法の全ての態様を実行させる命令を備えるコンピュータ可読媒体を提供する。
【００２６】
本発明はさらに、前述のコード化方法の全ての態様によって実行されるゲノムコードを保存するサポートデータを提供する。
【図面の簡単な説明】
【００２７】
【図１】図１は、「シグネチャ」と呼ばれるヌクレオチドの共有の部分シーケンスに従って、生リード、マッピングされていないリード及び整列されていないリードがどのようにクラスタ化されるかを示す。
【図２】図２は、同じシグネチャを共有しているが精度が異なる４つのリードの例を示す。ｒｅａｄ１は正確なシグネチャを含、ｒｅａｄ２は２つのミスマッチがあるシグネチャを含み、ｒｅａｄ３は１つの塩基がない（欠失）のシグネチャを含み、ｒｅａｄ４は追加の塩基（挿入）があるシグネチャが含まれる。
【図３】図３は、固定長シグネチャの場合に符号なしの３２ビット整数として、長さ８のシグネチャをコード化する方法を示す。
【図４】図４は、固定長シグネチャの場合にいくつかの符号なしの８ビット整数として、長さ６のシグネチャをコード化する方法を示す。
【図５】図５は、可変長シグネチャの場合に、符号なしの３２ビット整数として、長さ８および５のシグネチャをコード化する方法を示す。
【図６】図６は、可変長シグネチャの場合に、符号なし８ビット整数として、長さ６と５のシグネチャをコード化する方法を示す。
【図７】図７は、生リード、マッピングされていないリード又は整列されていないリードをコード化するとき、マスタインデックステーブルがコード化したシグネチャと、記憶媒体上のアクセスユニットによって含まれるコード化した記述子の対応ブロックへのポインタとを含む２つのベクターを含むことを示す。
【図８】図８は、８つのヌクレオチドにより構成され、３２ビット整数としてコード化された固定長シグネチャを復号化する方法の一例を示す。
【図９】図９は、８ビット整数としてコード化されることによって構成される可変長シグネチャを復号化する方法の一例を示す。
【図１０】図１０は、同じゲノムデータクラスのリードを表すために使用されるエントロピーコード化した記述子のブロックをアクセスユニットがどのように含むかを示す。ブロックはネットワーク転送のためにパケットに分割される。
【図１１】図１１は、生ゲノムシーケンスエンコーダの構造を示す。
【図１２】図１２は、整列されたリードを同様にコード化するより大きなアーキテクチャに組み込まれた図１１の生ゲノムシーケンスエンコーダを示す。
【図１３】図１３は、生シーケンスデータ、マッピングされていないシーケンスデータ及び整列されていないシーケンスデータを含むアクセスユニットのデコーダのアーキテクチャを示す。出力は、復号化されたシーケンスのリードのクラスタと関連するシグネチャからなる。
【図１４】図１４は、マッピングされていないリード（Ｃｌａｓｓ  Ｕデータ）を含むアクセスユニットを復号化するために、ゲノムシーケンスデコーダにおいて使用される図１２のデコーダを示す。
【図１５】図１５は、より長いシーケンス（「コンティグ」としても知られる）をマッピングされていないリードと組み合わせることによって、ハーフマッピングされたリード対（Ｃｌａｓｓ  ＨＭ）がリファレンスシーケンスの未知領域を埋めるために使用可能であることを示す。
【発明を実施するための形態】
【００２８】
関連アプリケーションとの相互参照
本出願は、特許出願ＰＣＴ／ＥＰ２０１６／０７４３１１、ＰＣＴ／ＥＰ２０１６／０７４３０１、ＰＣＴ／ＥＰ２０１６／０７４３０７、ＰＣＴ／ＥＰ２０１６／０７４２９７、ＰＣＴ／ＵＳ２０１７／１７８４２、ＰＣＴ／ＵＳ２０１７／１７８４１に優先権と利益を主張する。
【００２９】
本発明において言及されるゲノムシーケンス又はプロテオームシーケンスは、例えば、限定されるものではないが、ヌクレオチドシーケンス、デオキシリボ核酸（ＤＮＡ）シーケンス、リボ核酸（ＲＮＡ）及びアミノ酸シーケンスを含む。本明細書中の記載は、ヌクレオチドシーケンスの形態のゲノム情報に関してかなり詳細であるが、当業者によって理解されるように、圧縮のための方法及びシステムが、いくつかのバリエーションを伴うが、他のゲノムシーケンス又はプロテオームシーケンスについても同様に実施可能であることが理解される。ゲノムシーケンス情報は、定義された語彙からの文字列によって表されるヌクレオチド（別名「塩基」）のシーケンスの形態でハイスループットシーケンシング（ＨＴＳ）装置によって生成される。最小の語彙は、ＤＮＡに存在する４種類のヌクレオチド、すなわちアデニン、シトシン、グアニン及びチミンを表す５つの記号：｛Ａ、Ｃ、Ｇ、Ｔ、Ｎ｝で表される。ＲＮＡでは、チミンはウラシル（Ｕ）に置き換えられる。Ｎは、シーケンシング装置が何れの塩基か判断できず、したがってその位置におけるヌクレオチドの実際の性質は決定されていないことと示す。ＩＵＰＡＣ  ａｍｂｉｇｕｉｔｙ  ｃｏｄｅｓが語彙としてシーケンシング装置によって採用される場合、記号に使用されるアルファベットは以下の記号からなる：｛Ａ、Ｃ、Ｇ、Ｔ、Ｕ、Ｗ、Ｓ、Ｍ、Ｋ、Ｒ、Ｙ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎ又は−｝。アミノ酸の場合、サポートされる記号は以下の通りである：｛Ａ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｋ、Ｌ、Ｍ、Ｎ、Ｐ、Ｑ、Ｒ、Ｓ、Ｔ、Ｖ、Ｗ、Ｙ｝。
【００３０】
本発明の文脈において、ゲノムデータセットは、例えば、生物のゲノムデータ、生物のゲノムシーケンスによって、又は元のシーケンスデータに対して行われたゲノムデータ処理の他の任意のステップによって生成された１つ以上のシーケンス及びメタデータを含むゲノムデータの任意の構造化されたセットとして定義される。
【００３１】
本発明の文脈において、ゲノムデータセットヘッダは、本発明の開示に従ってコード化されたデータを処理するコード化装置及び復号化装置によって使用されるグローバルパラメータを含むデータ構造として定義される。
【００３２】
シーケンシング装置によって生成されたヌクレオチドシーケンスはリードと呼ばれる。シーケンスリードは、数十から数千の範囲の数のヌクレオチドから構成され得る。いくつかのシーケンシング技術は、１つのリードが１つのＤＮＡ鎖に由来し、他のリードが他のＤＮＡ鎖に由来する対からなるシーケンスリードを生成する。対を生成するシーケンスプロセスにおける別のリードに関連するリードは、そのメイトと呼ばれる。
【００３３】
本開示を通して、リファレンスシーケンスは、各整数座標が１つのヌクレオチドに関連付けられた一次元整数座標系に関連付けられたヌクレオチドのシーケンスである。座標値は、ゼロ以上でなければならない。本発明の文脈におけるこの座標系はゼロを基準とし（すなわち、最初のヌクレオチドは座標０を有し、それは位置０にあると呼ぶ）、且つ、左から右へ直線的に増加する。
【００３４】
マッピングシーケンスリードがリファレンスシーケンス上にあるとき、リファレンスシーケンスは、最も左の位置が位置０として示される一次元座標系の軸として使用される。リファレンスシーケンスにマッピングされた、シーケンスリードにおいて、最小の座標番号によって識別されるリファレンスシーケンス位置にマッピングされたリードを備えるヌクレオチドは、通常、「最も左の」ヌクレオチドと呼ばれ、最大の座標番号によって識別されたリファレンスシーケンス位置にマッピングされたリードを構成するヌクレオチドは、「最も右」のヌクレオチドと呼ばれる。これを図３に示す。本開示を通して、ヌクレオチドは塩基とも呼ばれる。これは、図３に示される。本開示を通して、ヌクレオチドは塩基とも呼ばれる。
【００３５】
シーケンスリードがリファレンスシーケンスにマッピングされると、最も左にマッピングされた塩基の座標は、リファレンスシーケンス上のリードのマッピング位置を表すと言われる。
【００３６】
整列されたリードに存在し、リファレンスシーケンスには存在しない塩基（別名、挿入）及びアラインメントプロセスによって保存され、リファレンスシーケンスにはマッピングされない塩基（別名ソフトクリップ）はマッピング位置を有さない。
【００３７】
シーケンスリードが、指定されたマッチング規則に従って、使用されたリファレンスシーケンスの何れのマップされた位置にもマッピングできない場合、マッピングされていないと言う。
【００３８】
シーケンスリードの間で重複領域を探すことによって、より長いゲノムシーケンスを構築する処理は、アセンブリと呼ばれる。
【００３９】
より短いリードを集めて構築されたより長いゲノムシーケンスはコンティグ（ｃｏｎｔｉｇ）と呼ばれる。
【００４０】
アセンブリ処理中にコンティグを構築することに失敗したシーケンスリードは、整列されていないと言う。
【００４１】
本発明の開示全体を通して、いくつかの共通の特徴に従ってリードをグループ化する処理は、クラスタリングと定義される。同じ特性を共有するリードのグループは、クラスタと呼ばれる。この概念の概略図を図１に示す。
【００４２】
本発明の開示を通して、同じクラスタに属するシーケンスリードの間で共有される特徴は、クラスターシグネチャ又はシグネチャと呼ばれる。精度の異なるシグネチャを含むリードの例を図２に示す。シグネチャは２〜数千の任意の数のヌクレオチドで構成でき、シグネチャはすべてのクラスタに対して一定の長さを有するか、又は可変長を有するかのいずれかである。シグネチャに属することができる記号のアルファベットは、処理されているシーケンスリードを生成するために配列決定された特定のゲノムサンプルに依存する。一例として、しかし限定としてではなく、以下のアルファベットを使用することができる。
・ＤＮＡ用
○｛Ａ、Ｇ、Ｃ、Ｔ、Ｎ｝
○｛Ａ、Ｇ、Ｃ、Ｔ、Ｒ、Ｙ、Ｓ、Ｗ、Ｋ、Ｍ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎ、．、−（ＩＵＰＡＣ表記）
・ＲＮＡ用
○｛Ａ、Ｇ、Ｃ、Ｕ、Ｎ｝
○｛Ａ、Ｇ、Ｃ、Ｕ、Ｒ、Ｙ、Ｓ、Ｗ、Ｋ、Ｍ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎ、．、−（ＩＵＰＡＣ表記）
・アミノ酸用
○｛Ａ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｋ、Ｌ、Ｍ、Ｎ、Ｐ、Ｑ、Ｒ、Ｓ、Ｔ、Ｖ、Ｗ、Ｙ｝
【００４３】
クラスタシグネチャを計算するために使用されるアルファベットの種類は、本開示で説明されるゲノムデータセットヘッダと呼ばれるデータ構造によってもたらされるパラメータＡｌｐｈａｂｅｔ＿ＩＤによって識別される。同じゲノムデータセットに属するクラスタのシグネチャは、固定長又は可変長である。ゲノムデータセットのヘッダにコード化されたグローバルパラメータは、シグネチャの長さが固定か可変かを示すために使用される。シグネチャ長が固定の場合、第２のグローバルパラメータはクラスタシグネチャの記号の長さを表す。可変のシグネチャ長の場合、この値は０である。
【００４４】
リファレンスゲノムは１つ以上のリファレンスシーケンスによって構成され、それは種の遺伝子セットの代表例として科学者によって集められる。例えば、ＧＲＣｈ３７、ゲノムリファレンスコンソーシアムのヒトゲノム（ｂｕｉｌｔ３７）は、ニューヨーク州バッファロー出身の１３人の匿名のボランティアに由来する。しかしながら、リファレンスシーケンスは、それらのさらなる処理を考慮して、リードの圧縮性を改善するために考えられ、単に構築された合成シーケンスからなることもできる。
【００４５】
本開示では、リファレンス上の最小座標上の塩基マッピングでリードペアを構成するリードを「リード１」と呼び、そのメイトを「リード２」と呼ぶ。
【００４６】
今日の技術を使用するシーケンス装置によって、対として生成された分離した２つのリードを、ヌクレオチド（または塩基）の数として表した距離は未知であり、ペアを構成する両方のリードをリファレンスシーケンスにマッピングする（すなわち適切なマッチング関数を最小にする）ことによって決定される。
【００４７】
以下の節で詳述するように、本発明の開示は、１つ以上のリファレンスシーケンスへシーケンスリードをマッピングした結果に従ってシーケンスリードを分類する方法を定義する。
・ミスマッチなしでリファレンスシーケンスにマッピングするリードは、Ｃｌａｓｓ  Ｐに属する
・ミスマッチとして未知の塩基（記号「Ｎ」で表される）のみを含むリファレンスシーケンスにマッピングするリードは、Ｃｌａｓｓ  Ｎに属する
・リファレンスに対して定義された閾値以下の置換数を有するリファレンスシーケンスにマッピングするリードは、Ｃｌａｓｓ  Ｍに属する
・リファレンスに対して定義された閾値以下の置換数、欠失数、挿入数又はソフトクリップされた塩基数を有するリファレンスシーケンスにマッピングするリードは、Ｃｌａｓｓ  Ｉに属する
・１つのマッピングされたリード（前の４つのＣｌａｓｓの何れかに属している）と、マッピングされていないメイトとのリードペアは、Ｃｌａｓｓ  ＨＭに属する
・許容されるミスマッチの最大数に関して確立された制約に従って、何れのリファレンスシーケンスにもマッピングされないリードは、Ｃｌａｓｓ  Ｕに属する
【００４８】
アクセスユニット（ＡＵ）は、ビットストリームのアクセス及び操作を容易にするために、ゲノム情報のコード化表現又は関連するメタデータを含む論理データ構造として定義される。最小のデータ構成が、本開示に記載の本発明を実施する復号化装置によって復号化することができる。アクセスユニットは、本開示において定義されている１つのデータクラスのみに属するリードを含むことができる。
【００４９】
コード化情報の種類に応じて、ＡＵは他のＡＵとは無関係に、又は他のＡＵに含まれる情報を使用して復号化することができる。
【００５０】
Ｃｌａｓｓ  Ｕに属するマッピングされていない、又は整列されていないリードは、特定の種類のアクセスユニットに格納されている構文要素の特定のサブセットを使用してコード化される。
【００５１】
アクセスユニットの一例が図１０に示される。アクセスユニットはコード化された記述子のブロックによって構成される（次のセクションで説明する）。ネットワーク上での転送を可能にするために、ブロックはさらにパケットに分解される。
【００５２】
記述子は、コード化されたリファレンスシーケンス、シーケンスのリード及び関連するマッピング情報を再構築（即ち、デコード）するために必要な情報の一部を表す構文要素である。異なる種類の記述子を表現するために定義する。
・リファレンスシーケンス上のリードのマッピング位置、
・リードとそのメイトとの距離、
・シーケンスリードの長さ、
・リファレンスシーケンスに対して整列させたリードのミスマッチの位置、
・関連する位置でのリファレンスシーケンスに対するミスマッチの種類、
・マッピング処理によってリファレンスシーケンスにマッピングできなかった塩基、及び「ソフトクリップ」塩基として分類された塩基、
・シーケンスリード長、
・ＳＡＭ仕様により指定されたマッピングフラグ、
・マッピング処理によって単一のリード又はリードペアに関連付けられた複数のマッピング位置、
・スプライシングされたリードの存在の識別（すなわち、チャンクに分割されたときに、次いでそれらがリファレンスシーケンス上の単一位置にマッピングされた単一の連結したリードとしてマッピングされたときに、より高いマッチング精度でマッピング位置を検出する）
・以下のように使用される特定の種類のリファレンスシーケンス：
○ゲノムリファレンスコンソーシアム（例えば、ＧＲＣｈ３７）、カリフォルニア大学サンタクルーズ校（例えば、ｈｇ１９）のようなコンソーシアムによって発表されたもののようなリファレンスゲノム、
○リードの特定のセット及びアセンブリルールの特定のセットを使用して構築されたリファレンスシーケンス、
・修飾されたリファレンスシーケンスにマッピングされたシーケンスリードのミスマッチを表すために使用される記述子のエントロピーを減少させる目的で、リファレンスシーケンスに適用される修飾の位置及び種類、
・特定のマッチング精度で、リファレンスシーケンスの何れの位置にもマッピングできないシーケンスリードの表現、
・特定のマッチング精度に従って、アセンブリ処理中にコンティグを構築するために整列させることができないシーケンスリードの表現、
・リファレンスシーケンス全体又はその一部の表現。
【００５３】
本発明に開示された方法によれば、リファレンスシーケンス又はその一部、シーケンスリード及び関連するアラインメント情報は、各記述子に特異的な統計的性質に従って複数のエントロピーコーダを用いてエントロピーコード化された上に挙げた記述子のサブセットを用いてコード化される。均一な統計的性質を有する記述子のブロックは、本開示に記載されている本発明を実施する装置によって操作することができる１つ以上のゲノムシーケンスの最小コード化表現を表すアクセスユニットで構成される。
【００５４】
本開示に記載される発明は、生シーケンスリード、マッピングされていないシーケンスリード及び整列されていないシーケンスリードのコード化表現を含むアクセスユニットにインデックスを付ける方法を定義する。
【００５５】
マッチングルールに従ったシーケンスリードの分類
【００５６】
シーケンス装置によって生成されたシーケンスリードは、開示された発明によって、１つ以上の「既存の」リファレンスシーケンスに関するアラインメントのマッチング結果に従って、６つの異なる「Ｃｌａｓｓ」に分類される。
【００５７】
リファレンスシーケンスに関してヌクレオチドのＤＮＡシーケンスを整列させる場合、以下の場合が同定され得る。
１．リファレンスシーケンス中の領域が、エラーがなくシーケンスリードと一致することが検出される（すなわち、完全マッピング）。そのようなヌクレオチドのシーケンスは、「完全に一致するリード」と呼ばれるか、または「Ｃｌａｓｓ  Ｐ」と表される。
【００５８】
２．リファレンスシーケンス中の領域は、リードを生成するシーケンス装置が何れの塩基（またはヌクレオチド）も判断できなかった位置の数によってのみ決定されたミスマッチの種類及び数と、シーケンスリードとが一致することが検出される。そのようなミスマッチの種類は、未定義のヌクレオチド塩基を示すために使用される文字である「Ｎ」よって表される。この文書では、この種類のミスマッチを「ｎ型」のミスマッチと呼ぶ。そのようなシーケンスは、「Ｃｌａｓｓ  Ｎ」リードに属する。リードが「Ｃｌａｓｓ  Ｎ」に属すると分類されると、一致の不正確さの程度を所定の上限に制限し、有効な一致と見なされるものとそうでないものとの間に境界を設定するのに有用である。したがって、Ｃｌａｓｓ  Ｎに割り当てられたリードはまた、リードが含むことができる未定義の塩基（すなわち「Ｎ」と呼ばれる塩基）の最大数を定義する閾値（ＭＡＸＮ）を設定することによって制約される。そのような分類は、Ｃｌａｓｓ  Ｎに属するすべてのリードが、対応するリファレンスシーケンスを参照したときに共有する必要最小限のマッチング精度（または最大のミスマッチ度合い）を自動的に定義し、これは選択データ検索を圧縮データに適用するための有用な基準を構成する。
【００５９】
３．リファレンスシーケンス中の領域は、リードを生成するシーケンス装置が何れの塩基（またはヌクレオチド）も判断できなかった位置の数によって決定されたミスマッチの種類及び数と、シーケンスリードとが一致することが検出され、もし、存在するなら（すなわち「ｎ型」ミスマッチ）であるならば、リファレンスに存在するものとは異なる塩基と判断されたミスマッチの数を追加する。「置換」として示されるそのような種類のミスマッチは、一塩基変異（ＳＮＶ）又は一塩基多型（ＳＮＰ）とも呼ばれる。この文書では、この種類のミスマッチは「ｓ型」のミスマッチとも呼ばれる。次いで、シーケンスリードは、「Ｍミスマッチリード」と呼ばれ、「Ｃｌａｓｓ  Ｍ」に割り当てられる。「Ｃｌａｓｓ  Ｎ」の場合と同様に、「Ｃｌａｓｓ  Ｍ」に属するすべてのリードについても、一致の不正確さの程度を所定の上限に制限し、有効な一致と見なされるものとそうでないものとの境界を設定するのに有用である。したがって、Ｃｌａｓｓ  Ｍに割り当てられたリードは、閾値のセットを定義することによっても制約され、存在するならば、１つは「ｎ型」のミスマッチの数「ｎ」（ＭＡＸＮ）、もう１つは置換数「ｓ」（ＭＡＸＳ）である。第３の制約は、数値「ｎ」と「ｓ」の両方の関数ｆ（ｎ、ｓ）によって定義される閾値である。そのような第３の制約は、任意の意味のある選択的アクセス基準に従ってマッチングの不正確さの上限を有するＣｌａｓｓを生成することを可能にする。例えば、限定としてではなく、ｆ（ｎ、ｓ）は、（ｎ＋ｓ）１／２もしくは（ｎ＋ｓ）、又は「Ｃｌａｓｓ  Ｍ」に属するｒｅａｄを許容する最大のマッチング不正確さレベルに境界を設定する任意の線形又は非線形の表現とすることができる。このような境界は、一方の種類またはもう一方の種類に適用された単純な閾値を超える「ｎ型」ミスマッチの数と「ｓ型」（置換）の数との任意の可能な組み合わせにさらなる境界を設定することを可能にするため、様々な目的でシーケンスリードを分析するときに所望の選択的データ検索を圧縮データに適用するための非常に有用な基準を構成する。
【００６０】
４．第４のＣｌａｓｓは、「挿入」、「欠失」（別名、インデル）及び「クリップ（ｃｌｉｐｐｅｄ）」の中の何れかの種類の少なくとも１つのミスマッチを示すシーケンスリードによって構成され、存在する場合には、Ｃｌａｓｓ  ＮまたはＭに属する任意のミスマッチの種類を加える。そのようなシーケンスは、「ミスマッチリードＩ」と呼ばれ、「Ｃｌａｓｓ  Ｉ」に割り当てられる。挿入は、リファレンスには存在しないがリードシーケンスには存在する１つまたは複数のヌクレオチドの追加のシーケンスによって構成される。この文書では、この種類のミスマッチを「ｉ型」ミスマッチと呼ぶ。文献では、挿入されたシーケンスがシーケンスの端にある場合、「ソフトクリップ」とも呼ばれる（すなわち、ヌクレオチドはリファレンスとは一致しないが、廃棄される「ハードクリップ」ヌクレオチドとは対照的に整列されたリードに保持される）。この文書では、この種類のミスマッチを「ｃ型」のミスマッチと呼ぶ。ヌクレオチドを保持または廃棄することは、シーケンス装置または次のアライメント段階によって決定されるような、リードを受け取って処理する本発明に開示されたリードの分類子によってではなく、アライナの段階によって行われる決定である。欠失は、リファレンスに対してリードにおける「穴」（欠けているヌクレオチド）である。この文書では、この種類のミスマッチを「ｄ型」ミスマッチと呼ぶ。Ｃｌａｓｓ「Ｎ」及び「Ｍ」の場合と同様に、マッチングの不正確さに対する制限を定義することは可能であり適切である。「Ｃｌａｓｓ  Ｉ」に対する制約のセットの定義は、「Ｃｌａｓｓ  Ｍ」に対して使用されたのと同じ原理に基づいており、表１において表の最後の行に報告されている。Ｃｌａｓｓ  Ｉデータに許容される各種類のミスマッチについての閾値に加えて、さらなる制約は、ミスマッチ「ｎ」、「ｓ」、「ｄ」、「ｉ」及び「ｃ」、ｗ（ｎ、ｓ、ｄ、ｉ、ｃ）の数の任意の関数によって決定される閾値によって定義される。そのような追加の制約は、任意の意味のあるユーザ定義の選択的アクセス基準に従って、マッチングの不正確さの上限を有するＣｌａｓｓを生成することを可能にする。例えば、限定としてではなく、ｗ（ｎ、ｓ、ｄ、ｉ、ｃ）は、（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）１／５又は（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）又は「Ｃｌａｓｓ  Ｉ」に属するリードについて認められる最大のマッチングの不正確レベルに境界を設定する任意の線形もしくは非線形の式であり得る。このような境界は、許容されるミスマッチの各種類に適用される単純な閾値を超えて、「Ｃｌａｓｓ  Ｉ」のリードで許容されるミスマッチの数のあらゆる可能な組み合わせに対してさらなる境界を設定することを可能にするため、様々な目的のためのシーケンスリードを分析するときに所望の選択的データ検索を圧縮データに適用するための非常に有用な基準を構成する。
【００６１】
５．第５のＣｌａｓｓは、リファレンスシーケンスを参照するときに、各データクラスについて、有効と見なされる（すなわち、表１に規定される最大のマッチングの不正確さに対する上限を定義するマッチングルールのセットを満たさない）マッピングを検出しない全てのリードを含む。そのようなシーケンスは、リファレンスシーケンスを参照ときに、「マッピングされていない」と呼ばれ、「Ｃｌａｓｓ  Ｕ」に属すると分類される。
【００６２】
マッチング規則に従ったリードペアの分類
前のセクションで指定された分類は、単一のシーケンスリードに関する。２つのリードが可変長の未知のシーケンスで区切られていることがわかっている、ペアでリードを生成するシーケンス技術（例えば、Ｉｌｌｕｍｉｎａ  Ｉｎｃ．）の場合は、ペア全体を単一のデータＣｌａｓｓに分類することを検討するのが適切である。互いに結合されているリードは、その「メイト」と呼ばれる。
【００６３】
両方の対のリードが同じＣｌａｓｓに属する場合、ペア全体のＣｌａｓｓへの割り当ては明らかであり、ペア全体が任意のＣｌａｓｓ（すなわちＰ、Ｎ、Ｍ、Ｉ、Ｕ）に対して同じＣｌａｓｓに割り当てられる。２つのリードが異なるＣｌａｓｓに属しているが、どちらも「Ｃｌａｓｓ  Ｕ」に属していない場合、ペア全体が次の式に従って定義された最も高い優先順位を有するＣｌａｓｓに割り当てられる。
Ｐ＜Ｎ＜Ｍ＜Ｉ
ここで、「Ｃｌａｓｓ  Ｐ」が最も低い優先順位を有し、「Ｃｌａｓｓ  Ｉ」が最も高い優先順位を有する。
【００６４】
リードのうちの１つだけが「Ｃｌａｓｓ  Ｕ」に属し、そのメイトがＣｌａｓｓ  Ｐ、Ｎ、Ｍのいずれかに一致する場合、第６のＣｌａｓｓは「ハーフマップ」を表す「Ｃｌａｓｓ  ＨＭ」として定義される。
【００６５】
そのような特定のＣｌａｓｓのリードの定義は、それがリファレンスゲノムに存在するギャップ又は未知の領域（別名、ほとんど知られていない又は未知の領域）を決定する試みのために使用されるという事実によって動機付けられる。そのような領域は、既知の領域にマッピングすること可能なペアリードを使用してエッジでペアをマッピングすることによって再構築される。次いで、図１５に示すように、マッピングされていないメイトを使用して、未知の領域のいわゆる「コンティグ」を構築する。したがって、そのような種類のリードペアのみへの選択的なアクセスを提供することは、最先端のソリューションを使用して完全に検査する必要があると思われる大量のデータセットによって生成されたデータの非常に効果的な処理が可能な関連した計算負荷を低減する。
【００６６】
以下の表に、各リードが属するデータのＣｌａｓｓを定義するためにリードに適用されるマッチングルールをまとめる。ルールは、ミスマッチの種類（ｎ、ｓ、ｄ、ｉ、及びｃ型のミスマッチ）の有無によって、表の最初の５列に定義される。６列目は、各ミスマッチの種類及び可能なミスマッチの種類の任意の関数ｆ（ｎ、ｓ）及びｗ（ｎ，ｓ、ｄ、ｉ、ｃ）に対する最大の閾値に関するルールを提供する。
【表１】
2019537172.tif 000003
表１．本発明の開示において定義されたデータクラスに分類されるために各シーケンスリードが満たすべきミスマッチの種類及び制約のセット。
【００６７】
ゲノムシーケンスリードとリファレンスシーケンスの圧縮表示
ゲノムシーケンスリードの圧縮に対する効率的なアプローチの一般的な要素は、リファレンスシーケンスに対するシーケンスデータの関係の利用である。たとえ、ヒトの集団の体性のプロファイルが非常に多様化したとしても、人によって異なるヌクレオチドの数の実際の部分は全ゲノムを構成するヌクレオチドの総数の約０．１％にすぎない。したがって、各個体を特徴付ける特定のゲノム情報は、全ゲノムによってもたらされる全情報に対して非常に限定されている。以前のシーケンスのため、又は公表されている「平均的」コンセンサスリファレンスとして存在する、既存のリファレンスゲノムが利用可能である場合、実際の情報をコード化する最も効率的な方法は、リファレンスゲノムに対する差異のみを識別しコード化することである。
【００６８】
ＦＡＳＴＱデータの形態の生シーケンスリードを用いてそうするために、利用可能なリファレンスゲノム上にマッピングする予備的な前処理工程が行われる。リファレンスゲノムが利用できない場合、又は特定のリファレンスの使用によって導入された偏りが望ましくない場合、利用可能なシーケンスリードをより長いシーケンスに組み込むことによる新しいリファレンスシーケンスの構築が可能な代替法である。
【００６９】
シーケンスリードが既存のリファレンスシーケンス又は構築されたリファレンスシーケンスに対してマッピングされている場合、各シーケンスリードは、本開示において「リード記述子」又は単に「記述子」として示されるいくつかの要素によって完全に表すことができる。
【００７０】
例えば、リファレンスシーケンスのセグメントと完全に一致するシーケンスリードの場合、シーケンスリードを表すのに必要な記述子のサブセットだけが、リファレンス上のマッピング位置の座標（通常はシーケンスリードの左端の塩基のマッピング位置の座標）、シーケンスの長さ自体及びリードがリファレンスシーケンス鎖に対してダイレクトなＤＮＡ鎖又はリバースのＤＮＡ鎖にマッピングされているかどうかを示す情報によって構成される。
【００７１】
シーケンスリードのすべての塩基がリファレンスシーケンスのすべての塩基と一致するマッピング位置を見つけることができない場合、最小数のミスマッチを有するマッピング（または複数のマッピング）が保持される。そのような場合、マッピング位置と最小数又は最小数に近いミスマッチとの対応で起こり得る置換、挿入、欠失及びクリップされた塩基も表現するために、異なるサブセットの記述子が必要とされる。記述子のそのようなサブセットを用いて、記述子によってもたらされる情報及びリファレンスシーケンスによってもたらされる情報を使用して、シーケンスリードを再構成することができる。
【００７２】
マッピングプロセスは、複数の可能なマッピング位置と関連スコア、マッピングの質、スプライスしたリードの指定、ペアに属するリードの２つの異なるリファレンス（通常は染色体）へのマッピング、シーケンシング処理の特徴（ＰＣＲまたは光学的複製）のような他の種類の情報も生成することができる。全てのそのような情報は、各サブセットを拡張する特定の追加の記述子を必要とし、それは次に記述子の各サブセットに対して適切なエントロピーコード化アルゴリズムを適用することによって圧縮される。
【００７３】
ゲノムシーケンシング処理は、以下の理由により、リードの重複（すなわち、同じゲノムシーケンスの２つ以上の正確なコピー）を生成し得る。
・ゲノムシーケンシングプロセスの化学的性質（ポリメラーゼ連鎖反応複製）、
・データ取得処理（光学的複製）。一対のリードが両方とも同じタイル上にあり、リード間の距離が実験に応じた所定の構成パラメータより小さい場合、リードは光学的複製と呼ばれる。
【００７４】
したがって、各リード又はリードペアは、マッピング処理の結果に従って、特定の記述子のサブセットによって一意的に表すことができる。
【００７５】
ＳＡＭ及びＣＲＡＭなどの一般的に使用される手法は、それらのマッピング情報を表すのに必要とされる記述子の特定のサブセットに従ってリード又はリードペアをコード化しない。ＳＡＭ及びＣＲＡＭは、それらがマッピングされているリファレンスシーケンスに関してそれらが含むミスマッチの数及び種類に従ってシーケンスリードをデータクラスに分類しない。さらに、これらのフォーマットは、単一のデータクラスに属するシーケンスリードのみを圧縮形式で含むアクセスユニットにシーケンスリードを別々にコード化しない。ペアで生成されたシーケンスリードの場合、最先端の手法では、リファレンスシーケンスに対するそれらのマッピング精度に従ってＣｌａｓｓに分割された単一の要素としてそれらをコード化しない。そのような最先端の手法は、以下の制限及び欠点によって特徴付けられる。
１．リファレンスシーケンスに対するマッピング結果に従ってシーケンスリードを別々のデータクラスに分類せず、記述子の固有のスーパーセットを使用せずに、リード又はリード対をコード化することは、不十分な圧縮性能をもたらす非効率的な手法である。
２．リードペアを別々のシーケンスリードとしてコード化することは、同じ情報をもたらすいくつかの記述子の複製を必要とし、従って非効率であり、劣った圧縮性能をもたらす。
３．この処理はおそらく次世代シーケンシング（ＮＧＳ）技術の場合のように非常に大きくなり得る全データセットにおいて力ずくのシーケンシャルサーチを必要とするので、リードペアを再構築するのに必要な情報の検索は複雑で非効率的になる。
４．特定のゲノム領域にマッピングされたリード又はリードペアへの選択的なアクセスは、すべてのリード又はリードペアが検索されることを保証するためにデータセット全体を検索する必要がある。
【００７６】
単一のサブセットの記述子の手段によりリードペアをコード化するとき、以下の技術的利点が当業者に明らかである。
１．明らかに冗長である、両方のリードに共通の情報は、単一の要素としてペアをコード化することによって複製されない（例えば、リードペア識別子、マッピング距離、マッピングリファレンス識別子、特定のフラグによってＳＡＭファイルフォーマットで現在コード化される様々なマッピング品質情報）
２．相互ペアリング情報（すなわち、どのリードが手元にあるどのリードのメイトであるかを提供する情報を）の検索は簡単であり、さらなる処理を必要としない。逆に、最先端の手法では、全データ量を解析する必要があるかもしれない。
【００７７】
シーケンスデータの特定の部分への効率的な選択的なアクセスを可能にし、それらをデジタルデータネットワーク上で輸送することを可能にするために、リファレンスに対して整列されたシーケンスリードを表すために使用される記述子のセットは、アクセスユニット（ＡＵ）と呼ばれる論理的に分離し、独立したデータブロックに構成される。各アクセスユニットは、単一のデータクラスの圧縮表現のみを含み、他のアクセスユニットとは無関係に、又はマッピングに使用されるリファレンスシーケンス領域のコード化表現をもたらすアクセスユニットのみを使用して復号化することができる。これにより、選択的なアクセスと順序外の転送機能が可能となる。
【００７８】
圧縮効率を向上させるために、本発明は、同じリファレンスシーケンス上にマッピングされた両方の対を有する各リードペアについて「マッピングリファレンス識別子」記述子を指定する必要性を排除する。各アクセスユニットには、同じリファレンスにマップされているリード又はペアのみを含めることができる。そのような解決策を使用すると、リファレンスシーケンス識別子を表す記述子は、各アクセスユニット又はアクセスユニットのセットごとに一度だけコード化される必要がある（そして、ＳＡＭ／ＢＡＭフォーマットで現在行われているようなリードごとの繰り返しはない）。
【００７９】
上記で表現された規則の唯一の例外は、異なるリファレンスシーケンス（例えば、染色体）上にマッピングされた２つのリードを有するリードペアの場合である。この場合、ペアは分割され、そして２つのリードは２つの別々のゲノムのレコードとしてコード化され、そして各コード化されたリードはそのメイトがマッピングされるリファレンスシーケンスの識別子を含む。
【００８０】
同種の統計的性質を有する要素のグループに情報を分類することは、異種のデータセットに適用される汎用のコンプレッサ（例えば、ＬＺタイプのアルゴリズム）の使用に関してより良い圧縮性能を提供することを当業者は知っている。結果として、ゲノムシーケンスリードを記述子の特定のサブセットを用いてペアとしてコード化する場合、各個別の記述子のサブセットを特徴付けるエントロピーがより低く、リードペアを再構築及び検索するときの処理効率がより高いため、より高い圧縮が達成される。
【００８１】
ゲノムシーケンスリードのクラスタリング
本開示に記載される発明は、所与のマッチング制約内でヌクレオチドの共通のサブシーケンス（シグネチャ）を共有するリードのグループ（または「クラスタ」）を作成する工程を備える。所与のクラスタに属するリードには、正確で完全なシグネチャが含まれているか、定義された閾値を下回る数のミスマッチ（置換、挿入又は欠失）がある。異なる精度でシグネチャを共有するリードの例を図２に示す。
閾値の例は、以下のものを有する。
・任意の種類のミスマッチの総数、
・各ミスマッチの種類に異なる重みを割り当て、各リードにおけるすべてのミスマッチの重みを合計して得られた合計のスコア、
・置換、挿入、欠失及びクリップされた塩基の出現回数の加重合計。上記の各リードクラスタは、１つ以上のアクセスユニットにコード化されている。したがって、各アクセスユニットは１つのクラスタシグネチャに関連付けられている。
【００８２】
本発明の開示を通して、アクセスユニットにコード化されたクラスタに関連するクラスタシグネチャは「アクセスユニットシグネチャ」とも呼ばれる。
【００８３】
コード化上の理由から、ＡＵごとにコード化されたリードの最大数に制限が設定される、つまり、１つのクラスタは複数のアクセスユニットでコード化してもよい場合に、２つ以上のアクセスユニットが同じシグネチャを共有することができる。
【００８４】
シグネチャのコード化
本発明の開示によれば、いったんすべてのゲノムシーケンスがクラスタに含まれると、シグネチャは１つ以上のＮビット整数のシーケンスとしてコード化される。シグネチャは、次の手順に従って１つ以上のＮビット整数としてコード化される。
・採用されている特定のクラスタリングアルゴリズムによると、クラスタシグネチャは可変長または固定長にすることができる。長さが固定であれば、それに応じて固定のシグネチャ長を知らせるグローバルパラメータが設定され、長さはゲノムデータセットヘッダに格納される。そうでなければ、可変のシグネチャ長を知らせるグローバルパラメータがそれに応じて設定され、長さはゲノムデータセットヘッダにおいて０に設定される。
・サポートされているアルファベットの各記号は、長さが次の値に等しい２進法表示に一意的に関連付けられています。
○シグネチャ長が一定の場合は、Ｍ＝ｃｅｉｌ（ｌｏｇ2（サポートされているアルファベットの濃度））
○可変のシグネチャの場合は、Ｍ＝ｃｅｉｌ（ｌｏｇ2（サポートされているアルファベットの濃度）＋１）
【００８５】
ここでｃｅｉｌは、その引数以上の最小の整数を返す操作である。
・シグネチャの長さが可変の場合、コード化されたシグネチャの末端を知らせるために使用されるターミネータと呼ばれる特別な記号を表すために、ビットの１つのシーケンスが予約される。
・本開示ではＳLと呼ばれる、固定のシグネチャ長の場合
○Ｍ×ＳL＜＝Ｎの場合、シグネチャ内の連続する記号の２進法表示は、Ｍ×ＳL＜Ｎの場合、最上位ビットに０が埋め込まれた単一のビット文字列に連結される。Ｎ＝３２で、４つの記号のアルファベットの場合の例を図３に示す。
○Ｍ×ＳL＞Ｎの場合、シグネチャ内の連続する記号の２進法表示は、ｂがＮの厳密な約数（因数としても知られる）でない場合は、各ビット文字列の最上位ビットが０で埋められた２以上のビット文字列に連結される。Ｎ＝８で、４つの記号のアルファベットの場合の例を図４に示す。
・本開示ではｉ番目のシグネチャに対してＳLiと呼ばれる、可変のシグネチャ長の場合
○Ｍ×ＳLi＜＝Ｎの場合、シグネチャ内の連続する記号の２進法表示は単一のビット文字列に連結される。すべてのコード化された記号が連結された後、ビット文字列は、最上位のビット位置に追加された終止記号で終端され、必要に応じて残りの最上位ビットに０が埋め込まれる。Ｎ＝３２と４つの記号のアルファベットの例を図５に示す。
○Ｍ×ＳLi＞Ｎの場合、シグネチャ内の連続する記号の２進法表示は、ｂがＮの厳密な約数（因数としても知られる）でない場合は、各ビット文字列の最上位ビットが０で詰め込まれた２以上のビット文字列に連結される。最後のビット文字列は終止記号で終端され、さらに最上位ビット位置に０が埋め込まれる。Ｎ＝８で、４つの記号のアルファベットの例を図６に示す。
【００８６】
効率的な選択的アクセスのための圧縮ゲノムデータのインデックス付け
整列されたデータの特定の領域への選択的なアクセスをサポートするために、本発明の開示は、２つのデータ構造：コード化処理及び復号化処理中に使用されるグローバルパラメータをもたらすゲノムデータセットヘッダと、マスタインデックステーブル（ＭＩＴ）と呼ばれるインデックスツールを定義する。ゲノムデータセットヘッダの構文は表２に提供され、マスタインデックステーブルの構文は表３に提供される。本発明の開示は、ＭＩＴおよびゲノムデータセットヘッダに含まれる要素を用いて、生リードインデックス、マッピングされていないリードインデックス及び整列されていないリードインデックスをサポートする方法を定義する。
【００８７】
ゲノムデータセットヘッダ
ゲノムデータセットヘッダは、コード化されたゲノム情報を操作するためにエンコーダ及びデコーダによって使用されるグローバルパラメータをもたらすデータ構造である。ゲノムデータセットヘッダの各要素の構成と意味を以下の表２に示す。
【００８８】
本発明で開示されるインデックス付けメカニズムに関連するグローバルパラメータは、表２に報告されているようにゲノムデータセットヘッダにコード化される。これらは以下の通りである。
・コード化されたシグネチャの各整数値を表すために使用されるビット数。これは、表２において、U_signature_sizeで表される。
・生リード、マッピングされていないリード、整列されていないリードが分割されたクラスタ及び関連するシグネチャの数。これは、表２において、U_clusters_numで表される。
・シグネチャがヌクレオチドに関して固定の長さを有するか可変の長さを有するかを示すフラグ。これは、表２において、U_signature_constant_lengthで表される。
・シグネチャ長が固定の場合のシグネチャ長。これは、表２において、U_signature_lengthで表される。
【表２】
2019537172.tif 000004
2019537172.tif 000005
表２−ゲノムデータセットヘッダーの構文
【００８９】
マスタインデックステーブル
マスタインデックステーブル（ＭＩＴ）と呼ばれるインデックス作成ツールが本発明に開示される。
マスタインデックステーブル（ＭＩＴ）は、次の要素を含む多次元アレイに基づくデータ構造である。
・リファレンスシーケンスに関して、異なる記述子ストリームからのブロックのセットとして、アクセスユニットに含まれるすべてのリード又はリードペアの一次アライメントの中で最も左の一致する塩基のヌクレオチド数としての位置。これは、表３の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と呼ばれるフラグによって通知される。
【表３】
2019537172.tif 000006
2019537172.tif 000007
2019537172.tif 000008
表３−マスタインデックステーブル
【００９３】
生リード、マッピングされていないリード及び整列されていないリードのためのインデックス付ツール
本発明の開示は、表３に報告されているマスタインデックステーブルに含まれる生シーケンスリード、マッピングされていないシーケンスリードおよび整列されていないシーケンスリード（Ｃｌａｓｓ  Ｕ）のためのインデックスメカニズムを記述する。
・前述のようにＮビット整数としてコード化されたシグネチャ。これは、表３のU_Cluster[Cluster_ID][0]により表される。
・第１のベクター内の各シグネチャに対応するリードのコード化されたクラスタの記憶媒体上の物理的位置へのポインタ。これは、表３のU_Cluster[Cluster_ID][l]により表される。
【００９４】
これら２つのベクターは、図７に示すＭＩＴの一部である。
コード化されたデータ（アクセスユニット）を復号化する必要なしに迅速なパターンマッチングを可能にするため、この解決法の利点は、当業者には明らかである。パターンマッチングの精度は、クラスタシグネチャの長さを変更することによって調整できる。短いシグネチャはより大きなクラスタを生成し、パターンの粗い検索を可能にするが、より長いシグネチャはより多数のより小さなクラスタと、より細かなパターン検索を生成する。
【００９５】
クラスタシグネチャの復号化
復号化装置が本発明の開示に記載されているようにコード化されたシグネチャを復号化しなければならないとき、以下のステップが必要とされる。
・以下に関連するゲノムデータセットヘッダのグローバルパラメータを読み込む。
○生リード、マッピングされていないリード、整列されていないリードのクラスタ数、U_clusters_num
○すべてのクラスタがヌクレオチドに同じ長さのシグネチャを有するかを示すフラグ、U_signature_constant_length
○コード化されたシグネチャを表す整数ごとに使用されるビット数、U_signature_size
○固定長の場合、各シグネチャのヌクレオチドの長さ、U_signature_length
○0≦Cluster_ID<U_cluster_numである、U_Clusterと名付けられたマスタインデックステーブル内の二次元ベクトルの各U_Cluster[Cluster_ID][0]要素は、U_signature_sizeのビット整数のシーケンスとして復号化される。
●固定のシグネチャ長の場合、読み取られる整数の数は以下のようになる。
【数１】
2019537172.tif 000009
ここで、ｃｅｉｌ関数は、引数以上の最小の整数を返す。
図８に、固定長シグネチャの復号化を示す。
●可変のシグネチャ長の場合、デコーダは、所与のシグネチャの整数の読み取りを停止するために、２進法表示でターミネータ記号を含む最初の整数を検出する。例を図９に示す。
・0<Cluster_D<U_cluster_numを有する、U_Clusterと名付けられたマスタインデックステーブルの２次元ベクトルの各U_Cluster[Cluster_ID][1]要素は、対応するシグネチャに属するクラスタに属するシーケンスリードをコード化する記述子の各ブロックのアクセスユニットにおける最初のバイトのオフセットをバイトで表す符号なしの整数のベクトルを含む。このようなオフセットは、データセットペイロードの最初のバイト（０から始まる）に関して表現される。
【００９６】
コード化装置
図１１は、本発明の原理によるコード化装置１１１５を示す。コード化装置１１１５は、例えばゲノムシーケンシング装置１１０によって生成された、生シーケンスデータ１１１を入力として受け取る。ゲノムシーケンシング装置１１０は、Ｉｌｌｕｍｉｎａ  ＨｉＳｅｑ  ２５００、Ｔｈｅｒｍｏ−Ｆｉｓｈｅｒ  Ｉｏｎ  Ｔｏｒｒｅｎｔ装置又はＯｘｆｏｒｄ  Ｎａｎｏｐｏｒｅ  ＭｉｎｌＯＮのように当技術分野において公知である。生シーケンスデータ１１１はリードクラスタリングユニット１１２に供給され、リードクラスタリングユニット１１２は、クラスタシグネチャと呼ばれるヌクレオチドの共通のシーケンスまたは部分シーケンスを共有するリードをクラスタリングすることによって、コード化のためのシーケンスを準備する。クラスタリングされたシーケンスリードは、その後、記述子エンコーダ１１５によって記述子と名付けられた構文要素に関して表現される。クラスタリングユニット１１２によって生成されたクラスタシグネチャ１１４は、シグネチャエンコード化ユニット１１６によってコード化される。記述子エンコーダ１１５によって生成されたゲノム記述子１１８は、その後エントロピーコード化され、ゲノムアクセスユニット１１１１として構成される。２値化されたシグネチャ１１７及びグローバルパラメータであるゲノムデータセットヘッダ、及びゲノムデータセットヘッダとＭＩＴ生成器１１９によって生成されたマスタインデックステーブル１１１２である。ゲノムアクセスユニット１１１１、ゲノムデータセットヘッダ及びマスタインデックステーブルは、その後、多重化ビットストリーム１１１４に多重化される。
【００９７】
コード化装置１１１５は、マッピングされていないリードがコード化され、コード化された整列されたリードと多重化される、図１２に示されるより大きなコード化装置１２１０の一部であり得る。図１２は、本発明の原理によるコード化装置１２１０を示す。コード化装置１２１０は、例えばゲノムシーケンス決定装置１２０によって生成された、生シーケンスデータ１２１を入力として受信する。ゲノムシーケンシング装置１２０は、Ｉｌｌｕｍｉｎａ  ＨｉＳｅｑ  ２５００、Ｔｈｅｒｍｏ−Ｆｉｓｈｅｒ  Ｉｏｎ  Ｔｏｒｒｅｎｔ装置又はＯｘｆｏｒｄ  Ｎａｎｏｐｏｒｅ  ＭｉｎｌＯＮなど、当技術分野において公知である。生シーケンスデータ１２１はアライナユニット１２２に供給され、アライナユニット１２２はリードをリファレンスシーケンス１２２０にアラインすることによってコード化のためのシーケンスを準備する。アラインメントユニット１２２によってアラインメントできないシーケンスリードは、マッピングされていないシーケンスリード（Ｃｌａｓｓ  Ｕデータ）として分類される。マッピングされていないシーケンスリードエンコーダ１１１５の内部アーキテクチャおよび内部動作は、前の段落で説明されており、図１１に示されている。整列ユニット１２２によって生成された整列されたシーケンスは、その後、データ分類モジュール１２４によって分類される。次に、データクラス１２８は、その後、記述子エンコーダ１２５〜１２７に供給される。次いで、ゲノム記述子ストリーム１２１１は、記述子ストリームによってもたらされるデータ又はメタデータの統計的特性に従って記述子をコード化する算術コード化装置１２１２〜１２１４に供給される。結果は、多重化ユニット１２１６によって単一のビットストリームに多重化された１つ以上のゲノムストリーム１２１５である。
【００９８】
復号化装置
図１３は、本開示の原理による復号化装置１３１３を示す。デマルチプレクスユニット１３２は、ネットワークまたは記憶素子から多重化したビットストリーム１３１を受信し、ゲノムデータセットヘッダ及びマスタインデックステーブル１３３ならびにゲノムアクセスユニット１３４を抽出する。復号化装置１３１３は、ゲノムデータセットヘッダ及びマスタインデックステーブル１３３を受信する。次いで、ゲノムアクセスユニット１３４は、それぞれをゲノムデータセットヘッダ、ＭＩＴパーサ１３５、およびエントロピーデコーダ１３６に供給する。次いで、ゲノムデータセットヘッダ及びＭＩＴパーサ１３５によって抽出されたコード化されたクラスタシグネチャ１３７は、シグネチャデコーダ１３９によって復号されてクラスタシグネチャ１３１１を生成する。ゲノム記述子ストリーム１３８は、デスクリプタデコーダ１３１０に供給され、記述子を生シーケンスリード、マッピングされていないシーケンスシーケンスリード及び整列されていないシーケンスリード１３１２にさらに復号化する。
【００９９】
図１４は、上記および図１３に示したクラスＵデコーダがいかにしてゲノムシーケンスリードのより大きなデコーダの一部となり得るかを示す。図１４は、本開示の原理による復号化装置１４８を示す。ストリームデマルチプレクサ１４０は、ネットワーク又は記憶素子から多重化されたゲノムビットストリーム１４１０を受信し、個別のゲノムビットストリーム１４１を生成し、次にエントロピーデコーダ１４２〜１４４に供給され、ゲノム記述子ストリーム１４５を生成する。生シーケンスリード、マッピングされていないシーケンスシーケンスリード及び整列されていないシーケンスリード（Ｃｌａｓｓ  Ｕ）１４１２をコード化するアクセスユニットを含むビットストリームは、上述され図１３に示されている生シーケンスリード、マッピングされていないシーケンスリード及び整列されていないシーケンスリード１３１３を含むアクセスユニットのデコーダに供給される。抽出されたゲノム記述子ストリーム１４５は、記述子デコーダ１４６〜１４７に供給され、さらに記述子をゲノムデータのＣｌａｓｓに分類する。クラスデコーダ１４９はさらにゲノム記述子１４１１を処理し、その結果をマージして圧縮していない整列したシーケンスリードを生成する。
【０１００】
クラスデコーダ１４９は、１つまたは複数のゲノムによってもたらされる元のリファレンスシーケンスに関する情報を活用することによって元のゲノムシーケンスを再構築することができる。リファレンスシーケンスがゲノムストリームによって輸送されない場合、それらはデコード側で利用可能でなければならず、クラスデコーダによってアクセス可能でなければならない。
【０１０１】
本明細書に開示されている本発明の技術は、ハードウェア、ソフトウェア、ファームウェア又はそれらの任意の組み合わせで実施することができる。ソフトウェアで実施されるとき、これらはコンピュータ媒体に格納され、ハードウェア処理装置によって実行されてもよい。ハードウェア処理ユニットは、１つ以上のプロセッサ、デジタル信号プロセッサ、汎用マイクロプロセッサ、特定用途向け集積回路、又は他の個別論理回路を備えることができる。
【０１０２】
本開示の技法は、携帯電話、デスクトップコンピュータ、サーバ、タブレット及び類似の装置を含む様々なデバイス又は装置において実施することができる。
【図１】
2019537172.tif 000010
【図２】
2019537172.tif 000011
【図３】
2019537172.tif 000012
【図４】
2019537172.tif 000013
【図５】
2019537172.tif 000014
【図６】
2019537172.tif 000015
【図７】
2019537172.tif 000016
【図８】
2019537172.tif 000017
【図９】
2019537172.tif 000018
【図１０】
2019537172.tif 000019
【図１１】
2019537172.tif 000020
【図１２】
2019537172.tif 000021
【図１３】
2019537172.tif 000022
【図１４】
2019537172.tif 000023
【図１５】
2019537172.tif 000024
【国際調査報告】
2019537172.tif 000025