(57)【要約】【課題】  ハプロタイプデータの保存、整列、及び検索方法を提供する。【解決手段】  ハプロタイプデータの一塩基多型のそれぞれの位置において対立遺伝子に順序を付与する段階と、付与された順序によって前記ハプロタイプデータを整列する段階と、整列されたハプロタイプデータを所定のデータ構造で保存する段階と、を含むことを特徴とするハプロタイプデータの保存方法により、上記課題は解決される。【選択図】図１
2005182815.tif 000002
【特許請求の範囲】
【請求項１】
ハプロタイプデータの一塩基多型のそれぞれの位置において対立遺伝子に順序を付与する段階と、
付与された順序によって前記ハプロタイプデータを整列する段階と、
整列された前記ハプロタイプデータを所定のデータ構造で保存する段階と、
を含むことを特徴とするハプロタイプデータの保存方法。
【請求項２】
前記ハプロタイプデータを整列する段階が、
前記対立遺伝子に付与された順序によって、一塩基多型のそれぞれの位置の前記対立遺伝子に整数を割り当てる段階と、
各ハプロタイプデータに含まれる対立遺伝子を、割り当てられた前記整数に置換する段階と、
各ハプロタイプデータに対応する整数の配列を桁値によって数値化し、その大きさを比較する段階と、
を含むことを特徴とする請求項１に記載のハプロタイプデータの保存方法。
【請求項３】
前記整数が、０から（対立遺伝子の数−１）まで１ずつ増加するように、一塩基多型のそれぞれに割り当てられることを特徴とする請求項２に記載のハプロタイプデータの保存方法。
【請求項４】
前記データ構造が、バランスバイナリツリー構造であることを特徴とする請求項２に記載のハプロタイプデータの保存方法。
【請求項５】
各ハプロタイプデータに対して数値化された値が、前記バランスバイナリツリー構造中に各ノードのキー値として保存されることを特徴とする請求項４に記載のハプロタイプデータの保存方法。
【請求項６】
前記ノードが、前記キー値以外に前記ハプロタイプデータに関する情報をさらに保存することを特徴とする請求項５に記載のハプロタイプデータの保存方法。
【請求項７】
ハプロタイプデータの一塩基多型のそれぞれの位置において対立遺伝子に順序を付与する段階と、
前記対立遺伝子に付与された順序によって、一塩基多型のそれぞれの位置の前記対立遺伝子に整数を割り当てる段階と、
各ハプロタイプデータに含まれる対立遺伝子を、割り当てられた前記整数に置換する段階と、
各ハプロタイプデータに対応する整数の配列を桁値によって数値化する段階と、
各ハプロタイプデータに対応する数値の大きさによって前記ハプロタイプデータを整列する段階と、
を含むことを特徴とするハプロタイプデータの整列方法。
【請求項８】
前記整数が、０から（対立遺伝子の数−１）まで１ずつ増加するように、一塩基多型のそれぞれに割り当てられることを特徴とする請求項７に記載のハプロタイプデータ整列方法。
【請求項９】
ハプロタイプデータの一塩基多型のそれぞれの位置において対立遺伝子に順序を付与し、その順序によって前記ハプロタイプデータを数値化し、その数値化された値を利用して前記ハプロタイプデータを所定のデータ構造で保存するデータベース中に試験ハプロタイプデータが存在するかどうかを検索するハプロタイプデータの検索方法において、
前記データベースに保存される前記ハプロタイプデータの一塩基多型の位置の対立遺伝子の順序と同様に、前記試験ハプロタイプデータ中の対立遺伝子に順序を付与する段階と、
前記対立遺伝子の順序によって、前記対立遺伝子に整数を割り当てる段階と、
前記試験ハプロタイプデータの対立遺伝子を、割り当てられた前記整数に置換する段階と、
置換された前記整数の配列を桁値によって数値化する段階と、
数値化された値を利用して、前記データ構造によって前記データベースを検索する段階と、
を含むことを特徴とするハプロタイプデータの検索方法。
【請求項１０】
前記整数が、一塩基多型０から（対立遺伝子の数−１）まで１ずつ増加するように、前記対立遺伝子のそれぞれに割り当てられることを特徴とする請求項９に記載のハプロタイプデータの検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はハプロタイプデータの保存、整列、及び検索方法に係り、特にハプロタイプデータをデータベースに保存する際に、ハプロタイプデータに順序を付与して整列して保存し、検索する方法に関する。
【背景技術】
【０００２】
ハプロタイプデータはＤＮＡシークエンスであって、染色体領域に沿って存在する一塩基多型（Ｓｉｎｇｌｅ  Ｎｕｃｌｅｏｔｉｄｅ  Ｐｏｌｙｍｏｒｐｈｉｓｍ；以下、ＳＮＰ）の対立遺伝子のセットをいう。ここで、ＳＮＰは、個人間の差を表すＤＮＡ塩基の変異をいい、ヒトゲノムでは約１千個の塩基毎に１個ずつ現れる。例えば、ヒト染色体が、対応するＳＮＰ、Ａ（アデニン）を３０％、およびＧ（グアニン）を７０％持つならば、これらのＡおよびＧを、そのＳＮＰの変異体または対立遺伝子という。
【０００３】
例えば、３人についてのハプロタイプデータが、それぞれ次のような塩基配列を持つと仮定しよう。
【０００４】
【表１】
2005182815.tif 000003
【０００５】
この際、ＳＮＰのセットは、３番目、１０番目、および１７番目に対応し、３番目の対立遺伝子はＡ／Ｃ、１０番目ではＴ／Ａ、１７番目ではＴ／Ｇとなる。
【０００６】
従来、このようなハプロタイプデータは、リスト型データ構造で保存される。しかし、多数のハプロタイプデータが保存されているデータベースから、任意のハプロタイプデータがデータベースに存在するかどうかを調べ、仮に存在するならば関連情報を抽出しようとした場合、リスト型データ構造では、検索にＯ（ｎ）（ここで、ｎはデータベースでのハプロタイプデータの数である）の時間がかかる。したがって、検索時間を短縮できるハプロタイプデータの保存及び整列方法が必要となる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明が解決しようとする技術的課題は、ハプロタイプデータに、整列化された順序を付与してバイナリツリー構造で保存することで、さらに速い検索が可能なハプロタイプデータの保存、整列、及び検索方法を提供するところにある。
【課題を解決するための手段】
【０００８】
前記技術的課題を解決するための、本発明のハプロタイプデータの保存方法は、ハプロタイプデータの一塩基多型のそれぞれの位置において対立遺伝子間に順序を付与する段階と、付与された順序によって前記ハプロタイプデータを整列する段階と、整列された前記ハプロタイプデータを所定のデータ構造で保存する段階と、を含むことを特徴とする。
【０００９】
前記技術的課題を解決するための、本発明のハプロタイプデータの整列方法は、ハプロタイプデータの一塩基多型のそれぞれの位置において対立遺伝子間に順序を付与する段階と、前記対立遺伝子に付与された順序によって、一塩基多形のそれぞれの位置の前記対立遺伝子に整数を割り当てる段階と、各ハプロタイプデータに含まれる対立遺伝子を、割り当てられた前記整数に置換する段階と、各ハプロタイプデータに対応する整数の配列を桁値によって数値化する段階と、各ハプロタイプデータに対応する数値の大きさによって前記ハプロタイプデータを整列する段階と、を含むことを特徴とする。
【００１０】
前記技術的課題を解決するための、本発明のハプロタイプデータの検索方法は、ハプロタイプデータの一塩基多型のそれぞれの位置において対立遺伝子に順序を付与し、その順序によって前記ハプロタイプデータを数値化し、その数値化された値を利用して前記ハプロタイプデータを所定のデータ構造で保存するデータベース中に試験ハプロタイプデータが存在するかどうかを検索するハプロタイプデータの検索方法において、前記データベースに保存される前記ハプロタイプデータの一塩基多型の位置の対立遺伝子の順序と同様に、前記試験ハプロタイプデータ中の対立遺伝子に順序を付与する段階と、前記対立遺伝子の順序によって、前記対立遺伝子に整数を割り当てる段階と、前記試験ハプロタイプデータの対立遺伝子を、割り当てられた前記整数に置換する段階と、置換された前記整数の配列を桁値によって数値化する段階と、数値化された値を利用して、前記データ構造によって前記データベースを検索する段階と、を含むことを特徴とする。
【発明の効果】
【００１１】
本発明の好ましい形態によれば、ｎ個のハプロタイプデータに整数を付与して整列し、その整列されたハプロタイプデータをバランスバイナリツリー構造で保存することによって、検索時に従来のＯ（ｎ）の検索時間よりも短いＯ（ｌｏｇｎ）の時間でのさらに速い検索が可能となる。また、速い検索により、いろいろな研究グループ間のハプロタイプデータについての比較及び交換がさらに容易になされうる。
【発明を実施するための最良の形態】
【００１２】
以下、添付された図面を参照して本発明を詳細に説明する。
【００１３】
本発明ではハプロタイプデータを、バランスバイナリツリー（ｂａｌａｎｃｅｄ  ｂｉｎａｒｙ  ｔｒｅｅ）形態のデータ構造で保存する。バランスバイナリツリー構造は、「Ｒ．Ｅ．Ｔａｒｊａｎ，Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ  ａｎｄ  Ｎｅｔｗｏｒｋ  Ａｌｇｏｒｉｔｈｍｓ，ＳＩＡＭ，１９８３」に開示されている。
【００１４】
ハプロタイプデータをバランスバイナリツリー構造で保存するためには、データを整列することが必要である。図１は、本発明によるハプロタイプデータの整列及び保存方法を示すフローチャートである。
【００１５】
図１によれば、まず各ＳＮＰのそれぞれの位置で、対立遺伝子を所定の順序で整列する（ステップ１０）。例えばＡ、Ｔ、Ｇの３つの対立遺伝子を持つＳＮＰであると仮定すれば、３つの対立遺伝子に任意に順序を付与する。その順序は次の６つの順序のうち一つである；Ａ＜Ｔ＜Ｇ、Ａ＜Ｇ＜Ｔ、Ｔ＜Ａ＜Ｇ、Ｔ＜Ｇ＜Ａ、Ｇ＜Ｔ＜Ａ、Ｇ＜Ａ＜Ｔ。
【００１６】
次の表は、各ＳＮＰのそれぞれの位置に対応する対立遺伝子にそれぞれ異なる順序を付与した例を示すものである。
【００１７】
【表２】
2005182815.tif 000004
【００１８】
次に、各ＳＮＰのそれぞれの位置において、対立遺伝子の順序によってハプロタイプデータの大きさを比較し、ハプロタイプデータの順序を決定する（ステップ１１）。大きさの比較は、最初のＳＮＰの位置から大きさを比較して、対立遺伝子が始めて異なるＳＮＰの位置における対立遺伝子の大きさを比較することによって行われる。すなわち、２つのハプロタイプデータＨＸ＝（ｘ１，ｘ２，…，ｘｎ）、ＨＹ＝（ｙ１，ｙ２，…，ｙｎ）に対して、ｘ１＝ｙ１，ｘ２＝ｙ２，…，ｘｉ−１＝ｙｉ−１であり、ｉ番目の位置でｘｉ＜ｙｉならば、ＨＸ＜ＨＹとなる。例えば、ＨＸ＝（Ａ，Ａ，Ｔ，Ｃ，Ｇ，Ｃ，Ｃ，Ｇ，Ｇ，Ｇ）、ＨＹ＝（Ａ，Ａ，Ｃ，Ｔ，Ｔ，Ｇ，Ｔ，Ａ，Ａ，Ｔ）の２つのハプロタイプデータがあるとき、ＨＸとＨＹとでは３番目の塩基がそれぞれＴとＣとなって、対立遺伝子が初めて異なる。表２によれば、３番目のＳＮＰの位置ではＴ＜Ｃであるため、ＨＸ＜ＨＹとなる。
【００１９】
決定されたハプロタイプデータの順序によって、各ハプロタイプデータに整数を割り当てる（ステップ１２）。各ＳＮＰのそれぞれの位置の対立遺伝子の順序によって、０，１，…，ｑの整数を割り当てる。ここで、ｑは（対応するＳＮＰの位置における対立遺伝子の数−１）である。
【００２０】
例えば、対立遺伝子の順序が表２に示すように決定された場合、ＳＮＰのそれぞれの位置においては、次の表に示すように各対立遺伝子に整数が割り当てられる。
【００２１】
【表３】
2005182815.tif 000005
【００２２】
次いで、対立遺伝子に割り当てられた整数によって、各ハプロタイプデータを整数の配列に置換する。置換が完了すれば、置換された整数の配列を整数値に変換する。変換は、置換された整数の桁値を考慮して行われる。桁値は端桁を１とし、端桁から桁数が増加するにつれて、直前の桁値に、直前の桁に対応するＳＮＰの位置に存在する対立遺伝子の数を乗じた値とする。表３に示した場合を例として整理すれば、次の表の通りである。
【００２３】
【表４】
2005182815.tif 000006
【００２４】
例えば、ＣＴＣＴＧＧＣＣＡＴの配列を持つハプロタイプデータは、表３によって２１１０１０１２００に置換され、この整数の配列は再び表４によって２×３０７２＋１×１５３６＋１×５１２＋０×２５６＋１×６４＋０×３２＋１×１６＋２×４＋０×２＋０×１＝８２８０の整数値に変換される。
【００２５】
このような計算により、あらゆるハプロタイプデータが整数値に変換される。次の表は、各ハプロタイプデータを表３に基づいて整数値に変換した例を示したものである。
【００２６】
【表５】
2005182815.tif 000007
【００２７】
ハプロタイプデータは、対応する整数値を利用してバランスバイナリツリー構造で保存される（ステップ１３）。各ハプロタイプデータに対応する整数値は、バランスバイナリツリー構造の各ノードのキー値として割り当てられる。また、ノードｘに対してｘの左側のサブツリーにあるノードにはｘより小さなキー値を持つハプロタイプデータを、右側のサブツリーにあるノードにはｘより大きいキー値を持つハプロタイプデータを保存する。各ノードには、ハプロタイプデータ、キー値以外にも、対応するハプロタイプデータに関する情報、例えば、特定の人種において対応するハプロタイプデータを持つ被検者の比率を表す頻度のような情報も共に保存される。
【００２８】
図２は、表５に示したハプロタイプデータをバランスバイナリツリー構造で保存した例を図示したものである。図２によれば、各ノードは、表５の各番号に該当する整数値をキー値として持つ。例えば、２番ノードに保存されたハプロタイプデータの整数値は２８５４であり、左側サブツリーには、２番ノードのキー値より小さな値を持つ４番ハプロタイプデータが保存される。右側サブツリーには、２番ノードのキー値より大きい値を持つ６番ハプロタイプデータが保存される。
【００２９】
図３は、他の実施例によってハプロタイプデータをバランスバイナリツリー構造により保存した例を図示したものである。図示されるツリー構造は、次の表６のように、ハプロタイプデータに対して対立遺伝子がＡ＜Ｃ＜Ｇ＜Ｔの順序である場合に、その大きさによって順次に整列した結果によるものである。
【００３０】
【表６】
2005182815.tif 000008
【００３１】
表６において、各番号に対応するノードは、各ハプロタイプに関する情報として、各サンプル人種における頻度を表す。
【００３２】
バランスバイナリツリー構造で保存されたハプロタイプデータは、ツリーの深さが（２ｌｏｇｎ）であるため、検索時に従来よりも速い検索速度を保証する。例えば、図３のツリー構造で、ＧＴＴＣＧＧＣＧＡＴという試験ハプロタイプデータが既知のハプロタイプデータであるかどうかを調べるためには、Ａ＜Ｃ＜Ｇ＜Ｔの条件及び表２〜表５に表した方式によってＧＴＴＣＧＧＣＧＡＴについての整数値を計算する。計算された整数値を最初のノードである９番ノードのキー値と比較して大小を判別する。判別した結果、大きいならば右側のサブツリーである１３番ノードのキー値と比較し、小さいならば左側のサブツリーの５番ノードのキー値と比較して再び大小を判別する。このような方式で検索を進めれば、最大３回の比較により既知のデータであるかどうかが判別できる。
【００３３】
本発明によるハプロタイプデータの保存、整列、及び検索方法は、コンピュータ読取り可能な記録媒体に、コンピュータ読取り可能なコードとして具現化されうる。コンピュータ読取り可能な記録媒体としては、コンピュータシステムによって読取られるデータが保存されるあらゆる種類の記録装置が挙げられる。
【００３４】
コンピュータ読取り可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、ハードディスク、フレキシブルディスク、フラッシュメモリ、光データ保存装置などがあり、また、キャリアウェーブ（例えば、インターネットを通じた伝送）の形態で具現化されるものも含む。また、コンピュータ読取り可能な記録媒体は、ネットワークに連結されたコンピュータシステムに分散されて、分散方式でコンピュータ読取り可能なコードとして保存され実行されてもよい。
【産業上の利用可能性】
【００３５】
個人差を示すＤＮＡ塩基の変異の対立遺伝子セットを分類してデータベースに保存して検索することに係る技術分野に利用できる。
【図面の簡単な説明】
【００３６】
【図１】本発明によるハプロタイプデータの保存方法を示すフローチャートである。
【図２】表５に示すハプロタイプデータをバランスバイナリツリー構造で保存した例を示す図面である。
【図３】表６に示すハプロタイプデータをバランスバイナリツリー構造で保存した例を示す図面である。
【図１】
2005182815.tif 000009
【図２】
2005182815.tif 000010
【図３】
2005182815.tif 000011