(57)【要約】  ゲノムシーケンシング装置によって生成されたゲノムシーケンスデータを圧縮するための方法および装置である。シーケンスリードは、それらを既存のまたは構築されたリファレンスシーケンスにアライメントさせることによってコード化され、コード化プロセスは、リードのデータクラスへの分類と、それに続くゲノム記述子の多様な観点からの各クラスのコード化で構成される。同じ種類のゲノム記述子は、連続した変換段階、バイナリ化化及びエントロピーコード化を適用することにより圧縮されるブロックに編成される。特定のソースモデル及びエントロピーコーダは、各データクラス及び関連する各記述子で使用される。【選択図】図１３
2020510907.tif 000002
【特許請求の範囲】
【請求項１】
ヌクレオチドシーケンスのリードを含むゲノムシーケンスデータをコード化する方法であって、
前記リードを1つ以上のリファレンスシーケンスにアラインメントし、それによってシーケンスリードを作成し、
前記1つ以上のリファレンスシーケンスとの指定されたマッチング規則に従って前記アライメントされたリードを分類し、それによってアライメントリードのクラスを作成し、
前記分類されたアライメントリードを、構文要素の多重のブロックとしてコード化し、
構文要素の前記ブロックをヘッダ情報で構成し、それによって連続的なアクセスユニットを作成すること、を含み、
前記コード化は、ゲノム記述子をバイナリ化及びエントロピーコード化する、
ことを含む方法。
【請求項２】
前記コード化及びエントロピーコード化されたゲノム記述子は、コード化及びエントロピーコード化が異なる記述子に対して異なるようにされている、
請求項１に記載の方法。
【請求項３】
前記記述子は、
リファレンスシーケンスのリードのマッピング位置をシグナリングするためのｐoｓ、
アライナがマッピングロセスの結果をさらに指定できるようにするために、リードがマッピングフラグにマッピングされたＤＮＡ又はＲＮＡ鎖をシグナリングするためのｒｃｏｍｐを含む、
請求項２に記載の方法。
【請求項４】
以下の記述子：
リファレンスシーケンスに関してアライメントされたリードのミスマッチの位置をシグナリングするｍｍｐoｓ、
関連付けられた位置のリファレンスシーケンスに関するミスマッチの類型をシグナリングするｍｍｔｙｐe、
をコード化することをさらに含む、
請求項３に記載の方法。
【請求項５】
ソフト又はハードクリップされたヌクレオチドをシグナリングするためのクリップ記述子をコード化することをさらに含む、
請求項４に記載の方法。
【請求項６】
各コード化されたシーケンスリードの長さをシグナリングするためにｒｌeｎ記述子をコード化することをさらに含む、
請求項５に記載の方法。
【請求項７】
以下の記述子：
マッピング手順によって単一のリード又はペアリードに関連付けられたマルチプルマッピング位置をシグナリングするためのｍｍａｐ、
スプライスされたリードが存在することの識別をシグナリングするｍｓａｒ（すなわち、リードは、チャンクに分割された場合、リファレンスシーケンス上の単一の位置にマッピングされた単一の連続したリードとしてマッピングされた場合よりも、マッチング精度の高いマッピング位置を見つける）、
をコード化することをさらに含む、
請求項６に記載の方法。
【請求項８】
ｍｓｃｏｒｅ記述子をコード化して、ゲノムシーケンスリードアライナによって生成されるリード当たりのマッピング／アラインメントスコアをシグナリングすることをさらに含む、
請求項７に記載の方法。
【請求項９】
ペアエンドリードにおいて、前記リードがどのようにペアリングされるかを示すために前記ｐａｉｒ記述子をコード化することをされに含む、
請求項８に記載の方法。
【請求項１０】
前記リファレンスシーケンスのいずれの位置にもアライメントできなかったリードをシグナリングするためのｕｒｅａｄｓ記述子をコード化することをさらに含む、
請求項９に記載の方法。
【請求項１１】
指定されたマッチング精度で前記リファレンスシーケンスのどの位置にもマッピングできないシーケンスリードをコード化するために使用される前記記述子のサブセットを通知するために使用されるｔｔｙｐｅ記述子をコード化することをさらに含む、
請求項１０に記載の方法。
【請求項１２】
前記リードがどのリードグループに属するかを示すために、ｒｇｒｏｕｐ記述子をコード化することをさらに含む、
請求項１１に記載の方法。
【請求項１３】
以下の記述子：
コンティグとリファレンスシーケンス間のミスマッチの位置をシグナリングするためのｒｆｔｐ、ミスマッチの位置は特殊なターミネータ文字で終了し、
コンティグとリファレンスシーケンス間のミスマッチの類型をシグナリングするｒｆｔｔ、
をコード化することをさらに含む、
請求項１２に記載の方法。
【請求項１４】
前記ｐoｓ記述子は、二重切捨単項コード又は単一の二重切捨単項コードを使用してバイナリ化され、
前記ｒｃoｍｐ記述子は、切捨単項コードを使用してバイナリ化され、
前記マッピングのｆｌａｇｓ記述子は、バイナリコード化を使用してバイナリ化される、
請求項１３に記載の方法。
【請求項１５】
リファレンスシーケンスに関するアライメントされたリードのミスマッチの位置をシグナリングするための前記ｍｍｐｏｓ記述子は、分割ユニットごとに切捨単項コードを使用してバイナリ化され、
関連する位置のリファレンスシーケンスに関してミスマッチの類型をシグナリングするための前記ｍｍｔｙｐｅ記述子は切捨単項コードを使用してバイナリ化される、
請求項４に記載の方法。
【請求項１６】
ソフト又はハードのクリップされたヌクレオチドをシグナリングするための前記クリップ記述子は、符号付き切捨指数ゴロム、切捨単項、符号付き指数ゴロム及びバイナリコードの連結を使用してバイナリ化される、
請求項５に記載の方法。
【請求項１７】
各コード化されたシーケンスリードの長さをシグナリングする前記ｒｌｅｎ記述子は、分割ユニットワイズ切捨単項コードを使用してバイナリ化される、
請求項６に記載の方法。
【請求項１８】
マッピング手順によって単一のリード又はリードペアに関連付けられたマルチプルマッピング位置をシグナリングするための前記ｍｍａｐ記述子は、分割ユニットワイズ切捨単項コードを使用してバイナリ化され、
前記スプライスされたリードの存在の識別をシグナリングするための前記ｍｓａｒ記述子は、符号付き指数ゴロムコードを使用してバイナリ化される、
請求項７に記載の方法。
【請求項１９】
ゲノムシーケンスリードアライナによって生成された各リードのマッピング／アライメントスコアをシグナリングする前記ｍｓｃｏｒｅ記述子は、切捨単項コードを使用してバイナリ化される、
請求項８に記載の方法。
【請求項２０】
前記ｐａｉｒ記述子をシグナリングするために、ペアエンドリードの場合において、どのようにリードがペア化されたかは、バイナリコードと分割ユニットワイズ切捨単項コードの連結を使用してバイナリ化する、
請求項９に記載の方法。
【請求項２１】
前記リファレンスシーケンスのいずれの位置にもアライメントすることができなかったリードのシグナリングに対する前記ｕｒｅａｄｓ記述子は、切捨単項コードを使用してバイナリ化される、
請求項１０に記載の方法。
【請求項２２】
前記ｒｔｙｐｅ記述子は、指定されたマッチング精度で前記リファレンスシーケンスの任意の位置にマッピングすることができないシーケンスリードをコード化するために使用される前記記述子のサブセットの信号をシグナリングするために使用され、切捨単項コードを使用してバイナリ化される、
請求項１１に記載の方法。
【請求項２３】
前記リードがどのリードグループが属するかをシグナリングするｒｇｒｏｕｐ記述子は、切捨単項コードを用いてバイナリ化される、
請求項１２に記載の方法。
【請求項２４】
前記ｒｆｔｐ記述子は、コンティグとリファレンスシーケンスとの間のミスマッチの位置をシグナリングするために、バイナリコード化と分割ユニットワイズ切捨単項コードの連結を用いてバイナリ化され、
コンティグとリファレンスシーケンスの間のミスマッチのタイプをシグナリングするための前記ｒｆｔｔ記述子は、バイナリコード化と切捨単項コードの連結を使用してバイナリ化される、
請求項１３に記載の方法。
【請求項２５】
前記記述子は、構成パラメータを構文ヘッダに挿入することによってコード化される、
請求項１３に記載の方法。
【請求項２６】
前記構成パラメータは、構文ヘッダがコード化されたゲノムファイルに追加されて更新されることによって更新される、
請求項２５に記載の方法。
【請求項２７】
前記構成パラメータは、コード化パラメータを参照してアクセスユニット内でコード化されたデータの種類をシグナリングするためのデータセットタイプを含む、
請求項２６に記載の方法。
【請求項２８】
前記構成パラメータは、リード長が一定の場合に、シーケンスリードのヌクレオチド長をシグナリングするためのリード長をさらに含む、
請求項２７に記載の方法。
【請求項２９】
前記構成パラメータは、各コード化されたヌクレオチドに関する品質値の数をシグナリングするための品質値深度パラメータをさらに含む、
請求項２８に記載の方法。
【請求項３０】
前記構成パラメータは、各コード化されたアライメントに関連するアライメントスコアの数をシグナリングするためのアライメントスコア深度をさらに含む、
請求項２９に記載の方法。
【請求項３１】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルのバイト単位のサイズをシグナリングするためのターミネータサイズをさらに含む、
請求項３０に記載の方法。
【請求項３２】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルの値をシグナリングするためのターミネータ値をさらに含む、
請求項３１に記載の方法。
【請求項３３】
前記構成パラメータは、前記構成パラメータを参照して全てのアクセスユニット内でコード化されたデータクラスの数をシグナリングするためのクラスの数をさらに含む、
請求項３２に記載の方法。
【請求項３４】
前記構成パラメータは、本開示で定義された前記データクラスに関連付けられた識別子（Ｐ、Ｎ、Ｍ、Ｉ、ＨＭ、Ｕ）をシグナリングするクラス識別子をさらに含む、
請求項３３に記載の方法。
【請求項３５】
前記構成パラメータは、前記構成パラメータを参照して、アクセスユニットに含まれる記述子の総数をシグナリングするための記述子の数をさらに含む、
請求項３４に記載の方法。
【請求項３６】
前記構成パラメータは、本開示で定義されたコード化モードをシグナリングするためのコード化モード識別子をさらに含む、
請求項３５に記載の方法。
【請求項３７】
前記構成パラメータは、現在のコード化パラメータを参照する全てのアクセスユニットに存在する前記ｒｇｒoｕｐ記述子の異なる値の数をシグナリングするためのグループ数パラメータをさらに含む、
請求項３６に記載の方法。
【請求項３８】
前記構成パラメータは、１つ以上のリードグループ識別子をシグナリングするための１つ以上のグループ名パラメータをさらに含む、
請求項３７に記載の方法。
【請求項３９】
前記構成パラメータは、前記アクセスユニット内のマルチプルアライメントの存在をシグナリングするためのマルチプルアライメントフラグをさらに含む、
請求項３８に記載の方法。
【請求項４０】
前記構成パラメータは、前記アクセスユニット内のスプライスされたリードの存在をシグナリングするためのスプライスされたリードフラグをさらに含む、
請求項３９に記載の方法。
【請求項４１】
前記構成パラメータは、マッピングされていないシーケンスリード（クラスＵ）を含むアクセスユニット内の複数のシグネチャの使用をシグナリングするためのマルチプルシグネチャ塩基フラグをさらに含む、
請求項４０に記載の方法。
【請求項４２】
前記構成パラメータは、コード化されたシグネチャを表す各整数のビット単位のサイズをシグナリングするためのシグネチャサイズをさらに含む、
請求項４１に記載の方法。
【請求項４３】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの指数部をコード化するために使用されるビット数をシグナリングするためのスコア指数パラメータをさらに含む、
請求項４２に記載の方法。
【請求項４４】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの仮数部分をコード化するために使用されるビット数をシグナリングするためのスコア仮数パラメータをさらに含む、
請求項４３に記載の方法。
【請求項４５】
ヌクレオチドシーケンスのリードを含むゲノムシーケンスデータのコード化されたゲノムデータをデコード化する方法であって、
ヘッダ情報を用いてゲノム記述子のマルチプルブロックを抽出して前記コード化されたゲノムデータを含むアクセスユニットを解析し、前記マルチプルブロックをデコード化することを含み、
前記マルチプルブロックのデコード化は、１つ以上のリファレンスシーケンスに関する分類を定義する特定のマッチング規則に従ってアライメントされたリードを抽出するために、ゲノム記述子をデコード化及びバイナリ化解除することを含む、
方法。
【請求項４６】
前記記述子は、
リファレンスシーケンス上のリードのマッピング位置をシグナリングするためのｐｏｓ記述子、
アライナがマッピングロセスの結果をさらに指定できるようにするために、リードがマッピングフラグにマッピングされたＤＮＡ又はＲＮＡ鎖をシグナリングするためのｒｃｏｍｐ記述子を含む、
請求項４５に記載の方法。
【請求項４７】
以下の記述子：
リファレンスシーケンスに関してアライメントされたリードのミスマッチの位置をシグナリングするｍｍｐoｓ、
関連付けられた位置のリファレンスシーケンスに関するミスマッチの類型をシグナリングするｍｍｔｙｐe、
をデコード化することをさらに含む、
請求項３に記載の方法。
【請求項４８】
ソフト又はハードクリップされたヌクレオチドをシグナリングするためのクリップ記述子をデコード化することをさらに含む、
請求項４７に記載の方法。
【請求項４９】
各コード化されたシーケンスリードの長さをシグナリングするためにｒｌeｎ記述子をコデード化することをさらに含む、
請求項４８に記載の方法。
【請求項５０】
以下の記述子：
マッピング手順によって単一のリード又はペアリードに関連付けられたマルチプルマッピング位置をシグナリングするためのｍｍａｐ、
スプライスされたリードが存在することの識別をシグナリングするｍｓａｒ（すなわち、リードは、チャンクに分割された場合、リファレンスシーケンス上の単一の位置にマッピングされた単一の連続したリードとしてマッピングされた場合よりも、マッチング精度の高いマッピング位置を見つける）、
をデコード化することをさらに含む、
請求項４９に記載の方法。
【請求項５１】
ｍｓｃｏｒｅ記述子をデコード化して、ゲノムシーケンスリードアライナによって生成されるリード当たりのマッピング／アラインメントスコアをシグナリングすることをさらに含む、
請求項５０に記載の方法。
【請求項５２】
ペアエンドリードにおいて、前記リードがどのようにペアリングされるかを示すために前記ｐａｉｒ記述子をデコード化することをされに含む、
請求項５１に記載の方法。
【請求項５３】
前記リファレンスシーケンスのいずれの位置にもアライメントできなかったリードをシグナリングするためのｕｒｅａｄｓ記述子をデコード化することをさらに含む、
請求項５１に記載の方法。
【請求項５４】
指定されたマッチング精度で前記リファレンスシーケンスのどの位置にもマッピングできないシーケンスリードをコード化するために使用される前記記述子のサブセットを通知するために使用されるｔｔｙｐｅ記述子をデコード化することをさらに含む、
請求項５３に記載の方法。
【請求項５５】
前記リードがどのリードグループに属するかを示すために、ｒｇｒｏｕｐ記述子をデコード化することをさらに含む、
請求項５４に記載の方法。
【請求項５６】
以下の記述子：
コンティグとリファレンスシーケンス間のミスマッチの位置をシグナリングするためのｒｆｔｐ、ミスマッチの位置は特殊なターミネータ文字で終了し、
コンティグとリファレンスシーケンス間のミスマッチの類型をシグナリングするｒｆｔｔ、
をデコード化することをさらに含む、
請求項５５に記載の方法。
【請求項５７】
前記記述子は、構文ヘッダから構成パラメータを抽出することによりデコード化される、
請求項５６に記載の方法。
【請求項５８】
前記構成パラメータは、コード化パラメータを参照してアクセスユニット内でコード化されたデータの種類をシグナリングするためのデータセットタイプ
を含む、
請求項５７に記載の方法。
【請求項５９】
前記構成パラメータは、リード長が一定の場合に、シーケンスリードのヌクレオチド長をシグナリングするためのリード長をさらに含む、
請求項２８に記載の方法。
【請求項６０】
前記構成パラメータは、各コード化されたヌクレオチドに関する品質値の数をシグナリングするための品質値深度パラメータをさらに含む、
請求項５９に記載の方法。
【請求項６１】
前記構成パラメータは、各コード化されたアライメントに関連するアライメントスコアの数をシグナリングするためのアライメントスコア深度をさらに含む、
請求項６０に記載の方法。
【請求項６２】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルのバイト単位のサイズをシグナリングするためのターミネータサイズをさらに含む、
請求項６１に記載の方法。
【請求項６３】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルの値をシグナリングするためのターミネータ値をさらに含む、
請求項６２に記載の方法。
【請求項６４】
前記構成パラメータは、前記構成パラメータを参照して全てのアクセスユニット内でコード化されたデータクラスの数をシグナリングするためのクラスの数をさらに含む、
請求項６３に記載の方法。
【請求項６５】
前記構成パラメータは、本開示で定義された前記データクラスに関連付けられた識別子（Ｐ、Ｎ、Ｍ、Ｉ、ＨＭ、Ｕ）をシグナリングするクラス識別子をさらに含む、
請求項６４に記載の方法。
【請求項６６】
前記構成パラメータは、前記構成パラメータを参照するアクセスユニットに含まれる記述子の総数をシグナリングするための記述子の数をさらに含む、
請求項６５に記載の方法。
【請求項６７】
前記構成パラメータは、本開示で定義されたコード化モードをシグナリングするためのコード化モード識別子をさらに含む、
請求項６６に記載の方法。
【請求項６８】
前記構成パラメータは、現在のコード化パラメータを参照する全てのアクセスユニットに存在する前記ｒｇｒoｕｐ記述子の異なる値の数をシグナリングするためのグループ数パラメータをさらに含む、
請求項６７に記載の方法。
【請求項６９】
前記構成パラメータは、１つ以上のリードグループ識別子をシグナリングするための１つ以上のグループ名パラメータをさらに含む、
請求項６８に記載の方法。
【請求項７０】
前記構成パラメータは、前記アクセスユニット内のマルチプルアライメントの存在をシグナリングするためのマルチプルアライメントフラグをさらに含む、
請求項６９に記載の方法。
【請求項７１】
前記構成パラメータは、前記アクセスユニット内のスプライスされたリードの存在をシグナリングするためのスプライスされたリードフラグをさらに含み、ここで０に設定されるとスプライスされたリードは存在しない、
請求項７０に記載の方法。
【請求項７２】
前記構成パラメータは、マッピングされていないシーケンスリード（クラスＵ）を含むアクセスユニット内の複数のシグネチャの使用をシグナリングするためのマルチプルシグネチャ塩基フラグをさらに含む、
請求項７１に記載の方法。
【請求項７３】
前記構成パラメータは、コード化されたシグネチャを表す各整数のビット単位のサイズをシグナリングするためのシグネチャサイズをさらに含む、
請求項７２に記載の方法。
【請求項７４】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの指数部をコード化するために使用されるビット数をシグナリングするためのスコア指数パラメータをさらに含む、
請求項７３に記載の方法。
【請求項７５】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの仮数部分をコード化するために使用されるビット数をシグナリングするためのスコア仮数パラメータをさらに含む、
請求項７４に記載の方法。
【請求項７６】
請求項１に記載のコード化方法を実施するためのコード化手段を備えるコード化装置。
【請求項７７】
請求項３１に記載のデコード化方法を実施するためのデコード手段を備えるデコード化装置。
【請求項７８】
請求項１３に記載のゲノム記述子を含むファイルフォーマット。
【請求項７９】
請求項１に記載のコード化方法を実行するための命令を含むコンピュータプログラム。
【請求項８０】
請求項３１に記載のデコード化方法を実行するための命令を含むコンピュータプログラム。
【請求項８１】
請求項1のコンピュータプログラムを保存するためのストレージ手段。
【請求項８２】
請求項１のコード化方法で作成されたファイルを保存するためのストレージ手段。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、既知の従来技術の表現方法では利用できない新しい機能を提供することにより、利用される記憶領域を削減し、アクセス性能を改善するゲノムシーケンシングデータの新しい表現方法を提供する。
［関連出願の相互参照］
【０００２】
本出願は、２０１７年７月１１日に出願されたＰＣＴ／ＵＳ２０１７／０４１５７９及び２０１７年２月１４日に出願されたＰＣＴ／ＵＳ１７／１７８４２の優先権及びその利益を主張する。
【背景技術】
【０００３】
ゲノムシーケンシングデータの適切な表示は、シーケンシングデータ及びメタデータを処理することによって、様々な目的で実施されるゲノム変異体の呼び出し、及び他の全ての分析等の効率的なゲノム分析アプリケーションを可能にするための基本である。    
【０００４】
ヒトゲノムのシーケンシングは、高スループットで低コストのシーケンシング技術の出現により安価になった。このような機会は、癌の診断及び治療から遺伝性疾患の同定に至るまで、抗体の同定のための病原体サーベイランスから、新しいワクチン、薬物、及び個別化された治療のカスタマイズに至るまで、いくつかの分野における新しい展望を開くものである。
【０００５】
病院、ゲノミクスデータ分析プロバイダー、バイオインフォマティクス、及び大規模な生物データ保存センターは、ゲノム医療を世界規模にスケールアップすることを可能にする、安価で、迅速で、信頼性があり、相互接続されたゲノム情報処理ソリューションを探している。シーケンシングプロセスにおけるボトルネックの一つがデータの記憶になっており、圧縮形式でゲノムシーケンシングデータを表現する方法が益々研究されている。
【０００６】
シーケンシングデータの最もよく使用されるゲノム情報の表示は、ＦＡＳＱ及びＳＡＭ形式の圧縮に基づいている。その目的は、従来から使用されているファイル形式（アライメントされていないデータとアライメントされたデータについては、それぞれＦＡＳＴＱ及びＳＡＭを使用）を圧縮することである。このようなファイルは、プレーンテキスト文字で構成され、ＬＺ（LempelとZiv、最初の版を出版した作成者）方式（よく知られたｚｉｐ、ｇｚｉｐ等）等の汎用アプローチを使用して、上述のように圧縮される。ｇｚｉｐ等の汎用喝圧縮方式を使用する場合、圧縮の結果は通常、バイナリデータの単一のかたまりとなっている。このようなモノリシック形式の情報は、特に高スループットシーケンスの場合のようにデータの量が非常に大きい場合、アーカイブ、転送、及び詳細化が非常に困難になる。ＢＡＭフォーマットは、ＳＡＭファイルによって伝達される実際のゲノム情報を抽出するよりもむしろ非効率的で、冗長なＳＡＭフォーマットの圧縮に焦点を当て、そして各データソースの特定の性質を利用するよりもむしろｇｚｉｐのような汎用テキストの圧縮アルゴリズムを採用するために、低い圧縮性能によって特徴付けられている（ゲノムデータ自体）。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
あまり使用されていないが、ＢＡＭよりも効率的なゲノムデータの圧縮へのより洗練されたアプローチはＣＲＡＭである。ＣＲＡＭは、リファレンス（データソースの冗長性を部分的に利用する）に関する微分コード化を採用するためのより効率的な圧縮を提供するが、増分更新、ストリーミングのサポート、及び特定クラスの圧縮データへの選択的アクセス等の機能を依然として欠いている。
【０００８】
これらのアプローチでは、圧縮率が低く、圧縮されるとナビゲートや操作が困難なデータ構造が生成される。簡単な操作を行うため、又はゲノムデータセットの選択された領域にアクセスするためにさえ、大きくて堅固なデータ構造を処理する必要があるため、下流の分析は非常に遅くなる可能性がある。ＣＲＡＭは、ＣＲＡＭレコードの概念に依存する。各ＣＲＡＭレコードは、再構築に必要な全ての要素をコード化することによって、単一のマッピング済みのリード又はマッピングされていないリードを表す。
【０００９】
ＣＲＡＭには、本明細書に記載されている発明によって解決及び克服される、次の欠点と制約がある：
１．ＣＲＡＭは、特定の機能を共有するデータインデックスとデータサブセットへのランダムアクセスをサポートしていない。データのインデックスは仕様の範囲外であり（ＣＲＡＭの仕様ｖ．３．０のセクション１２を参照）、別のファイルとして実装される。対照的に、本明細書に記載されている本発明のアプローチは、コード化プロセスと統合されたデータ索引方法を採用し、コード化された（すなわち圧縮された）ビットストリームに索引が埋め込まれている。
２．ＣＲＡＭは、あらゆる種類のマッピングされたリード（完全に一致するリード、置換のみを伴うリード、挿入又は削除を伴うリード（「インデル（indels）」とも呼ばれる））を含むことができるコアデータブロックによって構築される。リファレンスシーケンスに関するマッピングの結果に従って、データの分類やクラス内のリードのグループ化の概念は無い。これは、特定の機能を持つリードのみが検索される場合でも、全てのデータを検査する必要があることを意味する。このような制約は、コード化の前にクラスでデータを分類及び分割する、本発明により解決される。
３．ＣＲＡＭは、各リードを「ＣＲＡＭレコード」にカプセル化するという概念に基づいている。これは、特定の生物学的特徴（例えば：置換を伴うが「インデル（indels）」を伴わないリード、又は完全にマッピングされたリード）によって特徴づけられるリードを検索する場合、それぞれ完全な版の「記録」を検査する必要性を意味する。
対照的に、本発明では、別々の情報ブロックに別々にコード化されたデータクラスの概念があり、各リードをカプセル化するレコードの概念はない。これにより、各（ブロックの）リードをデコード化してその特徴を検査することなく、特定の生物学的特性（例えば：置換を伴うが「インデル（indels）」を伴わないリード、又は完全にマッピングされたリード）を有するリードのセットへのより効率的なアクセスが可能になる。
４．ＣＲＡＭレコードでは、各レコードフィールドは特定のフラグに関連付けられ、各ＣＲＡＭレコードには異なる種類のデータを含めることができるため、コンテキストの概念がなく、各フラグは常に同じ意味を持つ必要がある。このコード化メカニズムは冗長な情報を導入し、効率的なコンテキストの塩基のエントロピーコード化の使用を妨げる。
これに対し、本発明では、データを示すフラグは、データが属する情報を「ブロック」によって本質的に定義されるので、データを示すフラグの概念は存在しない。これは、使用されるべきシンボルの数が大幅に減少し、その結果、より効率的な圧縮に帰着する情報ソースのエントロピーが減少することを意味する。このような改善が可能なのは、異なる「ブロック」を使用することにより、エンコーダが、コンテキストに応じて異なる意味を有する各ブロックにわたって同じシンボルを再利用することが可能になるためである。ＣＲＡＭでは、コンテキストの概念がなく、各ＣＲＡＭレコードに任意の種類のデータを含めることができるため、各フラグは常に同じ意味を持つ必要がある。
５．ＣＲＡＭの置換では、挿入と削除は異なる記述子、情報ソースのアルファベットのサイズを増加させ、より高い情報ソースのエントロピーをもたらすオプションを用いて表現される。対照的に、開示された発明のアプローチは、単一のアルファベットおよび置換、挿入および欠落のためのコード化を使用する。これはコード化とデコード化プロセスをより単純にし、コード化が高圧縮性能で特徴付けられるビットストリームを生じ、エントロピーの低いソースモデルを生成する。
【００１０】
本発明は、コード化されるべき冗長な情報が最小化され、選択的アクセス及び増分更新のためのサポートのような特徴が圧縮ドメイン内で直接的に可能となるように、シーケンシングデータを分類及び分割することによってゲノムシーケンスを圧縮することを目的とする。
【課題を解決するための手段】
【００１１】
以下の請求項の特徴は、ヌクレオチドシーケンスのリードを含むゲノムシーケンスデータをコード化する方法により、既存の従来技術の解決策の問題を解決するものであり、前記方法は、
前記リードを1つ以上のリファレンスシーケンスにアラインメントさせ、それによってシーケンスリードを作成し、
前記1つ以上のリファレンスシーケンスとの指定されたマッチング規則に従って前記アライメントされたリードを分類し、それによってアライメントリードのクラスを作成し、
前記分類されたアライメントリードを、構文要素のマルチプルブロックとしてコード化し、
構文要素の前記ブロックをヘッダ情報で構成し、それによって連続的なアクセスユニットを作成すること、を含み、
前記コード化は、前記ゲノム記述子をバイナリ化及びエントロピーコード化する、
ことを含む。
【００１２】
コード化方法の別の態様は、前記コード化及びエントロピーコード化されたゲノム記述子は、コード化及びエントロピーコード化が異なる記述子に対して異なるようにされている。
【００１３】
コード化方法の別の態様は、前記記述子として、
リファレンスシーケンスのリードのマッピング位置をシグナリング（signaling）するためのｐoｓ、
アライナがマッピングロセスの結果をさらに指定できるようにするために、リードがマッピングフラグにマッピングされたＤＮＡ又はＲＮＡ鎖をシグナリングするためのｒｃｏｍｐ、
を含む。
【００１４】
コード化方法の別の態様は、以下の記述子、
リファレンスシーケンスに関してアライメントされたリードのミスマッチの位置をシグナリングするためのｍｍｐoｓ、
前記関連付けられた位置のリファレンスシーケンスに関するミスマッチの類型をシグナリングするためのｍｍｔｙｐe、
をコード化することをさらに含む。
【００１５】
コード化方法の別の態様は、ソフト又はハードクリップされたヌクレオチドをシグナリングするためのクリップ記述子をコード化することをさらに含む。
【００１６】
コード化方法の別の態様は、各コード化されたシーケンスリードの長さをシグナリングするためにｒｌeｎ記述子をコード化することをさらに含む。
【００１７】
コード化方法の別の態様は、以下の記述子、
マッピング手順によって単一のリード又はペアリードに関連付けられたマルチプルマッピング位置をシグナリングするためのｍｍａｐ、
スプライスされたリードが存在することの識別をシグナリングするためのｍｓａｒ（すなわち、リードは、チャンクに分割された場合、リファレンスシーケンス上の単一の位置にマッピングされた単一の連続したリードとしてマッピングされた場合よりも、マッチング精度の高いマッピング位置を見つける）、
をコード化することをさらに含む。
【００１８】
コード化方法の別の態様は、ｍｓｃｏｒｅ記述子をコード化して、ゲノムシーケンスリードアライナによって生成されるリード当たりのマッピング／アラインメントスコアをシグナリングする、ことをさらに含む。
【００１９】
コード化方法の別の態様は、前記ペアエンドリードにおいて、前記リードがどのようにペアリングされるかを示すために前記ｐａｉｒ記述子をコード化することをされに含む。
【００２０】
コード化方法の別の態様は、前記リファレンスシーケンスのいずれの位置にもアライメントできなかったリードをシグナリングするためのｕｒｅａｄｓ記述子をコード化することをさらに含む。
【００２１】
コード化方法の別の態様は、指定されたマッチング精度で前記リファレンスシーケンスのどの位置にもマッピングできないシーケンスリードをコード化するために使用される前記記述子のサブセットを通知するために使用されるｔｔｙｐｅ記述子をコード化することをさらに含む。
【００２２】
コード化方法の別の態様は、前記リードがどのリードグループに属するかを示すために、ｒｇｒｏｕｐ記述子をコード化することをさらに含む。
【００２３】
コード化方法の別の態様は、以下の記述子、
コンティグとリファレンスシーケンス間のミスマッチの位置をシグナリングするためのｒｆｔｐ、ミスマッチの位置は特殊なターミネータ文字で終了し、
コンティグとリファレンスシーケンス間のミスマッチの類型をシグナリングするｒｆｔｔ、
をコード化することをさらに含む。
【００２４】
コード化方法の別の態様は、
前記ｐoｓ記述子は、二重切捨単項コード又は単一の二重切捨単項コードを使用してバイナリ化され、
前記ｒｃoｍｐ記述子は、切捨単項コードを使用してバイナリ化され、
前記マッピングのｆｌａｇｓ記述子は、バイナリコード化を使用してバイナリ化される。
【００２５】
コード化方法の別の態様は、
リファレンスシーケンスに関するアライメントされたリードのミスマッチの位置をシグナリングするための前記ｍｍｐｏｓ記述子は、分割ユニットごとに切捨単項コードを使用してバイナリ化され、
関連する位置のリファレンスシーケンスに関してミスマッチの類型をシグナリングするための前記ｍｍｔｙｐｅ記述子は切捨単項コードを使用してバイナリ化される。
【００２６】
コード化方法の別の態様は、ソフト又はハードのクリップされたヌクレオチドをシグナリングするための前記クリップ記述子は、符号付き切捨指数ゴロム、切捨単項、符号付き指数ゴロム及びバイナリコードの連結を使用してバイナリ化される
【００２７】
コード化方法の別の態様は、各コード化されたシーケンスリードの長さをシグナリングするための前記ｒｌｅｎ記述子は、分割ユニットワイズ切捨単項（Split Unit-wise Truncated Unary）コードを使用してバイナリ化される。
【００２８】
コード化方法の別の態様は、
マッピング手順によって単一のリード又はリードペアに関連付けられたマルチプルマッピング位置をシグナリングするための前記ｍｍａｐ記述子は、分割ユニットワイズ切捨単項（Split Unit-wise Truncated Unary）コードを使用してバイナリ化され、
前記スプライスされたリードの存在の識別をシグナリングするための前記ｍｓａｒ記述子は、符号付き指数ゴロム（Signed Exponential Golomb）コードを使用してバイナリ化される。
【００２９】
コード化方法の別の態様は、ゲノムシーケンスリードアライナによって生成された各リードのマッピング／アライメントスコアをシグナリングする前記ｍｓｃｏｒｅ記述子は、切捨単項（Truncated Unary）コードを使用してバイナリ化される。
【００３０】
コード化方法の別の態様は、前記ｐａｉｒ記述子をシグナリングするために、ペアエンドリードの場合において、どのようにリードがペア化されたかは、バイナリコードと分割ユニットワイズ切捨単項（Split Unit-wise Truncated Unary）コードの連結を使用してバイナリ化する。
【００３１】
コード化方法の別の態様は、前記リファレンスシーケンスのいずれの位置にもアライメントすることができなかったリードのシグナリングに対する前記ｕｒｅａｄｓ記述子は、切捨単項（Truncated Unary）コードを使用してバイナリ化される。
【００３２】
コード化方法の別の態様は、前記ｒｔｙｐｅ記述子は、指定されたマッチング精度で前記リファレンスシーケンスの任意の位置にマッピングすることができないシーケンスリードをコード化するために使用される前記記述子のサブセットの信号をシグナリングするために使用され、切捨単項（Truncated Unary）コードを使用してバイナリ化される。
【００３３】
コード化方法の別の態様は、前記リードがどのリードグループが属するかをシグナリングするｒｇｒｏｕｐ記述子は、切捨単項（Truncated Unary）コードを用いてバイナリ化される。
【００３４】
コード化方法の別の態様は、
前記ｒｆｔｐ記述子は、コンティグとリファレンスシーケンスとの間のミスマッチの位置をシグナリングするために、バイナリコード化と分割ユニットワイズ切捨単項（Split Unit-wise Truncated Unary）コードの連結を用いてバイナリ化され、
コンティグとリファレンスシーケンスの間のミスマッチのタイプをシグナリングするための前記ｒｆｔｔ記述子は、バイナリコード化と切捨単項（Truncated Unary）コードの連結を使用してバイナリ化される。
【００３５】
コード化方法の別の態様は、前記記述子は、構成パラメータを構文ヘッダに挿入することによってコード化される。
【００３６】
コード化方法の別の態様は、前記構成パラメータは、構文ヘッダがコード化されたゲノムファイルに追加されて更新されることによって更新される。
【００３７】
コード化方法の別の態様は、前記構成パラメータは、コード化パラメータを参照してアクセスユニット内でコード化されたデータの種類をシグナリングするためのデータセットタイプを含む。
【００３８】
コード化方法の別の態様は、前記構成パラメータは、リード長が一定の場合に、シーケンスリードのヌクレオチド長をシグナリングするためのリード長をさらに含む。
【００３９】
コード化方法の別の態様は、前記構成パラメータは、各コード化されたヌクレオチドに関する品質値の数をシグナリングするための品質値深度パラメータをさらに含む。
【００４０】
コード化方法の別の態様は、前記構成パラメータは、各コード化されたアライメントに関連するアライメントスコアの数をシグナリングするためのアライメントスコア深度をさらに含む。
【００４１】
コード化方法の別の態様は、前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルのバイト単位のサイズをシグナリングするためのターミネータサイズをさらに含む。
【００４２】
コード化方法の別の態様は、前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルの値をシグナリングするためのターミネータ値をさらに含む。
【００４３】
コード化方法の別の態様は、前記構成パラメータは、前記構成パラメータを参照して全てのアクセスユニット内でコード化されたデータクラスの数をシグナリングするためのクラスの数をさらに含む。
【００４４】
コード化方法の別の態様は、前記構成パラメータは、本開示で定義されたデータクラスに関連付けられた識別子（Ｐ、Ｎ、Ｍ、Ｉ、ＨＭ、Ｕ）をシグナリングするクラス識別子をさらに含む。
【００４５】
コード化方法の別の態様は、前記構成パラメータは、前記構成パラメータを参照して、アクセスユニットに含まれる記述子の総数をシグナリングするための記述子の数をさらに含む。
【００４６】
コード化方法の別の態様は、前記構成パラメータは、本開示で定義されたコード化モードをシグナリングするためのコード化モード識別子をさらに含む。
【００４７】
コード化方法の別の態様は、前記構成パラメータは、現在のコード化パラメータを参照する全てのアクセスユニットに存在する前記ｒｇｒoｕｐ記述子の異なる値の数をシグナリングするためのグループ数パラメータをさらに含む。
【００４８】
コード化方法の別の態様は、前記構成パラメータは、１つ以上のリードグループ識別子をシグナリングするための１つ以上のグループ名パラメータをさらに含む。
【００４９】
コード化方法の別の態様は、前記構成パラメータは、前記アクセスユニット内のマルチプルアライメントの存在をシグナリングするためのマルチプルアライメントフラグをさらに含む。
【００５０】
コード化方法の別の態様は、前記構成パラメータは、前記アクセスユニット内のスプライスされたリードの存在をシグナリングするためのスプライスされたリードフラグをさらに含む。０がセットされたときスプライスされたリードは存在しない。
【００５１】
コード化方法の別の態様は、前記構成パラメータは、マッピングされていないシーケンスリード（クラスＵ）を含むアクセスユニット内の複数のシグネチャの使用をシグナリングするためのマルチプルシグネチャ塩基フラグをさらに含む。
【００５２】
コード化方法の別の態様は、前記構成パラメータは、コード化されたシグネチャを表す各整数のビット単位のサイズをシグナリングするためのシグネチャサイズをさらに含む。
【００５３】
コード化方法の別の態様は、前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの指数部をコード化するために使用されるビット数をシグナリングするためのスコア指数パラメータをさらに含む。
【００５４】
コード化方法の別の態様は、前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの仮数部分をコード化するために使用されるビット数をシグナリングするためのスコア仮数パラメータをさらに含む。
【００５５】
本発明は、ヌクレオチドシーケンスのリードを含むゲノムシーケンスデータのコード化されたゲノムデータをデコード化する方法をさらに提供し、前記方法は、
ヘッダ情報を用いてゲノム記述子のマルチプルブロックを抽出して前記コード化されたゲノムデータを含むアクセスユニットを解析し、前記マルチプルブロックをデコード化することを含み、
前記マルチプルブロックのデコード化は、１つ以上のリファレンスシーケンスに関する分類を定義する特定のマッチング規則に従ってアライメントされたリードを抽出するために、ゲノム記述子をデコード化及びバイナリ化解除することを含む。
【００５６】
デコード化方法の別の態様は、前記記述子が、
リファレンスシーケンス上のリードのマッピング位置をシグナリングするためのｐｏｓ記述子、
アライナがマッピングロセスの結果をさらに指定できるようにするために、リードがマッピングフラグにマッピングされたＤＮＡ又はＲＮＡ鎖をシグナリングするためのｒｃｏｍｐ記述子、を含む。
【００５７】
デコード化方法の別の態様は、以下の記述子が：
リファレンスシーケンスに関してアライメントされたリードのミスマッチの位置をシグナリングするためのｍｍｐoｓ、
前記関連付けられた位置のリファレンスシーケンスに関するミスマッチの類型をシグナリングするためのｍｍｔｙｐe、
をデコード化することをさらに含む。
【００５８】
デコード化方法の別の態様は、ソフト又はハードクリップされたヌクレオチドをシグナリングするためのクリップ記述子をデコード化することをさらに含む。
【００５９】
デコード化方法の別の態様は、各コード化されたシーケンスリードの長さをシグナリングするためにｒｌeｎ記述子をコデード化することをさらに含む。
【００６０】
デコード化方法の別の態様は、以下の記述子が、
マッピング手順によって単一のリード又はペアリードに関連付けられたマルチプルマッピング位置をシグナリングするためのｍｍａｐ、
スプライスされたリードが存在することの識別をシグナリングするｍｓａｒ（すなわち、リードは、チャンクに分割された場合、リファレンスシーケンス上の単一の位置にマッピングされた単一の連続したリードとしてマッピングされた場合よりも、マッチング精度の高いマッピング位置を見つける）、
をデコード化することをさらに含む。
【００６１】
デコード化方法の別の態様は、ｍｓｃｏｒｅ記述子をデコード化して、ゲノムシーケンスリードアライナによって生成されるリード当たりのマッピング／アラインメントスコアをシグナリングすることをさらに含む。
【００６２】
デコード化方法の別の態様は、前記ペアエンドリードにおいて、前記リードがどのようにペアリングされるかを示すために前記ｐａｉｒ記述子をデコード化することをされに含む。
【００６３】
デコード化方法の別の態様は、前記リファレンスシーケンスのいずれの位置にもアライメントできなかったリードをシグナリングするためのｕｒｅａｄｓ記述子をデコード化することをさらに含む。
【００６４】
デコード化方法の別の態様は、指定されたマッチング精度で前記リファレンスシーケンスのどの位置にもマッピングできないシーケンスリードをコード化するために使用される前記記述子のサブセットを通知するために使用されるｔｔｙｐｅ記述子をデコード化することをさらに含む。
【００６５】
デコード化方法の別の態様は、前記リードがどのリードグループに属するかを示すために、ｒｇｒｏｕｐ記述子をデコード化することをさらに含む。
【００６６】
デコード化方法の別の態様は、以下の記述子が、
コンティグとリファレンスシーケンス間のミスマッチの位置をシグナリングするためのｒｆｔｐ、ミスマッチの位置は特殊なターミネータ文字で終了し、
コンティグとリファレンスシーケンス間のミスマッチの類型をシグナリングするためのｒｆｔｔ、
をデコード化することをさらに含む。
【００６７】
デコード化方法の別の態様は、前記記述子が、構文ヘッダから構成パラメータを抽出することによりデコード化される。
【００６８】
デコード化方法の別の態様は、前記構成パラメータは、コード化パラメータを参照してアクセスユニット内でコード化されたデータの種類をシグナリングするためのデータセットタイプを含む。
【００６９】
デコード化方法の別の態様は、前記構成パラメータは、リード長が一定の場合に、シーケンスリードのヌクレオチド長をシグナリングするためのリード長をさらに含む。
【００７０】
デコード化方法の別の態様は、前記構成パラメータは、各コード化されたヌクレオチドに関する品質値の数をシグナリングするための品質値深度パラメータをさらに含む。
【００７１】
デコード化方法の別の態様は、前記構成パラメータは、各コード化されたアライメントに関連するアライメントスコアの数をシグナリングするためのアライメントスコア深度をさらに含む。
【００７２】
デコード化方法の別の態様は、前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルのバイト単位のサイズをシグナリングするためのターミネータサイズをさらに含む。
【００７３】
デコード化方法の別の態様は、前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルの値をシグナリングするためのターミネータ値をさらに含む。
【００７４】
デコード化方法の別の態様は、前記構成パラメータは、前記構成パラメータを参照して全てのアクセスユニット内でコード化されたデータクラスの数をシグナリングするためのクラスの数をさらに含む。
【００７５】
デコード化方法の別の態様は、前記構成パラメータは、本開示で定義されたデータクラスに関連付けられた識別子（Ｐ、Ｎ、Ｍ、Ｉ、ＨＭ、Ｕ）をシグナリングするクラス識別子をさらに含む。
【００７６】
デコード化方法の別の態様は、前記構成パラメータは、前記構成パラメータを参照するアクセスユニットに含まれる記述子の総数をシグナリングするための記述子の数をさらに含む。
【００７７】
デコード化方法の別の態様は、前記構成パラメータは、本開示で定義されたコード化モードをシグナリングするためのコード化モード識別子をさらに含む。
【００７８】
デコード化方法の別の態様は、前記構成パラメータは、現在のコード化パラメータを参照する全てのアクセスユニットに存在する前記ｒｇｒoｕｐ記述子の異なる値の数をシグナリングするためのグループ数パラメータをさらに含む。
【００７９】
デコード化方法の別の態様は、前記構成パラメータは、１つ以上のリードグループ識別子をシグナリングするための１つ以上のグループ名パラメータをさらに含む。
【００８０】
デコード化方法の別の態様は、前記構成パラメータは、前記アクセスユニット内のマルチプルアライメントの存在をシグナリングするためのマルチプルアライメントフラグをさらに含む。
【００８１】
デコード化方法の別の態様は、前記構成パラメータは、前記アクセスユニット内のスプライスされたリードの存在をシグナリングするためのスプライスされたリードフラグをさらに含む。０に設定されるとスプライスされたリードは存在しない。
【００８２】
デコード化方法の別の態様は、前記構成パラメータは、マッピングされていないシーケンスリード（クラスＵ）を含むアクセスユニット内の複数のシグネチャの使用をシグナリングするためのマルチプルシグネチャ塩基フラグをさらに含む。
【００８３】
デコード化方法の別の態様は、前記構成パラメータは、コード化されたシグネチャを表す各整数のビット単位のサイズをシグナリングするためのシグネチャサイズをさらに含む。
【００８４】
デコード化方法の別の態様は、前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの指数部をコード化するために使用されるビット数をシグナリングするためのスコア指数パラメータをさらに含む。
【００８５】
デコード化方法の別の態様は、前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの仮数部分をコード化するために使用されるビット数をシグナリングするためのスコア仮数パラメータをさらに含む。
【００８６】
本発明は、前述のコード化方法の全ての態様を実施するためのコード化手段を備えるコード化装置をさらに提供する。
【００８７】
本発明は、前述のデコード化方法の全ての態様を実施するためのデコード化手段を備えるデコード化装置をさらに提供する。
【００８８】
本発明は、前述で定義されたゲノム記述子を含むファイル形式を提供する。
【００８９】
本発明は、前述のコード化方法の全ての態様を実行するための少なくとも１のプロセッサを実行させる命令を含むコンピュータ可読媒体をさらに提供する。
【００９０】
本発明は、前述のデコード化方法の全ての態様を実行するための少なくとも１のプロセッサを実行させる命令を含むコンピュータ可読媒体をさらに提供する。
【００９１】
本発明に、前述のコード化方法の全ての態様に従ってコード化されたゲノムを記憶するサポートデータをさらに提供する。
【発明の効果】
【００９２】
提案されるアプローチの一態様は、異なるブロックで構造化され、別々にコード化されたデータとメタデータのクラスの定義である。既存の方法に関するこのようなアプローチのより適切な改善は以下の通りである：
１．データ又はメタデータのクラスごとに効率的なソースモデルを提供することにより構成される情報ソースのエントロピーの減少による圧縮性能の向上；
２．圧縮されたデータ及びメタデータの一部に対して、圧縮されたドメイン内で直接、更なる処理目的のために選択的アクセスを行う可能性；
３．新しいシーケンシングデータ及び／又はメタデータ及び／又は特定のシーケンスリードのセットに関連する新しい解析結果を用いて、圧縮データおよびメタデータを増分的に（すなわち、デコード化と再コード化を必要としない）更新する可能性。
【図面の簡単な説明】
【００９３】
【図１】リードペアにおけるリード１とリード２の定義、及びマッピングされたリードにおける左端と右端のヌクレオチドの定義を示す。
【図２】アクセスユニットが、リファレンスシーケンスの連続した間隔でマッピングされたシーケンスリードを表す圧縮記述子をカプセル化する方法を示す。ヘッダ情報は、データ解析を有効にするために、圧縮された記述子の前に付加される。
【図３】タイプＰのアクセスユニットがヘッダと、リードマッピング位置（ｐｏｓ）、逆補完情報（ｒｃｏｍｐ）、ペアになったエンドリードの場合のペア情報（ｐａｉｒ）、可変長リードの場合のリード長（ｒｌｅｎ）、及びマッピングフラグ（ｆｌａｇｓ）を表す記述子のブロックの多重化によってどのように構成されるかを示す。クラスＰのリードをコード化するために使用される。
【図４】リードペアｎが位置Ｐｎにマッピングされ、リードペアｎ＋１が位置Ｐｍにマッピングされているマッピングされたリードペアのｐｏｓ記述子の計算を示す。
【図５】リファレンスシーケンスの一つの塩基の絶対マッピング位置を計算する方法を示す。
【図６】ペアエンドリードにおけるｒｃｏｍｐ記述子の使用を示す。
【図７】リードペアのミスマッチの位置を計算する方法の例を示す。
【図８】ゲノムレコード長とペアリング距離の計算方法を示す。
【図９】スプライシングを行わないマルチプルアラインメントを示す。左端のリードにはＮ個のアライメントがある。Ｎはデコード化されるべきｍｍａｐの第１の値であり、第１のリードのアラインメントの数を示す。ｍｍａｐ記述子の次のＮ個の値がデコード化され、第２番目のリードのアライメントの数であるＰを計算するために使用される。
【図１０】ｐｏｓ、ｐａｉｒ、及びｍｍａｐ記述子を使用して、スプライスなしでマルチプルアライメントをコード化する方法を示す。左端のリードには、Ｎ個のアライメントがある。
【図１１】スプライスを使用したマルチプルアライメントを示す。
【図１２】スプライスを使用したマルチプルアライメントを示す。ｐｏｓ、ｐａｉｒ、ｍｍａｐ及びｍｓａｒ記述子を使用して、スプライスを使用したマルチプルアラインメントを表す。
【図１３】ゲノムシーケンスをリファレンスゲノムに対してアライメントさせ、リファレンスゲノムに対してゲノムシーケンスを表す記述子を生成し、記述子の各ブロックを専用エントロピーエンコーダで圧縮する工程を含むエンコーダ装置を示す。
【図１４】エントロピーコード化記述子を抽出するために入力ビットストリームを逆多重化するステップと、各種類の記述子のエントロピーデコード化と、リファレンスゲノムを使用したアライメントされたシーケンスリードのデコード化とを含む、圧縮ビットストリームのデコード化プロセスを示す。
【図１５】クラスＮ、Ｍ及びＩのデータのコード化がしきい値のベクトルで構成され、Ｎ、Ｍ、及びＩのデータクラスの別々のサブクラスを生成する方法を示す。
【図１６】ハーフマッピングされたリードペア（ＨＭクラス）を使用して、長いコンティグとマッピングされていないリードをアセンブリして、リファレンスシーケンスの未知の領域を埋める方法を示す。
【図１７】リファレンス変換を適用してリードのミスマッチを削除する方法を示す。場合によっては、リファレンス変換は、変換が適用される前にリファレンスを参照するときに、新たなミスマッチを生成するか、又は見つけられたミスマッチの種類を変更することがある。
【図１８】ミスマッチの全て又はサブセットが除去された場合に、リファレンス変換がどのようにリードのクラスの所属先を変更できるかを示す（つまり、変換前のクラスＭに属するリードは、リードの変換が適用された後にクラスＰに割り当てられる）。
【図１９】全てのクラスのデータが、再コード化のために同じ変換をされたリファレンスを使用することができるか、又は各クラスＮ、Ｍ及びＩ又はそれらの組み合わせに異なる変換を使用する方法を示す。
【発明を実施するための形態】
【００９４】
本発明に係るゲノム又はプロテオミックシーケンスには、例えば、限定ではなく、ヌクレオチドシーケンス、デオキシリボ核酸（ＤＮＡ）シーケンス、リボ核酸（ＲＮＡ）、及びアミノ酸シーケンスが含まれる。本明細書の説明は、ヌクレオチドシーケンスの形式のゲノム情報に関してかなり詳細であるが、当業者によって理解されるように、いくつかのバリエーションがあり、圧縮のための方法及びシステムは、他のゲノム又はプロテオームシーケンスについても同様に適用できることが理解されるであろう。
【００９５】
ゲノムシーケンシング情報は、高スループットシーケンシング（ＨＴＳ）装置によって、規定された語彙からの文字列によって表されるヌクレオチドのシーケンス（「塩基」とも呼ばれる）の形で生成される。最小の語彙は５つの記号で表され：｛Ａ、Ｃ、Ｇ、Ｔ、Ｎ｝はＤＮＡに存在する４種類のヌクレオチド、すなわちアデニン、シトシン、グアニン、チミンを表す。ＲＮＡにおいてチミンはウラシル（Ｕ）に置換される。Ｎは、シーケンシング装置がいずれの塩基も呼び出せなかったとき、その位置の実際の性質が決定されていないことを示す。ＩＵＰＡＣ曖昧性コードがシーケンシング装置によって採用される場合、シンボルに使用されるアルファベットは（Ａ、Ｃ、Ｇ、Ｔ、Ｕ、Ｗ、Ｓ、Ｍ、Ｋ、Ｒ、Ｙ、Ｂ、Ｄ、Ｈ、Ｖ、Ｎ、又は−）である。
【００９６】
シーケンシング装置によって生成されたヌクレオチドの配列は「リード」と呼ばれる。シーケンスリードは、数十から数千ヌクレオチドの長さを有する。一部の技術では、１つのリードは１つのＤＮＡ鎖から、第２のリードは他の鎖から得られた「ペア」のシーケンスリードを生成する。ペアを生成するシーケンシング処理で別のリードに関連付けられたリードは、そのメイト（mate）と呼ばれる。
【００９７】
一連のマッチング規則に従って、リファレンスゲノムのセグメントと類似する領域を同定するために、シーケンスリードをアレンジ（arranging）するプロセスは、「アライメント」又は「マッピング」と呼ばれる。
【００９８】
本開示全体を通じて、リファレンスシーケンスは、それぞれ整数座標が単一のヌクレオチドに関連する、一次元整数座標系に関連するヌクレオチドシーケンスである。座標値は０以上でなければならない。本発明のコンテキストにおけるこの座標系は、ゼロベース（すなわち、最初のヌクレオチドは座標０をもち、位置０にあるという）であり、左から右へ直線的に増加する。リファレンスシーケンスは、シーケンシング装置によって生成されたヌクレオチド配列がアライメント／マッピングされる任意のシーケンスである。シーケンスの一例は、実際には、種の遺伝子セットの代表的な例として科学者によってアセンブリされたシーケンスである「リファレンスゲノム」であり得る。例えば、ＧＲＣｈ３７は、ゲノム・リファレンス・コンソーシアム・ヒューマン・ゲノム（Genome Reference Consortium human genome）（build 37）が、ニューヨーク州バッファローの１３人の匿名のボランティアから派生している。しかしながら、リファレンスシーケンスは、それらの更なる処理の観点からリードの圧縮性を単に改善するために考えられ構築された合成シーケンスで構成することもできる。
【００９９】
ゲノムシーケンスリードの圧縮への効率的なアプローチの一般的な要素は、リファレンスシーケンスに関するシーケンスデータの相互利用である。ヒト集団の体細胞プロファイルが極端に多様であっても、ヒトによって異なるヌクレオチド数の実際の部分は、ゲノム全体を構成する全ヌクレオチド数の約０．１％にすぎない。したがって、個々の個体を特徴づける特徴的なゲノム情報は、ゲノム全体に含まれる全情報に関して非常に限られている。既存のリファレンスゲノムが利用可能な場合、それが以前のシーケンシングのためのものであれ、公表された「平均」コンセンサスリファレンスとしてのものであれ、情報をコード化する現在の最も一般的な方法は、リファレンスゲノムに関する差異のみを同定し、コード化することである。
【０１００】
一般にＦＡＳＴＱデータファイルの形式で表される未加工のシーケンスリードでこれを行うための、リファレンスゲノムのマッピングは予備的な前処理ステップである。適切なリファレンスゲノムが利用できない場合、又は特定のリファレンスの使用によって導入されたバイアスが望ましくない場合には、手元にあるシーケンスリードをコンティグと呼ばれるより長いシーケンスにアセンブリされることにより構築される新たなリファレンスシーケンスは、可能な代替である。
【０１０１】
リファレンスシーケンス上のマッピングシーケンスリードの場合、そのリファレンスシーケンスは、左端の位置を位置０とする一次元座標系の軸として使用される。リファレンスシーケンスにマッピングされたリードシーケンスごとに、最小の座標番号で識別されるリファレンスシーケンスの位置にマッピングされたヌクレオチドは、通常「左端の」ヌクレオチドと呼ばれ、一方、最大の座標番号で識別されるリファレンスシーケンスの位置にマッピングされたヌクレオチドは、「右端の」ヌクレオチドと呼ばれる。これは図１に示されている。本開示を通して、ヌクレオチドは塩基とも呼ばれる。
【０１０２】
シーケンスリードがリファレンスシーケンスにマッピングされるとき、左端にマッピングされた塩基の座標は、リファレンスシーケンス上のリードのマッピング位置を表すと言われる。
【０１０３】
アライメントされたリードに存在し、リファレンスシーケンスには存在しない塩基（挿入（insertion）とも呼ばれる）、及びアライメントプロセスによって保存されるが、リファレンスシーケンス上にマッピングされない塩基は（ソフトクリップ（soft clips）とも呼ばれる）、マッピング位置を有しない。
【０１０４】
シーケンスリードが、指定されたマッチング規則に従って使用されたリファレンスシーケンスのマッピングされた位置にマップできない場合、そのシーケンスはマッピングされていないと呼ばれる。
【０１０５】
シーケンスリード間で重複する領域を探すことによって、より長いゲノムシーケンスを構築するプロセスは、アセンブリと呼ばれる。
【０１０６】
短いリードをアセンブリして構築された長いゲノムシーケンスはコンティグと呼ばれる（https://en.wikipedia.org/wiki/Contig参照）。
【０１０７】
アセンブリプロセス中にコンティグの構築に失敗したシーケンスリードは、アライメントされていない（unaligned）と呼ばれる。
【０１０８】
リファレンスゲノムは、１つ以上のリファレンスシーケンスから構成され、それは、種の遺伝子セットの代表的な例として科学者によってアセンブリされる。例えば、ＧＲＣｈ３７は、ゲノム・リファレンス・コンソーシアム・ヒューマン・ゲノム（Genome Reference Consortium human genome）（build 37）が、ニューヨーク州バッファローの１３人の匿名のボランティアから派生している。しかしながら、リファレンスシーケンスは、それらの更なる処理の観点からリードの圧縮性を改善するために考えられ、単に構築された合成シーケンスから成ることもできる。
【０１０９】
本開示において、リファレンスシーケンス上の最小座標上に塩基のマッピング（base mapping）を有するリードペアを構成するリードを「リード１」と呼び、そのメイトを「リード２」と呼ぶ。
【０１１０】
ヌクレオチド（又は塩基）の数として表される、ペアとして生成された２つのリードを分離する距離は、現在の技術の最新のシーケンシング技術を使用するシーケンシング装置において未知であり、それは、ペア（すなわち、適切なマッチング関数の最小化）を構成する両方のリードをリファレンスシーケンスにマッピングすることによって決定される。
【０１１１】
本開示全体を通じて、ゲノムレコードは、アラインメント情報、リード識別子、及び品質値に任意に関連した単一のシーケンスリード又はペアのシーケンスリードのいずれかをコード化するデータ構造である。
【０１１２】
本開示全体を通じて、アクセスユニット（ＡＵ）は、ビットストリームのアクセス及び操作を容易にするために、ゲノム情報又は関連するメタデータのコード化された表現を含む論理データ構造として定義される。これは、本開示に記載された本発明を実施するデコーディング装置によってデコード化できる最小のデータ編成である。
【０１１３】
コード化情報の種類に応じて、ＡＵは、他のＡＵとは独立してデコード化することも、他のＡＵｓに含まれる情報を用いてデコード化することもできる。
【０１１４】
ＡＵｓは、コード化されたシーケンスデータの性質に従って、多くの種類に分類することができる。アクセスユニットは、リファレンスシーケンス又はその一部、あるいは単一クラスのデータに属するコード化されたリード又はリードペアのいずれかを含む。１つのＡＵに２つ以上の種類のシーケンスデータを含めることはできない。例えば、アクセスユニットは、ゲノム・リファレンス・コンソーシアムのヒトゲノム（build 37）であるＧＲＣｈ３７の染色体１の全体が含まれる場合がある。別のアクセスユニットには、座標５０，０００と１５０，０００との間に位置するＧＲＣｈ３７の第１番染色体のヌクレオチドのコード化された表示を含むことができる。別のアクセスユニットには、リファレンスシーケンスに完全にマッピングされたリード又はリードペアのみが含まれ、ミスマッチは含まれない。別のアクセスユニットには、リファレンスシーケンスに対するミスマッチとして「Ｎ」個のシンボルのみを含むリード又はリードペアが含まれる場合がある。別のアクセスユニットには、任意の種類の置換を含むリード又はリードペアが含まれる場合がある（例えば、リード又はリードペアに存在する１つの塩基は、リファレンスシーケンスの対応するマッピング位置の塩基とは異なる）。別のアクセスユニットには、ミスマッチ、挿入、削除、及びソフトクリップされた塩基を含むリード又はリードペアが含まれる場合がある。別のアクセスユニットには、リファレンスシーケンスにマッピングされないリード又はリードペアのみが含まれる場合がある。別のアクセスユニットは、一方のリードがマッピングされ、他方のリードがリファレンスシーケンスにマッピングされないリードペアのみが含まれる場合がある。別の種類のアクセスユニットには、１つ以上のリファレンスシーケンス（染色体など）で構成されるリファレンスゲノムのコード化されたセグメントのみが含まれる場合がある。
【０１１５】
アクセスユニットの本質的な特徴は、それが表すリード又はリードペアのゲノム情報（シーケンスリード又はリードペア、リファレンスシーケンス）、関連するアラインメント情報及びメタデータを再構築するのに必要な全ての要素を圧縮形式で含むことである。換言すれば、アクセスユニットによって運ばれるリード、リードペア又はリファレンスシーケンス及び関連情報を完全に再構築するためには、アクセスユニット自体、及び該当する場合には、それが参照するリファレンスシーケンスを含むアクセスユニットを検索するだけでよい。
【０１１６】
各アクセスユニットでは、コード化されたリード又はリードのペアを表す、次のセクションに掲載された記述子は、高性能のエントロピーコード化を達成するためにそれらの同種の統計的特性を利用するために、別々のデータブロック（種類ごとに１つ）に集約される。
【０１１７】
各アクセスユニットは、リファレンスシーケンス上のゲノム領域にマッピングされた同じクラスに属するシーケンスリード又はリードペアを表す記述子の圧縮サブセットを含む。このようなリファレンスシーケンス上のゲノム領域は、開始座標（又は開始位置）及び終了座標（又は終了位置）によって定義される。
【０１１８】
アクセスユニットの例を図２及び図３に示す。アクセスユニットは、コード化されたゲノム記述子（次のセクションで説明する）のブロックによって構成される。ネットワーク上での転送を可能にするために、ブロックはさらにパケットに分解される。ゲノムシーケンスリードを圧縮する場合、各アクセスユニットは、リファレンスシーケンス上のゲノム区間にマッピングされたシーケンスリード又はマッピングされていないシーケンスリードのいずれかを表す圧縮記述子を含む。アクセスユニットを用いて、リファレンスゲノム又はその一部を伝送することができる。リファレンスシーケンスは、ヌクレオチドの単一の長いシーケンスとしてコードされることができ、又はマッピングされていないゲノムシーケンスリードとしてコード化されるより短いシーケンスに分割されることができる。
【０１１９】
本開示のコンテキストにおいて、以下の定義が適用される。
アクセスユニット開始位置：アクセスユニットに含まれる全てのゲノムレコードのうち、左端のゲノムレコード位置。
アクセスユニットの終了位置：アクセスユニットに含まれる全ゲノムレコードのマッピングされた全塩基の中で右端の塩基位置。
アクセスユニット範囲：アクセスユニットに含まれる全てのゲノムレコードのうち、アクセスユニット開始位置と右端のゲノムレコード位置の間に含まれるゲノム範囲。
アクセスユニットサイズ：アクセスユニットに含まれるゲノムレコードの数。
アクセスユニットカバー領域：アクセスユニット開始位置とアクセスユニット終了位置の間に含まれるゲノム範囲。
【０１２０】
本開示のコンテキストにおいて、１つ以上のアクセスユニットは、ゲノムデータセットと呼ばれる構造に編成される。ゲノムデータセットはヘッダとアクセスユニットを含む圧縮ユニットである。ゲノムデータセットを構成するアクセスユニットのセットは、ゲノムデータセットペイロードを構成する。
【０１２１】
１つ以上のゲノムデータセットの集合をデータセット群と呼ぶ。
【０１２２】
本開示のコンテキストにおいて、ゲノム記述子は、コード化されたリファレンスシーケンス、シーケンスリード及び関連するマッピング情報を再構築（すなわち、デコード化）するのに必要な情報（また、ファイルフォーマット及び／又はビットストリームの構文構造（syntax structure）の要素でもある）の一部を表す構文要素（syntax elements）である。本発明で開示されるゲノム記述子を表４に掲載する。
【０１２３】
本発明に開示された方法によれば、リファレンスシーケンス又はその一部、シーケンスリード、及び関連するアラインメント情報は、上記にリストされた記述子のサブセットを使用してコード化され、次いで、各記述子固有の統計的特性に従って、複数のエントロピーエンコーダを使用してエントロピーコード化される。均質な統計的特性を有する圧縮された記述子のブロックは、本開示に記載される本発明を実施する装置によって操作することができる１つ以上のゲノムシーケンスの最小のコード化表現を表すアクセスユニットにおいて構造化される。
【０１２４】
ゲノム記述子は、以下に定義されるようにブロック及びストリームに編成される。ブロックは、ヘッダとペイロードで構成されるデータ単位として定義され、同じ種類の圧縮された記述子の一部で構成される。記述子ストリームは、特定のデータクラスの記述子をデコードするために使用されるコード化記述子ブロックのシーケンスとして定義される。
【０１２５】
シーケンシング装置では、次のようなシーケンスリードエラーが発生する可能性がある。
１．特定の塩基を呼び出す確証がないために、塩基の呼び出しをスキップする決定。これは未知の塩基と呼ばれ、「Ｎ」（「ｎタイプ」のミスマッチとして示される）と表示される；
２．シーケンスされたサンプルに実際に存在する核酸を表すものとは異なるシンボル（すなわち、異なる核酸を表す）の使用；これは通常「置換エラー」（「ｓタイプ」のミスマッチとして示される）と呼ばれる；
３．実際に存在する核酸を指し示さない追加のシンボルを１つのシーケンスリードへ挿入；これは通常、「挿入エラー」と呼ばれる（「ｉタイプ」のミスマッチとして示される）；
４．シーケンスされたサンプルに実際に存在する核酸を表すシンボルを、１つのシーケンスリードから削除；これは通常「削除エラー」と呼ばれる（「ｄタイプ」のミスマッチとして示される）；
５．元のシーケンスの現実を反映しない単一のフラグメントへの１つ以上のフラグメントの組換え；これは通常、アライナが塩基をクリップすると決定する結果となる（「ｃタイプ」のミスマッチとして示される）。
【０１２６】
ゲノムシーケンシングにおいて、「カバレッジ」という用語は、「リファレンスシーケンス」に関するシーケンスデータの冗長性のレベルを表すために使用される。アライメントされたゲノムシーケンスデータの平均カバレッジは、リファレンスゲノムの各位置の各塩基がアライメントされたデータに存在する平均回数である。たとえば、ヒトゲノム（長さ３２億塩基）で３０倍のカバレッジを達成するには、シーケンシング装置が合計３０×３２億塩基を生成し、リファレンスの各位置が平均３０回「カバー」されるようにする。
【０１２７】
カバレッジは次のように述べられている：
・  部分的（partial）（１×未満）は、リファレンスゲノムの一部が利用可能なシーケンスリードによってマッピングされていない場合であり；
・  シングル（single）（１×）は、リファレンスゲノムの全てのヌクレオチドが、シーケンスリードに存在する唯一のシンボルによってマッピングされる場合であり；
・  マルチプル（multiple）（２×、３×、Ｎ×）は、リファレンスゲノムの各ヌクレオチドが複数回マッピングされる場合である。
【０１２８】
本発明は、関連情報が効率的にアクセス可能かつ移動可能であり、冗長情報の重みが低減されたゲノム情報表示フォーマットを定義することを目的とする。
【０１２９】
開示された発明の主な革新的態様は、以下の通りである。
１  シーケンスリードは、リファレンスシーケンスに関するアラインメントの結果に従って、データクラスに分類され、区分化される。このような分類及び区分化は、アラインメント結果及びマッチング精度に関連する基準に従って、コード化データへの選択的アクセスを可能にする。
２  分類されたシーケンスリード及び関連するメタデータは、均一な統計的特性を有するブロックに編成されたゲノム記述子によって表され、低い情報エントロピーによって特徴付けられる個別の情報ソースの定義を可能にする。
３  各クラスの統計的特性に適合した個別のソースモデルを用いて、それぞれ分離された情報ソースをモデル化する可能性と、リードの各クラス内及び個別にアクセス可能なデータユニット（アクセスユニット）の各記述子ブロック内でソースモデルを変更する可能性。適切な変換、バイナリ化及びコンテキスト適応確率モデルと、各ソースモデルの統計的性質に従った関連エントロピーコード化の採用。
４  全ての情報が必要でない場合、全ての記述子ブロックをデコード化する必要なしに、シーケンシングデータ及び関連するメタデータへの選択的アクセスを可能にするための記述子ブロック間の対応関係及び依存関係の定義。
５  記述子ブロックの情報ソースのエントロピーを減少させるように、「既存の」（「外部の」とも呼ばれる）リファレンスシーケンス又は「既存の」リファレンスシーケンスに適切な変換を適用することによって得られる「変換」されたリファレンスシーケンスに関する、各シーケンスデータクラス及び関連するメタデータブロックのコード化。前記の記述子は、異なるデータクラスに分割されたリードを表す。「既存の」リファレンス又は「変換」「既存の」リファレンスシーケンスを参照して、対応する記述子を使用するリードのコード化に続いて、低エントロピーで最終的なコード化表現を見つけ、より高い圧縮効率を達成するために、種々のミスマッチの発生を使用して、リファレンスシーケンスに対する適切な変換を定義することができる。
６  一連の制約を満足しない既存のリファレンスシーケンスに関して、ある程度のマッチング精度を示すリードのクラスをコード化するために使用される一つ以上のリファレンスシーケンス（「内部の」リファレンスも呼ばれ、本明細書では「外部の」リファレンスシーケンスとも呼ばれる「既存の」リファレンスシーケンスと区別する）の構築。このような制約は、「内部の」リファレンスシーケンスに関してアライメントされたリードのクラスを圧縮形式で表現するためのコード化コスト及び「内部の」リファレンスシーケンス自体を表現するためのコストが、アライメントされていないリードのクラスを逐語的にコード化するよりも、又は変換を伴わずに又は伴う「外部の」リファレンスシーケンスを使用するよりも低いという目的で設定される。
７  ヘッダ情報の形で圧縮されたゲノムデータに埋め込まれたデータ構造によってコード化とデコード化の両方のプロセスを支配する構成パラメータの送信。このような構成パラメータは、圧縮性能を改善するために、コード化プロセス中に更新することができる。このような更新は、更新された構成データ構造の形式で圧縮されたコンテンツで伝達される。
【０１３０】
以下、上記各態様についてさらに詳細に説明する。
［マッチング規則に基づくシーケンスリードの分類］
【０１３１】
シーケンシング装置によって生成されたシーケンスリードは、開示された発明によって、一つ以上の「既存の」リファレンスシーケンスに関するアラインメントのマッチングの結果に従って、６つの異なる「クラス」に分類される。
【０１３２】
ヌクレオチドのＤＮＡシーケンスをリファレンスシーケンスに対してアライメントさせる場合、以下の場合を特定することができる:
１．リファレンスシーケンス内の領域は、エラーなしのシーケンスリードとマッチングすることがわかる（つまり、完全なマッピング）。そのようなヌクレオチドのシーケンスは、「完全にマッチングするリード」と呼ばれるか、「クラスＰ」と表示される。
２．リファレンスシーケンス内の領域は、シーケンスリードと、リードを生成するシーケンシング装置が塩基（又はヌクレオチド）を呼び出せなかった位置の数によってのみ決定されるミスマッチの数と類型とマッチングすることが見出される。この種のミスマッチは、未定義のヌクレオチド塩基を示すために用いられる文字である「Ｎ」によって示される。本開示では、この種のミスマッチを「ｎタイプ」ミスマッチと呼ぶ。このようなシーケンスは「クラスＮ」のリードに属する。リードが「クラスＮ」に属するように分類されたら、マッチングの不正確さの程度を所定の上限に制約し、有効なマッチングと見なされるものとそうでないものとの境界を設定することが有用である。したがって、クラスＮに割り当てられるリードも、リードに含めることができる未定義の塩基（すなわち、「Ｎ」と呼ばれる塩基）の最大数を定義するしきい値（ＭＡＸＮ）を設定することによって制約される。このような分類は、クラスＮに属する全てのリードが、対応するリファレンスシーケンスを参照するときに共有する必要な最小マッチング精度（又は最大マッチング度)を黙示的に定義し、これは、選択的データ検索を圧縮データに適用するための有用な基準を構成する。
３．リファレンスシーケンス中の領域は、シーケンスリードと、リードを生成するシーケンシング装置がいずれのヌクレオチド塩基も呼び出せなかった位置の数によって決定されたミスマッチの数及び類型がマッチングすることが見出される。仮に、それが存在する場合（すなわち「ｎタイプ」ミスマッチ）、それに加えて、リファレンス中に存在するものとは異なる塩基が呼び出されたミスマッチの数。「置換」と呼ばれるこのような種類のミスマッチは、一塩基変異（ＳＮＶ）又は一塩基多型（ＳＮＰ）とも呼ばれる。本開示では、この種のミスマッチは、「ｓタイプ」ミスマッチとも呼ばれる。シーケンスリードは「Ｍミスマッチリード」として参照され、「クラスＭ」に割り当てられる。「クラスＮ」の場合と同様に、「クラスＭ」に属する全てのリードについても、マッチングの不正確さの程度を特定の上限に設定し、有効なマッチングと見なされるものとそうでないものとの境界を設定すると便利である。したがって、クラスＭに割り当てられたリードは、しきい値のセットを定義することによって制限される。もし存在するならば、その一つは「ｎタイプ」のミスマッチの数「ｎ」（ＭＡＸＮ）、そして、もう１つは置換の数「ｓ」（ＭＡＸＳ）であり、第３の制約は、数「ｎ」と「ｓ」の両方の関数ｆ（ｎ，ｓ）によって定義されるしきい値である。このような第３の制約により、意味のある選択的アクセス基準に従って、マッチングする不正確さの上限を持つクラスを生成できる。例えば、制約としてではなく、ｆ（ｎ，ｓ）は（ｎ＋ｓ）１／２又は（ｎ＋ｓ）又は「クラスＭ」に属するリードに対して許容される最大マッチング不正確レベルに境界を設定する任意の線形式又は非線形式であり得る。このような境界は、さまざまな目的のためにシーケンスリードを分析する際に、所望の選択的データ検索を圧縮データに適用するための非常に有用な基準を構成する。なぜならば、この境界は、一つの種類又は他方に適用される単純しきい値を超える「ｎタイプ」ミスマッチ及び「ｓタイプ」ミスマッチの数（置換）の任意の可能な組み合わせに対して、さらなる境界を設定することを可能にするからである。
４．第４のクラスは、「挿入」、「削除」（インデル（indels）とも呼ばれる）、及び「クリップ」のいずれかの種類の少なくとも１つのミスマッチを示すシーケンスリードで構成され、クラスＮ又はＭに属するミスマッチのタイプが存在する場合、このようなシーケンスは「リードミスマッチ」と呼ばれ、「クラスＩ」に割り当てられる。挿入は、リファレンスに存在しないがリードシーケンスには存在する１つ以上のヌクレオチドの追加のシーケンスによって構成される。本開示では、このタイプのミスマッチは「ｉタイプ」のミスマッチと呼ばれる。文献においては、挿入されたシーケンスがシーケンスの端にある場合、それは「ソフトクリップ」とも呼ばれる（すなわち、ヌクレオチドはリファレンスにマッチングしていないが、廃棄される「ハードクリップ」ヌクレオチドとは対照的に、アライメントされたリードにおいて保持される）。本開示では、この種のミスマッチは「ｃタイプ」ミスマッチと呼ばれる。ヌクレオチドの保持又は廃棄は、シーケンシング装置又はその後のアライメント段階によって決定されるリードを受信及び処理する本発明で開示されるリードの識別子によってではなく、アライメント段階によって行われる決定である。削除は、リファレンスに関するリードの「ホール」（ヌクレオチドの欠落）である。本開示では、このタイプのミスマッチは「ｄタイプ」のミスマッチと呼ばれる。クラス「Ｎ」及び「Ｍ」の場合と同様に、マッチングの不正確さに対する制約を定義することは可能でありかつ適切である。「クラスＩ」に対する一連の制約の定義は、「クラスＭ」に使用されたものと同じ原則に基づいており、表２の最後の行に表される。クラスＩのデータに対して許容される各タイプのミスマッチに対するしきい値の他に、さらなる制約は、ミスマッチの数「ｎ」、「ｓ」、「ｄ」、「ｉ」及び「ｃ」、ｗ（ｎ，ｓ，ｄ，ｉ，ｃ）の関数によって決定されるしきい値によって定義される。そのような追加の制約により、意味のあるユーザー定義の選択的アクセス基準に従って、マッチングの不正確さの上限を持つクラスを生成できる。例えば、これに限定されるものではないが、ｗ（ｎ，ｓ，ｄ，ｉ，ｃ）は、（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）１／５又は（ｎ＋ｓ＋ｄ＋ｉ＋ｃ）、又は「クラスＩ」に属するリードに対して許容される最大マッチング不正確レベルに境界を設定する任意の線形式又は非線形式であり得る。このような境界は、さまざまな目的のためにシーケンスリードを解析するとき、所望の選択的データ検索を圧縮データに適用するための非常に有用な基準を構成する。なぜならば、この境界は、許容可能なミスマッチの各類型に適用される単純なしきい値を超えて、「クラスＩ」のリードにおいて許容可能なミスマッチの数の任意の可能な組み合わせに対して、さらなる境界を設定することを可能にするからである。
５．第５のクラスは、リファレンスシーケンスを参照するときに各データクラスに対して有効であると考えられるマッピング（すなわち、表２で指定された最大マッチング精度の上限を定義するマッチング規則のセットを満たしていない）を見つけない全てのリードを含むこのようなシーケンスは、リファレンスシーケンスを参照するときに「非マッピング」と呼ばれ、「クラスＵ」に属するものとして分類される。
６．ペアエンドリードの場合、第６のクラスが定義され、その中では、ペアの一方のリードはリファレンスゲノムのいずれの位置にもマッピングすることができず（クラスＵに属する）、他方のリードはＰ、Ｎ、Ｍ、Ｉクラスのいずれかに属する。このようなクラスは、ハーフマッピングから「ＨＭクラス」と呼ばれる。
［マッチング規則によるリードペアの分類］
【０１３３】
前のセクションで指定した分類は、単一のシーケンスリードに関するものである。２つのリードが可変長の未知のシーケンスで分離されていることがわかっているペアでリードを生成するシーケンシング技術（すなわち、イルミナ社）の場合、ペア全体を単一のデータクラスに分類することを検討するのが適切である。他にリードと結合されたリードは、その「メイト（mate）」と呼ばれている。
【０１３４】
両方のペアリードが同じクラスに属している場合、ペア全体のクラスへの割り当ては次のようになる。ペア全体は、任意のクラスの同じクラスに割り当てられる（Ｐ、Ｎ、Ｍ、Ｉ、Ｕ等）。２つのリードが異なるクラスに属しているが、いずれも「クラスＵ」に属していない場合、ペア全体が、次の式に従って定義された最も高い優先順位を持つクラスに割り当てられる。
Ｐ＜Ｎ＜Ｍ＜Ｉ
ここで、「クラスＰ」の優先順位が最も低く、「クラスＩ」の優先順位が最も高くなる。
【０１３５】
一つのリードだけが「クラスＵ」に属し、その組み合わせがクラスＰ、Ｎ、Ｍ、Ｉ、のいずれかに属している場合、第６番目のクラスは「ＨＭクラス」を表す「ハーフマッピング」として定義される。
【０１３６】
このような特定のクラスのリードの定義及び関連する割り当ての規則は、このようなデータがリファレンスゲノムのギャップ又は未知の領域（ほとんど知られていない領域とも呼ばれる）を究明しようとするために用いられるという事実によって動機づけられる。このような領域は、既知の領域にマッピングすることができるペアリードを使用してエッジでペアをマッピングすることによって再構成される。マッピングされていないメイトは、図１６に示すように、未知の領域のいわゆる「コンティグ」を作るのに使われる。したがって、このような類型のリードペアのみに選択的アクセスを提供することは、関連する計算負荷を大幅に低減し、最新技術のソリューションを使用する場合に、完全な検査をする必要がある大量のデータセットに起因するデータの非常に効率的な処理が可能になる。
【０１３７】
以下の表は、各リードが属するデータのクラスを定義するために、リードに適用されるマッチング規則を示す。この規則は、ミスマッチの種類（ｎ、ｓ、ｄ、ｉ、ｃ型ミスマッチ）の有無に関して、表の最初の５列で定義される。第６の列は、それぞれのミスマッチの類型に対する最大しきい値、及び起こり得るミスマッチの類型の任意の関数ｆ（ｎ，ｓ）及びｗ（ｎ，ｓ，ｄ，ｉ，ｃ）に関す規則ルを提供する。
【０１３８】
表１．各シーケンスリードが、本発明の開示において定義されるデータクラスに分類されるために満足しなければならないミスマッチの類型および制約のセット
【表１】
2020510907.tif 000003
［マッチング精度の異なるサブクラスを伴うシーケンスリードデータ・クラスＮ、Ｍ、及びＩのマッチング規則・パーティション］
【０１３９】
前のセクションで定義されたタイプＮ、Ｍ、及びＩのデータクラスは、さらに、マッチング精度の程度が異なる任意の数の別個のサブクラスに分解することができる。このようなオプションは、より細かい粒度を提供する上で重要な技術的利点であり、その結果、各データクラスへのより効率的な選択的アクセスを提供する。例えば、これに限定されるものではないが、Ｎ個のクラスをｋ個のサブクラス（サブクラスＮ１、・・・、サブクラスＮｋ）に分割するために、ＭＡＸＮ１＜ＭＡＸＮ２＜・・・ＭＡＸＮ（ｋ−１）＜ＭＡＸＮ（ｋ）という条件で、対応するコンポーネントＭＡＸＮ１、ＭＡＸＮ２、・・・、ＭＡＸＮ（ｋ−１）、ＭＡＸＮ（ｋ）を持つベクトルを定義する必要があり、ベクトルの各要素を評価するときに、表２で指定された制約を満たす最下位のサブクラスに各リードを割り当てる必要がある。これは、図１５に示されており、データ分類ユニット１５０１は、クラスＰ、Ｎ、Ｍ、Ｉ、Ｕ、ＨＭのエンコーダ及び注釈及びメタデータ用のエンコーダを含む。クラスＮのエンコーダは、Ｎ個のデータ（１５０６）のｋ個のサブクラスを生成するＭＡＸＮ１からＭＡＸＮｋ１５０２までのしきい値のベクトルで構成される。
【０１４０】
タイプＭとタイプＩのクラスにおいて、ＭＡＸＭとＭＡＸＴＯＴにそれぞれ同じ特性を持つベクトルを定義することによって同じ原理が適用され、関数ｆ（ｎ，ｓ）と関数ｗ（ｎ，ｓ，ｄ，Ｉ，ｃ）が条件を満たすかどうかをチェックするためのしきい値として、各ベクトル成分が使用される。タイプＮのサブクラスの場合と同様に、条件が満たされている最下位のサブクラスに割り当てられる。各クラスの類型に対するサブクラスの数は独立しており、細別の任意の組み合わせが許容される。これは図１５に示されており、クラスＭのエンコーダ１５０３及びクラスＩのエンーダ１５０４は、それぞれ、しきい値ＭＡＸＭ１からＭＡＸＭｊ及びＭＡＸＴＯＴ１からＭＡＸＴＯＴｈのベクトルで構成されている。２つのエンコーダはそれぞれＭ個のデータ（１５０７）のｊ個のサブクラスとＩ個のデータ（１５０８）のｈ個のサブクラスを生成する。
【０１４１】
ペア内の２つのリードが同じサブクラスに分類される場合、そのペアは同じサブクラスに属する。
【０１４２】
ペア内の２つのリードが異なるクラスのサブクラスに分類される場合、そのペアは次の式に従って優先順位の高いクラスのサブクラスに属する。
Ｎ＜Ｍ＜Ｉ
ここで、Ｎが最も優先度が低く、Ｉが最も優先度が高い。
【０１４３】
２つのリードが、クラスＮ、Ｍ、又はＩのうちの１つの異なるサブクラスに属している場合、そのペアは、次の式に従って、最も高い優先順位を持つサブクラスに属する。
Ｎ１＜Ｎ２＜・・・＜Ｎｋ
Ｍ１＜Ｍ２＜・・・＜Ｍｊ
Ｉ１＜Ｉ２＜・・・＜Ｉｈ
ここで、最も高いインデックスが最も高い優先順位を有する。
［「外部の」リファレンスシーケンスの変換］
【０１４４】
クラスＮ、Ｍ、Ｉに分類されたリードで見つかったミスマッチを使用して、リード表現をより効率的に圧縮するために使用される「変換」されたリファレンスを作成できる。
【０１４５】
クラスＮ、Ｍ又はＩ（ＲＳ０として示される「既存の」（すなわち「外部の」）リファレンスシーケンスに関して）に属すると分類されたリードは、「変換された（transformed）」リファレンスとの実際のミスマッチの発生に従って、「変換された」リファレンスシーケンスＲＳ１に関してコード化することができる。例えば、クラスＭに属するｒｅａｄＭｉｎ（クラスＭの第ｉ番目のリードとして示される）がリファレンスシーケンスＲＳｎとの間にミスマッチを含む場合、「変換」の後に、Ａ（Ｒｅｆｎ）＝Ｒｅｆｎ＋１を用いてｒｅａｄＭｉｎ＝ｒｅａｄＰｉ（ｎ＋１）を得ることができ、ここで、ＡはリファレンスシーケンスＲＳｎからリファレンスシーケンスＲＳｎ＋１への変換である。
【０１４６】
図１９は、リファレンスシーケンス１（ＲＳ１）に対するミスマッチ（クラスＭに属する）を含むリードを、ミスマッチ位置に対応する塩基を修正することによって、ＲＳ１から得られるリファレンスシーケンス２（ＲＳ２）に対する完全にマッチングするリードに変換する方法の例を示す。これらは分類されたままで、同じデータクラスアクセスユニットで他のリードと一緒にコード化されるが、コード化はクラスＰのリードに必要な記述子と記述子値のみを使用して行われる。この変換は、次式：
ＲＳ２＝Ａ（ＲＳ１）
として表すことができる。
【０１４７】
ＲＳ１に適用されたときにＲＳ２を生成する変換Ａの表現に、リードペアＲＳ２の表現を加えたものが、クラスＭに対するＲＳ１のリードの表現よりも低いエントロピーに対応する場合、データ表現のより高い圧縮が達成されるので、変換Ａの表現及びリードペアＲＳ２の対応する表現を伝送することが有利である。
【０１４８】
圧縮ビットストリームにおける伝送のための変換Ａのコード化は、以下の表に定義されるように、２つの追加の構文要素の定義を必要とする。
【表２】
2020510907.tif 000004
【０１４９】
図１８は、マッピングされたリードでコード化されるミスマッチの数を減らすために、リファレンス変換がどのように適用されるかの例を示す。
【０１５０】
場合によっては、リファレンス変換が適用されることに注意しなければならない。
・  変換を適用する前にリファレンスを参照したときに存在しなかったリードの表現にミスマッチが生じることがある。
・  ミスマッチの類型を変更することができ、リードにはＧの代わりにＡが含まれ、他の全てのリードにはＧの代わりにＣが含まれるが、ミスマッチは同じ位置に残る。
・  異なるデータクラス及び各データクラスのデータのサブセットは、同じ「変換された」リファレンスシーケンス、又は同じ既存のリファレンスシーケンスに異なる変換を適用することによって取得されたリファレンスシーケンスを参照する場合がある。
【０１５１】
図１９はさらに、リファレンス変換が適用され、リードが「変換された」リファレンスを使用して表された後に、リードが適切な記述子セット（例えば、クラスＰの記述子を使用してクラスＭからのリードをコード化する）によって、あるデータクラスから別のクラスにコード化の類型を変更する方法の例を示す。これは、たとえば、変換がリードに実際に存在する塩基のリードのミスマッチに対応する全ての塩基を変更し、クラスＭ（元の「変換されていない」リファレンスシーケンスを参照する場合）に属するリードをクラスＰ（「変換された」リファレンスを参照する場合）の仮想リードに仮想的に変換するときに発生する。データの各クラスに使用される記述子のセットの定義については、次のセクションで説明する。
【０１５２】
図１９は、異なるクラスのデータが、同一の「変換された」リファレンスＲ１＝Ａ０（Ｒ０）（１９００）を使用してリードを再コード化し、又は異なる変換ＡＮ（１９０１）、ＡＭ（１９０２）、ＡＩ（１９０３）を各クラスのデータに別々に適用して、異なるリファレンスゲノムＲＮ、ＲＭ、ＲＩを生成する方法を示す。
［ゲノム・データセット・ヘッダ］
【０１５３】
リードの分類がクラスの定義で完了すると、さらなる処理は、所定のリファレンスシーケンス上にマッピングされているとして表されるときに、リードシーケンスの再構築を可能にする残りの情報を表す別個の構文要素のセットを定義することからなる。これらの構文要素のデータ構造は、デコード化エンジンによって使用されるグローバルパラメータ及びメタデータの記憶を必要とする。これらのデータは、以下の表に示すゲノム・データセット・ヘッダ（Genomic Dataset Header）で構成されている。データセットは、単一のゲノムシーケンス決定ラン及び以下の全ての分析に関連するゲノム情報を再構築するのに必要なコード化のエレメントの集合として定義される。同一のゲノム試料を２回の個別の実行で２回シーケンシングする場合、得られたデータは２つの個別のデータセットにコード化される。
【０１５４】
表２．ゲノム・データセット・ヘッダ
【表３】
2020510907.tif 000005
2020510907.tif 000006
2020510907.tif 000007
［ゲノム記述子］
【０１５５】
所定のリファレンスシーケンスを参照するシーケンスリード（すなわちＤＮＡセグメント）は、以下の記述子の様々な組合せから形成されるサブセットを任意に使用して完全に表現することができる。
【０１５６】
表３．ゲノム記述子とその意味
【表４】
2020510907.tif 000008
2020510907.tif 000009
【０１５７】
クラスＵの場合、ｃｌｉｐｓ記述子は、指定されたマッチング精度の制約のセットと「内部の」リファレンスとマッチングしないリード部分（通常はエッジ）を識別する。
【０１５８】
ｕｒｅａｄｓ記述子は、既存の（すなわち、実際のリファレンスゲノムのような「外部の」）リファレンスシーケンス又は「内部の」リファレンスシーケンスであるため、使用可能なリファレンスにマップできないリードを逐語的にコード化するために使用される。
【０１５９】
この分類は、ゲノムシーケンスリードを一義的に表現するために用いることができる記述子（構文要素）のグループを作り出す。次の表は、「外部の」（すなわち「既存の」）又は「内部の」（すなわち「構築済みの」）リファレンスにアライメントされた各リードクラスに必要な構文要素をまとめたものである。アスタリスク「*」は、各クラスの全てのコード化されたリードで常に存在する必須な記述子を示す。
【０１６０】
表４．各クラスのデータを表すために必要なゲノム記述子
【表５】
2020510907.tif 000010
【０１６１】
クラスＰに属するリードは特徴付けられ、位置、逆相補情報（reverse complement information）、およびメイトペア、いくつかのフラグ、リード長を生成するシーケンシング技術によって取得された場合のメイト間のオフセットのみによって完全に再構築できる。
【０１６２】
次のセクションでは、これらの記述子がクラスＰ、Ｎ、Ｍ、Ｉに対してどのように定義されるかを詳細に説明し、クラスＵについては、以下のセクションで説明する。
【０１６３】
クラスＨＭはリードペアにのみ適用され、一方のリードがクラスＰ、Ｎ、Ｍ、又はＩに属し、もう一方のリードがクラスＵに属する特殊なケースである。
［ｐｏｓ記述子］
【０１６４】
ｐｏｓ記述子は、ゲノムレコードの左端にマッピングされた塩基のリファレンスシーケンス上の絶対マッピング位置を計算するために使用される。各ｐｏｓ記述子の値は、ゲノムレコードの左端にマッピングされた塩基と、その前にマッピングされた塩基のリファレンスシーケンス上の座標の差を表す。図４は、マッピングされたリードペアのｐｏｓ記述子の計算例を示す。
【０１６５】
各コード化されたブロック内のｐｏｓ記述子の第１番目の値は、アクセスユニット内でコード化された第１番目にマッピングされたリード又はリードペアに対して微分コード化が不可能であるため、常に０である。アクセスユニットにコード化された最初のマッピング済みのリード／リードペアの絶対位置は、アクセスユニットヘッダに含まれる。
【０１６６】
したがって、第ｎ番目のゲノムレコードの左端にマッピングされた塩基のリファレンスシーケンス上の絶対位置は、次のように計算される:
【数１】
2020510907.tif 000011
ここで、ｐ０は、アクセスユニットの最初のゲノムレコードに対して、アクセスユニットヘッダから検索されたマッピング値である。
【０１６７】
塩基のリファレンスシーケンス上の絶対位置を計算するために、次の公式が適用される:
【数２】
2020510907.tif 000012
ここで、
・  ｐは、塩基の基準シーケンス上の絶対位置であり、
・  ｐｓｔａｒｔは、塩基を含むゲノムレコードのマッピング位置であり、
・  ｎｉｎｓは、同じゲノムレコード内の塩基の前に挿入された塩基の数であり、
・  ｎｄｅｌは同じゲノムレコード内の塩基に先行する欠欠落した塩基の数であり、
・  ｄｓｔａｒｔは、ゲノムレコード位置からのゲノムレコード内の塩基のオフセットであり、
・  デルタ（delta）は、リードペアにおける２つのリード間の（符号付き（signed））ペアの距離である。これはゲノムレコードの２回目のリードにおける位置に対してのみ使用されなければならない。
【０１６８】
注記  ペアエンドリードの場合、ゲノム記録位置からオフセットｄｓｔａｒｔを計算するとき、２つのリードは連続していると見なされる。相対的なリードの位置は、ｄｅｌｔａを追加するときに考慮される。
【０１６９】
リファレンスシーケンス上の１つの塩基に対するマッピング位置ｐの計算の例は、図５に示される。
［ｒｃｏｍｐ記述子］
【０１７０】
ｒｃｏｍｐ記述子は、リードの階層性に関する情報を伝達する。デコード化されたｒｃｏｍｐ記述子の各ビットは、リードが順方向（０に設定されたビット）又は逆方向（１に設定されたビット）のどちらのストランドで行われたかを示すフラグである。図６は、ペアになったエンドリードのためのｒｃｏｍｐ記述子の値と意味づけを示す。図では、ｒ１がリード１、ｒ２がリード２となっている。各リードのマッピング位置に応じて、ｒｃｏｍｐ記述子は４つの異なる値を持つことができる。
【０１７１】
表５．ｒｃｏｍｐ記述子の値と意味
【表６】
2020510907.tif 000013
［ｆｌａｇｓ記述子］
【０１７２】
ｆｌａｇｓ記述子は、表７で説明するフラグのセットである。
【０１７３】
表６．ｆｌａｇｓ記述子の各ビットのセマンティクス
【表７】
2020510907.tif 000014
［ｍｍｐｏｓ］
【０１７４】
ｍｍｐｏｓ記述子は、リード又はリードペア内で、リファレンスシーケンスに対するミスマッチの位置を表す。その位置は、ゲノムレコードにおける以前のミスマッチの位置からの距離として表される。第１番目のミスマッチの位置はゲノムレコードの左端にマッピングされた塩基からの距離として表される。
【０１７５】
ペアリードの場合、又は複数のゲノムセグメントを含む一般的なレコードでは、連続するセグメント間のギャップは、連続するミスマッチ間の距離の計算では考慮されない。
【０１７６】
コード化されたペアにリード１とリード２の両方が含まれている場合、リード２のミスマッチの位置はリード１の長さだけオフセットされる。例えば、１００に等しい一定長さを有するリードの場合、ペアにおける最初のミスマッチが位置４４でリード２にある場合、このゲノムレコードについてデコード化された最初のｍｍｐｏｓ記述子は、値１４４を仮定する。
【０１７７】
記述されたペアがリード１を欠いている場合（別のブロックにコード化されているか、リード２がペアになっていないかのいずれか）、ミスマッチ位置はリード１の長さだけオフセットされない。例えば、リード長が１００に固定された場合、リード２の最初の変異が位置４４にあり、リード２がペアになっていない場合、このゲノムレコードについてコード化された最初のｍｍｐｏｓ記述子の値は４４を仮定する。
【０１７８】
各ｍｍｐｏｓ記述子は、ｍｍｐｏｓを使用して計算された位置でコード化されたリード又はリードペアで発生するミスマッチの類型を表すｍｍｔｙｐｅ記述子に関連付けられる。
【０１７９】
リードペアにおけるミスマッチ位置の計算方法の例を図７に示し、ここで、ｌｅｎ１はリード１の長さを示す。
【０１８０】
ゲノムレコードにおける第ｉ番目のミスマッチのリファレンスシーケンス上の絶対位置は、表７に示されるように計算される。
【０１８１】
表７．ゲノムレコードのミスマッチの絶対位置を計算する方法
【表８】
2020510907.tif 000015
【０１８２】
表７では、以下の変数が定義されている。
・  ｍｍａｂｓｉは、リード又はリードペアにおける第ｉ番目のミスマッチの基準シーケンスにおける絶対位置であり、
・  ｍｍｐｏｓｉはゲノムレコードのｍｍｐｏｓ記述子の第ｉ番目の値であり、
・  ｌｅｎ１は、リードペアのリード１の長さであり、
・  ｄｅｌｔａは、ペア記述子に対して定義され、図５に示すように計算されたリード１とリード２との間のペアリング距離である。
【０１８３】
ゲノムレコードを参照するｍｍｐｏｓ記述子のシーケンスは、ミスマッチ位置として解釈できない予め定められたターミネータ値で終了する。
［ｍｍｔｙｐｅ］
【０１８４】
ｍｍｔｙｐｅ記述子は、関連するｍｍｐｏｓ記述子を使用して計算された位置でデコード化されたリードで発生するミスマッチの類型を指定する。
【０１８５】
各ゲノムレコードが同じ数のｍｍｔｙｐｅとｍｍｐｏｓ記述子を含むので、ｍｍｔｙｐｅ記述子はターミネータのために予め定められた値を持たない。
【０１８６】
表８は、使用されるアルファベットに従って、ｍｍｔｙｐｅ記述子の値と対応する意味を掲載する。
【０１８７】
表８．使用されるアルファベットに従ったｍｍｔｙｐｅ記述子の値とセマンティクス
【表９】
2020510907.tif 000016
［ｃｌｉｐｓ］
【０１８８】
ｃｌｉｐｓ記述子は、マッピングされたリード又はリードペアのクリップされた塩基（ソフトクリップ又はハードクリップとも呼ばれる）を表すために使用される。この記述子は、リード又はリードペアのクリップされた塩基の位置を識別するための追加のエレメントを持つＡＳＣＩＩ文字のシーケンスとして、ソフトクリップをエンコードする。ハードクリップの場合は、クリップされた塩基の位置と数だけがコード化される。各記述子は、ゲノムレコード識別子と、ゲノムレコードにおけるクリッピングされた塩基の位置、及びソフトクリップの場合の実際のクリッピングされた塩基に関連する情報を含む。
【０１８９】
ｃｌｉｐｓ記述子の構文及び意味を、表９及び表１０に示す。
【０１９０】
表９．ｃｌｉｐｓ記述子を構成するフィールド
【表１０】
2020510907.tif 000017
【０１９１】
表１０．ｃｌｉｐｓ記述子の構文
【表１１】
2020510907.tif 000018
【０１９２】
ｒｅｃｏｒｆ＿ｉｄは、現在のアクセスユニットでエンコードされたゲノムレコードのカウンタである。
【０１９３】
ｃｌｉｐｓ＿ｐｏｓは、リード又はリードペアの次のクリップされた塩基の位置を表す。位置（position）の値の意味は次のとおりである：
【表１２】
2020510907.tif 000019
【０１９４】
ｓｏｆｔ＿ｃｌｉｐｐｅｄ＿ｂａｓｅｓは、ａｌｐｈａｂｅｔ＿ｉｄで識別されるアルファベットのシンボルの１つである。
【０１９５】
ｈａｒｄ＿ｃｌｉｐｐｅｄ＿ｂａｓｅｓは、対応するｃｌｉｐｓ＿ｐｏｓによって示される位置にあるハードクリップされた塩基の数を表す；
［ｕｒｅａｄｓ］
【０１９６】
ｕｒｅａｄｓ記述子は、ａｌｐｈａｂｅｔ＿ｉｄで識別される現在使用されているアルファベットに属するＡＳＣＩＩ文字のシーケンスとして、逐語的にリードを表す。
［ｒｌｅｎ］
【０１９７】
ｒｌｅｎ記述子は、本開示で定義されるパラメータセットでｒｅａｄ＿ｌｅｎｇｔｈ＝０のときに、可変長のリードの場合にのみ使用される。
【０１９８】
デコード化されたｒｌｅｎ記述子は、ソフトクリップを含む塩基の数として、現在のシーケンスリードの長さを表す。
［ｐａｉｒ］
【０１９９】
ペアリードの再構築に必要な情報は、ｐａｉｒ記述子を使用してコード化される。１つのゲノムセグメントと別のゲノムセグメントとを結びつけるペアリング情報は、次の３つの方法で表すことができる。
１．両方のリードが同じリファレンスにマッピングされ、同じゲノムレコードにコード化される場合、ペアリング距離は、リード１の左端にマッピングされた塩基とリード２の左端にマッピングされた塩基との間の距離として定義される。ペアリング距離の例を図８に示す。
２．第１のリードと同じリファレンスシーケンス上の第２のリードの絶対マッピング位置として。
３．第１のリードのリファレンスシーケンスとは異なるリファレンスシーケンス上の第２のリードのリファレンスシーケンスの絶対マッピング位置として。
【０２００】
ペアリング情報は、デコード化されたｐａｉｒ記述子の最初の２つのバイトが表１１に掲載された値の一つを有するとき、上記ポイント２及び３に記述されるようにコード化される。
【０２０１】
図８は、リード又はリードペアの左端にマッピングされた塩基と、右端にマッピングされた塩基とを分離するリファレンスシーケンス上のゲノム位置（genomic positions）の数として、ゲノムレコード長がどのように定義されるかを示す。リードペアの場合、これは、両方のリードが同じリファレンスシーケンス上にマッピングされているときに、リード１の左端の塩基をそのペアのリード２の右端の塩基から分離するリファレンスシーケンス上のゲノム位置の数である。「ペアリングの距離」は、リード１の左端の位置とリード２の左端の位置との差として定義される。「ペアリングの距離」は、ｐａｉｒ記述子の符号付き整数値として表される。
【０２０２】
リードをリファレンスシーケンスにアライメントさせる場合、リード２をリード１のマッピング位置よりも小さい位置（例えば、左側）にマッピングでき；この場合、上記のケース１で使用した対距離は負になる。これは、リードのストランド性（strandedness）に関する情報がペアリング距離記述子の符号でコード化されていることを意味する。
【０２０３】
表１１．リードペアがどのようにコード化されたかをシグナリングするリード距離記述子（read distance descriptors）の予め定められた値
【表１３】
2020510907.tif 000020
［リード距離］
【０２０４】
リード距離は、２バイトの符号付きの整数でコード化される。
・  ＬＳＢは符号（符号ビットが０の場合、数値は負ではなく、符号ビットが１の場合、数値は負である）を表すために使用され、
・  残りの１５ビットは、ペアリング距離の絶対値を表すために使用される。
【０２０５】
このアプローチは、−３２７６６から３２７６６の範囲のペアリング距離を表すことを可能にする。リードが大きなギャップによって分離される場合、絶対位置は表１２の中で定義される特殊な値０ｘ7ｆｆｄ又は０ｘ８００３の後のｐａｉｒ記述子の中でコード化され、そして２つのリードは２つの別々のゲノムレコード（つまり、ペアは「分割（split）」である）の中でコード化される。
［リード距離のデコード化プロセス］
【０２０６】
リード距離のデコード化プロセスは以下に示される：
【表１４】
2020510907.tif 000021
［ｍｓｃｏｒｅ］
【０２０７】
ｍｓｃｏｒｅ記述子はアラインメントごとのスコアを提供する。それはゲノムシーケンスリードアライナによって生成されたリード当たりのマッピング／アライメントスコアを表すために使用される。
【０２０８】
スコアは、指数部及び仮数部を用いて表示される。指数部及び仮数部を表すために使用されるビット数は、コード化パラメータ（下記のパラメータセットを参照）の中で指定される。表１３は、１１ビットの指数部と５２ビットの仮数部について、ＩＥＥＥＥ  ＲＦＣ７５４でどのように規定されているかを示す。
【０２０９】
各アラインメントのスコアは次のように表す：
・  １つの符号ビット（Ｓ）
・  指数部の１１ビット（Ｅ）
・  少数部の５３ビット（Ｓ）
【０２１０】
表１２．アライメントスコアは、６４ビット倍精度浮動小数点で表される
【表１５】
2020510907.tif 000022
【０２１１】
スコアの計算に使用される塩基（基数）が１０の場合、スコアは次のように計算される。
スコア＝-１ｓ×１０Ｅ×Ｍ
［ｒｇｒｏｕｐ］
【０２１２】
ｒｇｒｏｕｐ記述子は、ゲノムレコードが属するリードグループを識別する。０からｎｕｍ＿ｇｒｏｕｐｓ-１までの符号なしの８ビットの整数である。アクセスユニット内のリードグループの存在は、以下で定義されるパラメータセットで定義されるように、パラメータセット内のｎｕｍ＿ｇｒｏｕｐｓ＞０によって通知される。
［ｍｓａｒ］
【０２１３】
ｍｓａｒ（マルチプルセグメントのアライメントレコード）記述子は、スプライスされたリードと、インデル（indels）又はソフトクリップを含む代替のセカンダリアライメントをサポートする。
【０２１４】
ｍｓａｒは、次の情報を伝達することを目的としている。
・  マッピングされたセグメント長
・  セカンダリアライメント及び／又はスプライスされたリードのための異なるマッピング連続性（例：ＣＩＧＡＲ文字列）
【０２１５】
ｍｓａｒは、アラインメントされたリードデータのミスマッチ、挿入、欠落、ストランド性（strandedness）、セカンダリアラインメントのクリッピングされた基底を表現するために使用できる。
［マルチプルアライメント］
【０２１６】
マルチプルアラインメントをサポートするために、次の記述子が定義されている。
［ｍｍａｐ］
【０２１７】
ｍｍａｐ記述子は、ペアのリード又は左端のリードがアライメントされた位置の数を通知するために使用される。マルチプルアラインメントを含むゲノムレコードは、１つのマルチバイトのｍｍａｐ記述子に関連付けられる。ｍｍａｐ記述子の最初の２バイトは符号なしの整数Ｎを表し、これはリードを単一のセグメント（本開示で定義されているようにｓｐｌｉｃｅｄ＿ｒｅａｄｓ＿ｆｌａｇ＝０の場合）として参照するか、代わりにいくつかの可能なアライメントのためにリードがスプライスされた全てのセグメント（ｓｐｌｉｃｅｄ＿ｒｅａｄｓ＿ｆｌａｇ＝１の場合）を参照する。Ｎの値は、現在のレコードのテンプレート用にコード化されたｐｏｓ記述子の値の数を表す。Ｎの後には、本開示に記載の１つ以上の８ビット符号なしの整数Ｍｉが続く。
［マルチプルアライメントのストランド性］
【０２１８】
マルチプルアラインメントの場合、本開示で定義されるｒｃｏｍｐ記述子は、上記で指定されたものと同じ構文を使用して、各リードアラインメントのストランド性（strandedness）を指定するために使用される。
［マルチプルアライメントのスコア］
【０２１９】
マルチプルアライメントの場合、本開示で定義される１つのｍｓｃｏｒｅが各アライメントに割り当てられる。
【０２２０】
［スプライス無しのマルチプルアライメント］
【０２２１】
アクセスユニットにスプライスが存在しない場合、ｓｐｌｉｃｅｄ＿ｒｅａｄ＿ｆｌａｇは設定が解除される。
【０２２２】
ペアエンドシーケンシングにおいては、ｍｍａｐ記述子は、１６ビットの符号無しの整数Ｎとそれに続く１つ以上の８ビットの符号無し整数Ｍｉで構成され、ｉは１から第１の（ここでは左端）のリードアライメントの完全な数を想定している。スプライスされたか否かにかかわらず、それぞれ第１のリードアライメントに対して、Ｍｉは、第２のリードアライメントをするために使用されるセグメントの数（この場合、スプライスがなければ、これは線形の数に等しくなる）、及び、第１のリードアライメントに対してコード化されるｐａｉｒ記述子の値の数を通知するために使用される。
【０２２３】
Ｍｉの値を用いて第２のリードのアライメントの数を表す
【数３】
2020510907.tif 000023
を計算する。
【０２２４】
Ｍｉ（Ｍｉ＝０）の特別な値は、左端のリードの第ｉ番目のアライメントが、ｋ＜ｉ（上式とマッチングする新しいアラインメントは検出されない）を有する左端のリードの第ｋ番目のアライメントとすでにペアになっている右端のリードのアライメントとペアになっていることを示す。
【０２２５】
たとえば、最も単純な場合は次のようになる：
１．左端のリード位置に１つのアライメントがあり、右端のアライメントに２つの代替アライメントがある場合、Ｎは値１を、Ｍ１は値２をとる。
２．左端のリードで２つの代替アライメントが検出され、右端のアライメントのみが検出された場合、Ｎは値２を、Ｍ１は値１を、Ｍ２は値０をとる。
【０２２６】
Ｍｉが０であるとき、ペアに関連する値は、既存の第２のリードアライメントにリンクしなければならない；そうしないと構文エラーが発生し、アラインメントが壊れたとみなされる。
【０２２７】
例：先に述べたように、第１のリードが２つのマッピング位置を有し、第２のリードが１つのみである場合、Ｎは２であり、Ｍ１は１であり、Ｍ２は０である。これに続いて、テンプレート全体に対する別の代替のセカンダリマッピングが行われる場合、Ｎは値３をとり、Ｍ３は値１をとる。
【０２２８】
図９は、スプライスのないマルチプルアラインメントの場合のＮ、Ｐ、Ｍｉの意味を示し、図１０は、マルチプルアラインメント情報をコード化するためにｐｏｓ、ｐａｉｒ、ｍｍａｐ記述子がどのように使用されるかを示す。
【０２２９】
１０については、以下が適用される：
・  右端のリードは
【数４】
2020510907.tif 000024
個のアライメントを有する。
・  左端のリードの第ｉ番目のアラインメントが、ｋ＜ｉの左端のリードの第ｋ番目のアラインメントと既にペアになっている右端のリードのアラインメントとペアになっている場合、Ｍｉのいくつかの値は＝０になることがある。
・  ペア記述子の１つの予め定められた値は、他のＡＵの範囲に属するアライメントを通知するために存在することができる。もし、それが存在する場合は、常に現在のレコードの最初のペア記述子である。
［スプライスを伴うマルチプルアライメント］
【０２３０】
データセットがスプライスされたリードでコード化される場合、ｍｓａｒ記述子は、本開示において定義されるように、スプライスの長さ及び並び方の表現を可能にする。
【０２３１】
ｍｍａｐ及びｍｓａｒ記述子をデコード化した後、デコーダは、マルチプルマッピングを表すためにコード化されたリード又はリードペアの数、及び各リード又はリードペアのマッピングを構成しているセグメントの数を認識する。これを図１１と図１２に示す。
【０２３２】
図１１を参照すると、以下が適用される。
・  左端のリードは、Ｎ個のスプライス（Ｎ１≦Ｎ）を伴うＮ１個のアライメントを有する。
・  Ｎは、左端のリードの全てのアラインメントに存在するスプライスの数を表し、ｍｍａｐ記述子の最初の値としてコード化される。
・  右端のリードは、
【数５】
2020510907.tif 000025
個のスプライスであり、ここで、Ｍｉは、左端のリードの第ｉ番目のアラインメントに対応する、右端のリードのスプライスの数である（１≦ｉ≦Ｎ１）。換言すれば、Ｐは、右端のリードのスプライスの数を表し、ｍｍａｐ記述子の最初の値に続くＮ個の値を用いて計算される。
・  Ｎ１及びＮ２は、第１及び第２のリードのアラインメントの数を表し、ｍｓａｒ記述子のＮ＋Ｐ値を使用して計算される。
【０２３３】
図１２を参照すると、以下が適用される：
・  左端にはＮ１個のアライメントとＮ個のスプライス（Ｎ１≦Ｎ）がある。Ｎ１＝Ｎ及びＮ２＝Ｐの場合、スプライスは存在しない。
・  右端のリードは、
【数６】
2020510907.tif 000026
個のスプライスｔｊ（１≦ｊ≦Ｐ）及びＮ２（Ｎ２≦Ｐ）個のアライメントを有する。
・  ｐａｉｒ記述子の数は、ＮＰ＝Ｍａｘ（Ｎ１，Ｐ）＋Ｍ０として計算でき、ここで、
・  Ｍ０は、値が０のＭｉの数であり
・  ＮＰは、１つの特別なｐａｉｒ記述子が他のＡＵにアラインメントが存在することを示す場合に１だけ増分する必要がある。
［アライメントスコア］
【０２３４】
ｍｓｃｏｒｅ記述子を使用すると、アラインメントのマッピングスコアをシグナリング（signaling）することができる。シングルエンドシーケンシングでは、テンプレートごとにＮ１の値を有し；ペアエンドシーケンスでは、テンプレート全体のアラインメントごとに値を持つ（すなわち、Ｍｉ−１＞０の場合、第１のリードアライメントの異なるアライメントの数＋さらなる第２のリードアライメントの数）。
スコアの数（Number of scores）＝ＭＡＸ（Ｎ１，Ｎ２）＋Ｍ０
ここで、Ｍ０はＭｉ＝０の総数を表す。
【０２３５】
各アラインメントに関連するスコアの数は、本開示において定義されるように、コード化パラメータａｓ＿ｄｅｐｔｈによって示される。
［スプライスのないマルチプルアライメントの記述子］
【０２３６】
表１３．スプライスの無いマルチプルアラインメントの場合に、1つのゲノムレコードでマルチプルアラインメントを表すのに必要な記述子の数を計算する方法。
【表１６】
2020510907.tif 000027
［プライスを有するマルチプルアライメントの記述子］
【０２３７】
表１４は、スプライスを有するマルチプルアラインメントの場合に、一つのゲノムレコード中のマルチプルアラインメントを表すのに必要な記述子の数を計算する方法を示している。
【０２３８】
表１４．マルチプルアライメントと関連スコアを表すために使用される記述子
【表１７】
2020510907.tif 000028
［異なるシーケンス上のマルチプルアライメント］
【０２３９】
アライメントプロセスで、プライマリマッピングが配置されているリファレンスシーケンスとは別のリファレンスシーケンスへの代替マッピングが見つかることがある。
【０２４０】
ユニークにアライメントされたリードペアについては、例えば、別の染色体上のメイトとのキメラ配列がある場合、絶対的なリード位置を表すためにｐａｉｒ記述子を使用しなければならない。ｐａｉｒ記述子は、リファレンスと、同じテンプレートに対する更なるアラインメントを含む次のレコードとの位置を通知するために使用される。最後のレコード（例えば、代替マッピングが３つの異なるＡＵでコード化されている場合、第３番目）は、最初のレコードのリファレンス及び位置を含む。
【０２４１】
ペアの中で左端のリードに対する一つ以上のアラインメントが、現在コード化されたＡＵに関連するものとは異なるリファレンスシーケンス上に存在する場合、ｐａｉｒ記述子の予め定められた値が使用される（独自のアライメントの場合、別のリファレンスに存在するアライメントに使用されるものとは異なる）。予め定められた値の後には、リファレンスシーケンスの識別子と、次のＡＵに含まれる全ての中で左端のアライメントの位置（つまり、そのレコードのｐｏｓ記述子の最初のデコード化された値）が続く。
［挿入、削除、マッピングされていない部分を含むマルチプルアラインメント］
【０２４２】
代替のセカンダリマッピングが、シーケンスがアライメントされるリファレンス領域の連続性を保存しない場合、実際のシーケンス（及び、置換やインデル（indels）などのミスマッチに関連する記述子）はプライマリアライメントについてのみコード化されるので、アライナによって生成された正確なマッピングを再構築することは不可能である。ｍｓａｒ記述子は、それらがインデル（indels）及び／又はソフトクリップを含む場合に、セカンダリアライメントがリファレンスシーケンス上でどのようにマッピングするかを表現するために使用される。ｍｓａｒがセカンダリアライメントのための特殊な記号「＊」によって表現される場合、デコーダは、プライマリアライメント及びセカンダリアライメントのマッピング位置からセカンダリアライメントを再構築する。
［未加工のデータ］
【０２４３】
未加工のリードは、クラスＵにのみ属する。これらは、アライメントされたデータセット内でマッピングされていないリードとしてコード化される。外部リファレンス又は内部リファレンスにアライメントされたリード用に定義された記述子の一部は、未加工のリードのコード化に使用される。これは、未加工のリードが、コード化されるべきデータから、構築されたリファレンスシーケンスを使用してコード化されるという事実に基づいている。
【表１８】
2020510907.tif 000029
［ｕｒｅａｄｓ］
【０２４４】
ｕｒｅａｄｓ記述子は、現在使用されているアルファベットに属するＡＳＣＩＩ文字のシーケンスとして、逐語的なシーケンスリード表す。
［ｒｔｙｐｅ］
【０２４５】
ｒｔｙｐｅ記述子は、表１５に示すように、ゲノムレコード内の１つのマッピングされていないリード又はリードペアをコード化するために使用される記述子のサブセットを通知するために使用される。
【０２４６】
ｒｔｙｐｅ記述子を使用すると、同じデータセット内でリファレンスに基づく圧縮及びリファレンスに基づかない圧縮を混在させることもできる。このシナリオでは、ｒｔｙｐｅ＝０はリファレンスベースのコード化されたレコードを示し、ｒｔｙｐｅ＞０はリファレンスレス圧縮（この場合、記述子は必要に応じて計算されたリファレンスを参照する）に使用される記述子のセットを示す。
【０２４７】
表１５．ｒｔｙｐｅ記述子の意味
【表１９】
2020510907.tif 000030
［記述子のバイナリ化］
【０２４８】
本発明の一実施形態では、ゲノム記述子の圧縮のためにコンテキスト対応バイナリ算術コード化（ＣＡＢＡＣ）を使用する。ＣＡＢＡＣはまず、コード化される全てのシンボルをバイナリ表現に変換する。バイナリ化プロセスは、算術コード化に先立って、非バイナリシンボル（例えば、マッピング位置、マッピングされたリード長、又はミスマッチの類型）をバイナリコードに変換する。
【０２４９】
各記述子の統計的性質に適合した適切なバイナリ化の選択は、異種要素のブロックに適用された汎用コンプレッサに基づく既存フォーマットよりも良好な圧縮比を提供する。
【０２５０】
次の項では、これらの変数を定義する。
・  ｓｙｍＶａｌ：バイナリ化されるべきゲノム記述子の非バイナリ値。
・  ｃＬｅｎｇｔｈ：値がバイナリ化されるビット数を表す。
・  ｃＭａｘ：バイナリ化できる最大値。大きい値は切り捨てられる。
【０２５１】
以下のバイナリ化テーブルは、これらの変数の固定値について計算されるが、本発明の原理はこれらの値に限定されず、従って、本発明の原理の趣旨を維持しつつ、他の値も本発明の原理に従って使用することができることを理解されたい。
【０２５２】
本開示で使用される各バイナリ化アルゴリズムは、表１６に示される識別子によって識別される。
【０２５３】
表１６．バイナリ化の種類と対応する識別子
【表２０】
2020510907.tif 000031
［バイナリコード化（ＢＩ）］
【０２５４】
これは、各数値がそのバイナリ表現でコード化される標準のバイナリ表現である。変数ｃＬｅｎｇｔｈ−ｂｉｎａｒｉｚａｔｉｏｎ＿ｉｄ＝０の場合に表２９に示される変数ｃＬｅｎｇｔｈ−は、その値が表現されるビット数を表す。
［切捨単項（ＴＵ）バイナリ化］
【０２５５】
ＴＵバイナリ文字列は、ｓｙｍＶａｌに１つのゼロが続くものを連結したものである。ｓｙｍＶａｌ＝ｃＭａｘの場合、末尾の０ビットは破棄される。表１８は、ｃＭａｘ＝３のこの切捨単項バイナリ化のバイナリ文字列を示す。
【０２５６】
表１７．ｃＭａｘ＝３の切捨単項バイナリ化のバイナリ文字列
【表２１】
2020510907.tif 000032
【０２５７】
このバイナリ化プロセスと算術的なデコード化の構文を以下に説明する。
【表２２】
2020510907.tif 000033
ｂｉｎＶａｌｕｅはバイナリ化された値で、０又は１のいずれかである。
［指数ゴロム（ＥＧ）のバイナリ化］
【０２５８】
この手法を使用してバイナリ化されたゲノム記述子の解析プロセスは、ビットストリームの現在の位置から始まり、最初の非ゼロビットまでのビットを読み取り、０に等しい先頭ビットの数をカウントすることから始まる。
【０２５９】
このプロセスは次のように特定される：
【表２３】
2020510907.tif 000034
【０２６０】
変数ｓｙｍＶａｌは以下のように割り当てられる：
【表２４】
2020510907.tif 000035
ここで、ｒｅａｄ＿ｂｉｔｓ関数の呼び出しは、入力として渡されたパラメータに等しいビット数を記憶媒体から読み取る。ｒｅａｄ＿ｂｉｔｓ（「ｌｅａｄｉｎｇＺｅｒｏＢｉｔｓ」）から返された値は、最上位ビットが最初に書き込まれる符号なしの整数のバイナリ表現として解釈される。
【０２６１】
表１８は、ビット列を「ｐｒｅｆｉｘ」ビットと「ｓｕｆｆｉｘ」ビットに分けることによって、Ｅｘｐ−Ｇｏｌｏｍｂコードの構造を示す。「ｐｒｅｆｉｘ」ビットは、ｌｅａｄｉｎｇＺｅｒｏＢｉｔｓの計算のために上記のように解析されるビットであり、表１８のビット列列列において０又は１のいずれかとして示される。「ｓｕｆｆｉｘ」ビットは、ｓｙｍｖａｌの計算において解析されるビットであり、表１８においてｘｉとして示され、ｉは０から先頭のＺｅｒｏＢｉｔｓ−１までの範囲にある。各ｘｉは、０又は１に等しくなる。
【０２６２】
表１８．０から６２までのｓｙｍＶａｌ値のバイナリ表現
【表２５】
2020510907.tif 000036
【０２６３】
表１９は、ｓｙｍＶａｌ値へのビット文字列の明示的な割り当てを示す。
【０２６４】
表１９．指数ゴロムのビットストリームと明示的な形式のｓｙｍＶａｌ
【表２６】
2020510907.tif 000037
【０２６５】
ゲノム記述子に応じて、バイナリ化された構文要素の値は、次のいずれかの方法を使用してデコード化される。
・  デコード化されたゲノム記述子の値は、バイナリ化された記述子に対応するｓｙｍＶａｌ値に等しい
・  デコード化されたゲノム記述子の値は、例えばhttps://en.wikipedia.org/wiki/Exponential-Golomb_codingで定義されたように、ｓｙｍＶａｌを入力として符号付き０次指数ゴロムデコーディングを適用することによって計算される。
［符号付き指数ゴロム（ＳＥＧ）のバイナリ化］
【０２６６】
このバイナリ化方法によれば、ゲノム記述子は、構文要素をその絶対値で昇順に並べ、与えられた絶対値に対する正の値をより低いｓｙｍＶａｌで表すことによって、ｓｙｍＶａｌに関連付けられる。表２０に、割り当て規則を示す。
【０２６７】
表２０．符号付き指数ゴロムのコード化されたゲノム記述子に対するｓｙｍＶａｌへの構文要素の割り当て
【表２７】
2020510907.tif 000038
［切捨指数ゴロム（ＴＥＧ）のバイナリ化］
【０２６８】
このバイナリ化プロセスでは、バイナリ化の計算方法を定義する追加の入力パラメータｔｅｇＰａｒａｍを使用する必要がある。
【０２６９】
このプロセスの出力は、構文要素のＴＥＧのバイナリ化である。
【０２７０】
ＴＥＧのバイナリ文字列は、１（ｓｙｍＶａｌ＝０の場合）又は２（ｓｙｍＶａｌ＞０の場合）の種類のバイナリ化の連結である。
・  値Ｍｉｎ（ｓｙｍＶａｌ、ｔｅｇＰａｒａｍ）に対してｃＭａｃ＝ｔｅｇＰａｒａｍとなる切捨単項バイナリ化
・  ｓｙｍＶａｌ ！＝０の場合、Ａｂｓ（ｓｙｍＶａｌ−ｔｅｇＰａｒａｍ）値に対する指数ゴロムのバイナリ化
【０２７１】
表２１は、ｔｅｇＰａｒａｍ＝２を使用したこの切捨指数ゴロムのバイナリ化のバイナリ文字列を示す。
【０２７２】
表２１．ｔｅｇＰａｒａｍ＝２の切捨指数ゴロムのバイナリ化のバイナリ文字列
【表２８】
2020510907.tif 000039
［符号付き切捨指数ゴロム（ＳＴＥＧ）のバイナリ化］
【０２７３】
このバイナリ化プロセスでは、追加の入力パラメータｓｔｅｇＰａｒａｍを使用する必要がある。
【０２７４】
ＳＴＥＧバイナリ文字列は、１（その場合、ｓｙｍＶａｌ＝０）又は２（他の場合）のバイナリ化の連結である。
１．Ａｂｓ（ｓｙｍＶａｌ）の切捨指数ゴロムのバイナリ化
２．ｓｙｍＶａｌ ！＝０の場合、１（ｓｙｍＶａｌ＜０の場合）又は０（ｓｙｍＶａｌ＞０の場合）に等しい１ビットのフラグ
【０２７５】
表２２は、ｓｔｅｇＰａｒａｍ＝２でのこの符号付き切捨指数ゴロムのバイナリ化のバイナリ文字列を示す。
【０２７６】
表２２．ｓｔｅｇＰａｒａｍ＝２の符号付き切捨指数ゴロムのバイナリ化におけるバイナリ文字列
【表２９】
2020510907.tif 000040
［分割ユニットワイズ切捨単項（ＳＵＴＵ）バイナリ化］
【０２７７】
このバイナリ化プロセスでは、２つの入力パラメータｓｐｌｉｔＵｎｉｔＳｉｚｅとｏｕｔｐｕｔＳｙｍＳｉｚｅを使用する必要がある。ｏｕｔｐｕｔＳｙｍＳｉｚｅは、常にｓｐｌｉｔＵｎｉｔＳｉｚｅの倍数である必要がある。
【０２７８】
ＳＵＴＵバイナリ文字列は、繰り返されるＴＵバイナリの連結であり、ここで、各ＴＵバイナリ化は、ｓｐｌｉｔＵｎｉｔＳｉｚｅビット長であるｓｙｍＶａｌの部分に適用される。つまり、ｓｙｍＶａｌは、ＴＵバイナリ化で得られたｘバイナリ文字列（ｘ＝ｏｕｔｐｕｔＳｙｍＳｉｚｅ／ｓｐｌｉｔＵｎｉｔＳｉｚｅ）で表される。各バイナリ文字列のｃＭａｘパラメータは、ｘＭａｘ＝（１＜＜ｓｐｌｉｔＵｍｉｔＳｉｚｅ）−１と定義される。
【０２７９】
表２３は、ｓｐｌｉｔＵｎｉｔＳｉｚｅ＝２及びｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８を使用した、分割ユニットワイズ切捨単項バイナリ文字列を示す。
【０２８０】
表２３．ｓｐｌｉｔＵｎｉｔＳｉｚｅ＝２及びｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８の分割ユニットワイズ切捨単項バイナリ化のバイナリ文字列
【表３０】
2020510907.tif 000041
【０２８１】
このバイナリ化プロセスのためのビットストリーム構文を以下に説明する。
【０２８２】
表２４．ＴＵバイナリ化のためのＣＡＢＡＣデコード化プロセス
【表３１】
2020510907.tif 000042
［符号付き分割ユニットワイズ切捨単項（ＳＳＵＴＵ）バイナリ化］
【０２８３】
このバイナリ化プロセスでは、２つの入力パラメータｓｐｌｉｔＵｎｉｔＳｉｚｅとｏｕｔｐｕｔＳｙｍＳｉｚｅを使用する必要がある。
【０２８４】
ＳＳＵＴＵバイナリ文字列は、別々のフラグとしてコード化されたｓｙｍＶａｌの符号を有するＳＵＴＵバイナリ化プロセスの拡張によって得られる。
・  値Ａｂｓ（ｓｙｍＶａｌ）に対するＳＵＴＵバイナリ化。
・  ｓｙｍＶａｌ ！＝０の場合、１に等しい（ｓｙｍＶａｌ＜０の場合）か、0に等しい（ｓｙｍＶａｌ＞０の場合）の１ビットフラグである。
【０２８５】
表２５は、ｓｐｌｉｔＵｎｉｔＳｉｚｅ＝２、ｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８を使用した符号付き分割ユニットワイズ切捨単項のバイナリ文字列を示す。
【０２８６】
表２５．ｓｐｌｉｔＵｎｉｔＳｉｚｅ＝２、ｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８を使用した符号付き分割ユニットワイズ切捨単項のバイナリ化におけるバイナリ文字列。
【表３２】
2020510907.tif 000043
【０２８７】
このバイナリ化プロセスの構文を以下に説明する。
【表３３】
2020510907.tif 000044
ｓｉｇｎ＿ｆｌａｇは、ｃｔｘＩｄｘによって識別されるコンテキスト変数のビットのｃａｂａｃデコード化を表す。
ｄｅｃｏｄｅ＿ｃａｂａｃ＿ＳＵＴＵ（）は、ＳＵＴＵバイナリ化のためのｃａｂａｃデコード化プロセスを表す。
［二重切捨単項（ＤＴＵ）バイナリ化］
【０２８８】
このバイナリ化プロセスでは、２つの入力パラメータｓｐｌｉｔＵｎｉｔＳｉｚｅとｏｕｔｐｕｔＳｙｍＳｉｚｅを使用する必要がある。
【０２８９】
ＤＴＵバイナリ文字列は、２つのバイナリ化、すなわちＴＵバイナリ化及びＳＵＴＵバイナリ化の連結である。ＴＵバイナリ化にはパラメータｃＭＡｘが使用され、ＳＵＴＵバイナリ化にはパラメータｓｐｌｉｔＵｎｉｔＳｉｚｅとｏｕｔｐｕｔＳｙｍＳｉｚｅが使用される（ここで、ｃＭＡｘは内部的に派生する）。
・  値Ｍｉｎ（Ａｂｓ（ｓｙｍＶａｌ）、ｃＭａｘ）に対するＴＵバイナリ化の第１の例。
・  Ａｂｓ（ｓｙｍＶａｌ）＞ｃＭＡｘの場合、Ａｂｓ（ｓｙｍＶａｌ）−ｃＭａｘに対するＳＵＴＵバイナリ化の第２の例。
【０２９０】
表２6は、ｃＭＡｘ＝1、ｓｐｌｉｔＵｎｉｔＳｉｚｅ＝２、ｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８を使用した二重切捨単項バイナリ化のバイナリ文字列を示す。
【０２９１】
表２６．ｃＭＡｘ＝1、ｓｐｌｉｔＵｎｉｔＳｉｚｅ＝２、ｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８の二重切捨単項バイナリ化のバイナリ文字列
【表３４】
2020510907.tif 000045
【０２９２】
このバイナリ化プロセスを以下に説する。
【表３５】
2020510907.tif 000046
ｄｅｃｏｄｅ＿ｃａｂａｃ＿ＴＵ（）は、ＴＵバイナリ化のためのｃａｂａｃデコード化プロセスを表す。
ｄｅｃｏｄｅ＿ｃａｂａｃ＿ＳＵＴＵ（）は、ＳＵＴＵバイナリ化のためのｃａｂａｃのデコード化プロセスを表す。
［符号付き二重切捨単項（ＳＤＴＵ）バイナリ化］
【０２９３】
このバイナリ化プロセスは、２つの追加入力パラメータｓｐｌｉｔＵｎｉｔＳｉｚａｅとｏｕｔｐｕｔＳｙｍＳｉｚｅを使用する必要がある。
【０２９４】
ＳＤＴＵバイナリ文字列は、フラグとしてコード化されたｓｙｍＶａｌの符号付きＤＴＵバイナリ化プロセスの拡張により得られる。
・  値Ａｂｓ（ｓｙｍＶａｌ）に対するＤＴＵバイナリ化。
・  ｓｙｍＶａｌ ！＝0の場合、１に等しい（ｓｙｍＶａｌ＜０の場合）か、０に等しい（ｓｙｍＶａｌ＞０の場合）の１ビットのフラグである。
【０２９５】
表２７は、ｃＭａｘ＝１、ｓｐｌｉｔＵｎｉｔＳｉｚａｅ＝２、ｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８を使用した、二重切捨単項バイナリ化のバイナリ文字列を示す。
【０２９６】
表２７．ｃＭａｘ＝１、ｓｐｌｉｔＵｎｉｔＳｉｚａｅ＝２、ｏｕｔｐｕｔＳｙｍＳｉｚｅ＝８の場合の二重切捨単項バイナリ化のバイナリ文字列
【表３６】
2020510907.tif 000047
【０２９７】
このバイナリ化プロセスの構文を以下に説明する。
【表３７】
2020510907.tif 000048
ｓｉｇｎ＿ｆｌａｇは、ｃｔｘＴｄｘによって識別されるコンテキスト変数のビットのｃａｂａｃデコード化を表す。
ｄｅｃｏｄｅ＿ｃａｂａｃ＿ＤＴＵ（）は、ＤＴＵバイナリ化によるｃａｂａｃデコード化を表す。
［バイナリ化のパラメータ］
【０２９８】
前のセクションで紹介した各バイナリ化アルゴリズムは、コード化及びデコード化の終了時に構成パラメータを必要とする。一実施形態では、前記の構成パラメータは、表２８に記載のデータ構造にカプセル化される。各バイナリ化アルゴリズムは、表１６に記載の識別子によって識別される。
【０２９９】
表２８．バイナリ化パラメータの構成
【表３８】
2020510907.tif 000049
【０３００】
表2８では、次の意味（semantics）が適用される。
ｃＭａｘは、バイナリ化される最大値を表す。大きい値は切り捨てられる。
ｃＬｅｎｇｔｈは、バイナリ化される値のビット数を表す。
ｔｅｇＰａｒａｍは、本開示においてＴＥＧバイナリ化用に定義されるｔｅｇＰａｒａｍ変数を表す。
ｓｔｅｇＰａｒａｍは、本開示においてＳＴＥＧバイナリ化用に定義されるｓｔｅｇＰａｒａｍ変数を表す。
ｓｐｌｉｔＵｎｉｔＳｉｚｅは、本開示でＳＵＴＵ、ＳＳＵＴＵ及びＤＴＵバイナリ化用に定義されるｓｐｌｉｔＵｎｉｔＳｉｚｅ変数を表す。
ｏｕｔｐｕｔＳｙｍＳｉｚｅは、本開示でＳＵＴＵ、ＳＳＵＴＵ、ＤＴＵ及びＳＤＴＵバイナリ化用に定義されるｏｕｔｐｕｔＳｙｍＳｉｚｅ変数を表す。
［本発明の技術的利点の証拠］
【０３０１】
表２９に示されるように、示されたＣＡＢＡＣバイナリ化をそれぞれのゲノム記述子に適用することによって、表３０に示される圧縮性能を得ることができる。本開示に記載された方法の圧縮性能の改善は、ＢＡＭ及びＣＲＡＭアプローチの対応するファイルサイズ、及びＤｅｅＺ（ヌマヤギッチ，Ｉ．（Numanagic, I.）、他、「高スループットシーケンシングデータ圧縮ツールの比較（Comparison of high-throughput sequencing data compression tools）」、ネイチャーメソッド（Nature Methods）（ISSN:1548-7091）、ｖｏｌ．１３、ｐ．１００５−１００８、ロンドン：ネイチャーパブリッシンググループ、２０１６）として知られている文献における最良のコンプレッサのうちの一つと比較することによって評価することができる。ＤｅｅＺ、ＢＡＭ及びＣＲＡＭの圧縮性能は、圧縮されたゲノムシーケンスデータのサイズにアラインメントに使用される圧縮リファレンスゲノムのサイズを加えることによって計算されることを理解されたい。本開示の原理によれば、リファレンスゲノムは圧縮ファイルに埋め込まれる。今日では、圧縮リファレンスゲノムは、ＧＺＩＰ、ＬＺＭＡ、Ｂｚｉｐ２などの汎用コンプレッサを用いて圧縮されたＦＡＳＴＡ（ＡＳＣＩＩテキスト）ファイルであると述べられている。提案された比較では、リファレンスゲノムｈｓ３７ｄ５．ｆａを最大圧縮（−９）のオプション付きのｘｚ  Ｌｉｎｕｘ（登録商標）コマンドを使って圧縮した。
［記述子に適用されるバイナリ化］
【０３０２】
表３０は、本開示において定義されるゲノム記述子に適用されるバイナリ化を示す。いくつかのバイナリ化の連結が示される場合、異なるバイナリ化は、本開示で定義されるように、各記述子を構成する異なる要素に適用される。
【０３０３】
表２９．各ゲノム記述子に関連付けられたバイナリ化
【表３９】
2020510907.tif 000050
［ｒｆｔｐ及びｒｆｔｔ］
【０３０４】
ｒｆｔｐ及びｒｆｔｔのバイナリ化の例を本セクションで示し、図１０に示す。
【０３０５】
コンティグとアラインメントに用いたリファレンスゲノムとの間の５つのミスマッチに関連する記述子を以下に示す。
【表４０】
2020510907.tif 000051
【０３０６】
各ヌクレオチドのシンボルは整数コードに関連付けられている。
【表４１】
2020510907.tif 000052
【０３０７】
変換後の値は次のようになる。
【表４２】
2020510907.tif 000053
【０３０８】
ｒｆｔｐのバイナリ化された値は次のように計算される。
１．ターミネータ（terminator）の値は、０又は１としてバイナリ化できる。この例では、０を選択している。
２．ターミネータ（terminator）＝０の場合、ｓｐｌｉｔＵｎｉｔＳｉｚｅ＝４でのバイナリ化Ｎｏ．６が使用され、ｏｕｔｐｕｔＳｙｍｂｏｌＳｉｚｅ＝１２が使用され、次のバイナリ文字列がｒｆｔｐの値に関連付けられる。
ａ．  ５＝１１１１０
ｂ．  ２＝１１０
ｃ．  ５＝１１１１０
ｄ．  １＝１０
ｅ．  ２＝１１０
【０３０９】
ｒｆｔｔのバイナリ化された値は、次のように計算される。
１．リファレンスゲノム中に存在するヌクレオチドを知っていれば、コード化される可能性のある記号から対応する記号を取り除く。すなわち。この例の最初のミスマッチでは、リファレンス内の対応するシンボルが「Ｇ」である場合、コード化される可能性のあるシンボルのスペースは０、１、３、４である。
２．コード化されるデータ上のミスマッチの類型のシンボルの頻度が測定され、０から３のインデックスが付けられる。インデックス０は最も頻度の高いミスマッチに影響され、インデックス３はより頻度の低いミスマッチに影響される。この例では、インデックス作成は次のようになる。{0=>3、1=>0、2=>4、3=>1}
３．与えられた例では、５つのミスマッチは以下のようにＴＵバイナリ化を使用してバイナリ化される：
【表４３】
2020510907.tif 000054
【０３１０】
上記のバイナリ化アプローチにより、以下の圧縮結果が得られる：
【０３１１】
表３０．最先端のソリューションに関する圧縮パフォーマンス（バイト単位のサイズ）
【表４４】
2020510907.tif 000055
＊本開示の原則に従って、圧縮された表現で既に利用可能であるため、追加情報は必要ない。
［コード化パラメータ］
【０３１２】
一実施形態では、各アクセスユニットをコード化及びデコード化するのに必要なパラメータは、表３１に定義されるパラメータセットという名前のデータ構造でカプセル化される。
【０３１３】
表３１．ゲノム記述子のコード化パラメータ
【表４５】
2020510907.tif 000056
2020510907.tif 000057
［コード化装置］
【０３１４】
図１３は、本発明の原理に基づくコード化装置を示す。コード化装置は、リファレンスゲノム１３０２、及び、例えばゲノムシーケンシング装置によって生成された非アライメントゲノムシーケンス１３００を入力として受け取る。ゲノムシーケンシング装置は、イルミナＨｉＳｅｑ２５００、Ｔｈｅｒｍｏ−Ｆｉｓｈｅｒ  Ｉｏｎ  Ｔｏｒｒｅｎｔの装置又はＯｘｆｏｒｄＮａｎｏｐｏｒｅ  ＭｉｎＩＯＮのような当技術分野において公知である。アライメントされていないシーケンスデータ１３００は、リードアライメントユニット１３０１に供給され、それは、リファレンスゲノム１３０２上のシーケンスをマッピングする。次いで、アライメントされたゲノムシーケンス３０３は、マッピングされた及びマッピングされていないゲノムシーケンスの両方を表すゲノム記述子１３０６を生成するリファレンスに基づくコンプレッサ１３０５に供給される。リファレンスに基づくコンプレッサ１３０５によって生成されたゲノム記述子１３０６は、最初にいくつかのバイナリ化ユニット１３０７によってバイナリ化され、次にいくつかのエントロピーエンコーダ１３０８によってエントロピーコード化される。エントロピーコード化ゲノム記述子は、次に、多重化装置１３１０に供給され、圧縮ビットストリーム１３１１を構成する一つ以上のアクセスユニットを構築する。多重化されたビットストリームは、コード化パラメータエンコーダ１３０９によって構築されたコード化パラメータ構造１３０をも含む。各アクセスユニットは、本開示において定義されるように、アライメント情報及び１つのクラスのデータに属するシーケンスリードを表すエントロピーコード化記述子を含む。
［デコード化装置］
【０３１５】
図１４は、本開示の原理に基づくデコード化装置を示す。多重分離ユニット１４０1は、ネットワーク又は記憶素子から多重化ビットストリーム１４００を受信し、当該ビットストリームを構成するアクセスユニットのエントロピーコード化ペイロードを抽出する。エントロピーデコーダ１４０２は、抽出されたペイロードを受信し、異なるタイプのゲノム記述子をそれらのバイナリ表現にデコード化する。次いで、前記バイナリ表現は、ゲノム記述子１４０５を生成するいくつかのバイナリデコーダ１４０４に供給される。コード化パラメータデコーダ１４０３は、ゲノム情報と多重化されたコード化パラメータを受信し、デコードユニット１４０６に供給する。ゲノムシーケンスリードを表すゲノム記述子１４０５は、シーケンスリード再構築ユニット１４０６に供給され、それは、利用可能なリファレンスゲノム１４０８を用いて、アライメントされたゲノムシーケンス１４０７を再構築する。
【０３１６】
本明細書に開示された本発明の技術は、ハードウェア、ソフトウェア、ファームウェア、又はそれらの任意の組み合わせで実施することができる。ソフトウェアで実現される場合、これらは、コンピュータ媒体に記憶され、ハードウェア処理ユニットによって実行されてもよい。ハードウェア処理ユニットは、１つ以上のプロセッサ、デジタルシグナルプロセッサ、汎用マイクロプロセッサ、特定用途向け集積回路又は他の個別論理回路を含むことができる。
【０３１７】
本開示の技術は、携帯電話、デスクトップコンピュータ、サーバ、タブレット及び同様のデバイスを含む様々なデバイス又は装置で実施することができる。
【図１】
2020510907.tif 000058
【図２】
2020510907.tif 000059
【図３】
2020510907.tif 000060
【図４】
2020510907.tif 000061
【図５】
2020510907.tif 000062
【図６】
2020510907.tif 000063
【図７】
2020510907.tif 000064
【図８】
2020510907.tif 000065
【図９】
2020510907.tif 000066
【図１０】
2020510907.tif 000067
【図１１】
2020510907.tif 000068
【図１２】
2020510907.tif 000069
【図１３】
2020510907.tif 000070
【図１４】
2020510907.tif 000071
【図１５】
2020510907.tif 000072
【図１６】
2020510907.tif 000073
【図１７】
2020510907.tif 000074
【図１８】
2020510907.tif 000075
【図１９】
2020510907.tif 000076
【手続補正書】
【提出日】平成30年12月14日(2018.12.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ヌクレオチドシーケンスのリードを含むゲノムシーケンスデータをコード化する方法であって、
前記リードを1つ以上のリファレンスシーケンスにアラインメントし、それによってシーケンスリードを作成し、
前記1つ以上のリファレンスシーケンスとの指定されたマッチング規則に従って前記アライメントされたリードを分類し、それによって同種のデータのブロックに配置されたゲノム記述子によって表される、アライメントリードのクラスを作成し、
前記分類されたアライメントリードを、構文要素の多重のブロックとしてコード化し、
構文要素及び前記記述子の前記ブロックをヘッダ情報で構成し、それによって連続的なアクセスユニットを作成すること、を含み、
前記コード化は、前記ゲノム記述子をバイナリ化及びエントロピーコード化する、
ことを含む方法。
【請求項２】
前記コード化及びエントロピーコード化されたゲノム記述子は、コード化及びエントロピーコード化が異なる記述子に対して異なるようにされている、
請求項１に記載の方法。
【請求項３】
前記記述子は、
リファレンスシーケンスのリードのマッピング位置をシグナリングするためのｐoｓ、
アライナがマッピングロセスの結果をさらに指定できるようにするために、リードがマッピングフラグにマッピングされたＤＮＡ又はＲＮＡ鎖をシグナリングするためのｒｃｏｍｐを含む、
請求項２に記載の方法。
【請求項４】
以下の記述子：
リファレンスシーケンスに関してアライメントされたリードのミスマッチの位置をシグナリングするｍｍｐoｓ、
関連付けられた位置のリファレンスシーケンスに関するミスマッチの類型をシグナリングするｍｍｔｙｐe、
をコード化することをさらに含む、
請求項３に記載の方法。
【請求項５】
ソフト又はハードクリップされたヌクレオチドをシグナリングするためのクリップ記述子をコード化することをさらに含む、
請求項４に記載の方法。
【請求項６】
各コード化されたシーケンスリードの長さをシグナリングするためにｒｌeｎ記述子をコード化することをさらに含む、
請求項５に記載の方法。
【請求項７】
以下の記述子：
マッピング手順によって単一のリード又はペアリードに関連付けられたマルチプルマッピング位置をシグナリングするためのｍｍａｐ、
スプライスされたリードが存在することの識別をシグナリングするｍｓａｒ（すなわち、リードは、チャンクに分割された場合、リファレンスシーケンス上の単一の位置にマッピングされた単一の連続したリードとしてマッピングされた場合よりも、マッチング精度の高いマッピング位置を見つける）、
をコード化することをさらに含む、
請求項６に記載の方法。
【請求項８】
ｍｓｃｏｒｅ記述子をコード化して、ゲノムシーケンスリードアライナによって生成されるリード当たりのマッピング／アラインメントスコアをシグナリングすることをさらに含む、
請求項７に記載の方法。
【請求項９】
ペアエンドリードにおいて、前記リードがどのようにペアリングされるかを示すために前記ｐａｉｒ記述子をコード化することをされに含む、
請求項８に記載の方法。
【請求項１０】
前記リファレンスシーケンスのいずれの位置にもアライメントできなかったリードをシグナリングするためのｕｒｅａｄｓ記述子をコード化することをさらに含む、
請求項９に記載の方法。
【請求項１１】
指定されたマッチング精度で前記リファレンスシーケンスのどの位置にもマッピングできないシーケンスリードをコード化するために使用される前記記述子のサブセットを通知するために使用されるｔｔｙｐｅ記述子をコード化することをさらに含む、
請求項１０に記載の方法。
【請求項１２】
前記リードがどのリードグループに属するかを示すために、ｒｇｒｏｕｐ記述子をコード化することをさらに含む、
請求項１１に記載の方法。
【請求項１３】
以下の記述子：
コンティグとリファレンスシーケンス間のミスマッチの位置をシグナリングするためのｒｆｔｐ、ミスマッチの位置は特殊なターミネータ文字で終了し、
コンティグとリファレンスシーケンス間のミスマッチの類型をシグナリングするｒｆｔｔ、
をコード化することをさらに含む、
請求項１２に記載の方法。
【請求項１４】
前記ｐoｓ記述子は、二重切捨単項コード又は単一の二重切捨単項コードを使用してバイナリ化され、
前記ｒｃoｍｐ記述子は、切捨単項コードを使用してバイナリ化され、
前記マッピングのｆｌａｇｓ記述子は、バイナリコード化を使用してバイナリ化される、
請求項１３に記載の方法。
【請求項１５】
リファレンスシーケンスに関するアライメントされたリードのミスマッチの位置をシグナリングするための前記ｍｍｐｏｓ記述子は、分割ユニットごとに切捨単項コードを使用してバイナリ化され、
関連する位置のリファレンスシーケンスに関してミスマッチの類型をシグナリングするための前記ｍｍｔｙｐｅ記述子は切捨単項コードを使用してバイナリ化される、
請求項４に記載の方法。
【請求項１６】
ソフト又はハードのクリップされたヌクレオチドをシグナリングするための前記クリップ記述子は、符号付き切捨指数ゴロム、切捨単項、符号付き指数ゴロム及びバイナリコードの連結を使用してバイナリ化される、
請求項５に記載の方法。
【請求項１７】
各コード化されたシーケンスリードの長さをシグナリングする前記ｒｌｅｎ記述子は、分割ユニットワイズ切捨単項コードを使用してバイナリ化される、
請求項６に記載の方法。
【請求項１８】
マッピング手順によって単一のリード又はリードペアに関連付けられたマルチプルマッピング位置をシグナリングするための前記ｍｍａｐ記述子は、分割ユニットワイズ切捨単項コードを使用してバイナリ化され、
前記スプライスされたリードの存在の識別をシグナリングするための前記ｍｓａｒ記述子は、符号付き指数ゴロムコードを使用してバイナリ化される、
請求項７に記載の方法。
【請求項１９】
ゲノムシーケンスリードアライナによって生成された各リードのマッピング／アライメントスコアをシグナリングする前記ｍｓｃｏｒｅ記述子は、切捨単項コードを使用してバイナリ化される、
請求項８に記載の方法。
【請求項２０】
前記ｐａｉｒ記述子をシグナリングするために、ペアエンドリードの場合において、どのようにリードがペア化されたかは、バイナリコードと分割ユニットワイズ切捨単項コードの連結を使用してバイナリ化する、
請求項９に記載の方法。
【請求項２１】
前記リファレンスシーケンスのいずれの位置にもアライメントすることができなかったリードのシグナリングに対する前記ｕｒｅａｄｓ記述子は、切捨単項コードを使用してバイナリ化される、
請求項１０に記載の方法。
【請求項２２】
前記ｒｔｙｐｅ記述子は、指定されたマッチング精度で前記リファレンスシーケンスの任意の位置にマッピングすることができないシーケンスリードをコード化するために使用される前記記述子のサブセットの信号をシグナリングするために使用され、切捨単項コードを使用してバイナリ化される、
請求項１１に記載の方法。
【請求項２３】
前記リードがどのリードグループが属するかをシグナリングするｒｇｒｏｕｐ記述子は、切捨単項コードを用いてバイナリ化される、
請求項１２に記載の方法。
【請求項２４】
前記ｒｆｔｐ記述子は、コンティグとリファレンスシーケンスとの間のミスマッチの位置をシグナリングするために、バイナリコード化と分割ユニットワイズ切捨単項コードの連結を用いてバイナリ化され、
コンティグとリファレンスシーケンスの間のミスマッチのタイプをシグナリングするための前記ｒｆｔｔ記述子は、バイナリコード化と切捨単項コードの連結を使用してバイナリ化される、
請求項１３に記載の方法。
【請求項２５】
前記記述子は、構成パラメータを構文ヘッダに挿入することによってコード化される、
請求項１３に記載の方法。
【請求項２６】
前記構成パラメータは、構文ヘッダがコード化されたゲノムファイルに追加されて更新されることによって更新される、
請求項２５に記載の方法。
【請求項２７】
前記構成パラメータは、コード化パラメータを参照してアクセスユニット内でコード化されたデータの種類をシグナリングするためのデータセットタイプを含む、
請求項２６に記載の方法。
【請求項２８】
前記構成パラメータは、リード長が一定の場合に、シーケンスリードのヌクレオチド長をシグナリングするためのリード長をさらに含む、
請求項２７に記載の方法。
【請求項２９】
前記構成パラメータは、各コード化されたヌクレオチドに関する品質値の数をシグナリングするための品質値深度パラメータをさらに含む、
請求項２８に記載の方法。
【請求項３０】
前記構成パラメータは、各コード化されたアライメントに関連するアライメントスコアの数をシグナリングするためのアライメントスコア深度をさらに含む、
請求項２９に記載の方法。
【請求項３１】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルのバイト単位のサイズをシグナリングするためのターミネータサイズをさらに含む、
請求項３０に記載の方法。
【請求項３２】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルの値をシグナリングするためのターミネータ値をさらに含む、
請求項３１に記載の方法。
【請求項３３】
前記構成パラメータは、前記構成パラメータを参照して全てのアクセスユニット内でコード化されたデータクラスの数をシグナリングするためのクラスの数をさらに含む、
請求項３２に記載の方法。
【請求項３４】
前記構成パラメータは、各データクラスに関連付けられた識別子をシグナリングするクラス識別子をさらに含む、
請求項３３に記載の方法。
【請求項３５】
前記構成パラメータは、前記構成パラメータを参照して、アクセスユニットに含まれる記述子の総数をシグナリングするための記述子の数をさらに含む、
請求項３４に記載の方法。
【請求項３６】
前記構成パラメータは、異なるコード化モードのコード化モード識別子をさらに含む、
請求項３５に記載の方法。
【請求項３７】
前記構成パラメータは、現在のコード化パラメータを参照する全てのアクセスユニットに存在する前記ｒｇｒoｕｐ記述子の異なる値の数をシグナリングするためのグループ数パラメータをさらに含む、
請求項３６に記載の方法。
【請求項３８】
前記構成パラメータは、１つ以上のリードグループ識別子をシグナリングするための１つ以上のグループ名パラメータをさらに含む、
請求項３７に記載の方法。
【請求項３９】
前記構成パラメータは、前記アクセスユニット内のマルチプルアライメントの存在をシグナリングするためのマルチプルアライメントフラグをさらに含む、
請求項３８に記載の方法。
【請求項４０】
前記構成パラメータは、前記アクセスユニット内のスプライスされたリードの存在をシグナリングするためのスプライスされたリードフラグをさらに含む、
請求項３９に記載の方法。
【請求項４１】
前記構成パラメータは、マッピングされていないシーケンスリード（クラスＵ）を含むアクセスユニット内の複数のシグネチャの使用をシグナリングするためのマルチプルシグネチャ塩基フラグをさらに含む、
請求項４０に記載の方法。
【請求項４２】
前記構成パラメータは、コード化されたシグネチャを表す各整数のビット単位のサイズをシグナリングするためのシグネチャサイズをさらに含む、
請求項４１に記載の方法。
【請求項４３】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの指数部をコード化するために使用されるビット数をシグナリングするためのスコア指数パラメータをさらに含む、
請求項４２に記載の方法。
【請求項４４】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの仮数部分をコード化するために使用されるビット数をシグナリングするためのスコア仮数パラメータをさらに含む、
請求項４３に記載の方法。
【請求項４５】
ヌクレオチドシーケンスのリードを含むゲノムシーケンスデータのコード化されたゲノムデータをデコード化する方法であって、
ヘッダ情報を用いてゲノム記述子のマルチプルブロックを抽出して前記コード化されたゲノムデータを含むアクセスユニットを解析し、前記マルチプルブロックをデコード化することを含み、
前記マルチプルブロックのデコード化は、１つ以上のリファレンスシーケンスに関する分類を定義する特定のマッチング規則に従ってアライメントされたリードを抽出するために、同種のデータのブロックに配置されたゲノム記述子をデコード化及びバイナリ化解除することを含む、
方法。
【請求項４６】
前記記述子は、
リファレンスシーケンス上のリードのマッピング位置をシグナリングするためのｐｏｓ記述子、
アライナがマッピングロセスの結果をさらに指定できるようにするために、リードがマッピングフラグにマッピングされたＤＮＡ又はＲＮＡ鎖をシグナリングするためのｒｃｏｍｐ記述子を含む、
請求項４５に記載の方法。
【請求項４７】
以下の記述子：
リファレンスシーケンスに関してアライメントされたリードのミスマッチの位置をシグナリングするｍｍｐoｓ、
関連付けられた位置のリファレンスシーケンスに関するミスマッチの類型をシグナリングするｍｍｔｙｐe、
をデコード化することをさらに含む、
請求項３に記載の方法。
【請求項４８】
ソフト又はハードクリップされたヌクレオチドをシグナリングするためのクリップ記述子をデコード化することをさらに含む、
請求項４７に記載の方法。
【請求項４９】
各コード化されたシーケンスリードの長さをシグナリングするためにｒｌeｎ記述子をコデード化することをさらに含む、
請求項４８に記載の方法。
【請求項５０】
以下の記述子：
マッピング手順によって単一のリード又はペアリードに関連付けられたマルチプルマッピング位置をシグナリングするためのｍｍａｐ、
スプライスされたリードが存在することの識別をシグナリングするｍｓａｒ（すなわち、リードは、チャンクに分割された場合、リファレンスシーケンス上の単一の位置にマッピングされた単一の連続したリードとしてマッピングされた場合よりも、マッチング精度の高いマッピング位置を見つける）、
をデコード化することをさらに含む、
請求項４９に記載の方法。
【請求項５１】
ｍｓｃｏｒｅ記述子をデコード化して、ゲノムシーケンスリードアライナによって生成されるリード当たりのマッピング／アラインメントスコアをシグナリングすることをさらに含む、
請求項５０に記載の方法。
【請求項５２】
ペアエンドリードにおいて、前記リードがどのようにペアリングされるかを示すために前記ｐａｉｒ記述子をデコード化することをされに含む、
請求項５１に記載の方法。
【請求項５３】
前記リファレンスシーケンスのいずれの位置にもアライメントできなかったリードをシグナリングするためのｕｒｅａｄｓ記述子をデコード化することをさらに含む、
請求項５１に記載の方法。
【請求項５４】
指定されたマッチング精度で前記リファレンスシーケンスのどの位置にもマッピングできないシーケンスリードをコード化するために使用される前記記述子のサブセットを通知するために使用されるｔｔｙｐｅ記述子をデコード化することをさらに含む、
請求項５３に記載の方法。
【請求項５５】
前記リードがどのリードグループに属するかを示すために、ｒｇｒｏｕｐ記述子をデコード化することをさらに含む、
請求項５４に記載の方法。
【請求項５６】
以下の記述子：
コンティグとリファレンスシーケンス間のミスマッチの位置をシグナリングするためのｒｆｔｐ、ミスマッチの位置は特殊なターミネータ文字で終了し、
コンティグとリファレンスシーケンス間のミスマッチの類型をシグナリングするｒｆｔｔ、
をデコード化することをさらに含む、
請求項５５に記載の方法。
【請求項５７】
前記記述子は、構文ヘッダから構成パラメータを抽出することによりデコード化される、
請求項５６に記載の方法。
【請求項５８】
前記構成パラメータは、コード化パラメータを参照してアクセスユニット内でコード化されたデータの種類をシグナリングするためのデータセットタイプ
を含む、
請求項５７に記載の方法。
【請求項５９】
前記構成パラメータは、リード長が一定の場合に、シーケンスリードのヌクレオチド長をシグナリングするためのリード長をさらに含む、
請求項２８に記載の方法。
【請求項６０】
前記構成パラメータは、各コード化されたヌクレオチドに関する品質値の数をシグナリングするための品質値深度パラメータをさらに含む、
請求項５９に記載の方法。
【請求項６１】
前記構成パラメータは、各コード化されたアライメントに関連するアライメントスコアの数をシグナリングするためのアライメントスコア深度をさらに含む、
請求項６０に記載の方法。
【請求項６２】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルのバイト単位のサイズをシグナリングするためのターミネータサイズをさらに含む、
請求項６１に記載の方法。
【請求項６３】
前記構成パラメータは、前記ｍｍｐoｓ記述子に使用されるターミネータシンボルの値をシグナリングするためのターミネータ値をさらに含む、
請求項６２に記載の方法。
【請求項６４】
前記構成パラメータは、前記構成パラメータを参照して全てのアクセスユニット内でコード化されたデータクラスの数をシグナリングするためのクラスの数をさらに含む、
請求項６３に記載の方法。
【請求項６５】
前記構成パラメータは、各データクラスに関連付けられた識別子をシグナリングするクラス識別子をさらに含む、
請求項６４に記載の方法。
【請求項６６】
前記構成パラメータは、前記構成パラメータを参照するアクセスユニットに含まれる記述子の総数をシグナリングするための記述子の数をさらに含む、
請求項６５に記載の方法。
【請求項６７】
前記構成パラメータは、本開示で定義されたコード化モードをシグナリングするためのコード化モード識別子をさらに含む、
請求項６６に記載の方法。
【請求項６８】
前記構成パラメータは、現在のコード化パラメータを参照する全てのアクセスユニットに存在する前記ｒｇｒoｕｐ記述子の異なる値の数をシグナリングするためのグループ数パラメータをさらに含む、
請求項６７に記載の方法。
【請求項６９】
前記構成パラメータは、１つ以上のリードグループ識別子をシグナリングするための１つ以上のグループ名パラメータをさらに含む、
請求項６８に記載の方法。
【請求項７０】
前記構成パラメータは、前記アクセスユニット内のマルチプルアライメントの存在をシグナリングするためのマルチプルアライメントフラグをさらに含む、
請求項６９に記載の方法。
【請求項７１】
前記構成パラメータは、前記アクセスユニット内のスプライスされたリードの存在をシグナリングするためのスプライスされたリードフラグをさらに含み、ここで０に設定されるとスプライスされたリードは存在しない、
請求項７０に記載の方法。
【請求項７２】
前記構成パラメータは、マッピングされていないシーケンスリード（クラスＵ）を含むアクセスユニット内の複数のシグネチャの使用をシグナリングするためのマルチプルシグネチャ塩基フラグをさらに含む、
請求項７１に記載の方法。
【請求項７３】
前記構成パラメータは、コード化されたシグネチャを表す各整数のビット単位のサイズをシグナリングするためのシグネチャサイズをさらに含む、
請求項７２に記載の方法。
【請求項７４】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの指数部をコード化するために使用されるビット数をシグナリングするためのスコア指数パラメータをさらに含む、
請求項７３に記載の方法。
【請求項７５】
前記構成パラメータは、前記ｍｓｃｏｒｅ記述子にコード化されたマルチプルアライメントスコアの仮数部分をコード化するために使用されるビット数をシグナリングするためのスコア仮数パラメータをさらに含む、
請求項７４に記載の方法。
【請求項７６】
請求項１に記載のコード化方法を実施するためのコード化手段を備えるコード化装置。
【請求項７７】
請求項４５に記載のデコード化方法を実施するためのデコード手段を備えるデコード化装置。
【請求項７８】
請求項１３に記載のゲノム記述子を含むファイルフォーマット。
【請求項７９】
請求項１に記載のコード化方法を実行するための命令を含むコンピュータプログラム。
【請求項８０】
請求項４５に記載のデコード化方法を実行するための命令を含むコンピュータプログラム。
【請求項８１】
請求項８０のコンピュータプログラムを保存するためのストレージ手段。
【請求項８２】
請求項１のコード化方法で作成されたファイルを保存するためのストレージ手段。
【国際調査報告】
2020510907.tif 000077
2020510907.tif 000078
2020510907.tif 000079