(57)【要約】【課題】問い合わせ配列（クエリー）として与えるアミノ酸配列、または塩基配列に対して配列類似性の高い配列候補をアミノ酸配列データベース、または塩基配列データベースから、より少ない計算ステップ数で検索することを可能とする。【解決手段】クエリーとして与えられたアミノ酸配列、または塩基配列を符号化し、同様に符号化されたデータベースにおける複数の配列とのハミング長を計算し、任意の閾値以下のデータベース配列を量子アルゴリズムによって、並列的に計算することにより、クエリー配列と類似性の高い配列をデータベースから高速に抽出する。【選択図】図３
2011165142.tif 000002
【特許請求の範囲】
【請求項１】
アミノ酸配列、またはDNAやRNAによる遺伝配列からなる生物学的配列データベースから、目的とする配列データと一致あるいは類似した配列の検索を、量子アルゴリズムを利用して効率よく行うデータ検索方法。
【請求項２】
アミノ酸配列、またはDNAやRNAによる遺伝配列からなる前記生物学的配列データベースに含まれる検索対象サンプル配列と、前記の目的とする配列データ間に対し類似度を設定し、前記類似度の任意の複数の値のうち、少なくともひとつに一致する全ての配列の検索を、量子アルゴリズムを利用して効率よく行うデータ検索方法。
【請求項３】
前記類似度のもとでの任意の閾値に対して、問い合わせ配列として与えられたアミノ酸配列、または塩基配列に類似した全ての配列を、種々のアミノ酸配列、または塩基配列を格納した前記生物学的データベースから抽出するデータ検索方法であって、前記問い合わせ配列と前記データベースに格納された全配列をそれぞれ符号化し、前記２種類の配列間のハミング長の値の計算により、前記データベースに格納された配列から、与えられたハミング長の任意の複数の値のうち少なくとも一つに一致する全ての配列の検索を、量子アルゴリズムを利用して高速で行うデータ検索方法。
【請求項４】
前記類似度のもとでの任意の閾値に対して、問い合わせ配列として与えられた未知のアミノ酸配列、または塩基配列に類似した全ての配列を、N 種類のアミノ酸配列、または塩基配列を格納した前記生物学的データベースから抽出するデータ検索方法であって、前記問い合わせ配列と前記データベースに格納された全配列をそれぞれ符号化し、前記２種類の配列間のハミング長の値の計算により、前記データベースに格納された配列から、与えられたハミング長の任意の複数の値のうち少なくとも一つに一致する全ての配列の検索を、量子アルゴリズムを利用して √N 程度のステップ数で行うデータ検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子コンピュータを用いてあるいは量子アルゴリズムを適用して、クエリー配列として問い合わせるアミノ酸配列または塩基配列に類似する配列を、生物学的データベースから任意の閾値を用いて探索するアルゴリズムに関する。
【背景技術】
【０００２】
近年、盛んに行われている生物学におけるゲノム解析などの大量生物情報の情報学的解析：バイオインフォマティクスにおいては、新規の生物学的情報（タンパク質・アミノ酸配列、DNA、RNA配列など）の類似性を既知の生物学的データベースから検索することが可能になった。そして、目的タンパク質や塩基配列の機能などを類推・分類することが生物学だけでなく、遺伝学、医学、薬学の分野などで重要な手法として用いられるようになった。
【０００３】
しかしながら、ゲノム情報などの生物学的情報・データベースが拡充されるに従って、データベースに格納された大量の生物学的配列に対してデータ検索を行うことは大量の計算時間とメモリ空間を要し、計算コストが非常に高くなってきている。実際にBLAST (Basic local alignment search tool)等の検索速度を重視したデータベース検索プログラムが開発されているが、生物学的データベースにおける格納アミノ酸配列、塩基配列数の指数的な増加に追いついていない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許公開２００５−７８４０７
【非特許文献】
【０００５】
【非特許文献１】L. C. L. Hollenberg, “Fast Quantum Search Algorithms in Protein Sequence Comparison - Quantum Biocomputing”, Phys. Rev. E62 (2000)7532-7535.
【非特許文献２】S. F. Altschul, W. Gish, W. Miller, E. W. Myers & D. J. Lipman, “Basic local alignment search tool”, J. Mol. Biol., 215 (1990) 403-410.
【非特許文献３】Lov K. Grover, “Quantum Mechanics Helps in Searching for a Needle in a Haystack”, Phys. Rev. Let., 79 (1997) 325.
【非特許文献４】Ahmed Younes, “Strength and Weakness in Grover's Quantum Search Algorithm”, arXiv:0811.4481v1.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
生物学の分野において、近年、ヒトゲノム計画などのゲノム解析が盛んになり、生物学的情報データベースが整備され、アミノ酸配列、塩基配列のデータ検索が重要な解析手法となっている。データベースに格納されている配列を N 個とした場合、そのデータ検索量のオーダーは N 程度であるが、遺伝配列を解析する技術の発達により、生物学的データベースに格納されるアミノ酸配列、塩基配列の数が驚異的速度で増加し、データ検索のための計算量が負担となってきており、より高速なデータ検索方法の開発が必要となっている。
【０００７】
現在、アミノ酸配列や塩基配列の類似性を、データベースに対して高速に検索するBLASTなどの方法が開発・使用されているが、データ検索量のオーダーが N 程度であることに変わりはなく、並列化などの技術を用いて計算量の増加に対応しているのが現状である。
【０００８】
そこで、本発明の目的は与えられたアミノ酸配列や遺伝配列に対して類似性の高い配列をデータベースから高速に検索する方法を提供することにある。
【課題を解決するための手段】
【０００９】
現在、一般的に利用されているコンピュータに対して、並列処理を基本とした「量子コンピュータ」による高速な演算処理が提案されている。量子コンピュータは量子力学で記述される物理現象に特有な量子重ね合わせ状態を利用する方法である。この量子コンピュータの実現には量子重ね合わせ状態を実現し、演算回路を組むことができる量子ビットという素子を使用する。量子ビットを使用した量子コンピュータによる量子アルゴリズムでは、因数分解やデータ検索などで現在のコンピュータよりも、はるかに高速な演算が可能であることが示されており、量子コンピュータに実現に向けた研究が勢力的に行われている。
【００１０】
本発明は、量子コンピュータの計算原理を利用して、生物学的情報である、アミノ酸配列、塩基配列の類似配列をデータ検索するアルゴリズムであり、非特許文献１で提案されているアイデアを参考にして、より現実的なデータ検索アルゴリズムを提案するものである。故に、与えられたクエリー配列との類似性が高い配列を、データベースから任意の複数の類似度の値を設定して同時に検索することができる。類似性の高さは符号化して比較した、ハミング長である。
【００１１】
よって、本発明のデータ検索方法は、クエリー配列とデータベースの配列を符号化する段階と、量子的重ね合わせを利用して並列的に、クエリー配列と多数のデータベース配列間でのハミング長を算出し、設定した類似度の任意の複数の値のうち少なくともひとつに合致するデータベース中の配列を全て検索する段階を持つ量子アルゴリズムである。
【００１２】
この方法は、非特許文献１で使用されているグローバーのデータ検索アルゴリズムにおける、オラクル（計算処理方法は提示せず、あるインプットに対して決められたアウトプットを提示する仮想的ブラックボックス）を仮定せずに、実行可能な量子回路を実装するものである。
【発明の効果】
【００１３】
本発明は、膨大な数の生物学的情報（アミノ酸配列・塩基配列）が格納されているデータベースから、量子アルゴリズムを使用して並列計算的にクエリー配列と類似の配列を、高効率・高速度で検索できるという効果がある。データベースに N 個のデータが存在する場合、一般のコンピュータで行う計算ステップ数のオーダーは N 程度となるが、本発明を仕様すれば √N 程度となり、 N が100倍に増えても、計算ステップ数は100倍ではなく、√100 ＝ 10 倍になる。従って、本方法を利用すればデータベースの格納数が多くなっても、検索速度が遅くなることを抑制することができる。
【図面の簡単な説明】
【００１４】
【図１】図１は数４で定義した演算子Dを量子回路図で表したものである。
【図２】図２は数５で定義した演算子Pを量子回路図で表したものである。
【図３】図３は数１７を量子回路図で表したものである。
【図４】図４は数３５を量子回路図で表したものである。
【発明を実施するための形態】
【００１５】
次に、本発明の量子アルゴリズムについて詳細に説明する。
【００１６】
最初に量子アルゴリズムを定義する。
【００１７】
古典的計算機とは、チューリングマシンによってその数学的モデルが定義される計算機であって、実際にはノイマン型コンピュータである計算機のことである。量子コンピュータにおいては、古典的計算機におけるビットに相当するものは量子ビットと呼ばれる。量子コンピュータは複数の量子ビットから構成され、各量子ビットは古典計算機におけるビットの状態：０か１、のみならずそれらの重ね合わせ状態をとることができ、量子コンピュータで計算を行うことは、各量子ビットに初期値を与え、それらに操作を行うことによって各量子ビットの情報を操作し、最後に量子ビットを観察して情報を取り出すことである。各量子ビットに実行されるビット情報の一連の操作を量子アルゴリズムと呼び、量子ビットに施す基本操作単位を決定すれば、量子アルゴリズムはこの操作の組み合わせによって決定される。
【００１８】
本発明において用いられるデータベースについて記述する。
【００１９】
入力アミノ酸配列、塩基配列をSとする。S中のアミノ酸配列（２０種類）を１−２０で符号化し、さらにそれぞれの番号を０、１の２進数で表現する。データベースにおいては、それぞれの配列にID番号が与えられており、各IDの配列を入力配列と同じように符号化し、２進数で表現する。塩基配列の場合は１−４の符号化を実施し、やはり２進数で表現する。
【００２０】
上記のようなデータベースを作成する際には、目的とする長さのすべての配列を格納するデータベースを用意する。例えば、長さ５残基のデータベースを用意する際には、２０の５乗の配列を格納したデータベースを量子ビット上に準備する。
【００２１】
すべての状態を網羅したデータベースを準備する式|ψ＞は以下のようになる。
【００２２】
【数１】
2011165142.tif 000003
【００２３】
数１において、nは2nが目的とする長さの配列の総数以上になるような最小の自然数である。Nnは0から2n-1までの整数の集合である。|Nn|は集合Nnの要素数を表す。また、量子状態|x＞はNnの要素xから以下のようにして得られる。まず、xを２進数表示する。
【００２４】
【数２】
2011165142.tif 000004
【００２５】
数２によって得られたxi=0,1に対して、値が0の場合は
2011165142.tif 000005
を、1の場合は
2011165142.tif 000006
をそれぞれ対応させ、総称して|xi＞と書く。全てのiに対して以上の対応付けを行い、それらの直積状態として量子状態|x＞を定義する。
【００２６】
【数３】
2011165142.tif 000007
【００２７】
2011165142.tif 000008
【００２８】
また、反転演算子Dを以下のように定義する。
【００２９】
【数４】
2011165142.tif 000009
【００３０】
2011165142.tif 000010
【００３１】
目的とする検索データを反転するオラクルΟを設定する。
【００３２】
【数５】
2011165142.tif 000011
【００３３】
数５において、Tnはデータベースに格納されている各データの中で、00…0という配列からのハミング長が、設定した複数の値のうち少なくともひとつに合致するデータの集合である。|Tn＞はTnを用いて以下の式で表現される。
【００３４】
【数６】
2011165142.tif 000012
【００３５】
次に、クエリー配列に対する類似配列をデータベースから検索するアルゴリズムを説明する。まず、クエリー配列を r とすると、データベースとクエリー配列の初期状態は以下の式で表現される。
【００３６】
【数７】
2011165142.tif 000013
【００３７】
次にクエリー配列をなす各量子ビットとデータベースの各量子ビットの間に、クエリー配列の量子ビットを制御ビットとした制御付き否定操作（CNOT）を行う。これにより、データベース状態は以下のように変換される。
【００３８】
【数８】
2011165142.tif 000014
【００３９】
2011165142.tif 000015
【００４０】
上記の式を使用して、以下のような繰り返し演算を行う過程を実施することにより、√N のオーダーの計算ステップ数で000…0という配列からのハミング長が、設定した複数の値のうち少なくともひとつに合致するデータを全て検索できる。
【００４１】
【数９】
2011165142.tif 000016
【００４２】
数９において、mは繰り返し演算回数を示す自然数である。
【００４３】
√N のオーダーの計算ステップの後にデータベースに対して測定を行うと、数６の状態が検索結果として出てくる。この状態に[００３７]と同様のCNOT操作を行うことにより、クエリー配列からのハミング長が、設定した複数の値のうち少なくともひとつに合致する全てのデータが、r が未知の場合でも取り出せる。
【００４４】
数５で記されているオラクルΟ(Tn) は、以下の式のような分解が可能である。
【００４５】
【数１０】
2011165142.tif 000017
【００４６】
ここで記述されている演算子Pは以下の式で表される。
【００４７】
【数１１】
2011165142.tif 000018
【００４８】
この演算子については非特許文献４により構成法が知られている。演算子U(Tn)は数６を生成するユニタリ演算子である。
【００４９】
【数１２】
2011165142.tif 000019
【００５０】
上記のデータベース検索の手順を生物学的データベースに応用する場合、演算子U(Tn) が具体的に構成できなければならない。そのための数学的手法を説明する。
【００５１】
まず、２つの集合を以下の操作により定義する。集合Tn の全ての要素について、１桁目のビットの値が０か１かによって分類を行い、２つの部分集合を作る。その後、２つの部分集合の要素に対して、分類に使用した１桁目のビットを消去し(n - 1)桁のビット列に変換する。１桁目のビットの値が０だった要素に対してこの操作を行うことによって得られる(n - 1)桁のビット列のなす集合を T0n-1 とし、１桁目のビットの値が１だった要素に対して同様にして得られる集合を T1n-1 とする。これらの集合に対して、数６と同様の量子状態を考えることができる。
【００５２】
【数１３】
2011165142.tif 000020
【００５３】
【数１４】
2011165142.tif 000021
【００５４】
数１３と数１４に対して数１２と同様の関係を持つユニタリ演算子がU(T0n-1) と U(T1n-1) である。
【００５５】
【数１５】
2011165142.tif 000022
【００５６】
【数１６】
2011165142.tif 000023
【００５７】
この二つの演算子を残りの一個の量子ビットを制御ビットとして制御付き演算子にしたものが CU(T0n-1) 及び CU(T1n-1) である。
【００５８】
一般に数１２を満たすユニタリ演算子は無数に存在するが、それらの中で、U(T0n-1) と U(T1n-1) から以下の関係式を用いて構成したものを U(Tn) とする。
【００５９】
【数１７】
2011165142.tif 000024
【００６０】
数１７において、演算子Xn は１番目の量子ビットに対する反転操作を表す。
【００６１】
【数１８】
2011165142.tif 000025
【００６２】
反転操作は以下で表される。
【００６３】
【数１９】
2011165142.tif 000026
【００６４】
演算子Vn は1番目の量子ビットに対する回転操作を表す。
【００６５】
【数２０】
2011165142.tif 000027
【００６６】
回転操作は以下で表される。
【００６７】
【数２１】
2011165142.tif 000028
【００６８】
回転角θ は以下を満たすものである。
【００６９】
【数２２】
2011165142.tif 000029
【００７０】
数１７によって n量子ビットの回路が (n - 1)量子ビットの回路の組み合わせとして表現されてゆくので、これを繰り返し用いれば基本的な量子回路の組み合わせとして U(Tn) が表されることになる。
【００７１】
数１７によって構成された U(Tn) が実際に数１２を満たすことは、以下のように示される。まず、
2011165142.tif 000030
とを１桁目の量子ビットに対して使用すると、以下の式が導ける。
【００７２】
【数２３】
2011165142.tif 000031
【００７３】
次に、数２３、数２０及び数２１によって以下の式変形が出来る。
【００７４】
【数２４】
2011165142.tif 000032
2011165142.tif 000033
2011165142.tif 000034
【００７５】
数２４で Y は以下を表す。
【００７６】
【数２５】
2011165142.tif 000035
【００７７】
2011165142.tif 000036
【００７８】
【数２６】
2011165142.tif 000037
2011165142.tif 000038
2011165142.tif 000039
【００７９】
よって数１７の右辺は数１２を満たすことが確認された。
【実施例】
【００８０】
実施例として３量子ビット系においてハミング長１を閾値とする検索を行う場合のユニタリ演算子 U(Tn) の回路を構成する。
【００８１】
まず、集合は以下のようになる。
【００８２】
【数２７】
2011165142.tif 000040
【００８３】
【数２８】
2011165142.tif 000041
【００８４】
【数２９】
2011165142.tif 000042
【００８５】
数２２に以上の集合の要素数を代入すれば、Vが得られる。
【００８６】
【数３０】
2011165142.tif 000043
【００８７】
数１７内の残りの回路を求めるために、再び数１７を利用する。そのために、数２８の集合 T02 を T2 とみなす。すると以下の集合が得られる。
【００８８】
【数３１】
2011165142.tif 000044
【００８９】
【数３２】
2011165142.tif 000045
【００９０】
数２２に集合の要素数を代入すると、回転操作は以下のようになる。
【００９１】
【数３３】
2011165142.tif 000046
【００９２】
また、それぞれの集合に対して数１２を満たす演算子を探すと、以下のように表される。
【００９３】
【数３４】
2011165142.tif 000047
【００９４】
【数３５】
2011165142.tif 000048
【００９５】
これらを数１７に代入すると以下の式が得られる。
【００９６】
【数３６】
2011165142.tif 000049
【００９７】
同様の手順を数２９に対して行うと以下の式が得られる。
【００９８】
【数３７】
2011165142.tif 000050
【００９９】
数３３と数３４を数１７に代入すると以下の式が得られ、回路を構成することができる。
【０１００】
【数３８】
2011165142.tif 000051
【産業上の利用可能性】
【０１０１】
生物学的情報の解析に利用が可能である。
【図１】
2011165142.tif 000052
【図２】
2011165142.tif 000053
【図３】
2011165142.tif 000054
【図４】
2011165142.tif 000055