テスト配列の誤り訂正方法、対応するシステム及び遺伝子のアセンブリ装置
本発明は、テスト配列の誤り訂正方法であって、配列を受け取り、そして高頻度の短い配列リストを、予め定められた高頻度閾値に基づき構築すること、それぞれの受け取ったテスト配列を配列方向に調べ、そして高頻度の短い配列と組み合わせて、それぞれのテスト配列上の連続した高頻度の短い配列の最大多数の領域を検索すること、対応する受け取ったテスト配列及び高頻度の短い配列リストに従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築すること、及び検索した領域と構築した左側及び／又は右側の配列とを、対応するテスト配列へと結合することを含む。また、本発明は、テスト配列及び遺伝子アセンブリ装置の対応する誤り訂正システムを提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遺伝子工学の技術分野に関し、より詳しくは、テスト配列の誤り訂正方法、対応するシステム及び遺伝子のアセンブリ装置に関する。
【背景技術】
【０００２】
既存の遺伝子のシークエンシング技術に基づき、塩基の配列決定において誤りが起こる可能性がある。シークエンシングにおける誤りは、後続のデータ解析、短い配列のアセンブリ等に影響する。誤りのない配列が低頻度の短い配列を含む可能性は、深いシークエンシングデプスでは非常に低いため、既存の誤り訂正の戦略は、テスト配列中の低頻度の短い配列を単純に選別し、そして低頻度の短い配列を特定の比率で含む配列を除去することである。実際に、有効な誤り訂正が行われず、それは、テスト配列の低い利用率につながる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明の態様の目的は、テスト配列の誤り訂正方法を提供することであり、それは、既存のテスト配列の誤り訂正方法におけるテスト配列の低い利用率という以下の問題を解決することを意図する。
【０００４】
本発明の一態様は、以下のステップを含む、テスト配列の誤り訂正方法により実行される：
配列を受け取り、そして高頻度の短い配列リストを、予め定められた高頻度閾値に基づき構築すること、
受け取ったそれぞれのテスト配列を配列方向に調べ、そして高頻度の短い配列リストと組み合わせて、それぞれのテスト配列上の連続した高頻度の短い配列の最大多数の領域を検索すること、
対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索された領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築すること、及び
領域と構築した左側及び／又は右側の配列とを、対応するテスト配列へと結合すること。
【０００５】
本発明の別の態様は、
テスト配列を受け取るため、及び予め定められた高頻度閾値に基づき高頻度の短い配列のリストを構築するための高頻度の短い配列の統計ユニットと、
それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列のリストと組み合わせて、そしてそれぞれのテスト配列上の連続した高頻度の短い配列の最大多数の領域を検索するための、高頻度領域の検索ユニットと、
対応する受け取ったテスト配列のリスト及び高頻度の短い配列に従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築し、及び／又は、検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築するための、配列構築ユニットと、
領域と、構築した左側及び／又は右側の配列を、対応するテスト配列へと結合する、配列結合ユニット
とを含む、テスト配列の誤り修復システムを提供することである。
【０００６】
本発明の態様の別の目的は、上記のテスト配列の誤り訂正システムを含む、遺伝子アセンブリ装置を提供することである。
【０００７】
本発明の態様において、高頻度の短い配列のリストは、予め定められた高頻度閾値に基づいて構築され、各テスト配列の離散的な高頻度の短い配列を持つ領域の配列は、構築された高頻度の短い配列のリストにしたがって、連続的な高頻度の短い配列の配列に再結合される。再結合配列は、可能な限り元のテスト配列の数と長さを維持し、そして配列の使用率を向上させ、そして、誤り訂正された配列内での誤りのない配列の比率と深さに関して、劇的な改善が達成されることは、実験を介して証明される。誤り訂正配列は、高頻度の短い配列に分割することができ、そしてより少ない高頻度の短い配列を得ることができ、それによって、その後の短い配列のアセンブリング中のメモリの使用量が低減する。
【図面の簡単な説明】
【０００８】
【図１】図１は、本発明の一態様において提供される、テスト配列の誤り訂正方法のフローチャートである。
【図２】図２は、本発明の態様において提供される、左側のツリーの概略的な構築図である。
【図３】図３は本発明の態様において提供される、テスト配列の誤り訂正システムの構築図である。
【発明を実施するための形態】
【０００９】
本発明の技術的な解決策と利点をより理解する目的のために、本発明のさらに詳細な説明は、図面および態様と組み合わせて、以下に記載する。本明細書中の特定の態様は、本発明を単に説明するためであり、本発明を制限するためではないことが理解されるべきである。
【００１０】
本発明の態様において、高頻度の短い配列のリストは、予め定められた（プリセット）高頻度閾値に基づいて構築され、及び構築された高頻度の短い配列のリストにしたがって、各テスト配列において、離散的な高頻度の短い配列を有する領域の配列は、連続的な高頻度の短い配列の配列に再結合される。
【００１１】
図１は、本発明の態様において提供される、テスト配列の誤り訂正方法のフローチャートを示す。詳細は、以下のとおりである：
ステップＳ１０１：テスト配列を受け取り、予め定められた高頻度閾値に基づいて、高頻度の短い配列（ｋｍｅｒ）リストを構築する。
ステップＳ１０２：それぞれの受け取ったテスト配列を配列方向に調べ、そして高頻度の短い配列のリストと組み合わせて、それぞれのテスト配列上の連続的な高頻度の短い配列の最大多数の領域を検索する。
ステップＳ１０３：対応する受け取ったテスト配列のリスト及び高頻度の短い配列にしたがって、少なくとも検索領域の左側の高頻度の短い配列のみからなる左側の配列を構築し、及び／又は、少なくとも検索領域の右側の高頻度の短い配列のみからなる右側の配列を構築する；及び
ステップＳ１０４：領域と構築した左側及び／又は右側の配列とを、対応するテスト配列に結合する。
【００１２】
本発明の態様において、上記ステップＳ１０１を、以下に記載する。
１．テスト配列を受け取り、そしてそれぞれの受け取ったテスト配列を、一塩基ごとに基づくプリセット長さを有する短い配列に分割する。
２．予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築する。
【００１３】
ここで、それぞれの受け取ったテスト配列の長さに関して、処理手順のロジックに制限はないが、一般的には２００塩基対（ｂｐ）以下である。短い配列の予め定められた長さｎは１７ｂｐであり、予め定められた高頻度閾値は５（回）である。５回以上現われる短い配列は、高頻度の短い配列であると仮定される。高頻度の短い配列は、高頻度の短い配列のリストに追加される。もちろん、短い配列の予め定められた長さｎは、１からテスト配列の塩基長までの任意の整数であることができる。しかし、ｎが１７ｂｐを超える場合、メモリ及び計算時間が増加し、及びｎが１７ｂｐ未満である場合、誤り訂正の効果が良くない。よって、ｎは好ましくは１７ｂｐである。高頻度閾値は、分割された短い配列の頻度分布に応じて決定してよい。理論的には、頻度分布には２つのピークがあるはずである：最初のピークは、配列誤りによってもたらされ、そして次のピークは、シークエンシングデプスによってもたらされる。したがって、最初の谷の値が、通常、高頻度閾値として使用される。
【００１４】
次に、それぞれのテスト配列で高頻度の短い配列の連続する最大多数を有する領域が検索される。ステップＳ１０２を、以下に詳述する。
【００１５】
１．それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列のリストと組み合わせて、それぞれのテスト配列で高頻度の短い配列が連続した領域を検索する。つまり、テスト配列の短い配列が順番に配列方向に調べられる。短い配列が高頻度の短い配列のリストに現われる場合、短い配列は、高頻度の短い配列と考えられ、それ以外の場合、短い配列は、非高頻度の短い配列と考えられる。このようにそれぞれのテスト配列を配列方向に調べた後、それぞれのテスト配列に対応する高頻度の短い配列を連続的に有する領域を得ることができる。
【００１６】
２．それぞれのテストの配列上で検索された最長の領域を、連続的な高頻度の短い配列の最大数を有する領域として、取得する。ここで、それぞれのテスト配列で連続的な高頻度の短い配列の最大多数を有する領域は、［ｓ１、ｓ２］と置かれ、ここで、ｓ１とｓ２は、対応するテスト配列の最初の塩基から、連続的な高頻度の短い配列を有する検索された最も長い領域の開始塩基と終了塩基までの塩基の数である。
【００１７】
テスト配列がＸ１Ｘ２Ｘ３．．．．．．Ｘｌｎ−１Ｘｌｎであって、ここでｌｎが、テスト配列の塩基長である場合、Ｘｉは、テスト配列のｉ番目の塩基を表す。テスト配列の連続的な高頻度の短い配列を有する最長の領域は[２６，４６]であり、すなわち、Ｘ２６Ｘ２７．．．．．．Ｘ４６は、テスト配列中の最長の高頻度の配列である。
【００１８】
その後、元のテスト配列と高頻度の短い配列のリストに基づいて、高頻度の短い配列のみで構築される配列はそれぞれ、［ｓ１、ｓ２］である左側及び右側に構築される。上記のステップＳ１０３を、以下に詳述する。
【００１９】
ステップ１：ｎ−１の長さの配列を取得し、ツリーのルートノードとして対応するテスト配列のｓ１番目の塩基から始め、そしてｓ１の深さを有する左側のツリーを各ノードのリーフとしての４種類の塩基Ａ、Ｃ、Ｇ、Ｔから構築する。構築されたツリーを、図２に示す。ここで、深さｓ１は２６である。
【００２０】
ステップ２：左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードからパスの上方に沿って高頻度の短い配列だけからなる左側の配列を構築する。
【００２１】
ここで、ツリーはルートノードから下向きに配列方向に調べられる。ルートノードは、ｎ−１の長さの配列Ｎ１であり、およびサブノードＬ１は、順番に４種類の塩基、Ａ、Ｃ、Ｇ、Ｔである。短い配列ｋｍｅｒ１＝Ｌ１＋Ｎ１が高頻度の短い配列であるかどうか、すなわち、短い配列は、高頻度の短い配列のリストにあるかどうかが決定される。そうでない場合は、対応するベースの対応するパスが終了し、そして“ｙｅｓ”の場合、Ｌ１の値が、対応するテスト配列Ｘ１Ｘ２Ｘ３．．．．．．Ｘ４９Ｘ５０中の、対応する塩基の値ＸＳ１−１に等しいかどうかが判断される。“ｙｅｓ”の場合、レベル１のノードのスコアであるスコア１が０ｔと設定され、そうでない場合はレベル１のノードのスコアであるスコア１が１と設定される。さらに、ｎ−１の長さを有する配列Ｎ２を、ｋｍｅｒ１の左端で取る。短い配列ｋｍｅｒ２＝Ｌ２＋Ｎ２は、上記の方法で解析され、およびそのサブノードＬ２は、順に4種類の塩基Ａ、Ｃ、Ｇ、Ｔである。反復と解析は、このルールにしたがってリーフノードに向かって実行される。反復の後、最小の総スコア
【数１】
が位置づけられ、ここでスコアｉは、対応するパスのレベルｉノードスコアである。位置づけられた最小のパスは、高頻度の短い配列のみで構築されるパスである。リーフノードからルートノードへ配列方向に調べることにより得られた配列は、配置されるべき高頻度の短い配列だけからなる左側の配列である。もちろん、等しい最小合計スコアを有する複数のパスを反復後に得ている場合は、そのうちの一つがランダムに選択される。そして、配置されるべき高頻度の短い配列だけからなる左側の配列が、リーフノードからルートノードへ配列方向に調べることによって得られる。もちろん、ツリーはまた、高頻度の短い配列だけからなるパスを検索するために、下から上に配列方向に調べてよい。
【００２２】
ステップ３：テスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列をツリーのルートノードとして取り、各ノードのリーフとして、４種類の塩基Ａ、Ｃ、Ｇ、Ｔを有するｌｎ−（ｓ２−１）の深さを有する右側のツリーを構築する。ここで、ｌｎはテスト配列の塩基長である。ツリーは、上記のステップ１と同様に構築されるため、ここでは説明を省略する。
【００２３】
ステップ４：右側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてルートノードからパスに沿って下方に、高頻度の短い配列だけからなる右側の配列を構築する。最小パスは上記のステップ２と同様に検索されるため、ここでは詳細な説明は省略する。
【００２４】
対応するテスト配列の右側及び左側にある高頻度の短い配列だけからなる配列が得られた後、得られた左側の配列は、対応する最長の高頻度配列Ｘｓ１Ｘｓ１＋１... ... Ｘｓ２の左側に追加され、そして得られた右側の配列は、対応する最長の高頻度配列Ｘｓ１Ｘｓ１＋１... ... Ｘｓ２の右側に追加される。すなわち、誤り訂正後の対応するテスト配列が得られる。
【００２５】
もちろん、対応するテスト配列における連続的な高頻度の短い配列の最大多数を有する領域が[１、ｓ２]又は[ｓ１、ｌｎ]である場合、すなわち、領域がテスト配列の左端又は右端である場合、[ｓ２、１]の右側の高頻度の短い配列だけからなる右側の配列を構築すること、又は[ｓ１、ｌｎ]の左側の高頻度の短い配列だけからなる左側の配列を構築する事のみが必要である。このような状況下では、対応するテスト配列が回復される場合、対応する最長の高頻度配列の左側に得られた左側の配列を足し、対応する最長の高頻度配列の右側に得られた右側の配列を足す事のみが必要とされる。
【００２６】
本発明のテスト配列の誤り訂正方式の技術的効果を、実験によって説明する。この実験では、本発明の上記の態様で提供される方法は、ヒト対照ＢＡＣ及びアフリカ人のヒトゲノム上の誤り訂正を実行するために使用される。誤り訂正前のデータを、表１に示し、誤り訂正後のデータを、表２に示す：
【表１】
【表２】
【００２７】
表１及び表２に示すように、誤り訂正後、テスト配列における誤りのない配列の割合は約３０％増加し、誤りのない配列の深さは約１０％増加する。
【００２８】
以下は、本発明の態様で提供されるテスト配列の誤り訂正方法を、誤り訂正処理を実行するために使用する場合に必要なメモリリソースの概算である。短い配列が１７塩基長であるときは、１６Ｇのメモリが占有される。各スレッドがファイルを処理している時、一つのファイルに記憶されている全ての配列がメモリに読み込まれなければならないので、１つのテスト配列が５０バイト、配列名が５０バイト、及び各ファイルが１０Ｍのテスト配列を占めると仮定すると、１つのファイルに記憶されているテスト配列について誤り訂正をするために、１Ｇのメモリが占有される必要がある。また、各スレッドは１Ｇのメモリを占有する個別の動的スケジューリングのテーブルを有するため、一つのスレッドは２Ｇのメモリを占有する。４つのスレッドをデフォルトで実行すると、２４Ｇのメモリが占有される。
【００２９】
さらに、短い配列の頻度を計算し、そして頻度のリストを出力することにかかる消費時間は、ファイルのサイズと入力／出力条件に依存して変わる。一つのファイルを処理するのに約１００秒かかる。アフリカ人のゲノムは合計６０６個のファイルを有する。最初のステップで、頻度のリストを出力するのに１５時間かかる。
【００３０】
本発明の態様で提供されるテスト配列の誤り訂正方法を、テスト配列での誤り訂正を実行するために使用した後、その後の短い配列のゲノムアセンブリに占有されるメモリを５０％低減し得る。また、低頻度の短い配列は、誤り訂正（すなわち、低頻度の短い配列は、高頻度の短い配列に訂正されている）の後に、高頻度の短い配列に合わされて、そしてそれに続くアセンブリの戦略は、アセンブリのために、より長めの短い配列（例えば２５塩基長）に配列を分割するだけとなり、したがって、メモリの使用は低減される。
【００３１】
さらに、誤り訂正の速度を改善するために、複数のスレッドを、誤り訂正するすべてのファイルを分割して処理するのに使用してもよい。一つのファイルを処理するのに約１０００秒かかり、そして４個のスレッドを用いて１００個のファイルを処理するのに１０００＊１００／４＝２５０００ｓ＝約７時間かかる。第２ステップでは、６個のスレッドを、６０６個のアフリカ人のゲノムのファイルを６個のサブセットに分割して処理するのに使用する場合、たった７時間しかかからず、そして誤り訂正を実行するのに合計２２時間かかる。
【００３２】
当業者であれば、実施態様により提供される上記の方法におけるこれらのステップの全て又は一部は、プログラムに指示にされた、関連するハードウェアで実行できることが可能であることを理解するであろう。該プログラムを、ＲＯＭ／ＲＡＭ、磁気ディスク、光ディスクなどの、コンピュータが読み取り可能な記憶媒体に保存することができる。プログラムは、以下のステップを実行するように構成される。
１．テスト配列を受け取り、そして高頻度の短い配列リストを、予め定められた高頻度閾値に基づき構築する；
２．それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列リストと組み合わせて、それぞれのテスト配列上の連続した高頻度の短い配列の最大多数を有する領域を検索する；
３．対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築する、及び
４．領域と構築した左側及び／又は右側の配列とを結合して、対応するテスト配列にする。
【００３３】
図３は、本発明の態様で提供される、テスト配列の誤り訂正システムの構造を示している。説明を簡単にするために、本発明の態様に係る部分だけが示されている。
【００３４】
システムは、遺伝子アセンブリ装置で使用することができる。システムは、装置内で動作するソフトウェアユニット、ハードウェアユニット、又はソフトウェアユニットとハードウェアユニットの組み合わせでよく、装置又は独立したコンポーネントとして装置内で動作するアプリケーションシステムに統合することもでき、該システムにおいて：
【００３５】
テスト配列を受け取り、そして予め定められた高頻度閾値に基づいて、高頻度の短い配列のリストを構築するための、高頻度の短い配列の統計ユニット３０１。これの実行法は上述されているため、詳細な説明を省略する。
【００３６】
それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列と組み合わせて、それぞれのテスト配列上の、連続した高頻度の短い配列の最大多数を有する領域を検索するための、高頻度領域の検索ユニット３０２。
【００３７】
対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築するための、配列構築ユニット３０３。
【００３８】
領域と、構築された左側及び／又は右側の配列を、対応するテスト配列へと結合する、配列回復ユニット３０４。
【００３９】
ここで、高頻度の短い配列の統計ユニット３０１は、以下を含む：
【００４０】
テスト配列を受け取り、それぞれの受け取ったテスト配列を、一塩基ごとに基づき予め定められた長さを有する短い配列に分割するための、短い配列分割モジュール３０１１。
【００４１】
予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築するための、高頻度の短い配列の取得モジュール３０１２。これの実行法は上述されているため、詳細な説明を省略する。
【００４２】
また、配列構築ユニット３０３は以下を含む：
【００４３】
ツリーのルートノードとしての、対応するテスト配列のｓ１番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｓ１の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する左側のツリーを構築するための、左側のツリー構築ユニット３０３１。ｓ１およびｎの定義、並びに左側のツリー構築モジュール３０３１の実行法は、上述されているため、その説明を省略する。
【００４４】
左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードから上方へのパスに沿って高頻度の短い配列だけからなる左側の配列を構築する、左側の配列構築モジュール３０３２。これの実行法は上述されているため、説明を省略する。
【００４５】
ツリーのルートノードとしての、対応するテスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列を取得し、各ノードのリーフとして、４種類の塩基Ａ、Ｃ、Ｇ、Ｔを有するｌｎ−（ｓ２−１）の深さを有する右側のツリーを構築するための、右側のツリーを構築するモジュール３０３３であって、ここでｓ２、ｎ及びｌｎの定義、並びに右側のツリー構築モジュール３０３３の実行法は上述されているため、説明を省略する。
【００４６】
高頻度の短い配列だけからなるパスを検索するために、右側のツリーを配列方向に調べ、ルートノードからパスに沿って下方に、高頻度の短い配列だけからなる右側の配列を構築するための、右側の配列構築モジュール３０３４。これの実行法は上述されているため、説明を省略する。
【００４７】
本発明の態様において、高頻度の短い配列のリストが予め定められた高頻度閾値に基づいて構築され、各テスト配列における離散的な高頻度の短い配列の領域の配列は、構築された高頻度の短い配列のリストによって、連続的な高頻度の短い配列の配列に再結合される。再結合された配列は、元のテスト配列の数と長さを保持し、配列の使用率が向上し、そして誤り訂正された配列において、誤りのない配列の割合と深さについて劇的な改善が達成されることが、実験を介して証明される。誤り訂正された配列は、比較的長い、高頻度の短い配列に分割してもよく、その後の短い配列のアセンブリ時のメモリの使用は大幅に低減される。
【００４８】
また、本発明は、上記のテスト配列の誤り訂正システムを包含する遺伝子アセンブリ装置も提供し、ここでアセンブリ時に占有されるメモリは、誤り訂正に付されていないテスト配列の場合に占有されるメモリよりも少ない。何故なら、誤りが訂正された配列は、アセンブリ用のやや長めの高頻度の短い配列に分割することができ、そしてより少ない高頻度の短い配列を得ることもでき、これによってメモリの使用を低減することができるからである。
【００４９】
上記態様は、本発明の好ましい態様だけであり、本発明を制限するものではない。本発明の精神と原理内の任意の変更、交替やバリエーションなどは、本発明の保護範囲内に含まれるものとする。
【技術分野】
【０００１】
本発明は、遺伝子工学の技術分野に関し、より詳しくは、テスト配列の誤り訂正方法、対応するシステム及び遺伝子のアセンブリ装置に関する。
【背景技術】
【０００２】
既存の遺伝子のシークエンシング技術に基づき、塩基の配列決定において誤りが起こる可能性がある。シークエンシングにおける誤りは、後続のデータ解析、短い配列のアセンブリ等に影響する。誤りのない配列が低頻度の短い配列を含む可能性は、深いシークエンシングデプスでは非常に低いため、既存の誤り訂正の戦略は、テスト配列中の低頻度の短い配列を単純に選別し、そして低頻度の短い配列を特定の比率で含む配列を除去することである。実際に、有効な誤り訂正が行われず、それは、テスト配列の低い利用率につながる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明の態様の目的は、テスト配列の誤り訂正方法を提供することであり、それは、既存のテスト配列の誤り訂正方法におけるテスト配列の低い利用率という以下の問題を解決することを意図する。
【０００４】
本発明の一態様は、以下のステップを含む、テスト配列の誤り訂正方法により実行される：
配列を受け取り、そして高頻度の短い配列リストを、予め定められた高頻度閾値に基づき構築すること、
受け取ったそれぞれのテスト配列を配列方向に調べ、そして高頻度の短い配列リストと組み合わせて、それぞれのテスト配列上の連続した高頻度の短い配列の最大多数の領域を検索すること、
対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索された領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築すること、及び
領域と構築した左側及び／又は右側の配列とを、対応するテスト配列へと結合すること。
【０００５】
本発明の別の態様は、
テスト配列を受け取るため、及び予め定められた高頻度閾値に基づき高頻度の短い配列のリストを構築するための高頻度の短い配列の統計ユニットと、
それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列のリストと組み合わせて、そしてそれぞれのテスト配列上の連続した高頻度の短い配列の最大多数の領域を検索するための、高頻度領域の検索ユニットと、
対応する受け取ったテスト配列のリスト及び高頻度の短い配列に従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築し、及び／又は、検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築するための、配列構築ユニットと、
領域と、構築した左側及び／又は右側の配列を、対応するテスト配列へと結合する、配列結合ユニット
とを含む、テスト配列の誤り修復システムを提供することである。
【０００６】
本発明の態様の別の目的は、上記のテスト配列の誤り訂正システムを含む、遺伝子アセンブリ装置を提供することである。
【０００７】
本発明の態様において、高頻度の短い配列のリストは、予め定められた高頻度閾値に基づいて構築され、各テスト配列の離散的な高頻度の短い配列を持つ領域の配列は、構築された高頻度の短い配列のリストにしたがって、連続的な高頻度の短い配列の配列に再結合される。再結合配列は、可能な限り元のテスト配列の数と長さを維持し、そして配列の使用率を向上させ、そして、誤り訂正された配列内での誤りのない配列の比率と深さに関して、劇的な改善が達成されることは、実験を介して証明される。誤り訂正配列は、高頻度の短い配列に分割することができ、そしてより少ない高頻度の短い配列を得ることができ、それによって、その後の短い配列のアセンブリング中のメモリの使用量が低減する。
【図面の簡単な説明】
【０００８】
【図１】図１は、本発明の一態様において提供される、テスト配列の誤り訂正方法のフローチャートである。
【図２】図２は、本発明の態様において提供される、左側のツリーの概略的な構築図である。
【図３】図３は本発明の態様において提供される、テスト配列の誤り訂正システムの構築図である。
【発明を実施するための形態】
【０００９】
本発明の技術的な解決策と利点をより理解する目的のために、本発明のさらに詳細な説明は、図面および態様と組み合わせて、以下に記載する。本明細書中の特定の態様は、本発明を単に説明するためであり、本発明を制限するためではないことが理解されるべきである。
【００１０】
本発明の態様において、高頻度の短い配列のリストは、予め定められた（プリセット）高頻度閾値に基づいて構築され、及び構築された高頻度の短い配列のリストにしたがって、各テスト配列において、離散的な高頻度の短い配列を有する領域の配列は、連続的な高頻度の短い配列の配列に再結合される。
【００１１】
図１は、本発明の態様において提供される、テスト配列の誤り訂正方法のフローチャートを示す。詳細は、以下のとおりである：
ステップＳ１０１：テスト配列を受け取り、予め定められた高頻度閾値に基づいて、高頻度の短い配列（ｋｍｅｒ）リストを構築する。
ステップＳ１０２：それぞれの受け取ったテスト配列を配列方向に調べ、そして高頻度の短い配列のリストと組み合わせて、それぞれのテスト配列上の連続的な高頻度の短い配列の最大多数の領域を検索する。
ステップＳ１０３：対応する受け取ったテスト配列のリスト及び高頻度の短い配列にしたがって、少なくとも検索領域の左側の高頻度の短い配列のみからなる左側の配列を構築し、及び／又は、少なくとも検索領域の右側の高頻度の短い配列のみからなる右側の配列を構築する；及び
ステップＳ１０４：領域と構築した左側及び／又は右側の配列とを、対応するテスト配列に結合する。
【００１２】
本発明の態様において、上記ステップＳ１０１を、以下に記載する。
１．テスト配列を受け取り、そしてそれぞれの受け取ったテスト配列を、一塩基ごとに基づくプリセット長さを有する短い配列に分割する。
２．予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築する。
【００１３】
ここで、それぞれの受け取ったテスト配列の長さに関して、処理手順のロジックに制限はないが、一般的には２００塩基対（ｂｐ）以下である。短い配列の予め定められた長さｎは１７ｂｐであり、予め定められた高頻度閾値は５（回）である。５回以上現われる短い配列は、高頻度の短い配列であると仮定される。高頻度の短い配列は、高頻度の短い配列のリストに追加される。もちろん、短い配列の予め定められた長さｎは、１からテスト配列の塩基長までの任意の整数であることができる。しかし、ｎが１７ｂｐを超える場合、メモリ及び計算時間が増加し、及びｎが１７ｂｐ未満である場合、誤り訂正の効果が良くない。よって、ｎは好ましくは１７ｂｐである。高頻度閾値は、分割された短い配列の頻度分布に応じて決定してよい。理論的には、頻度分布には２つのピークがあるはずである：最初のピークは、配列誤りによってもたらされ、そして次のピークは、シークエンシングデプスによってもたらされる。したがって、最初の谷の値が、通常、高頻度閾値として使用される。
【００１４】
次に、それぞれのテスト配列で高頻度の短い配列の連続する最大多数を有する領域が検索される。ステップＳ１０２を、以下に詳述する。
【００１５】
１．それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列のリストと組み合わせて、それぞれのテスト配列で高頻度の短い配列が連続した領域を検索する。つまり、テスト配列の短い配列が順番に配列方向に調べられる。短い配列が高頻度の短い配列のリストに現われる場合、短い配列は、高頻度の短い配列と考えられ、それ以外の場合、短い配列は、非高頻度の短い配列と考えられる。このようにそれぞれのテスト配列を配列方向に調べた後、それぞれのテスト配列に対応する高頻度の短い配列を連続的に有する領域を得ることができる。
【００１６】
２．それぞれのテストの配列上で検索された最長の領域を、連続的な高頻度の短い配列の最大数を有する領域として、取得する。ここで、それぞれのテスト配列で連続的な高頻度の短い配列の最大多数を有する領域は、［ｓ１、ｓ２］と置かれ、ここで、ｓ１とｓ２は、対応するテスト配列の最初の塩基から、連続的な高頻度の短い配列を有する検索された最も長い領域の開始塩基と終了塩基までの塩基の数である。
【００１７】
テスト配列がＸ１Ｘ２Ｘ３．．．．．．Ｘｌｎ−１Ｘｌｎであって、ここでｌｎが、テスト配列の塩基長である場合、Ｘｉは、テスト配列のｉ番目の塩基を表す。テスト配列の連続的な高頻度の短い配列を有する最長の領域は[２６，４６]であり、すなわち、Ｘ２６Ｘ２７．．．．．．Ｘ４６は、テスト配列中の最長の高頻度の配列である。
【００１８】
その後、元のテスト配列と高頻度の短い配列のリストに基づいて、高頻度の短い配列のみで構築される配列はそれぞれ、［ｓ１、ｓ２］である左側及び右側に構築される。上記のステップＳ１０３を、以下に詳述する。
【００１９】
ステップ１：ｎ−１の長さの配列を取得し、ツリーのルートノードとして対応するテスト配列のｓ１番目の塩基から始め、そしてｓ１の深さを有する左側のツリーを各ノードのリーフとしての４種類の塩基Ａ、Ｃ、Ｇ、Ｔから構築する。構築されたツリーを、図２に示す。ここで、深さｓ１は２６である。
【００２０】
ステップ２：左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードからパスの上方に沿って高頻度の短い配列だけからなる左側の配列を構築する。
【００２１】
ここで、ツリーはルートノードから下向きに配列方向に調べられる。ルートノードは、ｎ−１の長さの配列Ｎ１であり、およびサブノードＬ１は、順番に４種類の塩基、Ａ、Ｃ、Ｇ、Ｔである。短い配列ｋｍｅｒ１＝Ｌ１＋Ｎ１が高頻度の短い配列であるかどうか、すなわち、短い配列は、高頻度の短い配列のリストにあるかどうかが決定される。そうでない場合は、対応するベースの対応するパスが終了し、そして“ｙｅｓ”の場合、Ｌ１の値が、対応するテスト配列Ｘ１Ｘ２Ｘ３．．．．．．Ｘ４９Ｘ５０中の、対応する塩基の値ＸＳ１−１に等しいかどうかが判断される。“ｙｅｓ”の場合、レベル１のノードのスコアであるスコア１が０ｔと設定され、そうでない場合はレベル１のノードのスコアであるスコア１が１と設定される。さらに、ｎ−１の長さを有する配列Ｎ２を、ｋｍｅｒ１の左端で取る。短い配列ｋｍｅｒ２＝Ｌ２＋Ｎ２は、上記の方法で解析され、およびそのサブノードＬ２は、順に4種類の塩基Ａ、Ｃ、Ｇ、Ｔである。反復と解析は、このルールにしたがってリーフノードに向かって実行される。反復の後、最小の総スコア
【数１】
が位置づけられ、ここでスコアｉは、対応するパスのレベルｉノードスコアである。位置づけられた最小のパスは、高頻度の短い配列のみで構築されるパスである。リーフノードからルートノードへ配列方向に調べることにより得られた配列は、配置されるべき高頻度の短い配列だけからなる左側の配列である。もちろん、等しい最小合計スコアを有する複数のパスを反復後に得ている場合は、そのうちの一つがランダムに選択される。そして、配置されるべき高頻度の短い配列だけからなる左側の配列が、リーフノードからルートノードへ配列方向に調べることによって得られる。もちろん、ツリーはまた、高頻度の短い配列だけからなるパスを検索するために、下から上に配列方向に調べてよい。
【００２２】
ステップ３：テスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列をツリーのルートノードとして取り、各ノードのリーフとして、４種類の塩基Ａ、Ｃ、Ｇ、Ｔを有するｌｎ−（ｓ２−１）の深さを有する右側のツリーを構築する。ここで、ｌｎはテスト配列の塩基長である。ツリーは、上記のステップ１と同様に構築されるため、ここでは説明を省略する。
【００２３】
ステップ４：右側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてルートノードからパスに沿って下方に、高頻度の短い配列だけからなる右側の配列を構築する。最小パスは上記のステップ２と同様に検索されるため、ここでは詳細な説明は省略する。
【００２４】
対応するテスト配列の右側及び左側にある高頻度の短い配列だけからなる配列が得られた後、得られた左側の配列は、対応する最長の高頻度配列Ｘｓ１Ｘｓ１＋１... ... Ｘｓ２の左側に追加され、そして得られた右側の配列は、対応する最長の高頻度配列Ｘｓ１Ｘｓ１＋１... ... Ｘｓ２の右側に追加される。すなわち、誤り訂正後の対応するテスト配列が得られる。
【００２５】
もちろん、対応するテスト配列における連続的な高頻度の短い配列の最大多数を有する領域が[１、ｓ２]又は[ｓ１、ｌｎ]である場合、すなわち、領域がテスト配列の左端又は右端である場合、[ｓ２、１]の右側の高頻度の短い配列だけからなる右側の配列を構築すること、又は[ｓ１、ｌｎ]の左側の高頻度の短い配列だけからなる左側の配列を構築する事のみが必要である。このような状況下では、対応するテスト配列が回復される場合、対応する最長の高頻度配列の左側に得られた左側の配列を足し、対応する最長の高頻度配列の右側に得られた右側の配列を足す事のみが必要とされる。
【００２６】
本発明のテスト配列の誤り訂正方式の技術的効果を、実験によって説明する。この実験では、本発明の上記の態様で提供される方法は、ヒト対照ＢＡＣ及びアフリカ人のヒトゲノム上の誤り訂正を実行するために使用される。誤り訂正前のデータを、表１に示し、誤り訂正後のデータを、表２に示す：
【表１】
【表２】
【００２７】
表１及び表２に示すように、誤り訂正後、テスト配列における誤りのない配列の割合は約３０％増加し、誤りのない配列の深さは約１０％増加する。
【００２８】
以下は、本発明の態様で提供されるテスト配列の誤り訂正方法を、誤り訂正処理を実行するために使用する場合に必要なメモリリソースの概算である。短い配列が１７塩基長であるときは、１６Ｇのメモリが占有される。各スレッドがファイルを処理している時、一つのファイルに記憶されている全ての配列がメモリに読み込まれなければならないので、１つのテスト配列が５０バイト、配列名が５０バイト、及び各ファイルが１０Ｍのテスト配列を占めると仮定すると、１つのファイルに記憶されているテスト配列について誤り訂正をするために、１Ｇのメモリが占有される必要がある。また、各スレッドは１Ｇのメモリを占有する個別の動的スケジューリングのテーブルを有するため、一つのスレッドは２Ｇのメモリを占有する。４つのスレッドをデフォルトで実行すると、２４Ｇのメモリが占有される。
【００２９】
さらに、短い配列の頻度を計算し、そして頻度のリストを出力することにかかる消費時間は、ファイルのサイズと入力／出力条件に依存して変わる。一つのファイルを処理するのに約１００秒かかる。アフリカ人のゲノムは合計６０６個のファイルを有する。最初のステップで、頻度のリストを出力するのに１５時間かかる。
【００３０】
本発明の態様で提供されるテスト配列の誤り訂正方法を、テスト配列での誤り訂正を実行するために使用した後、その後の短い配列のゲノムアセンブリに占有されるメモリを５０％低減し得る。また、低頻度の短い配列は、誤り訂正（すなわち、低頻度の短い配列は、高頻度の短い配列に訂正されている）の後に、高頻度の短い配列に合わされて、そしてそれに続くアセンブリの戦略は、アセンブリのために、より長めの短い配列（例えば２５塩基長）に配列を分割するだけとなり、したがって、メモリの使用は低減される。
【００３１】
さらに、誤り訂正の速度を改善するために、複数のスレッドを、誤り訂正するすべてのファイルを分割して処理するのに使用してもよい。一つのファイルを処理するのに約１０００秒かかり、そして４個のスレッドを用いて１００個のファイルを処理するのに１０００＊１００／４＝２５０００ｓ＝約７時間かかる。第２ステップでは、６個のスレッドを、６０６個のアフリカ人のゲノムのファイルを６個のサブセットに分割して処理するのに使用する場合、たった７時間しかかからず、そして誤り訂正を実行するのに合計２２時間かかる。
【００３２】
当業者であれば、実施態様により提供される上記の方法におけるこれらのステップの全て又は一部は、プログラムに指示にされた、関連するハードウェアで実行できることが可能であることを理解するであろう。該プログラムを、ＲＯＭ／ＲＡＭ、磁気ディスク、光ディスクなどの、コンピュータが読み取り可能な記憶媒体に保存することができる。プログラムは、以下のステップを実行するように構成される。
１．テスト配列を受け取り、そして高頻度の短い配列リストを、予め定められた高頻度閾値に基づき構築する；
２．それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列リストと組み合わせて、それぞれのテスト配列上の連続した高頻度の短い配列の最大多数を有する領域を検索する；
３．対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築する、及び
４．領域と構築した左側及び／又は右側の配列とを結合して、対応するテスト配列にする。
【００３３】
図３は、本発明の態様で提供される、テスト配列の誤り訂正システムの構造を示している。説明を簡単にするために、本発明の態様に係る部分だけが示されている。
【００３４】
システムは、遺伝子アセンブリ装置で使用することができる。システムは、装置内で動作するソフトウェアユニット、ハードウェアユニット、又はソフトウェアユニットとハードウェアユニットの組み合わせでよく、装置又は独立したコンポーネントとして装置内で動作するアプリケーションシステムに統合することもでき、該システムにおいて：
【００３５】
テスト配列を受け取り、そして予め定められた高頻度閾値に基づいて、高頻度の短い配列のリストを構築するための、高頻度の短い配列の統計ユニット３０１。これの実行法は上述されているため、詳細な説明を省略する。
【００３６】
それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列と組み合わせて、それぞれのテスト配列上の、連続した高頻度の短い配列の最大多数を有する領域を検索するための、高頻度領域の検索ユニット３０２。
【００３７】
対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築するための、配列構築ユニット３０３。
【００３８】
領域と、構築された左側及び／又は右側の配列を、対応するテスト配列へと結合する、配列回復ユニット３０４。
【００３９】
ここで、高頻度の短い配列の統計ユニット３０１は、以下を含む：
【００４０】
テスト配列を受け取り、それぞれの受け取ったテスト配列を、一塩基ごとに基づき予め定められた長さを有する短い配列に分割するための、短い配列分割モジュール３０１１。
【００４１】
予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築するための、高頻度の短い配列の取得モジュール３０１２。これの実行法は上述されているため、詳細な説明を省略する。
【００４２】
また、配列構築ユニット３０３は以下を含む：
【００４３】
ツリーのルートノードとしての、対応するテスト配列のｓ１番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｓ１の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する左側のツリーを構築するための、左側のツリー構築ユニット３０３１。ｓ１およびｎの定義、並びに左側のツリー構築モジュール３０３１の実行法は、上述されているため、その説明を省略する。
【００４４】
左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードから上方へのパスに沿って高頻度の短い配列だけからなる左側の配列を構築する、左側の配列構築モジュール３０３２。これの実行法は上述されているため、説明を省略する。
【００４５】
ツリーのルートノードとしての、対応するテスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列を取得し、各ノードのリーフとして、４種類の塩基Ａ、Ｃ、Ｇ、Ｔを有するｌｎ−（ｓ２−１）の深さを有する右側のツリーを構築するための、右側のツリーを構築するモジュール３０３３であって、ここでｓ２、ｎ及びｌｎの定義、並びに右側のツリー構築モジュール３０３３の実行法は上述されているため、説明を省略する。
【００４６】
高頻度の短い配列だけからなるパスを検索するために、右側のツリーを配列方向に調べ、ルートノードからパスに沿って下方に、高頻度の短い配列だけからなる右側の配列を構築するための、右側の配列構築モジュール３０３４。これの実行法は上述されているため、説明を省略する。
【００４７】
本発明の態様において、高頻度の短い配列のリストが予め定められた高頻度閾値に基づいて構築され、各テスト配列における離散的な高頻度の短い配列の領域の配列は、構築された高頻度の短い配列のリストによって、連続的な高頻度の短い配列の配列に再結合される。再結合された配列は、元のテスト配列の数と長さを保持し、配列の使用率が向上し、そして誤り訂正された配列において、誤りのない配列の割合と深さについて劇的な改善が達成されることが、実験を介して証明される。誤り訂正された配列は、比較的長い、高頻度の短い配列に分割してもよく、その後の短い配列のアセンブリ時のメモリの使用は大幅に低減される。
【００４８】
また、本発明は、上記のテスト配列の誤り訂正システムを包含する遺伝子アセンブリ装置も提供し、ここでアセンブリ時に占有されるメモリは、誤り訂正に付されていないテスト配列の場合に占有されるメモリよりも少ない。何故なら、誤りが訂正された配列は、アセンブリ用のやや長めの高頻度の短い配列に分割することができ、そしてより少ない高頻度の短い配列を得ることもでき、これによってメモリの使用を低減することができるからである。
【００４９】
上記態様は、本発明の好ましい態様だけであり、本発明を制限するものではない。本発明の精神と原理内の任意の変更、交替やバリエーションなどは、本発明の保護範囲内に含まれるものとする。
【特許請求の範囲】
【請求項１】
テスト配列の誤り訂正方法であって、
テスト配列を受け取り、そして高頻度の短い配列リストを、予め定められた高頻度閾値に基づき構築すること、
それぞれの受け取ったテスト配列を配列方向に調べ、そして高頻度の短い配列リストと組み合わせて、それぞれのテスト配列上の、連続した高頻度の短い配列の最大多数を有する領域を検索すること、
対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索された領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築することと、及び
領域と構築した左側及び／又は右側の配列とを、対応するテスト配列へと結合すること
を含むことを特徴とする、方法。
【請求項２】
前記テスト配列を受け取り、そして予め定められた高頻度閾値に基づいて、高頻度の短い配列のリストを構築するステップは、
テスト配列を受け取り、それぞれの受け取ったテスト配列を、一塩基ごとに基づく予め定められた長さを有する短い配列に分割すること、及び
予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築すること
を含む、請求項１に記載の方法。
【請求項３】
前記予め定められた高頻度閾値を、予め定められた長さの、分割した短い配列の頻度分布に従って決定し、ここで予め定められた長さは１７塩基長である、請求項２に記載の方法。
【請求項４】
前記対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築するステップは、
ツリーのルートノードとしての、対応するテスト配列のｓ１番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｓ１の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する左側のツリーを構築すること、
左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードから上方へのパスに沿って高頻度の短い配列だけからなる左側の配列を構築すること
を含み、
前記対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築するステップは、
ツリーのルートノードとしての、対応するテスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｌｎ−（ｓ２−１）の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する右側のツリーを構築すること、
右側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてルートノードからパスに沿って下方に、高頻度の短い配列だけからなる右側の配列を構築すること、
を含み、
ここで、前記ｓ１、ｓ２はそれぞれ対応するテスト配列の最初の塩基から、連続的な高頻度の短い配列の最大多数を有する検索された最も長い領域の開始塩基と終了塩基までの塩基の数であり、ｎは高頻度の短い配列の塩基長であり、及びｌｎはテスト配列の塩基長である、請求項１に記載の方法。
【請求項５】
前記受け取ったテスト配列の長さが２００塩基以下である、請求項１に記載の方法。
【請求項６】
テスト配列の誤り訂正システムであって、前記システムは、
テスト配列を受け取るため、及び予め定められた高頻度閾値に基づき高頻度の短い配列のリストを構築するための高頻度の短い配列の統計ユニットと、
それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列のリストと組み合わせて、それぞれのテスト配列上の、連続した高頻度の短い配列の最大多数を有する領域を検索するための検索ユニットと、
対応する受け取ったテスト配列のリスト及び高頻度の短い配列にしたがって、少なくとも検索領域の左側の高頻度の短い配列だけからなる左側の配列を構築し、及び／又は、少なくとも検索領域の右側の高頻度の短い配列だけからなる右側の配列を構築するための配列構築ユニットと、
領域と、構築された左側及び／又は右側の配列を、対応するテスト配列へと結合する、配列結合ユニット
とを含むことを特徴とする、システム。
【請求項７】
前記高頻度の短い配列の統計ユニットは、
テスト配列を受け取り、それぞれの受け取ったテスト配列を、一塩基ごとに基づく予め定められた長さを有する短い配列に分割するための、短い配列分割モジュールと、
予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築するための、高頻度の短い配列の取得モジュール
とを含む、請求項６に記載のシステム。
【請求項８】
前記予め定められた高頻度閾値を、予め定められた長さの、分割した短い配列の頻度分布に従って決定し、ここで予め定められた長さは１７塩基長である、請求項７に記載のシステム。
【請求項９】
前記配列構築ユニットは、
ツリーのルートノードとしての、対応するテスト配列のｓ１番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｓ１の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する左側のツリーを構築するための、左側のツリー構築モジュールと、
左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードから上方へのパスに沿って高頻度の短い配列だけからなる左側の配列を構築する、左側の配列構築モジュールと、
ツリーのルートノードとしての、対応するテスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列を取得し、各ノードのリーフとして、４種類の塩基Ａ、Ｃ、Ｇ、Ｔを有するｌｎ−（ｓ２−１）の深さを有する右側のツリーを構築するための、右側のツリー構築モジュールと、
右側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてルートノードからパスに沿って下方に、高頻度の短い配列のみからなる右側の配列を構築するための、右側の配列構築モジュールと
を含み、
ここで、前記ｓ１、ｓ２はそれぞれ対応するテスト配列の最初の塩基から、連続的な高頻度の短い配列の最大多数を有する検索された最も長い領域の開始塩基と終了塩基の塩基までの数であり、ｎは高頻度の短い配列の塩基長であり、及びｌｎはテスト配列の塩基長である、請求項６に記載のシステム。
【請求項１０】
請求項６〜９のいずれか一項に記載のテスト配列の誤り訂正システムを含む、遺伝子アセンブリ装置。
【請求項１】
テスト配列の誤り訂正方法であって、
テスト配列を受け取り、そして高頻度の短い配列リストを、予め定められた高頻度閾値に基づき構築すること、
それぞれの受け取ったテスト配列を配列方向に調べ、そして高頻度の短い配列リストと組み合わせて、それぞれのテスト配列上の、連続した高頻度の短い配列の最大多数を有する領域を検索すること、
対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索された領域の左側において高頻度の短い配列だけからなる左側の配列を構築すること、及び／又は検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築することと、及び
領域と構築した左側及び／又は右側の配列とを、対応するテスト配列へと結合すること
を含むことを特徴とする、方法。
【請求項２】
前記テスト配列を受け取り、そして予め定められた高頻度閾値に基づいて、高頻度の短い配列のリストを構築するステップは、
テスト配列を受け取り、それぞれの受け取ったテスト配列を、一塩基ごとに基づく予め定められた長さを有する短い配列に分割すること、及び
予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築すること
を含む、請求項１に記載の方法。
【請求項３】
前記予め定められた高頻度閾値を、予め定められた長さの、分割した短い配列の頻度分布に従って決定し、ここで予め定められた長さは１７塩基長である、請求項２に記載の方法。
【請求項４】
前記対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の左側において高頻度の短い配列だけからなる左側の配列を構築するステップは、
ツリーのルートノードとしての、対応するテスト配列のｓ１番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｓ１の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する左側のツリーを構築すること、
左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードから上方へのパスに沿って高頻度の短い配列だけからなる左側の配列を構築すること
を含み、
前記対応する受け取ったテスト配列及び高頻度の短い配列のリストに従い、検索した領域の右側において高頻度の短い配列だけからなる右側の配列を構築するステップは、
ツリーのルートノードとしての、対応するテスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｌｎ−（ｓ２−１）の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する右側のツリーを構築すること、
右側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてルートノードからパスに沿って下方に、高頻度の短い配列だけからなる右側の配列を構築すること、
を含み、
ここで、前記ｓ１、ｓ２はそれぞれ対応するテスト配列の最初の塩基から、連続的な高頻度の短い配列の最大多数を有する検索された最も長い領域の開始塩基と終了塩基までの塩基の数であり、ｎは高頻度の短い配列の塩基長であり、及びｌｎはテスト配列の塩基長である、請求項１に記載の方法。
【請求項５】
前記受け取ったテスト配列の長さが２００塩基以下である、請求項１に記載の方法。
【請求項６】
テスト配列の誤り訂正システムであって、前記システムは、
テスト配列を受け取るため、及び予め定められた高頻度閾値に基づき高頻度の短い配列のリストを構築するための高頻度の短い配列の統計ユニットと、
それぞれの受け取ったテスト配列を配列方向に調べ、高頻度の短い配列のリストと組み合わせて、それぞれのテスト配列上の、連続した高頻度の短い配列の最大多数を有する領域を検索するための検索ユニットと、
対応する受け取ったテスト配列のリスト及び高頻度の短い配列にしたがって、少なくとも検索領域の左側の高頻度の短い配列だけからなる左側の配列を構築し、及び／又は、少なくとも検索領域の右側の高頻度の短い配列だけからなる右側の配列を構築するための配列構築ユニットと、
領域と、構築された左側及び／又は右側の配列を、対応するテスト配列へと結合する、配列結合ユニット
とを含むことを特徴とする、システム。
【請求項７】
前記高頻度の短い配列の統計ユニットは、
テスト配列を受け取り、それぞれの受け取ったテスト配列を、一塩基ごとに基づく予め定められた長さを有する短い配列に分割するための、短い配列分割モジュールと、
予め定められた高頻度閾値より大きい数値で現われる分割された短い配列に基づいて、高頻度の短い配列のリストを構築するための、高頻度の短い配列の取得モジュール
とを含む、請求項６に記載のシステム。
【請求項８】
前記予め定められた高頻度閾値を、予め定められた長さの、分割した短い配列の頻度分布に従って決定し、ここで予め定められた長さは１７塩基長である、請求項７に記載のシステム。
【請求項９】
前記配列構築ユニットは、
ツリーのルートノードとしての、対応するテスト配列のｓ１番目の塩基から始まるｎ−１の長さの配列を取得し、そしてｓ１の深さと４種類の塩基Ａ、Ｃ、Ｇ、Ｔを各ノードのリーフとして有する左側のツリーを構築するための、左側のツリー構築モジュールと、
左側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてリーフノードから上方へのパスに沿って高頻度の短い配列だけからなる左側の配列を構築する、左側の配列構築モジュールと、
ツリーのルートノードとしての、対応するテスト配列のｓ２番目の塩基から始まるｎ−１の長さの配列を取得し、各ノードのリーフとして、４種類の塩基Ａ、Ｃ、Ｇ、Ｔを有するｌｎ−（ｓ２−１）の深さを有する右側のツリーを構築するための、右側のツリー構築モジュールと、
右側のツリーを配列方向に調べ、高頻度の短い配列だけからなるパスを検索し、そしてルートノードからパスに沿って下方に、高頻度の短い配列のみからなる右側の配列を構築するための、右側の配列構築モジュールと
を含み、
ここで、前記ｓ１、ｓ２はそれぞれ対応するテスト配列の最初の塩基から、連続的な高頻度の短い配列の最大多数を有する検索された最も長い領域の開始塩基と終了塩基の塩基までの数であり、ｎは高頻度の短い配列の塩基長であり、及びｌｎはテスト配列の塩基長である、請求項６に記載のシステム。
【請求項１０】
請求項６〜９のいずれか一項に記載のテスト配列の誤り訂正システムを含む、遺伝子アセンブリ装置。
【図１】
【図２】
【図３】
【図２】
【図３】
【公表番号】特表２０１２−５１１７５２（Ｐ２０１２−５１１７５２Ａ）
【公表日】平成２４年５月２４日（２０１２．５．２４）
【国際特許分類】
【出願番号】特願２０１１−５３９８７４（Ｐ２０１１−５３９８７４）
【出願日】平成２１年１２月１１日（２００９．１２．１１）
【国際出願番号】ＰＣＴ／ＣＮ２００９／００１４２６
【国際公開番号】ＷＯ２０１０／０６６１１４
【国際公開日】平成２２年６月１７日（２０１０．６．１７）
【出願人】（５１１１３８２４９）シェンチェン ホワダ ジーン インスティテュート (2)
【Ｆターム（参考）】
【公表日】平成２４年５月２４日（２０１２．５．２４）
【国際特許分類】
【出願日】平成２１年１２月１１日（２００９．１２．１１）
【国際出願番号】ＰＣＴ／ＣＮ２００９／００１４２６
【国際公開番号】ＷＯ２０１０／０６６１１４
【国際公開日】平成２２年６月１７日（２０１０．６．１７）
【出願人】（５１１１３８２４９）シェンチェン ホワダ ジーン インスティテュート (2)
【Ｆターム（参考）】
[ Back to top ]