相同性検索装置及びプログラム
【課題】特定のシード構造を使用せず、最適化マッチを適応的に生成可能な、ワードベース探索戦略に基づく相同性検索装置の提供。
【解決手段】相同性判定の編集距離閾値Ｔに対し、検索要求ワードＷを段階的に分割する終端節点数Ｔ＋１のワード二分木を生成し、各終端節点に対応する素ワード素ワードＷｉをクエリとして検索対象シーケンスＳに対する完全検索を行い、完全マッチを抽出する。次いで、抽出した各完全マッチについて、ワード二分木に基づき、ワード二分木の各節点に対するワードを単位として素ワードＷｉを伸長し、検索対象シーケンスＳの完全マッチ部分に所定の検索ウィンドウを追加した比較対象シーケンスと伸長した素ワードとの編集距離を算出し、編集距離がＴ以下ならば伸長した素ワードとのマッチを出力するという処理を繰り返す。
【解決手段】相同性判定の編集距離閾値Ｔに対し、検索要求ワードＷを段階的に分割する終端節点数Ｔ＋１のワード二分木を生成し、各終端節点に対応する素ワード素ワードＷｉをクエリとして検索対象シーケンスＳに対する完全検索を行い、完全マッチを抽出する。次いで、抽出した各完全マッチについて、ワード二分木に基づき、ワード二分木の各節点に対するワードを単位として素ワードＷｉを伸長し、検索対象シーケンスＳの完全マッチ部分に所定の検索ウィンドウを追加した比較対象シーケンスと伸長した素ワードとの編集距離を算出し、編集距離がＴ以下ならば伸長した素ワードとのマッチを出力するという処理を繰り返す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、核酸の塩基配列やタンパク質のアミノ酸配列のように所定の種類の文字又は記号の文字列からなるシーケンスについて、２つのシーケンスの相同性を検索するための相同性検索技術に関する。
【背景技術】
【０００２】
「相同性（homology）」とは、共通の祖先からの進化的関係に由来して、異なる有機体間で構造が対応することをいう。生物情報科学においては、「相同」は、異なるシーケンス（タンパク質又は核酸の塩基配列）間の類似するセグメントによって表される。相同性検索は、このような類似性を探索し、対応するマッチ（match）の位置決めを行うための計算プロセスである。これは、生物情報科学においては、様々な調査・研究の基礎となる基本的な問題である。
【０００３】
シーケンスの類似性は、２つのシーケンス間の編集距離（edit distance）によって定義することができる。多くの場合、編集距離としては、レーベンシュタイン距離（Levenshtein distance）が用いられる。２つのシーケンス間の編集距離とは、一方のシーケンスを他方のシーケンスに変換する基本操作の最小数をいう。「基本操作」とは、挿入（insert）、欠失（deletion）、及び置換（substitution）である。この定義によれば、編集距離が小さいほど、類似性が高くなる。
【０００４】
レーベンシュタイン距離は、最初に非特許文献１において生物情報科学に導入され、非特許文献２において、局所配列に拡張された。このレーベンシュタイン距離は、動的計画法によって正確に計算することが可能である（非特許文献３，ｐｐ．１８−２８参照）。これらの動的計画法の基本アルゴリズムは、相同性検索にも使用することができ、最適な検出感度を維持することができる。
【０００５】
しかしながら、動的計画法の計算複雑性はＯ（ｎｍ）である（非特許文献３，ｐ．２８，３１，３４参照）。ここで、ｎ，ｍは、それぞれのシーケンスの長さである。このように、動的計画法は計算量が多く速度が遅いため、調査すべきシーケンスデータの量が膨大化するに従って、相同性検索問題の大部分に適用することができなくなった。
【０００６】
そのため、多少の検出感度の低下（すなわち、多少のマッチの欠失）と引き替えに、より高速化する方向で、発見的アプローチが発展してきた。発見的アプローチでは、シードを基礎とするアプローチ（シードベースアプローチ）が主流である。このシードベースアプローチでは、低くても十分な感度を維持しつつ検索速度を極めて高速化するために提案されたフィルタ原理に基づき、動的計画法のプロセスの近似値を求める。
【０００７】
シードは、「１１１００１０１」のような２進列で表される。ここで、「１」は正確にマッチする位置を表し、「０」はマッチ条件を満たさない位置を表す。シードパターンに一致する、クエリシーケンス及び検索対象シーケンス間の部分シーケンスのマッチは「ヒット（hit）」と呼ばれる。
【０００８】
このシードベースアプローチでは、次のようなステップを含む戦略が用いられる。
（１）クエリシーケンスから、シードの長さと等しい長さの部分シーケンスをすべてリストアップする。
（２）クエリシーケンスと検索対象シーケンスとの間で、上記部分シーケンスのすべてのヒットを索出する。
（３）近似マッチングによりヒットを伸長する。この伸長は、類似性スコア（例えば、非特許文献３，ｐｐ．２８−３１参照）が、ユーザにより予め決められた検索要求まで減少した時点で終了する。
【０００９】
現在、最も広く使用されているこの種のアルゴリズムは、ＢＬＡＳＴ（非特許文献４参照）であり、これは連続的な完全一致のシードパターンを使用している。一方、ＢＬＡＳＴの性能と柔軟性を向上させるため、多くの取り組みがなされており、同様のアイデアを用いた相同性検索の様々なバージョンが考案されている（非特許文献５−９参照）。
【００１０】
また、「０」を含んだ分隔シード（spaced prime）は、非特許文献１０において最初に提案された。非特許文献１０において、分隔シードにより作られる近似マッチにより生成されるヒットは、感度と速度の間のバランスがよいことが示された。シードにおける「１」の数は「シードの重み（prime weight）」と呼ばれる。その後、非特許文献１１−１３等のように、多くのシード最適化法が開発された。
【００１１】
他方、非特許文献１４−１７では、単一シードパターンの代わりに、１組の最適化された多重シード（multiple prime）を使用する方法が導入されている。これらのアプローチでは、様々な統計的又は実証的方法に基づいて、複数のシードパターンの評価が行われている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２０００−１９４７１３号公報
【特許文献２】特開２００２−２２９９９８号公報
【特許文献３】特開２００９−１１６５５９号公報
【特許文献４】特開２００５−８４８５９号公報
【特許文献５】特表２００２−５２９８１７号公報
【特許文献６】特表２０００−５００８９６号公報
【非特許文献】
【００１３】
【非特許文献１】Needleman, Saul B.; Wunsch, Christian D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 1970, 48 (3): 443-53.
【非特許文献２】Smith, Temple F.; Waterman, Michael S. Identification of Common Molecular Subsequences. Journal of Molecular Biology 1981, 147: 195-197.
【非特許文献３】阿久津達也，「アルゴリズム・サイエンスシリーズ１２ バイオインフォマティクスの数理とアルゴリズム」，初版，共立出版株式会社，２００７年２月．
【非特許文献４】Altschul, S.F.; Gish, W.; Miller, W.; Myers, E.W.; Lipman, D.J.: Basic local alignment search tool. J Mol Biol 1990, 215 (3): 403-410.
【非特許文献５】Altschul, S.F.; Madden, T.L.; Schaffer, A.A.; Zhang, J.; Zhang, Z.; Miller, W.; and Lipman, D.J. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. Nucleic Acids Res. 1997 25: 3389-3402
【非特許文献６】Gish, W. and States, D.J. Identification of protein coding regions by database similarity search. Nat. Genet. 1993 3: 266-272.
【非特許文献７】Gotoh, O. Homology-based gene structure prediction: Simplified matching algorithm using a translated codon (tron) and improved accuracy by allowing for long gaps. Bioinformatics 2000 16: 190-202.
【非特許文献８】Zhang, Z.; Schwartz, S.; Wagner, L.; and Miller, W. A greedy algorithm for aligning DNA sequences. J. Comput. Biol. 2000 7: 203-214.
【非特許文献９】Kent, W. J. BLAT-the BLAST-Like Alignment Tool. Genome Res. 2002, 12:656-664.
【非特許文献１０】Ma, B.; Tromp, J.; Li, M.: PatternHunter: faster and more sensitive homology search. Bioinformatics. 2002, 18:440-445.
【非特許文献１１】B. Brejova, D. Brown, and T. Vinar, Optimal spaced primes for homologous coding regions. J. Bioinf. And Comp. Biol. 1(2004), pp. 595-610.
【非特許文献１２】J. Buhler, U. Keich, and Y. Sun, Designing primes for similarity search in genomic DNA. Proc. 7th Annual Int'l Conf. on Comput. Mol. Biol. (RECOMB'03), pp. 67-75, Berlin, Germany.
【非特許文献１３】K.P. Choi, and L. Zhang, Sensitivity analysis and efficient method for identifying optimal spaced primes, J. Comput. Sys. Sci., 68(2004), pp. 22-40.
【非特許文献１４】Sun, Y.; Buhler, J.: Designing multiple simultaneous primes for DNA similarity search. J. Comput. Biol. 2005 12:847-861.
【非特許文献１５】J. Xu, D. Brown, M. Li, and B. Ma, Optimizing multiple spaced primes for homology search, In Proc. of CPM'04, LNCS, vol. 3109, pp. 47-58.
【非特許文献１６】I.-H. Yang et al. E_cient Methods for Generating Optimal Single and Multiple Spaced Primes, In Proc. IEEE 4th Symp. on Bioinformatics and Bioengineering, Taiwan, 2004, pp. 411-418.
【非特許文献１７】Li, M., Ma, B., Kisman, D., et al. 2004. PatternHunter II: highly sensitive and fast homology search. J. Bioinform. Comput. Biol. 2, 417-439.
【非特許文献１８】M. Li, B. Ma, L. Zhang, Superiority and complexity of the spaced primes, in: Proceedings of the 17th Annual ACM-SIAM Symposium On Discrete Algorithms (SODA'06), ACM Press, 2006, pp. 444-453.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
以上のような各相同性検索方法は、その性能が、いずれもシードの構造に大きく依存する。シード最適化法でさえ、予め定義されたシードの重みによって制限される（非特許文献１６−１８参照）。従って、上記各各相同性検索方法は、シードの重みをあまり大きく設定しすぎると多くの相同配列を欠失する（感度が低下する）こととなる一方、シードをあまり短くしすぎると誤ったヒットが増加して検索速度も低下するといったジレンマが、未解決のまま残されている。これは、上述した（１）〜（３）のステップを含む戦略から発展したことに起因する根本的な問題である。
【００１５】
そこで、本発明の目的は、特定のシード構造を使用することなく、最適化されたマッチを適応的に生成することが可能な、ワードベースの探索戦略に基づく相同性検索装置及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００１６】
最初に、本発明の基礎となるアルゴリズムについて説明し、次いで、本発明の構成について説明する。
【００１７】
〔１〕本発明の基礎となるアルゴリズム
最初に、本発明の基礎となるワードベースの探索戦略について説明する。
【００１８】
相同性検索の目標は、最小の編集距離が閾値Ｔ以下である、クエリシーケンスと検索対象シーケンスの部分シーケンスのペアを検出することにある。本発明におけるワードベースの探索戦略は、上記従来のシードベースの探索戦略とは異なるため、以下、本発明の検索アルゴリズムを説明する際には、混同を避けるために「シード（prime）」，「ヒット（hit）」等の用語は使用しない。
【００１９】
本発明の相同性検索装置の基礎となるアルゴリズムは、以下のような手順で実行される。
【００２０】
（１）クエリシーケンスから、長さＬの全てのサブシーケンスのリストを作る。これらのサブシーケンスを「検索要求ワード」と呼ぶ。
【００２１】
この段階では、従来のシードベースのアプローチと類似している。しかしながら、本発明で用いるアルゴリズムでは、シードパターンに相当する検索要求ワードがマッチする必要はなく、この検索要求ワードを構成する非重畳セグメント（non-overlapped segment）を、相同性判定を行いながら連結していくことによって適応的にマッチが作り出されていく点で、従来とは全く相違する。
【００２２】
（２）全ての検索要求ワードを、非重畳セグメントに分解する。これらの非重畳セグメントを「素ワード（prime word：ＰＷ）」と呼ぶ。
【００２３】
（３）検索対象シーケンスに対して、素ワードをクエリとする完全一致検索を行い、すべての厳密な素ワード・マッチ（prim word match：ＰＷＭ）を索出する。
【００２４】
（４）素ワード・マッチを伸長（expand）する。
【００２５】
（５）検索対象シーケンスにおいて、編集距離がＴ以下の素ワード・マッチが検出された場合、この素ワード・マッチを検索結果（相同性索出データ）として出力し、さらなる伸長は、従来方法と同じくできるだけ長い結果が得られるように実行する。
【００２６】
このワードベースの探索戦略においては、次の２つの重要な問題を解決する必要がある。
【００２７】
（１）素ワードの長さ： 素ワードの長さは、偽性候補（false candidate）が索出されるのを制限しつつ、陽性候補（positive candidate）が欠失するのを回避するように設定しなければならない。
【００２８】
（２）素ワード・マッチの伸長の計算速度。
これらの課題を解決するために、本発明においては、以下に説明する「最小マッチ性（least match property）」に基づいて新たに開発したアプローチを用いる。
【００２９】
〔１−１〕最小マッチ性
シーケンスの距離測度に関して、以下のような簡単に証明可能な定理がある。
【００３０】
（定理１）
シーケンスＷ及びＳに対して、それらの間の距離をＤ（Ｗ，Ｓ）＝ｄとし、シーケンスＷはｄ＋１個の非重畳セグメントＷ＝Ｗ１Ｗ２…Ｗｄ＋１に分割されるとすると、Ｓ内に完全マッチ（exact match）を持つセグメントＷｉ（１≦ｉ≦ｄ＋１）が、少なくとも１つ存在する。
（定理終り）
【００３１】
この定理は明らかである。なぜなら、ＷからＳに変換するにはｄ回の操作のみが必要とされ、それらは少なくともｄ個の非重畳サブシーケンスを生じるからである。
【００３２】
この（定理１）に示される性質は、以下の（定理２）により、より一般化することができる。
【００３３】
（定理２）
Ｄ（Ｗ，Ｓ）＝ｄとし、Ｗはｋ個の非重畳セグメントＷ＝Ｗ１Ｗ２…Ｗｋに分割される場合、次式を満たすような、１つのＳのサブシーケンスＳｊと、少なくとも１つのＷのセグメントＷｉが存在する。
【００３４】
【数１】
ここで、Ｗｉ及びＳｊは、それぞれ、Ｗ及びＳのサブシーケンス（セグメント）、［ｄ／ｋ］はｄ／ｋを超えない最大の整数である（［ ］は、一般に「ガウス記号」と呼ばれる）。
（定理終り）
【００３５】
この（定理２）に示される性質を「最小マッチ性」と呼ぶ。
【００３６】
〔１−２〕素ワード長の選定
今、クエリシーケンスから切り出される一つのワードＷを考え、ワードＷの長さを｜Ｗ｜＝Ｌとする。また、Ｄ（Ｗ，Ｓ）≦Ｔとなる検索対象シーケンス内のサブシーケンスＳを索出したいものとする。
【００３７】
上述の最小マッチ性によれば、もしワードＷがＴ＋１個の非重畳セグメントに分割されるならば、検索対象シーケンスにおいて当該セグメントの完全マッチが少なくとも１つ存在するか、然もなくばＤ（Ｗ，Ｓ）≦Ｔの条件を満たすサブシーケンスＳは存在しない。従って、ワードＷをＴ＋１個の同じ長さの非重畳セグメントに分割する。すなわち、任意の１≦ｉ≦Ｔ＋１及び１≦ｊ≦Ｔ＋１について、Ｗ＝Ｗ１Ｗ２…ＷＴ＋１，｜Ｗｉ｜＝｜Ｗｊ｜とする。但し、最後のセグメントＷＴ＋１の長さは、それよりも前の各セグメントの長さよりも短くてもよいこととする。本発明では、これらのセグメントを素ワードとして使用する。これによって、Ｗの如何なる可能なマッチも欠失しないことが保証される。
【００３８】
〔１−３〕素ワード・マッチの高速伸長
完全一致検索により素ワード・マッチの位置が決定されると、次に、より長いマッチを探索するために、それらの素ワード・マッチを伸長する。
【００３９】
ここで、従来の動的計画法又は完全探索法（窮舉法：exhausted search）の代わりとして、最小マッチ性に基づいて、素ワード・マッチに隣接する素ワードをワード単位で連結していくことにより、素ワード・マッチの伸長を行うことが可能である。これは、最小マッチ性により許容される距離は、分割の変化のみによるとともに、最小マッチ性に係る（定理２）は、任意のシーケンスの分割及び初期素ワード同士の結合を行ったとしても、依然として成り立つからである。
【００４０】
すなわち、最小マッチ性の成立条件は次式のように表される。
【００４１】
【数２】
【００４２】
各ステップにおいて、ｋは２の冪乗である。式（２）は、Ｗｉ，Ｓｊの完全一致から距離［Ｔ／ｋ］までを相同条件として容認し、この相同条件を満たす限り隣接する２つのセグメントは互いに結合することができることを意味している。そこで、素ワードを二進木（binary tree）により体系化する。ここで、二進木の根節点は検索要求ワードＷに対応し、各終端節点（terminal node）は素ワードに対応し、非終端節点は、その子節点に向かう１つ又は２つの枝を有する。ここで、各非終端節点の左側の枝は、常に右側の枝と同数か又は１つだけ多い素ワードを有するものとする。
【００４３】
図５にワード二分木の一例を示す。この例では、探索条件である最大許容編集距離Ｔが６である。ここで、終端節点の親節点のみが、１つの枝のみを有することができるものとする。ワード二分木のレベル（階数）は、終端節点がレベル１とし、終端節点から根節点に向かってレベルが増加するとする。ワード二分木の各レベルにおいて、１つの節点はワードＷのセグメントの距離［Ｔ／ｋ］の近似マッチを表す。ここで、ｋ＝２１−ｎ（Ｔ＋１）であり、ｎはレベルを表すインデックスである。例えば、ｎ＝１はレベル１である。
【００４４】
図５の例を用いて、本発明の素ワード・マッチの伸長アルゴリズムについて説明する。
【００４５】
ワード二分木の各レベルは、検索要求ワードＷの分割を表す。例えば、図５におけるレベル２の分割は、Ｗ＝Ｗ１’ Ｗ２’ Ｗ３’ Ｗ４’である。ここで、ｉ＜４に対してはＷｉ’＝Ｗ２ｉ−１Ｗ２ｉであり、Ｗ４’＝Ｗ７である。
【００４６】
レベル１における素ワード・マッチの伸長は、レベル２において、相同判定条件Ｄ（Ｗｉ’，Ｓｊ）≦［６／４］＝１の素ワードの連結を探索することと等価である。ここで、Ｓｊは、先頭又は末尾にワードＷｉ’内の素ワードを含んだ検索対象シーケンスＳのサブシーケンスである。従って、素ワードＷｉの素ワード・マッチを伸長することは、検索要求ワードＷにおける素ワードＷｉと親節点を共有する兄弟節点Ｑｉ＾を探索することと等価である。最小マッチ性によれば、探索窓のサイズは｜Ｑｉ＾｜＋［Ｔ／ｋ］である。図５の例では、レベル２に対しては、Ｔ＝４，ｋ＝６である。従って、検索対象シーケンスＳにおけるワードＷ２のワードマッチを伸長する場合、探索窓は、検索対象シーケンスＳ内のワードＷ２の左側のサイズ｜Ｑ１｜＋［Ｔ／ｋ］の領域となる（図６参照）。
【００４７】
任意のレベルにおいて、全ての節点でマッチが検出されなかったときに、素ワード・マッチの伸長は終了する。
【００４８】
検索窓のサイズは、特に最低レベルにおいて、検索対象シーケンスＳに比べて極めて小さくなる。故に、窓内探索の過程は、距離閾値［Ｔ／ｋ］を与えることにより非常に高速に実行することができる。
【００４９】
レベルが上がるにつれて、探索窓のサイズは大きくなり、伸長において探索すべきシーケンスは、ワード二分木に従って連結した素ワードの連鎖に成長していく。素ワードの連鎖が伸長できない場合には、そのサブツリーが、予め決められた巡回順序に従って探索される。この過程の間、探索空間は小片に分解され、偽性候補は初期の段階で淘汰される。従って、探索過程の計算複雑性は低い値に保たれる。
【００５０】
〔１−４〕さらなる伸長過程
上記素ワード・マッチの伸長によって、相同性判定基準に合致する全ての局所シーケンスが索出された後、さらにできるだけ長いアラインメントとなるように、両サイドにさらに伸長することができないかチェックされる。このステージにおいては、従来方法と同じギャップのある伸長フェーズと同様の方法が使用されるが、本発明とは直接関係がないので説明は割愛する。
【００５１】
〔２〕本発明の構成
【００５２】
本発明に係る相同性検索装置の第１の構成は、所定の種類の文字又は記号の文字列からなる検索対象シーケンスを記憶する検索対象シーケンス記憶手段と、
前記検索対象シーケンス内の相同な文字列を検索するために検索条件として設定される文字列である検索要求ワードを記憶する検索要求ワード記憶手段と、
前記検索要求ワードを段階的に順次二分割してなる完全二分木又は不完全二分木であるワード二分木のデータを記憶するワード二分木テーブル記憶手段と、
前記検索要求ワードを分割して生成される素ワードを記憶する素ワード記憶手段と、
前記検索対象シーケンス内における前記素ワードに一致するマッチ部分文字列の位置を記憶する完全一致位置記憶手段と、
前記素ワード，前記検索要求ワード内における前記素ワードの位置，前記マッチ部分文字列，及び検索対象シーケンス内における前記マッチ部分文字列の位置を含む相同性索出データを記憶する相同テーブル記憶手段と、
２つの文字列が相同と判定するための許容編集距離の最大値である最大許容編集距離Ｔを入力手段により取得する最大許容編集距離設定手段と、
前記検索要求ワード記憶手段に記憶された前記検索要求ワードを（Ｔ＋１）個の前記素ワードに分割し、終端節点が（Ｔ＋１）個の前記各素ワードに対応する前記ワード二分木を生成し、前記ワード二分木テーブル記憶手段に前記ワード二分木テーブルとして格納するワード二分木生成手段と、
前記ワード二分木の各終端節点を順次選択し、選択した終端節点に対応する素ワードを前記素ワード記憶手段に格納する初期素ワード設定手段と、
前記素ワード記憶手段に記憶された前記素ワードに基づき、前記検索対象シーケンス内における当該素ワードと完全に一致するマッチ部分文字列の位置をすべて索出し、当該マッチ部分文字列の位置を完全一致位置記憶手段に格納するとともに、当該素ワード，当該素ワードの位置，当該マッチ部分文字列，及び当該マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納する完全一致検索手段と、
前記完全一致位置記憶手段に記憶された前記各マッチ部分文字列について、前記素ワード記憶手段に記憶された前記素ワードに対し、前記ワード二分木に従って、当該素ワードの節点に双対する節点に対応する部分ワードを当該素ワードに結合した伸長素ワード、及び前記伸長素ワードに対応する節点に双対する節点又はその子孫節点に対応する部分ワードを当該伸長ワードに結合した伸長素ワードを順次生成し、前記各伸長素ワードのうち、当該マッチ部分文字列を当該伸長素ワードと同方向に伸長した文字列である伸長マッチ部分文字列が当該伸長素ワードと相同な場合に、当該伸長素ワード，当該伸長素ワードの位置，当該伸長マッチ部分文字列，及び当該伸長マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納する素ワード伸長検索処理を行う素ワード伸長検索処理手段と、を備えたことを特徴とする。
【００５３】
この構成により、上述のワードベースの探索戦略に基づくアルゴリズムにより、検索対象シーケンスに対する検索要求ワードによる相同性探索を具体的に実行することが可能となり、最適化されたマッチを適応的に生成することが可能となる。
【００５４】
また、本発明に係る相同性検索装置の第２の構成は、前記第１の構成において、前記最大許容編集距離設定手段は、前記最大許容編集距離Ｔに１を加えた値を相同判定パラメータｋの初期値に設定するものであり、
前記素ワード伸長検索処理手段は、
前記素ワード伸長検索処理の開始時に、降下階数ｎｄを０に初期化するとともに、［ｋ／２］（［ ］はガウス記号）の値を前記相同判定パラメータｋの新たな値に更新する降下階数初期化手段と、
前記素ワード記憶手段に記憶された現在の前記素ワードに対応する前記ワード二分木の節点が、左側子節点の場合にはそれに双対する右側子節点から左枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定し、右側子節点の場合にはそれに双対する左側子節点から右枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定する結合候補節点設定手段と、
前記結合候補節点に対応する結合候補ワードを前記検索要求ワード記憶手段から読み出し、現在の前記素ワードに前記結合候補ワードを結合した結合ワードを前記伸長素ワードに設定する伸長素ワード設定手段と、
前記伸長素ワードに対応して、前記マッチ部分文字列を伸長した部分文字列を前記検索対象シーケンスから抽出し、比較対象シーケンスに設定する比較対象シーケンス抽出手段と、
前記比較対象シーケンスから前記伸長素ワードとの距離が最小となる前記伸長マッチ部分文字列を抽出し、当該伸長マッチ部分文字列と前記伸長素ワードとの距離である最小編集距離Ｌｃを算出する最小編集距離演算手段と、
前記最大許容編集距離Ｔと前記相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］（［ ］はガウス記号）に設定する編集距離閾値設定手段と、
前記最小編集距離Ｌｃと前記編集距離閾値Ｄｔｈとを比較し、Ｌｃ≦Ｄｔｈの場合には相同条件充足と判定し、前記伸長素ワード，前記伸長素ワードの位置，前記伸長マッチ部分文字列，及び前記伸長マッチ部分文字列の位置を前記相同性索出データとして前記相同テーブル記憶手段に格納する一方、Ｌｃ＞Ｄｔｈの場合には相同条件未充足と判定する相同条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードに対応する前記ワード二分木の節点の親節点が根節点であれば素ワード伸長検索処理を終了し、前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、最後に設定された前記結合候補節点が終端節点であれば素ワード伸長検索処理を終了する終了条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードを前記伸長素ワードに更新し前記素ワード記憶手段に格納するとともに、［ｋ／２］（［ ］はガウス記号）の値を前記相同判定パラメータｋの新たな値に更新する素ワード更新手段と、
前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、降下階数ｎｄを１だけ増加させる降下階数変更手段と、
前記終了条件判定手段により素ワード伸長検索処理が終了されるまで、前記結合候補節点設定手段、前記伸長素ワード設定手段、前記比較対象シーケンス抽出手段、前記最小編集距離演算手段、前記編集距離閾値設定手段、前記相同条件判定手段、前記終了条件判定手段、前記素ワード更新手段、及び前記降下階数変更手段による素ワード伸長検索処理を反復実行する制御を行う素ワード伸長検索処理制御手段と、を備えたことを特徴とする。
【００５５】
また、本発明に係る相同性検索装置の第３の構成は、前記第１又は２の構成において、前記検索対象シーケンスを構成する文字記号と同種の文字記号の文字列からなるクエリシーケンスを記憶するクエリシーケンス記憶手段と、
前記クエリシーケンスから前記クエリシーケンス内の所定の長さの部分文字列を切り出し、前記検索要求ワードとして前記検索要求ワード記憶手段に格納する検索要求ワード設定手段と、を備え、
前記要求ワード設定手段は、前記部分文字列の先頭位置を、前記クエリシーケンスの先頭から１文字ずつ移動させながら前記部分文字列を順次切り出し、前記検索要求ワード記憶手段に格納された前記検索要求ワードを逐次更新するものであり、
前記ワード二分木生成手段は、前記検索要求ワード記憶手段に格納された前記検索要求ワードが更新される毎に、前記ワード二分木を生成し、前記ワード二分木テーブルの更新を行うことを特徴とする。
【００５６】
また、本発明に係るプログラムは、コンピュータに読み込ませて実行させることにより、当該コンピュータを請求項１乃至３のいずれかの構成の相同性検索装置として動作させることを特徴とする。
【発明の効果】
【００５７】
上記本発明に係る相同性検索装置によれば、素ワード伸長検索処理の際に検索対象シーケンス内のマッチを探索する際の探索空間が極めて小さいため、高速で検索を行うことが可能となるとともに、特定のシード構造に依存せず適応的に構成されるワード（素ワード及び伸長素ワード）による検索が行われるため、ヒットの欠失を低く抑え、検索感度を向上左折ことが可能となる。
【図面の簡単な説明】
【００５８】
【図１】本発明の実施例１に係る相同性検索装置１の全体構成を表すブロック図である。
【図２】図１の検索実行部１９の構成を表すブロック図である。
【図３】図２の素ワード伸長検索処理部の構成を表すブロック図である。
【図４】検索対象シーケンスＳ及びクエリシーケンスＱのデータ構造、並びにクエリシーケンスＱと検索要求ワードＷとの関係を表す図である。
【図５】ワード二分木のデータ構造を表す図である。
【図６】比較対象シーケンス抽出部３３が検索対象シーケンスから抽出する比較対象シーケンスの一例を表す図である。
【図７】本発明の実施例１に係る相同性検索装置１の動作の全体の流れを表すＰＡＤ（Problem Analysis Diagram）図である。
【図８】図７の二分木相同性検索処理サブルーチンの処理の流れを表すＰＡＤ図である。
【図９】図８の素ワード伸長検索処理サブルーチンの処理の流れを表すＰＡＤ図である。
【発明を実施するための形態】
【００５９】
以下、本発明を実施するための形態について、図面を参照しながら説明する。
【実施例１】
【００６０】
図１は、本発明の実施例１に係る相同性検索装置の全体構成を表すブロック図である。本実施例の相同性探索装置１は、入力装置２から入力されるクエリシーケンスＱと相同性判定の際の最大許容編集距離Ｔに基づいて、シーケンスデータベース３に格納された検索対象シーケンスＳと当該クエリシーケンスＱとの相同性検索を行い、その索出結果を出力装置４に出力するものである。入力装置２としては、キーボードやマウス、ディスクドライブ等の通常のコンピュータの入力装置が使用される。また、出力装置４としては、ディスプレイや外部記憶装置等の通常のコンピュータの出力装置が使用される。シーケンスデータベース３は、ハードディスクドライブ等の大容量記憶装置が使用される。
【００６１】
本実施例の相同性探索装置１は、検索対象シーケンス選択部１０、検索対象シーケンス記憶部１１、クエリシーケンス入力部１２、クエリシーケンス記憶部１３、検索要求ワード設定部１４、検索要求ワード記憶部１５、ワード二分木生成部１６、ワード二分木テーブル記憶部１７、最大許容編集距離設定部１８、検索実行部１９、及び相同テーブル記憶部２０を備えている。これらの機能構成は、専用回路として構成してもよいが、コンピュータ・プログラムとして提供し、当該プログラムをコンピュータにロードして実行することにより機能的に構成されるようにしてもよい。
【００６２】
シーケンスデータベース３には、複数の検索対象シーケンスＳが記憶されている。ここで、「検索対象シーケンス」とは、所定の種類の文字又は記号の文字列からなるシーケンスであり、核酸の塩基配列（核酸を構成する塩基を表す「Ａ」，「Ｃ」，「Ｇ」，「Ｔ」の文字及びドント・ケア（欠失部分）を表す記号「−」からなる配列）やタンパク質のアミノ酸配列（アミノ酸を表す２０種類の文字「Ａ」，「Ｃ」，「Ｄ」，「Ｅ」，「Ｆ」，「Ｇ」，「Ｈ」，「Ｉ」，「Ｋ」，「Ｌ」，「Ｍ」，「Ｎ」，「Ｐ」，「Ｑ」，「Ｒ」，「Ｓ」，「Ｔ」，「Ｖ」，「Ｗ」，「Ｙ」及びドント・ケアを表す記号「−」からなる配列）等が想定されている。
【００６３】
検索対象シーケンス選択部１０は、シーケンスデータベース３から、相同性検索に使用する検索対象シーケンスＳを選択して読み出し、検索対象シーケンス記憶部１１に格納する。検索対象シーケンス記憶部１１は、この検索対象シーケンスＳを記憶する。
【００６４】
図４（ａ），（ｂ）に、検索対象シーケンスＳ及びクエリシーケンスＱのデータ構造を示す。検索対象シーケンスＳはＮｓ個の文字配列から構成され、クエリシーケンスＱはＮｑ個の文字配列から構成されている。核酸やタンパク質のシーケンスの場合、Ｎｓ，Ｎｑは通常非常に大きな値となる。
【００６５】
最大許容編集距離設定部１８は、２つの文字列が相同であると判定するための許容される２つの文字列間の編集距離の最大値である最大許容編集距離Ｔを入力手段から取得する。また、最大許容編集距離Ｔに１を加えた値を相同判定パラメータｋの初期値に設定する。「相同判定パラメータ」とは、検索対象の文字列と素ワードとの相同性を判定するための編集距離閾値Ｄｔｈを算出するパラメータであり、最大許容編集距離Ｔと編集距離閾値Ｄｔｈと相同判定パラメータｋとはＤｔｈ＝［Ｔ／ｋ］の関係にある。
【００６６】
クエリシーケンス入力部１２は、ユーザが入力装置２から入力するクエリシーケンスＱを取得して、クエリシーケンス記憶部１３に格納する。クエリシーケンス記憶部１３は、このクエリシーケンスＱを記憶する。ここで、「クエリシーケンス」は、前記検索対象シーケンスと同種の文字又は記号の配列からなるシーケンスである。
【００６７】
検索要求ワード設定部１４は、クエリシーケンス記憶部１３に記憶されたクエリシーケンスＱから、当該クエリシーケンスＱ内の所定の長さＬの部分文字列を切り出し、検索要求ワードＷとして検索要求ワード記憶部１５に格納する。検索要求ワード記憶部１５は、当該検索要求ワードＷを一時的に記憶する。
【００６８】
図４（ｃ）に、クエリシーケンスＱと検索要求ワードＷとの関係を示す。検索要求ワード設定部１４は、検索要求ワードＷの先頭位置を、クエリシーケンスＱの先頭から末尾方向に、１文字ずつずらしながら長さＬの検索要求ワードＷを順次切り出して、検索要求ワード記憶部１５に格納する。従って、この切り出しの全回数をＮｗ回とすると、Ｎｗ＝Ｎｑ−Ｌ＋１となる。
【００６９】
ワード二分木生成部１６は、検索要求ワード記憶部１５に検索要求ワードＷが設定されると、その検索要求ワードＷに基づき、終端節点の数が（Ｔ＋１）個のワード二分木を生成し、ワード二分木テーブル記憶部１７にワード二分木テーブルとして格納する。ワード二分木テーブル記憶部１７は、当該ワード二分木テーブルを記憶する。
【００７０】
ここで、ワード二分木については既に説明したが、ワード二分木は、例えば、図５に示したようなデータ構造を有する。ワード二分木の終端節点は、検索要求ワードＷを（Ｔ＋１）個に分割した素ワードＷｉ（ｉ＝１，…，Ｔ＋１）に対応する。検索要求ワードＷの長さＬが（Ｔ＋１）で割り切れる場合には、すべての素ワードＷｉの長さは等しくなり、｜Ｗｉ｜＝Ｌ／（Ｔ＋１）となる。一方、Ｌが（Ｔ＋１）で割り切れない場合、素ワードＷ１〜ＷＴまでは同じ長さ［Ｌ／（Ｔ＋１）］とし、ＷＴの長さは余りのＬ−Ｔ（［Ｌ／（Ｔ＋１）］）とする。ここで、［ ］はガウス記号を表す（以下同じ）。また、ワード二分木の根節点は、検索要求ワードＷそのものに対応する。ワード二分木は、終端節点から構成してゆき、最も左側の節点から、隣接する２つの節点のペアを作り、それらの節点ペアの共通の親節点を生成するという処理を繰り返すことにより容易に構成することができる。尚、最も右側の終端節点だけは、ペアの相手がない場合（すなわち、終端節点の数が奇数の場合）には単独の節点とし、その親節点を１つ生成すればよい（図５参照）。
【００７１】
ワード二分木テーブルは、上述のようなデータ構造のワード二分木の情報を格納するテーブルであり、例えば、図５のワード二分木を格納するワード二分木テーブルは、表１のようになる。
【００７２】
【表１】
【００７３】
表１において、「節点名」フィールドには、図５の各節点に付されたラベルが格納される。「位置ｐｏｓ」フィールドには、各節点に対応するセグメントの検索要求ワードＷ内における位置が格納され、具体的には、各節点に対応するワードの先頭位置のポインタが格納される。「ワード長ｌ」フィールドには、それぞれのセグメントの長さ、「階層Ｌｅｖ」フィールドには節点の階層（レベル）、「親節点ｐparent」フィールドには各節点の親節点のラベル、「左子節点ｐｌｅｆｔ」フィールドには各節点から出る左枝に接続する子節点のラベル、「右子節点ｐｒｉｇｈｔ」フィールドには各節点から出る右枝に接続する子節点のラベルがそれぞれ格納される。
【００７４】
検索実行部１９は、上記ワード二分木に基づき、検索対象シーケンスＳと検索要求ワードＷとの相同性検索を行い、その結果索出される相同性索出データを相同テーブル記憶部２０に相同テーブルとして格納する。相同テーブル記憶部２０は、当該相同テーブルを記憶する。
【００７５】
ここで、相同テーブルは、表２に示すような構造のデータテーブルである。
【００７６】
【表２】
【００７７】
表２において、「検索要求ワード位置」フィールドには、検索要求ワードＷの先頭位置の、クエリシーケンスＱの先頭位置からのシフト量（すなわち、クエリシーケンスＱ内の検索要求ワードＷの位置）が格納される（図４（ｃ）参照）。「素ワード」フィールドには、検索対象シーケンスＳ内のサブシーケンスにマッチした素ワードのシーケンスが格納される。「マッチ位置」フィールドには、マッチした素ワードの先頭文字の検索要求ワードＷ内における位置が格納される。「相同シーケンス」フィールドには、前記サブシーケンスと相同と判定された検索対象シーケンスＳ内のサブシーケンスが格納される。また、「相同シーケンス位置」フィールドには、前記サブシーケンスの先頭文字の検索対象シーケンスＳ内における位置が格納される。
【００７８】
次に、図１の検索実行部１９の構成について説明する。図２は、検索実行部１９の構成を表すブロック図である。
【００７９】
検索実行部１９は、クエリ素ワード設定部２５、素ワード記憶部２６、完全一致検索部２７、完全一致位置記憶部２８、及び素ワード伸長検索処理部２９を備えている。
【００８０】
クエリ素ワード設定部２５は、ワード二分木テーブル記憶部１７に格納されているワード二分木の各終端節点を左側から順次選択し、選択した終端節点に対する文字列Ｗｉ（ｉ＝１，…，Ｔ＋１）を初期の素ワードＷprimeとして素ワード記憶部２６に格納する。素ワード記憶部２６は、当該素ワードＷprimeを記憶し保持する。
【００８１】
完全一致検索部２７は、素ワード記憶部２６に記憶されている素ワードＷprimeに基づき、検索対象シーケンスＳ内における当該素ワードＷprimeと完全に一致するマッチ部分文字列Ｓexactの位置ｐmatchをすべて索出し、当該マッチ部分文字列の位置ｐmatchを完全一致位置記憶部２８に格納するとともに、｛検索要求ワードＷの位置，当該素ワードＷprime，当該素ワードＷprimeの位置，当該マッチ部分文字列Ｓexact，当該マッチ部分文字列Ｓexactの位置ｐmatch｝を相同性索出データとして相同テーブル記憶部２０に格納する。完全一致位置記憶部２８は、前記マッチ部分文字列の位置を記憶し保持する。
【００８２】
素ワード伸長検索処理部２９は、完全一致位置記憶部２８に記憶された各マッチ部分文字列について、素ワード記憶部２６に記憶された素ワードＷprimeに対し後述の素ワード伸長検索処理を行うとともに、素ワード伸長検索処理により伸長される伸長素ワードＷexpandのうち、当該マッチ部分文字列Ｓexactの位置にある当該伸長素ワードＷexpandに対応する文字列である伸長マッチ部分文字列Ｓmatchが当該伸長素ワードＷexpandと相同な場合に、｛検索要求ワードＷの位置，当該伸長素ワードＷexpand，当該伸長素ワードＷexpandの位置，当該伸長マッチ部分文字列Ｓmatch，当該伸長マッチ部分文字列Ｓmatchの位置｝を相同性索出データとして相同テーブル記憶部２０に格納する。
【００８３】
次に、図２の素ワード伸長検索処理部２９の構成について説明する。図３は、図２の素ワード伸長検索処理部の構成を表すブロック図である。
【００８４】
素ワード伸長検索処理部２９は、降下階数初期化部３０、結合候補節点設定部３１、伸長素ワード設定部３２、比較対象シーケンス抽出部３３、最小編集距離演算部３４、編集距離閾値設定部３５、相同条件判定部３６、終了条件判定部３７、素ワード更新部３８、降下階数変更部３９、及び素ワード伸長検索処理制御部４０を備えている。
【００８５】
降下階数初期化部３０は、素ワード伸長検索処理の開始時に、降下階数ｎｄを０に初期化するとともに、［ｋ／２］の値を相同判定パラメータｋの新たな値に更新する。
【００８６】
結合候補節点設定部３１は、素ワード記憶部２６に記憶された現在の素ワードに対応するワード二分木の節点が、左側子節点の場合にはそれに双対する右側子節点から左枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点ｐcombに設定し、右側子節点の場合にはそれに双対する左側子節点から右枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点ｐcombに設定する。
【００８７】
伸長素ワード設定部３２は、結合候補節点ｐcombに対応する結合候補ワードＷcombを検索要求ワード記憶部１５から読み出し、現在の素ワードＷprimeに結合候補ワードＷcombを結合した結合ワードを伸長素ワードＷexpandに設定する。
【００８８】
比較対象シーケンス抽出部３３は、伸長素ワードＷexpandに対応して、マッチ部分文字列Ｓexactを伸長した部分文字列を検索対象シーケンスＳから抽出し、比較対象シーケンスに設定する。
【００８９】
最小編集距離演算部３４は、比較対象シーケンスＳ１から伸長素ワードＷexpandとの編集距離が最小となる伸長マッチ部分文字列Ｓmatchを抽出し、当該伸長マッチ部分文字列Ｓmatchと伸長素ワードＷexpandとの編集距離である最小編集距離Ｌｃを出力する。
【００９０】
編集距離閾値設定部３５は、最大許容編集距離Ｔと相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］に設定する。
【００９１】
相同条件判定部３６は、最小編集距離Ｌｃと編集距離閾値Ｄｔｈとを比較し、Ｌｃ≦Ｄｔｈの場合には相同条件充足と判定し、｛検索要求ワードＷの位置，伸長素ワードＷexpand，伸長素ワードの位置，伸長マッチ部分文字列Ｓmatch，伸長マッチ部分文字列の位置｝を相同性索出データとして相同テーブル記憶部に格納する一方、Ｌｃ＞Ｄｔｈの場合には相同条件未充足と判定する。
【００９２】
終了条件判定部３７は、相同条件判定部３６が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の素ワードＷprimeに対応するワード二分木の節点の親節点が根節点であれば素ワード伸長検索処理を終了し、相同条件判定部３６が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、最後に設定された結合候補節点が終端節点であれば素ワード伸長検索処理を終了する。
【００９３】
素ワード更新部３８は、相同条件判定部３６が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の素ワードを伸長素ワードに更新し素ワード記憶部２６に格納するとともに、［ｋ／２］の値を相同判定パラメータｋの新たな値に更新する。
【００９４】
降下階数変更部３９は、相同条件判定部３６が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、降下階数ｎｄを１だけ増加させる。
【００９５】
素ワード伸長検索処理制御部４０は、終了条件判定部３７により素ワード伸長検索処理が終了されるまで、結合候補節点設定部３１、伸長素ワード設定部３２、比較対象シーケンス抽出部３３、最小編集距離演算部３４、編集距離閾値設定部３５、相同条件判定部３６、終了条件判定部３７、素ワード更新部３８、及び降下階数変更部３９による素ワード伸長検索処理を反復実行する制御を行う。
【００９６】
以上のように構成された本発明の実施例１に係る相同性検索装置について、以下その動作を説明する。
【００９７】
図７は、本発明の実施例１に係る相同性検索装置１の動作の全体の流れを表すＰＡＤ（Problem Analysis Diagram）図である。
【００９８】
まず、ステップＳ１において、ユーザにより入力手段から最大許容編集距離Ｔ、ワード長Ｌ、及びクエリシーケンスＱが入力される。最大許容編集距離設定部１８は、入力された最大許容編集距離Ｔを保持する。検索要求ワード設定部１４は、入力されたワード長Ｌを保持する。また、クエリシーケンス入力部１２は、入力されたクエリシーケンスＱを、クエリシーケンス記憶部１３に保存する。
【００９９】
また、検索対象シーケンス選択部１０は、シーケンスデータベース３から１つの検索対象シーケンスＳを選択して読み出し、検索対象シーケンス記憶部１１に保存する。
【０１００】
次に、ステップＳ２において、最大許容編集距離設定部１８は、相同判定パラメータｋの値をＴ＋１に初期化する。
【０１０１】
次に、ステップＳ３において、検索要求ワード設定部１４がシフト量を表す内部変数ｉを０からＮｗ−１まで１ずつ増加させながら、以下のステップＳ４〜Ｓ６の処理が反復実行される。
【０１０２】
次に、ステップＳ４において、検索要求ワード設定部１４は、図４（ｃ）に示したように、切り出し位置をクエリシーケンスＱの先頭からｉ文字シフトさせ、クエリシーケンスＱの当該切り出し位置から長さＬの部分文字列を切り出し、これを検索要求ワードＷとして検索要求ワード記憶部１５に格納する。
【０１０３】
次に、ステップＳ５において、ワード二分木生成部１６は、検索要求ワード記憶部１５に記憶された検索要求ワードＷに基づき、終端節点の数が（Ｔ＋１）個の図５に示したようなワード二分木を生成し、ワード二分木テーブル記憶部１７に表１のようなワード二分木テーブルとして格納する。
【０１０４】
次に、ステップＳ６において、ワード二分木テーブル記憶部１７に格納されたワード二分木に基づいて、検索実行部１９による二分木相同性探索処理が行われる。
【０１０５】
以上のステップＳ４〜Ｓ６の処理がＮｗ回反復実行された後、相同性探索装置１は相同性検索を終了する。相同性検索による相同性索出データは、二分木相同性探索処理により相同テーブル記憶部２０に蓄積されるので、これらの結果を出力装置４に出力すればよい。
【０１０６】
次に、上記ステップＳ６における二分木相同性探索処理について説明する。図８は、図７の二分木相同性検索処理サブルーチンの処理の流れを表すＰＡＤ図である。
【０１０７】
まず、ステップＳ１１において、クエリ素ワード設定部２５は、選択する終端節点のインデックスを表す内部変数ｊを１からＴ−１まで１ずつ増加させながら、以下のステップＳ１２〜Ｓ１７の処理を反復実行する。
【０１０８】
ステップＳ１２において、クエリ素ワード設定部２５は、ワード二分木テーブル記憶部１７に格納されたワード二分木テーブルを参照し、左からｊ番目の終端節点に対応するワードＷｊを検索要求ワード記憶部１５から読み出して、初期の素ワードＷprimeとして素ワード記憶部２６に格納する。
【０１０９】
次に、ステップＳ１３において、完全一致検索部２７は、素ワード記憶部２６に記憶された素ワードＷprimeに基づき、検索対象シーケンスＳ内における当該素ワードＷprimeと完全に一致するマッチ部分文字列Ｗexactの位置ｐmatchをすべて索出し、当該マッチ部分文字列の位置ｐmatchを完全一致位置記憶部２８に格納する。ここで、索出されたマッチ部分文字列の数をＮmatchとし、各マッチ部分文字列の位置をｐmatch（ξ）（ξ＝１，…，Ｎmatch）と記す。
【０１１０】
次に、ステップＳ１４において、Ｎmatch＞０（完全マッチが存在する）の場合、完全一致検索部２７は、マッチ部分文字列のインデックスξを１からＮmatchまで１ずつ増加させながら、以下のステップＳ１５〜Ｓ１７の処理を反復実行する。
【０１１１】
ステップＳ１５において、完全一致検索部２７は、ξ番目のマッチ部分文字列ｐmatch（ξ）に対して、｛検索要求ワードＷの位置，素ワードＷprime，素ワードの位置，マッチ部分文字列，マッチ部分文字列の位置ｐmatch（ξ）｝を相同性索出データとして相同テーブル記憶部２０に格納する。
【０１１２】
次に、ステップＳ１６において、降下階数初期化部３０は、内部変数である降下階数ｎdownを０に初期化するとともに、［ｋ／２］の値を相同判定パラメータｋの新たな値として更新する。
【０１１３】
最後に、ステップＳ１７において、｛マッチ部分文字列の位置ｐmatch（ξ），現在の素ワードＷ，現在選択されている終端節点のレベルＬｅｖ＝１，現在選択されている終端節点の親節点ｐparent，現在選択されている終端節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown＝０｝を入力値として、後述の素ワード伸長検索処理部２９による素ワード伸長検索処理素素ワード伸長検索処理が実行される。
【０１１４】
図９は、図８の素ワード伸長検索処理サブルーチンの処理の流れを表すＰＡＤ図である。この素ワード伸長検索処理サブルーチンでは、再帰処理が用いられている。なお、この素ワード伸長検索処理サブルーチンは、入力値として、｛マッチ部分文字列の位置ｐmatch，現在の素ワードＷprime，現在選択されている節点のレベルＬｅｖ，現在選択されている節点の親節点ｐparent，現在選択されている節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝をとるものとする。
【０１１５】
まず、ステップＳ２１において、編集距離閾値設定部３５は、最大許容編集距離Ｔと現在の相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］に設定する。
【０１１６】
次に、ステップＳ２２において、結合候補節点設定部３１は、入力されたサイドＳｉｄｅを参照して、現在選択されている節点が、その親節点に対し左側子節点か右側子節点かを判定する。
【０１１７】
左側子節点と判定された場合、ステップＳ２３において、結合候補節点設定部３１は、現在選択されている節点の親節点ｐparentの右側子節点を指定節点に設定し、ステップＳ２４において、結合候補節点設定部３１は、当該指定節点から左側枝を辿りながらｎdown階降下した節点を結合候補節点ｐcombに設定する。次いで、ステップＳ２５において、伸長素ワード設定部３２は、結合候補節点ｐcombに対応するワード（結合候補ワード）Ｗcombを素ワード記憶部２６から読み出して、現在の素ワードＷprimeの右側に当該結合候補ワードＷcombを結合した結合ワードを生成し、これを伸長素ワードＷexpandに設定する。そして、ステップＳ２６において、比較対象シーケンス抽出部３３は、探索窓幅を｜Ｗcomb｜＋Ｄｔｈとして、検索対象シーケンスＳのマッチ部分文字列Ｗexactの位置ｐmatchから長さ｜Ｗexpand｜＋Ｄｔｈ（＝｜Ｗprime｜＋｜Ｗcomb｜＋Ｄｔｈ）のシーケンスを抽出し、これを比較対象シーケンスＳ１に設定する。
【０１１８】
一方、ステップＳ２２において右側子節点と判定された場合、ステップＳ２７において、結合候補節点設定部３１は、現在選択されている節点の親節点ｐparentの左側子節点を指定節点に設定し、ステップＳ２８において、結合候補節点設定部３１は、当該指定節点から右側枝を辿りながらｎdown階降下した節点を結合候補節点ｐcombに設定する。次いで、ステップＳ２９において、伸長素ワード設定部３２は、結合候補節点ｐcombに対応するワード（結合候補ワード）Ｗcombを素ワード記憶部２６から読み出して、現在の素ワードＷprimeの左側に当該結合候補ワードＷcombを結合した結合ワードを生成し、これを伸長素ワードＷexpandに設定する。そして、ステップＳ３０において、比較対象シーケンス抽出部３３は、探索窓幅を｜Ｗcomb｜＋Ｄｔｈとして、検索対象シーケンスＳのマッチ部分文字列の位置ｐmatchに対し｜Ｗcomb｜＋Ｄｔｈだけ左（先頭側）にシフトした位置ｐｔｏｐ＝ｐmatch−（｜Ｗcomb｜＋Ｄｔｈ）から、長さ｜Ｗexpand｜＋Ｄｔｈ（＝｜Ｗprime｜＋｜Ｗcomb｜＋Ｄｔｈ）のシーケンスを抽出し、これを比較対象シーケンスＳ１に設定する。
【０１１９】
次に、ステップＳ３１において、最小編集距離演算部３４は、比較対象シーケンスＳ１から伸長素ワードＷexpandとの編集距離が最小となる伸長マッチ部分文字列Ｓmatchを抽出し、当該伸長マッチ部分文字列Ｓmatchと伸長素ワードＷexpandとの距離である最小編集距離Ｌｃを算出する。
【０１２０】
次に、ステップＳ３２において、相同条件判定部３６は、最小編集距離Ｌｃと編集距離閾値Ｄｔｈとを比較し、ＬｃがＤｔｈ以下であるか否かを判定する。
【０１２１】
ここで、Ｌｃ≦Ｄｔｈの場合、相同条件判定部３６は、伸長素ワードＷexpandと伸長マッチ部分文字列Ｓmatchとが相同性条件を充足する（相同性条件充足）と判定し、ステップＳ３３において、マッチ部分文字列の位置ｐmatchを伸長マッチ部分文字列Ｓmatchの先頭位置に更新した後、ステップＳ３４において、｛検索要求ワードＷの位置，伸長素ワードＷexpand，伸長素ワードＷexpandの位置ｐexpand，伸長マッチ部分文字列Ｓmatch，伸長マッチ部分文字列Ｓmatchの位置ｐmatch｝を相同性索出データとして相同テーブル記憶部２０に格納する。
【０１２２】
次いで、ステップＳ３５において、終了条件判定部３７は、現在の降下階数ｎdownが０か否かを判定する。
【０１２３】
ｎdown＝０の場合は、ステップＳ３６において、終了条件判定部３７は、現在の節点のレベルＬｅｖが根節点のレベルＬｅｖｍａｘよりも小さいか否かを判定する。ここで、Ｌｅｖ＝Ｌｅｖｍａｘならば、終了条件判定部３７は素ワード伸長検索処理を終了する。一方、Ｌｅｖ＜Ｌｅｖｍａｘならば、ステップＳ３７において、素ワード更新部３８は、素ワードＷを伸長素ワードＷexpandに更新し素ワード記憶部２６に格納するとともに、ステップＳ３８において、［ｋ／２］の値を相同判定パラメータｋの新たな値としてｋを更新する。そして、ステップＳ３９において、素ワード伸長検索処理制御部４０は、｛伸長マッチ部分文字列の位置ｐmatch，現在の素ワードＷ，現在選択されている節点の親節点のレベルＬｅｖ＋１，現在選択されている節点の祖父節点ｐgrand，現在選択されている節点の親節点の祖父節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝を入力値として、素ワード伸長検索処理部２９による素ワード伸長検索処理を再帰的に実行する。
【０１２４】
ステップＳ３５においてｎdown＞０の場合は、ステップＳ４０において、終了条件判定部３７は、現在の節点のレベルＬｅｖから降下階数ｎdownを引いた値Ｌｅｖ−ｎdownが１より大きい（すなわち、最後に設定された結合候補節点ｐcombが終端節点でない）か否かを判定する。ここで、Ｌｅｖ−ｎdown＝１ならば、終了条件判定部３７は素ワード伸長検索処理を終了する。一方、Ｌｅｖ−ｎdown＞１ならば、ステップＳ４１において、降下階数変更部３９は、降下階数ｎｄを１だけ増加させる。そして、ステップＳ４２において、素ワード伸長検索処理制御部４０は、｛伸長マッチ部分文字列の位置ｐmatch，現在の素ワードＷprime，現在選択されている節点のレベルＬｅｖ，現在選択されている節点の親節点ｐparent，現在選択されている節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝を入力値として、素ワード伸長検索処理部２９による素ワード伸長検索処理を再帰的に実行する。
【０１２５】
ステップＳ３２においてＬｃ＞Ｄｔｈの場合、相同条件判定部３６は、相同条件未充足と判定し、ステップＳ４３において、終了条件判定部３７は、現在の節点のレベルＬｅｖから降下階数ｎdownを引いた値Ｌｅｖ−ｎdownが１より大きい（すなわち、最後に設定された結合候補節点ｐcombが終端節点でない）か否かを判定する。ここで、Ｌｅｖ−ｎdown＝１ならば、終了条件判定部３７は素ワード伸長検索処理を終了する。一方、Ｌｅｖ−ｎdown＞１ならば、ステップＳ４４において、降下階数変更部３９は、降下階数ｎｄを１だけ増加させる。そして、ステップＳ３９において、素ワード伸長検索処理制御部４０は、｛伸長マッチ部分文字列の位置ｐmatch，現在の素ワードＷprime，現在選択されている節点のレベルＬｅｖ，現在選択されている節点の親節点ｐparent，現在選択されている節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝を入力値として、素ワード伸長検索処理部２９による素ワード伸長検索処理を再帰的に実行する。
【０１２６】
以上の一連の処理によって、素ワード伸長検索処理が実行され、伸長された素ワードによるすべてのマッチの相同性索出データが相同テーブル記憶部２０に蓄積される。
【符号の説明】
【０１２７】
１ 相同性探索装置
２ 入力装置
３ シーケンスデータベース
４ 出力装置
１０ 検索対象シーケンス選択部
１１ 検索対象シーケンス記憶部
１２ クエリシーケンス入力部
１３ クエリシーケンス記憶部
１４ 検索要求ワード設定部
１５ 検索要求ワード記憶部
１６ ワード二分木生成部
１７ ワード二分木テーブル記憶部
１８ 最大許容編集距離設定部
１９ 検索実行部
２０ 相同テーブル記憶部
２５ クエリ素ワード設定部
２６ 素ワード記憶部
２７ 完全一致検索部
２８ 完全一致位置記憶部
２９ 素ワード伸長検索処理部
３０ 降下階数初期化部
３１ 結合候補節点設定部
３２ 伸長素ワード設定部
３３ 比較対象シーケンス抽出部
３４ 最小編集距離演算部
３５ 編集距離閾値設定部
３６ 相同条件判定部
３７ 終了条件判定部
３８ 素ワード更新部
３９ 降下階数変更部
４０ 素ワード伸長検索処理制御部
【技術分野】
【０００１】
本発明は、核酸の塩基配列やタンパク質のアミノ酸配列のように所定の種類の文字又は記号の文字列からなるシーケンスについて、２つのシーケンスの相同性を検索するための相同性検索技術に関する。
【背景技術】
【０００２】
「相同性（homology）」とは、共通の祖先からの進化的関係に由来して、異なる有機体間で構造が対応することをいう。生物情報科学においては、「相同」は、異なるシーケンス（タンパク質又は核酸の塩基配列）間の類似するセグメントによって表される。相同性検索は、このような類似性を探索し、対応するマッチ（match）の位置決めを行うための計算プロセスである。これは、生物情報科学においては、様々な調査・研究の基礎となる基本的な問題である。
【０００３】
シーケンスの類似性は、２つのシーケンス間の編集距離（edit distance）によって定義することができる。多くの場合、編集距離としては、レーベンシュタイン距離（Levenshtein distance）が用いられる。２つのシーケンス間の編集距離とは、一方のシーケンスを他方のシーケンスに変換する基本操作の最小数をいう。「基本操作」とは、挿入（insert）、欠失（deletion）、及び置換（substitution）である。この定義によれば、編集距離が小さいほど、類似性が高くなる。
【０００４】
レーベンシュタイン距離は、最初に非特許文献１において生物情報科学に導入され、非特許文献２において、局所配列に拡張された。このレーベンシュタイン距離は、動的計画法によって正確に計算することが可能である（非特許文献３，ｐｐ．１８−２８参照）。これらの動的計画法の基本アルゴリズムは、相同性検索にも使用することができ、最適な検出感度を維持することができる。
【０００５】
しかしながら、動的計画法の計算複雑性はＯ（ｎｍ）である（非特許文献３，ｐ．２８，３１，３４参照）。ここで、ｎ，ｍは、それぞれのシーケンスの長さである。このように、動的計画法は計算量が多く速度が遅いため、調査すべきシーケンスデータの量が膨大化するに従って、相同性検索問題の大部分に適用することができなくなった。
【０００６】
そのため、多少の検出感度の低下（すなわち、多少のマッチの欠失）と引き替えに、より高速化する方向で、発見的アプローチが発展してきた。発見的アプローチでは、シードを基礎とするアプローチ（シードベースアプローチ）が主流である。このシードベースアプローチでは、低くても十分な感度を維持しつつ検索速度を極めて高速化するために提案されたフィルタ原理に基づき、動的計画法のプロセスの近似値を求める。
【０００７】
シードは、「１１１００１０１」のような２進列で表される。ここで、「１」は正確にマッチする位置を表し、「０」はマッチ条件を満たさない位置を表す。シードパターンに一致する、クエリシーケンス及び検索対象シーケンス間の部分シーケンスのマッチは「ヒット（hit）」と呼ばれる。
【０００８】
このシードベースアプローチでは、次のようなステップを含む戦略が用いられる。
（１）クエリシーケンスから、シードの長さと等しい長さの部分シーケンスをすべてリストアップする。
（２）クエリシーケンスと検索対象シーケンスとの間で、上記部分シーケンスのすべてのヒットを索出する。
（３）近似マッチングによりヒットを伸長する。この伸長は、類似性スコア（例えば、非特許文献３，ｐｐ．２８−３１参照）が、ユーザにより予め決められた検索要求まで減少した時点で終了する。
【０００９】
現在、最も広く使用されているこの種のアルゴリズムは、ＢＬＡＳＴ（非特許文献４参照）であり、これは連続的な完全一致のシードパターンを使用している。一方、ＢＬＡＳＴの性能と柔軟性を向上させるため、多くの取り組みがなされており、同様のアイデアを用いた相同性検索の様々なバージョンが考案されている（非特許文献５−９参照）。
【００１０】
また、「０」を含んだ分隔シード（spaced prime）は、非特許文献１０において最初に提案された。非特許文献１０において、分隔シードにより作られる近似マッチにより生成されるヒットは、感度と速度の間のバランスがよいことが示された。シードにおける「１」の数は「シードの重み（prime weight）」と呼ばれる。その後、非特許文献１１−１３等のように、多くのシード最適化法が開発された。
【００１１】
他方、非特許文献１４−１７では、単一シードパターンの代わりに、１組の最適化された多重シード（multiple prime）を使用する方法が導入されている。これらのアプローチでは、様々な統計的又は実証的方法に基づいて、複数のシードパターンの評価が行われている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２０００−１９４７１３号公報
【特許文献２】特開２００２−２２９９９８号公報
【特許文献３】特開２００９−１１６５５９号公報
【特許文献４】特開２００５−８４８５９号公報
【特許文献５】特表２００２−５２９８１７号公報
【特許文献６】特表２０００−５００８９６号公報
【非特許文献】
【００１３】
【非特許文献１】Needleman, Saul B.; Wunsch, Christian D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology 1970, 48 (3): 443-53.
【非特許文献２】Smith, Temple F.; Waterman, Michael S. Identification of Common Molecular Subsequences. Journal of Molecular Biology 1981, 147: 195-197.
【非特許文献３】阿久津達也，「アルゴリズム・サイエンスシリーズ１２ バイオインフォマティクスの数理とアルゴリズム」，初版，共立出版株式会社，２００７年２月．
【非特許文献４】Altschul, S.F.; Gish, W.; Miller, W.; Myers, E.W.; Lipman, D.J.: Basic local alignment search tool. J Mol Biol 1990, 215 (3): 403-410.
【非特許文献５】Altschul, S.F.; Madden, T.L.; Schaffer, A.A.; Zhang, J.; Zhang, Z.; Miller, W.; and Lipman, D.J. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. Nucleic Acids Res. 1997 25: 3389-3402
【非特許文献６】Gish, W. and States, D.J. Identification of protein coding regions by database similarity search. Nat. Genet. 1993 3: 266-272.
【非特許文献７】Gotoh, O. Homology-based gene structure prediction: Simplified matching algorithm using a translated codon (tron) and improved accuracy by allowing for long gaps. Bioinformatics 2000 16: 190-202.
【非特許文献８】Zhang, Z.; Schwartz, S.; Wagner, L.; and Miller, W. A greedy algorithm for aligning DNA sequences. J. Comput. Biol. 2000 7: 203-214.
【非特許文献９】Kent, W. J. BLAT-the BLAST-Like Alignment Tool. Genome Res. 2002, 12:656-664.
【非特許文献１０】Ma, B.; Tromp, J.; Li, M.: PatternHunter: faster and more sensitive homology search. Bioinformatics. 2002, 18:440-445.
【非特許文献１１】B. Brejova, D. Brown, and T. Vinar, Optimal spaced primes for homologous coding regions. J. Bioinf. And Comp. Biol. 1(2004), pp. 595-610.
【非特許文献１２】J. Buhler, U. Keich, and Y. Sun, Designing primes for similarity search in genomic DNA. Proc. 7th Annual Int'l Conf. on Comput. Mol. Biol. (RECOMB'03), pp. 67-75, Berlin, Germany.
【非特許文献１３】K.P. Choi, and L. Zhang, Sensitivity analysis and efficient method for identifying optimal spaced primes, J. Comput. Sys. Sci., 68(2004), pp. 22-40.
【非特許文献１４】Sun, Y.; Buhler, J.: Designing multiple simultaneous primes for DNA similarity search. J. Comput. Biol. 2005 12:847-861.
【非特許文献１５】J. Xu, D. Brown, M. Li, and B. Ma, Optimizing multiple spaced primes for homology search, In Proc. of CPM'04, LNCS, vol. 3109, pp. 47-58.
【非特許文献１６】I.-H. Yang et al. E_cient Methods for Generating Optimal Single and Multiple Spaced Primes, In Proc. IEEE 4th Symp. on Bioinformatics and Bioengineering, Taiwan, 2004, pp. 411-418.
【非特許文献１７】Li, M., Ma, B., Kisman, D., et al. 2004. PatternHunter II: highly sensitive and fast homology search. J. Bioinform. Comput. Biol. 2, 417-439.
【非特許文献１８】M. Li, B. Ma, L. Zhang, Superiority and complexity of the spaced primes, in: Proceedings of the 17th Annual ACM-SIAM Symposium On Discrete Algorithms (SODA'06), ACM Press, 2006, pp. 444-453.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
以上のような各相同性検索方法は、その性能が、いずれもシードの構造に大きく依存する。シード最適化法でさえ、予め定義されたシードの重みによって制限される（非特許文献１６−１８参照）。従って、上記各各相同性検索方法は、シードの重みをあまり大きく設定しすぎると多くの相同配列を欠失する（感度が低下する）こととなる一方、シードをあまり短くしすぎると誤ったヒットが増加して検索速度も低下するといったジレンマが、未解決のまま残されている。これは、上述した（１）〜（３）のステップを含む戦略から発展したことに起因する根本的な問題である。
【００１５】
そこで、本発明の目的は、特定のシード構造を使用することなく、最適化されたマッチを適応的に生成することが可能な、ワードベースの探索戦略に基づく相同性検索装置及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００１６】
最初に、本発明の基礎となるアルゴリズムについて説明し、次いで、本発明の構成について説明する。
【００１７】
〔１〕本発明の基礎となるアルゴリズム
最初に、本発明の基礎となるワードベースの探索戦略について説明する。
【００１８】
相同性検索の目標は、最小の編集距離が閾値Ｔ以下である、クエリシーケンスと検索対象シーケンスの部分シーケンスのペアを検出することにある。本発明におけるワードベースの探索戦略は、上記従来のシードベースの探索戦略とは異なるため、以下、本発明の検索アルゴリズムを説明する際には、混同を避けるために「シード（prime）」，「ヒット（hit）」等の用語は使用しない。
【００１９】
本発明の相同性検索装置の基礎となるアルゴリズムは、以下のような手順で実行される。
【００２０】
（１）クエリシーケンスから、長さＬの全てのサブシーケンスのリストを作る。これらのサブシーケンスを「検索要求ワード」と呼ぶ。
【００２１】
この段階では、従来のシードベースのアプローチと類似している。しかしながら、本発明で用いるアルゴリズムでは、シードパターンに相当する検索要求ワードがマッチする必要はなく、この検索要求ワードを構成する非重畳セグメント（non-overlapped segment）を、相同性判定を行いながら連結していくことによって適応的にマッチが作り出されていく点で、従来とは全く相違する。
【００２２】
（２）全ての検索要求ワードを、非重畳セグメントに分解する。これらの非重畳セグメントを「素ワード（prime word：ＰＷ）」と呼ぶ。
【００２３】
（３）検索対象シーケンスに対して、素ワードをクエリとする完全一致検索を行い、すべての厳密な素ワード・マッチ（prim word match：ＰＷＭ）を索出する。
【００２４】
（４）素ワード・マッチを伸長（expand）する。
【００２５】
（５）検索対象シーケンスにおいて、編集距離がＴ以下の素ワード・マッチが検出された場合、この素ワード・マッチを検索結果（相同性索出データ）として出力し、さらなる伸長は、従来方法と同じくできるだけ長い結果が得られるように実行する。
【００２６】
このワードベースの探索戦略においては、次の２つの重要な問題を解決する必要がある。
【００２７】
（１）素ワードの長さ： 素ワードの長さは、偽性候補（false candidate）が索出されるのを制限しつつ、陽性候補（positive candidate）が欠失するのを回避するように設定しなければならない。
【００２８】
（２）素ワード・マッチの伸長の計算速度。
これらの課題を解決するために、本発明においては、以下に説明する「最小マッチ性（least match property）」に基づいて新たに開発したアプローチを用いる。
【００２９】
〔１−１〕最小マッチ性
シーケンスの距離測度に関して、以下のような簡単に証明可能な定理がある。
【００３０】
（定理１）
シーケンスＷ及びＳに対して、それらの間の距離をＤ（Ｗ，Ｓ）＝ｄとし、シーケンスＷはｄ＋１個の非重畳セグメントＷ＝Ｗ１Ｗ２…Ｗｄ＋１に分割されるとすると、Ｓ内に完全マッチ（exact match）を持つセグメントＷｉ（１≦ｉ≦ｄ＋１）が、少なくとも１つ存在する。
（定理終り）
【００３１】
この定理は明らかである。なぜなら、ＷからＳに変換するにはｄ回の操作のみが必要とされ、それらは少なくともｄ個の非重畳サブシーケンスを生じるからである。
【００３２】
この（定理１）に示される性質は、以下の（定理２）により、より一般化することができる。
【００３３】
（定理２）
Ｄ（Ｗ，Ｓ）＝ｄとし、Ｗはｋ個の非重畳セグメントＷ＝Ｗ１Ｗ２…Ｗｋに分割される場合、次式を満たすような、１つのＳのサブシーケンスＳｊと、少なくとも１つのＷのセグメントＷｉが存在する。
【００３４】
【数１】
ここで、Ｗｉ及びＳｊは、それぞれ、Ｗ及びＳのサブシーケンス（セグメント）、［ｄ／ｋ］はｄ／ｋを超えない最大の整数である（［ ］は、一般に「ガウス記号」と呼ばれる）。
（定理終り）
【００３５】
この（定理２）に示される性質を「最小マッチ性」と呼ぶ。
【００３６】
〔１−２〕素ワード長の選定
今、クエリシーケンスから切り出される一つのワードＷを考え、ワードＷの長さを｜Ｗ｜＝Ｌとする。また、Ｄ（Ｗ，Ｓ）≦Ｔとなる検索対象シーケンス内のサブシーケンスＳを索出したいものとする。
【００３７】
上述の最小マッチ性によれば、もしワードＷがＴ＋１個の非重畳セグメントに分割されるならば、検索対象シーケンスにおいて当該セグメントの完全マッチが少なくとも１つ存在するか、然もなくばＤ（Ｗ，Ｓ）≦Ｔの条件を満たすサブシーケンスＳは存在しない。従って、ワードＷをＴ＋１個の同じ長さの非重畳セグメントに分割する。すなわち、任意の１≦ｉ≦Ｔ＋１及び１≦ｊ≦Ｔ＋１について、Ｗ＝Ｗ１Ｗ２…ＷＴ＋１，｜Ｗｉ｜＝｜Ｗｊ｜とする。但し、最後のセグメントＷＴ＋１の長さは、それよりも前の各セグメントの長さよりも短くてもよいこととする。本発明では、これらのセグメントを素ワードとして使用する。これによって、Ｗの如何なる可能なマッチも欠失しないことが保証される。
【００３８】
〔１−３〕素ワード・マッチの高速伸長
完全一致検索により素ワード・マッチの位置が決定されると、次に、より長いマッチを探索するために、それらの素ワード・マッチを伸長する。
【００３９】
ここで、従来の動的計画法又は完全探索法（窮舉法：exhausted search）の代わりとして、最小マッチ性に基づいて、素ワード・マッチに隣接する素ワードをワード単位で連結していくことにより、素ワード・マッチの伸長を行うことが可能である。これは、最小マッチ性により許容される距離は、分割の変化のみによるとともに、最小マッチ性に係る（定理２）は、任意のシーケンスの分割及び初期素ワード同士の結合を行ったとしても、依然として成り立つからである。
【００４０】
すなわち、最小マッチ性の成立条件は次式のように表される。
【００４１】
【数２】
【００４２】
各ステップにおいて、ｋは２の冪乗である。式（２）は、Ｗｉ，Ｓｊの完全一致から距離［Ｔ／ｋ］までを相同条件として容認し、この相同条件を満たす限り隣接する２つのセグメントは互いに結合することができることを意味している。そこで、素ワードを二進木（binary tree）により体系化する。ここで、二進木の根節点は検索要求ワードＷに対応し、各終端節点（terminal node）は素ワードに対応し、非終端節点は、その子節点に向かう１つ又は２つの枝を有する。ここで、各非終端節点の左側の枝は、常に右側の枝と同数か又は１つだけ多い素ワードを有するものとする。
【００４３】
図５にワード二分木の一例を示す。この例では、探索条件である最大許容編集距離Ｔが６である。ここで、終端節点の親節点のみが、１つの枝のみを有することができるものとする。ワード二分木のレベル（階数）は、終端節点がレベル１とし、終端節点から根節点に向かってレベルが増加するとする。ワード二分木の各レベルにおいて、１つの節点はワードＷのセグメントの距離［Ｔ／ｋ］の近似マッチを表す。ここで、ｋ＝２１−ｎ（Ｔ＋１）であり、ｎはレベルを表すインデックスである。例えば、ｎ＝１はレベル１である。
【００４４】
図５の例を用いて、本発明の素ワード・マッチの伸長アルゴリズムについて説明する。
【００４５】
ワード二分木の各レベルは、検索要求ワードＷの分割を表す。例えば、図５におけるレベル２の分割は、Ｗ＝Ｗ１’ Ｗ２’ Ｗ３’ Ｗ４’である。ここで、ｉ＜４に対してはＷｉ’＝Ｗ２ｉ−１Ｗ２ｉであり、Ｗ４’＝Ｗ７である。
【００４６】
レベル１における素ワード・マッチの伸長は、レベル２において、相同判定条件Ｄ（Ｗｉ’，Ｓｊ）≦［６／４］＝１の素ワードの連結を探索することと等価である。ここで、Ｓｊは、先頭又は末尾にワードＷｉ’内の素ワードを含んだ検索対象シーケンスＳのサブシーケンスである。従って、素ワードＷｉの素ワード・マッチを伸長することは、検索要求ワードＷにおける素ワードＷｉと親節点を共有する兄弟節点Ｑｉ＾を探索することと等価である。最小マッチ性によれば、探索窓のサイズは｜Ｑｉ＾｜＋［Ｔ／ｋ］である。図５の例では、レベル２に対しては、Ｔ＝４，ｋ＝６である。従って、検索対象シーケンスＳにおけるワードＷ２のワードマッチを伸長する場合、探索窓は、検索対象シーケンスＳ内のワードＷ２の左側のサイズ｜Ｑ１｜＋［Ｔ／ｋ］の領域となる（図６参照）。
【００４７】
任意のレベルにおいて、全ての節点でマッチが検出されなかったときに、素ワード・マッチの伸長は終了する。
【００４８】
検索窓のサイズは、特に最低レベルにおいて、検索対象シーケンスＳに比べて極めて小さくなる。故に、窓内探索の過程は、距離閾値［Ｔ／ｋ］を与えることにより非常に高速に実行することができる。
【００４９】
レベルが上がるにつれて、探索窓のサイズは大きくなり、伸長において探索すべきシーケンスは、ワード二分木に従って連結した素ワードの連鎖に成長していく。素ワードの連鎖が伸長できない場合には、そのサブツリーが、予め決められた巡回順序に従って探索される。この過程の間、探索空間は小片に分解され、偽性候補は初期の段階で淘汰される。従って、探索過程の計算複雑性は低い値に保たれる。
【００５０】
〔１−４〕さらなる伸長過程
上記素ワード・マッチの伸長によって、相同性判定基準に合致する全ての局所シーケンスが索出された後、さらにできるだけ長いアラインメントとなるように、両サイドにさらに伸長することができないかチェックされる。このステージにおいては、従来方法と同じギャップのある伸長フェーズと同様の方法が使用されるが、本発明とは直接関係がないので説明は割愛する。
【００５１】
〔２〕本発明の構成
【００５２】
本発明に係る相同性検索装置の第１の構成は、所定の種類の文字又は記号の文字列からなる検索対象シーケンスを記憶する検索対象シーケンス記憶手段と、
前記検索対象シーケンス内の相同な文字列を検索するために検索条件として設定される文字列である検索要求ワードを記憶する検索要求ワード記憶手段と、
前記検索要求ワードを段階的に順次二分割してなる完全二分木又は不完全二分木であるワード二分木のデータを記憶するワード二分木テーブル記憶手段と、
前記検索要求ワードを分割して生成される素ワードを記憶する素ワード記憶手段と、
前記検索対象シーケンス内における前記素ワードに一致するマッチ部分文字列の位置を記憶する完全一致位置記憶手段と、
前記素ワード，前記検索要求ワード内における前記素ワードの位置，前記マッチ部分文字列，及び検索対象シーケンス内における前記マッチ部分文字列の位置を含む相同性索出データを記憶する相同テーブル記憶手段と、
２つの文字列が相同と判定するための許容編集距離の最大値である最大許容編集距離Ｔを入力手段により取得する最大許容編集距離設定手段と、
前記検索要求ワード記憶手段に記憶された前記検索要求ワードを（Ｔ＋１）個の前記素ワードに分割し、終端節点が（Ｔ＋１）個の前記各素ワードに対応する前記ワード二分木を生成し、前記ワード二分木テーブル記憶手段に前記ワード二分木テーブルとして格納するワード二分木生成手段と、
前記ワード二分木の各終端節点を順次選択し、選択した終端節点に対応する素ワードを前記素ワード記憶手段に格納する初期素ワード設定手段と、
前記素ワード記憶手段に記憶された前記素ワードに基づき、前記検索対象シーケンス内における当該素ワードと完全に一致するマッチ部分文字列の位置をすべて索出し、当該マッチ部分文字列の位置を完全一致位置記憶手段に格納するとともに、当該素ワード，当該素ワードの位置，当該マッチ部分文字列，及び当該マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納する完全一致検索手段と、
前記完全一致位置記憶手段に記憶された前記各マッチ部分文字列について、前記素ワード記憶手段に記憶された前記素ワードに対し、前記ワード二分木に従って、当該素ワードの節点に双対する節点に対応する部分ワードを当該素ワードに結合した伸長素ワード、及び前記伸長素ワードに対応する節点に双対する節点又はその子孫節点に対応する部分ワードを当該伸長ワードに結合した伸長素ワードを順次生成し、前記各伸長素ワードのうち、当該マッチ部分文字列を当該伸長素ワードと同方向に伸長した文字列である伸長マッチ部分文字列が当該伸長素ワードと相同な場合に、当該伸長素ワード，当該伸長素ワードの位置，当該伸長マッチ部分文字列，及び当該伸長マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納する素ワード伸長検索処理を行う素ワード伸長検索処理手段と、を備えたことを特徴とする。
【００５３】
この構成により、上述のワードベースの探索戦略に基づくアルゴリズムにより、検索対象シーケンスに対する検索要求ワードによる相同性探索を具体的に実行することが可能となり、最適化されたマッチを適応的に生成することが可能となる。
【００５４】
また、本発明に係る相同性検索装置の第２の構成は、前記第１の構成において、前記最大許容編集距離設定手段は、前記最大許容編集距離Ｔに１を加えた値を相同判定パラメータｋの初期値に設定するものであり、
前記素ワード伸長検索処理手段は、
前記素ワード伸長検索処理の開始時に、降下階数ｎｄを０に初期化するとともに、［ｋ／２］（［ ］はガウス記号）の値を前記相同判定パラメータｋの新たな値に更新する降下階数初期化手段と、
前記素ワード記憶手段に記憶された現在の前記素ワードに対応する前記ワード二分木の節点が、左側子節点の場合にはそれに双対する右側子節点から左枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定し、右側子節点の場合にはそれに双対する左側子節点から右枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定する結合候補節点設定手段と、
前記結合候補節点に対応する結合候補ワードを前記検索要求ワード記憶手段から読み出し、現在の前記素ワードに前記結合候補ワードを結合した結合ワードを前記伸長素ワードに設定する伸長素ワード設定手段と、
前記伸長素ワードに対応して、前記マッチ部分文字列を伸長した部分文字列を前記検索対象シーケンスから抽出し、比較対象シーケンスに設定する比較対象シーケンス抽出手段と、
前記比較対象シーケンスから前記伸長素ワードとの距離が最小となる前記伸長マッチ部分文字列を抽出し、当該伸長マッチ部分文字列と前記伸長素ワードとの距離である最小編集距離Ｌｃを算出する最小編集距離演算手段と、
前記最大許容編集距離Ｔと前記相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］（［ ］はガウス記号）に設定する編集距離閾値設定手段と、
前記最小編集距離Ｌｃと前記編集距離閾値Ｄｔｈとを比較し、Ｌｃ≦Ｄｔｈの場合には相同条件充足と判定し、前記伸長素ワード，前記伸長素ワードの位置，前記伸長マッチ部分文字列，及び前記伸長マッチ部分文字列の位置を前記相同性索出データとして前記相同テーブル記憶手段に格納する一方、Ｌｃ＞Ｄｔｈの場合には相同条件未充足と判定する相同条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードに対応する前記ワード二分木の節点の親節点が根節点であれば素ワード伸長検索処理を終了し、前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、最後に設定された前記結合候補節点が終端節点であれば素ワード伸長検索処理を終了する終了条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードを前記伸長素ワードに更新し前記素ワード記憶手段に格納するとともに、［ｋ／２］（［ ］はガウス記号）の値を前記相同判定パラメータｋの新たな値に更新する素ワード更新手段と、
前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、降下階数ｎｄを１だけ増加させる降下階数変更手段と、
前記終了条件判定手段により素ワード伸長検索処理が終了されるまで、前記結合候補節点設定手段、前記伸長素ワード設定手段、前記比較対象シーケンス抽出手段、前記最小編集距離演算手段、前記編集距離閾値設定手段、前記相同条件判定手段、前記終了条件判定手段、前記素ワード更新手段、及び前記降下階数変更手段による素ワード伸長検索処理を反復実行する制御を行う素ワード伸長検索処理制御手段と、を備えたことを特徴とする。
【００５５】
また、本発明に係る相同性検索装置の第３の構成は、前記第１又は２の構成において、前記検索対象シーケンスを構成する文字記号と同種の文字記号の文字列からなるクエリシーケンスを記憶するクエリシーケンス記憶手段と、
前記クエリシーケンスから前記クエリシーケンス内の所定の長さの部分文字列を切り出し、前記検索要求ワードとして前記検索要求ワード記憶手段に格納する検索要求ワード設定手段と、を備え、
前記要求ワード設定手段は、前記部分文字列の先頭位置を、前記クエリシーケンスの先頭から１文字ずつ移動させながら前記部分文字列を順次切り出し、前記検索要求ワード記憶手段に格納された前記検索要求ワードを逐次更新するものであり、
前記ワード二分木生成手段は、前記検索要求ワード記憶手段に格納された前記検索要求ワードが更新される毎に、前記ワード二分木を生成し、前記ワード二分木テーブルの更新を行うことを特徴とする。
【００５６】
また、本発明に係るプログラムは、コンピュータに読み込ませて実行させることにより、当該コンピュータを請求項１乃至３のいずれかの構成の相同性検索装置として動作させることを特徴とする。
【発明の効果】
【００５７】
上記本発明に係る相同性検索装置によれば、素ワード伸長検索処理の際に検索対象シーケンス内のマッチを探索する際の探索空間が極めて小さいため、高速で検索を行うことが可能となるとともに、特定のシード構造に依存せず適応的に構成されるワード（素ワード及び伸長素ワード）による検索が行われるため、ヒットの欠失を低く抑え、検索感度を向上左折ことが可能となる。
【図面の簡単な説明】
【００５８】
【図１】本発明の実施例１に係る相同性検索装置１の全体構成を表すブロック図である。
【図２】図１の検索実行部１９の構成を表すブロック図である。
【図３】図２の素ワード伸長検索処理部の構成を表すブロック図である。
【図４】検索対象シーケンスＳ及びクエリシーケンスＱのデータ構造、並びにクエリシーケンスＱと検索要求ワードＷとの関係を表す図である。
【図５】ワード二分木のデータ構造を表す図である。
【図６】比較対象シーケンス抽出部３３が検索対象シーケンスから抽出する比較対象シーケンスの一例を表す図である。
【図７】本発明の実施例１に係る相同性検索装置１の動作の全体の流れを表すＰＡＤ（Problem Analysis Diagram）図である。
【図８】図７の二分木相同性検索処理サブルーチンの処理の流れを表すＰＡＤ図である。
【図９】図８の素ワード伸長検索処理サブルーチンの処理の流れを表すＰＡＤ図である。
【発明を実施するための形態】
【００５９】
以下、本発明を実施するための形態について、図面を参照しながら説明する。
【実施例１】
【００６０】
図１は、本発明の実施例１に係る相同性検索装置の全体構成を表すブロック図である。本実施例の相同性探索装置１は、入力装置２から入力されるクエリシーケンスＱと相同性判定の際の最大許容編集距離Ｔに基づいて、シーケンスデータベース３に格納された検索対象シーケンスＳと当該クエリシーケンスＱとの相同性検索を行い、その索出結果を出力装置４に出力するものである。入力装置２としては、キーボードやマウス、ディスクドライブ等の通常のコンピュータの入力装置が使用される。また、出力装置４としては、ディスプレイや外部記憶装置等の通常のコンピュータの出力装置が使用される。シーケンスデータベース３は、ハードディスクドライブ等の大容量記憶装置が使用される。
【００６１】
本実施例の相同性探索装置１は、検索対象シーケンス選択部１０、検索対象シーケンス記憶部１１、クエリシーケンス入力部１２、クエリシーケンス記憶部１３、検索要求ワード設定部１４、検索要求ワード記憶部１５、ワード二分木生成部１６、ワード二分木テーブル記憶部１７、最大許容編集距離設定部１８、検索実行部１９、及び相同テーブル記憶部２０を備えている。これらの機能構成は、専用回路として構成してもよいが、コンピュータ・プログラムとして提供し、当該プログラムをコンピュータにロードして実行することにより機能的に構成されるようにしてもよい。
【００６２】
シーケンスデータベース３には、複数の検索対象シーケンスＳが記憶されている。ここで、「検索対象シーケンス」とは、所定の種類の文字又は記号の文字列からなるシーケンスであり、核酸の塩基配列（核酸を構成する塩基を表す「Ａ」，「Ｃ」，「Ｇ」，「Ｔ」の文字及びドント・ケア（欠失部分）を表す記号「−」からなる配列）やタンパク質のアミノ酸配列（アミノ酸を表す２０種類の文字「Ａ」，「Ｃ」，「Ｄ」，「Ｅ」，「Ｆ」，「Ｇ」，「Ｈ」，「Ｉ」，「Ｋ」，「Ｌ」，「Ｍ」，「Ｎ」，「Ｐ」，「Ｑ」，「Ｒ」，「Ｓ」，「Ｔ」，「Ｖ」，「Ｗ」，「Ｙ」及びドント・ケアを表す記号「−」からなる配列）等が想定されている。
【００６３】
検索対象シーケンス選択部１０は、シーケンスデータベース３から、相同性検索に使用する検索対象シーケンスＳを選択して読み出し、検索対象シーケンス記憶部１１に格納する。検索対象シーケンス記憶部１１は、この検索対象シーケンスＳを記憶する。
【００６４】
図４（ａ），（ｂ）に、検索対象シーケンスＳ及びクエリシーケンスＱのデータ構造を示す。検索対象シーケンスＳはＮｓ個の文字配列から構成され、クエリシーケンスＱはＮｑ個の文字配列から構成されている。核酸やタンパク質のシーケンスの場合、Ｎｓ，Ｎｑは通常非常に大きな値となる。
【００６５】
最大許容編集距離設定部１８は、２つの文字列が相同であると判定するための許容される２つの文字列間の編集距離の最大値である最大許容編集距離Ｔを入力手段から取得する。また、最大許容編集距離Ｔに１を加えた値を相同判定パラメータｋの初期値に設定する。「相同判定パラメータ」とは、検索対象の文字列と素ワードとの相同性を判定するための編集距離閾値Ｄｔｈを算出するパラメータであり、最大許容編集距離Ｔと編集距離閾値Ｄｔｈと相同判定パラメータｋとはＤｔｈ＝［Ｔ／ｋ］の関係にある。
【００６６】
クエリシーケンス入力部１２は、ユーザが入力装置２から入力するクエリシーケンスＱを取得して、クエリシーケンス記憶部１３に格納する。クエリシーケンス記憶部１３は、このクエリシーケンスＱを記憶する。ここで、「クエリシーケンス」は、前記検索対象シーケンスと同種の文字又は記号の配列からなるシーケンスである。
【００６７】
検索要求ワード設定部１４は、クエリシーケンス記憶部１３に記憶されたクエリシーケンスＱから、当該クエリシーケンスＱ内の所定の長さＬの部分文字列を切り出し、検索要求ワードＷとして検索要求ワード記憶部１５に格納する。検索要求ワード記憶部１５は、当該検索要求ワードＷを一時的に記憶する。
【００６８】
図４（ｃ）に、クエリシーケンスＱと検索要求ワードＷとの関係を示す。検索要求ワード設定部１４は、検索要求ワードＷの先頭位置を、クエリシーケンスＱの先頭から末尾方向に、１文字ずつずらしながら長さＬの検索要求ワードＷを順次切り出して、検索要求ワード記憶部１５に格納する。従って、この切り出しの全回数をＮｗ回とすると、Ｎｗ＝Ｎｑ−Ｌ＋１となる。
【００６９】
ワード二分木生成部１６は、検索要求ワード記憶部１５に検索要求ワードＷが設定されると、その検索要求ワードＷに基づき、終端節点の数が（Ｔ＋１）個のワード二分木を生成し、ワード二分木テーブル記憶部１７にワード二分木テーブルとして格納する。ワード二分木テーブル記憶部１７は、当該ワード二分木テーブルを記憶する。
【００７０】
ここで、ワード二分木については既に説明したが、ワード二分木は、例えば、図５に示したようなデータ構造を有する。ワード二分木の終端節点は、検索要求ワードＷを（Ｔ＋１）個に分割した素ワードＷｉ（ｉ＝１，…，Ｔ＋１）に対応する。検索要求ワードＷの長さＬが（Ｔ＋１）で割り切れる場合には、すべての素ワードＷｉの長さは等しくなり、｜Ｗｉ｜＝Ｌ／（Ｔ＋１）となる。一方、Ｌが（Ｔ＋１）で割り切れない場合、素ワードＷ１〜ＷＴまでは同じ長さ［Ｌ／（Ｔ＋１）］とし、ＷＴの長さは余りのＬ−Ｔ（［Ｌ／（Ｔ＋１）］）とする。ここで、［ ］はガウス記号を表す（以下同じ）。また、ワード二分木の根節点は、検索要求ワードＷそのものに対応する。ワード二分木は、終端節点から構成してゆき、最も左側の節点から、隣接する２つの節点のペアを作り、それらの節点ペアの共通の親節点を生成するという処理を繰り返すことにより容易に構成することができる。尚、最も右側の終端節点だけは、ペアの相手がない場合（すなわち、終端節点の数が奇数の場合）には単独の節点とし、その親節点を１つ生成すればよい（図５参照）。
【００７１】
ワード二分木テーブルは、上述のようなデータ構造のワード二分木の情報を格納するテーブルであり、例えば、図５のワード二分木を格納するワード二分木テーブルは、表１のようになる。
【００７２】
【表１】
【００７３】
表１において、「節点名」フィールドには、図５の各節点に付されたラベルが格納される。「位置ｐｏｓ」フィールドには、各節点に対応するセグメントの検索要求ワードＷ内における位置が格納され、具体的には、各節点に対応するワードの先頭位置のポインタが格納される。「ワード長ｌ」フィールドには、それぞれのセグメントの長さ、「階層Ｌｅｖ」フィールドには節点の階層（レベル）、「親節点ｐparent」フィールドには各節点の親節点のラベル、「左子節点ｐｌｅｆｔ」フィールドには各節点から出る左枝に接続する子節点のラベル、「右子節点ｐｒｉｇｈｔ」フィールドには各節点から出る右枝に接続する子節点のラベルがそれぞれ格納される。
【００７４】
検索実行部１９は、上記ワード二分木に基づき、検索対象シーケンスＳと検索要求ワードＷとの相同性検索を行い、その結果索出される相同性索出データを相同テーブル記憶部２０に相同テーブルとして格納する。相同テーブル記憶部２０は、当該相同テーブルを記憶する。
【００７５】
ここで、相同テーブルは、表２に示すような構造のデータテーブルである。
【００７６】
【表２】
【００７７】
表２において、「検索要求ワード位置」フィールドには、検索要求ワードＷの先頭位置の、クエリシーケンスＱの先頭位置からのシフト量（すなわち、クエリシーケンスＱ内の検索要求ワードＷの位置）が格納される（図４（ｃ）参照）。「素ワード」フィールドには、検索対象シーケンスＳ内のサブシーケンスにマッチした素ワードのシーケンスが格納される。「マッチ位置」フィールドには、マッチした素ワードの先頭文字の検索要求ワードＷ内における位置が格納される。「相同シーケンス」フィールドには、前記サブシーケンスと相同と判定された検索対象シーケンスＳ内のサブシーケンスが格納される。また、「相同シーケンス位置」フィールドには、前記サブシーケンスの先頭文字の検索対象シーケンスＳ内における位置が格納される。
【００７８】
次に、図１の検索実行部１９の構成について説明する。図２は、検索実行部１９の構成を表すブロック図である。
【００７９】
検索実行部１９は、クエリ素ワード設定部２５、素ワード記憶部２６、完全一致検索部２７、完全一致位置記憶部２８、及び素ワード伸長検索処理部２９を備えている。
【００８０】
クエリ素ワード設定部２５は、ワード二分木テーブル記憶部１７に格納されているワード二分木の各終端節点を左側から順次選択し、選択した終端節点に対する文字列Ｗｉ（ｉ＝１，…，Ｔ＋１）を初期の素ワードＷprimeとして素ワード記憶部２６に格納する。素ワード記憶部２６は、当該素ワードＷprimeを記憶し保持する。
【００８１】
完全一致検索部２７は、素ワード記憶部２６に記憶されている素ワードＷprimeに基づき、検索対象シーケンスＳ内における当該素ワードＷprimeと完全に一致するマッチ部分文字列Ｓexactの位置ｐmatchをすべて索出し、当該マッチ部分文字列の位置ｐmatchを完全一致位置記憶部２８に格納するとともに、｛検索要求ワードＷの位置，当該素ワードＷprime，当該素ワードＷprimeの位置，当該マッチ部分文字列Ｓexact，当該マッチ部分文字列Ｓexactの位置ｐmatch｝を相同性索出データとして相同テーブル記憶部２０に格納する。完全一致位置記憶部２８は、前記マッチ部分文字列の位置を記憶し保持する。
【００８２】
素ワード伸長検索処理部２９は、完全一致位置記憶部２８に記憶された各マッチ部分文字列について、素ワード記憶部２６に記憶された素ワードＷprimeに対し後述の素ワード伸長検索処理を行うとともに、素ワード伸長検索処理により伸長される伸長素ワードＷexpandのうち、当該マッチ部分文字列Ｓexactの位置にある当該伸長素ワードＷexpandに対応する文字列である伸長マッチ部分文字列Ｓmatchが当該伸長素ワードＷexpandと相同な場合に、｛検索要求ワードＷの位置，当該伸長素ワードＷexpand，当該伸長素ワードＷexpandの位置，当該伸長マッチ部分文字列Ｓmatch，当該伸長マッチ部分文字列Ｓmatchの位置｝を相同性索出データとして相同テーブル記憶部２０に格納する。
【００８３】
次に、図２の素ワード伸長検索処理部２９の構成について説明する。図３は、図２の素ワード伸長検索処理部の構成を表すブロック図である。
【００８４】
素ワード伸長検索処理部２９は、降下階数初期化部３０、結合候補節点設定部３１、伸長素ワード設定部３２、比較対象シーケンス抽出部３３、最小編集距離演算部３４、編集距離閾値設定部３５、相同条件判定部３６、終了条件判定部３７、素ワード更新部３８、降下階数変更部３９、及び素ワード伸長検索処理制御部４０を備えている。
【００８５】
降下階数初期化部３０は、素ワード伸長検索処理の開始時に、降下階数ｎｄを０に初期化するとともに、［ｋ／２］の値を相同判定パラメータｋの新たな値に更新する。
【００８６】
結合候補節点設定部３１は、素ワード記憶部２６に記憶された現在の素ワードに対応するワード二分木の節点が、左側子節点の場合にはそれに双対する右側子節点から左枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点ｐcombに設定し、右側子節点の場合にはそれに双対する左側子節点から右枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点ｐcombに設定する。
【００８７】
伸長素ワード設定部３２は、結合候補節点ｐcombに対応する結合候補ワードＷcombを検索要求ワード記憶部１５から読み出し、現在の素ワードＷprimeに結合候補ワードＷcombを結合した結合ワードを伸長素ワードＷexpandに設定する。
【００８８】
比較対象シーケンス抽出部３３は、伸長素ワードＷexpandに対応して、マッチ部分文字列Ｓexactを伸長した部分文字列を検索対象シーケンスＳから抽出し、比較対象シーケンスに設定する。
【００８９】
最小編集距離演算部３４は、比較対象シーケンスＳ１から伸長素ワードＷexpandとの編集距離が最小となる伸長マッチ部分文字列Ｓmatchを抽出し、当該伸長マッチ部分文字列Ｓmatchと伸長素ワードＷexpandとの編集距離である最小編集距離Ｌｃを出力する。
【００９０】
編集距離閾値設定部３５は、最大許容編集距離Ｔと相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］に設定する。
【００９１】
相同条件判定部３６は、最小編集距離Ｌｃと編集距離閾値Ｄｔｈとを比較し、Ｌｃ≦Ｄｔｈの場合には相同条件充足と判定し、｛検索要求ワードＷの位置，伸長素ワードＷexpand，伸長素ワードの位置，伸長マッチ部分文字列Ｓmatch，伸長マッチ部分文字列の位置｝を相同性索出データとして相同テーブル記憶部に格納する一方、Ｌｃ＞Ｄｔｈの場合には相同条件未充足と判定する。
【００９２】
終了条件判定部３７は、相同条件判定部３６が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の素ワードＷprimeに対応するワード二分木の節点の親節点が根節点であれば素ワード伸長検索処理を終了し、相同条件判定部３６が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、最後に設定された結合候補節点が終端節点であれば素ワード伸長検索処理を終了する。
【００９３】
素ワード更新部３８は、相同条件判定部３６が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の素ワードを伸長素ワードに更新し素ワード記憶部２６に格納するとともに、［ｋ／２］の値を相同判定パラメータｋの新たな値に更新する。
【００９４】
降下階数変更部３９は、相同条件判定部３６が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、降下階数ｎｄを１だけ増加させる。
【００９５】
素ワード伸長検索処理制御部４０は、終了条件判定部３７により素ワード伸長検索処理が終了されるまで、結合候補節点設定部３１、伸長素ワード設定部３２、比較対象シーケンス抽出部３３、最小編集距離演算部３４、編集距離閾値設定部３５、相同条件判定部３６、終了条件判定部３７、素ワード更新部３８、及び降下階数変更部３９による素ワード伸長検索処理を反復実行する制御を行う。
【００９６】
以上のように構成された本発明の実施例１に係る相同性検索装置について、以下その動作を説明する。
【００９７】
図７は、本発明の実施例１に係る相同性検索装置１の動作の全体の流れを表すＰＡＤ（Problem Analysis Diagram）図である。
【００９８】
まず、ステップＳ１において、ユーザにより入力手段から最大許容編集距離Ｔ、ワード長Ｌ、及びクエリシーケンスＱが入力される。最大許容編集距離設定部１８は、入力された最大許容編集距離Ｔを保持する。検索要求ワード設定部１４は、入力されたワード長Ｌを保持する。また、クエリシーケンス入力部１２は、入力されたクエリシーケンスＱを、クエリシーケンス記憶部１３に保存する。
【００９９】
また、検索対象シーケンス選択部１０は、シーケンスデータベース３から１つの検索対象シーケンスＳを選択して読み出し、検索対象シーケンス記憶部１１に保存する。
【０１００】
次に、ステップＳ２において、最大許容編集距離設定部１８は、相同判定パラメータｋの値をＴ＋１に初期化する。
【０１０１】
次に、ステップＳ３において、検索要求ワード設定部１４がシフト量を表す内部変数ｉを０からＮｗ−１まで１ずつ増加させながら、以下のステップＳ４〜Ｓ６の処理が反復実行される。
【０１０２】
次に、ステップＳ４において、検索要求ワード設定部１４は、図４（ｃ）に示したように、切り出し位置をクエリシーケンスＱの先頭からｉ文字シフトさせ、クエリシーケンスＱの当該切り出し位置から長さＬの部分文字列を切り出し、これを検索要求ワードＷとして検索要求ワード記憶部１５に格納する。
【０１０３】
次に、ステップＳ５において、ワード二分木生成部１６は、検索要求ワード記憶部１５に記憶された検索要求ワードＷに基づき、終端節点の数が（Ｔ＋１）個の図５に示したようなワード二分木を生成し、ワード二分木テーブル記憶部１７に表１のようなワード二分木テーブルとして格納する。
【０１０４】
次に、ステップＳ６において、ワード二分木テーブル記憶部１７に格納されたワード二分木に基づいて、検索実行部１９による二分木相同性探索処理が行われる。
【０１０５】
以上のステップＳ４〜Ｓ６の処理がＮｗ回反復実行された後、相同性探索装置１は相同性検索を終了する。相同性検索による相同性索出データは、二分木相同性探索処理により相同テーブル記憶部２０に蓄積されるので、これらの結果を出力装置４に出力すればよい。
【０１０６】
次に、上記ステップＳ６における二分木相同性探索処理について説明する。図８は、図７の二分木相同性検索処理サブルーチンの処理の流れを表すＰＡＤ図である。
【０１０７】
まず、ステップＳ１１において、クエリ素ワード設定部２５は、選択する終端節点のインデックスを表す内部変数ｊを１からＴ−１まで１ずつ増加させながら、以下のステップＳ１２〜Ｓ１７の処理を反復実行する。
【０１０８】
ステップＳ１２において、クエリ素ワード設定部２５は、ワード二分木テーブル記憶部１７に格納されたワード二分木テーブルを参照し、左からｊ番目の終端節点に対応するワードＷｊを検索要求ワード記憶部１５から読み出して、初期の素ワードＷprimeとして素ワード記憶部２６に格納する。
【０１０９】
次に、ステップＳ１３において、完全一致検索部２７は、素ワード記憶部２６に記憶された素ワードＷprimeに基づき、検索対象シーケンスＳ内における当該素ワードＷprimeと完全に一致するマッチ部分文字列Ｗexactの位置ｐmatchをすべて索出し、当該マッチ部分文字列の位置ｐmatchを完全一致位置記憶部２８に格納する。ここで、索出されたマッチ部分文字列の数をＮmatchとし、各マッチ部分文字列の位置をｐmatch（ξ）（ξ＝１，…，Ｎmatch）と記す。
【０１１０】
次に、ステップＳ１４において、Ｎmatch＞０（完全マッチが存在する）の場合、完全一致検索部２７は、マッチ部分文字列のインデックスξを１からＮmatchまで１ずつ増加させながら、以下のステップＳ１５〜Ｓ１７の処理を反復実行する。
【０１１１】
ステップＳ１５において、完全一致検索部２７は、ξ番目のマッチ部分文字列ｐmatch（ξ）に対して、｛検索要求ワードＷの位置，素ワードＷprime，素ワードの位置，マッチ部分文字列，マッチ部分文字列の位置ｐmatch（ξ）｝を相同性索出データとして相同テーブル記憶部２０に格納する。
【０１１２】
次に、ステップＳ１６において、降下階数初期化部３０は、内部変数である降下階数ｎdownを０に初期化するとともに、［ｋ／２］の値を相同判定パラメータｋの新たな値として更新する。
【０１１３】
最後に、ステップＳ１７において、｛マッチ部分文字列の位置ｐmatch（ξ），現在の素ワードＷ，現在選択されている終端節点のレベルＬｅｖ＝１，現在選択されている終端節点の親節点ｐparent，現在選択されている終端節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown＝０｝を入力値として、後述の素ワード伸長検索処理部２９による素ワード伸長検索処理素素ワード伸長検索処理が実行される。
【０１１４】
図９は、図８の素ワード伸長検索処理サブルーチンの処理の流れを表すＰＡＤ図である。この素ワード伸長検索処理サブルーチンでは、再帰処理が用いられている。なお、この素ワード伸長検索処理サブルーチンは、入力値として、｛マッチ部分文字列の位置ｐmatch，現在の素ワードＷprime，現在選択されている節点のレベルＬｅｖ，現在選択されている節点の親節点ｐparent，現在選択されている節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝をとるものとする。
【０１１５】
まず、ステップＳ２１において、編集距離閾値設定部３５は、最大許容編集距離Ｔと現在の相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］に設定する。
【０１１６】
次に、ステップＳ２２において、結合候補節点設定部３１は、入力されたサイドＳｉｄｅを参照して、現在選択されている節点が、その親節点に対し左側子節点か右側子節点かを判定する。
【０１１７】
左側子節点と判定された場合、ステップＳ２３において、結合候補節点設定部３１は、現在選択されている節点の親節点ｐparentの右側子節点を指定節点に設定し、ステップＳ２４において、結合候補節点設定部３１は、当該指定節点から左側枝を辿りながらｎdown階降下した節点を結合候補節点ｐcombに設定する。次いで、ステップＳ２５において、伸長素ワード設定部３２は、結合候補節点ｐcombに対応するワード（結合候補ワード）Ｗcombを素ワード記憶部２６から読み出して、現在の素ワードＷprimeの右側に当該結合候補ワードＷcombを結合した結合ワードを生成し、これを伸長素ワードＷexpandに設定する。そして、ステップＳ２６において、比較対象シーケンス抽出部３３は、探索窓幅を｜Ｗcomb｜＋Ｄｔｈとして、検索対象シーケンスＳのマッチ部分文字列Ｗexactの位置ｐmatchから長さ｜Ｗexpand｜＋Ｄｔｈ（＝｜Ｗprime｜＋｜Ｗcomb｜＋Ｄｔｈ）のシーケンスを抽出し、これを比較対象シーケンスＳ１に設定する。
【０１１８】
一方、ステップＳ２２において右側子節点と判定された場合、ステップＳ２７において、結合候補節点設定部３１は、現在選択されている節点の親節点ｐparentの左側子節点を指定節点に設定し、ステップＳ２８において、結合候補節点設定部３１は、当該指定節点から右側枝を辿りながらｎdown階降下した節点を結合候補節点ｐcombに設定する。次いで、ステップＳ２９において、伸長素ワード設定部３２は、結合候補節点ｐcombに対応するワード（結合候補ワード）Ｗcombを素ワード記憶部２６から読み出して、現在の素ワードＷprimeの左側に当該結合候補ワードＷcombを結合した結合ワードを生成し、これを伸長素ワードＷexpandに設定する。そして、ステップＳ３０において、比較対象シーケンス抽出部３３は、探索窓幅を｜Ｗcomb｜＋Ｄｔｈとして、検索対象シーケンスＳのマッチ部分文字列の位置ｐmatchに対し｜Ｗcomb｜＋Ｄｔｈだけ左（先頭側）にシフトした位置ｐｔｏｐ＝ｐmatch−（｜Ｗcomb｜＋Ｄｔｈ）から、長さ｜Ｗexpand｜＋Ｄｔｈ（＝｜Ｗprime｜＋｜Ｗcomb｜＋Ｄｔｈ）のシーケンスを抽出し、これを比較対象シーケンスＳ１に設定する。
【０１１９】
次に、ステップＳ３１において、最小編集距離演算部３４は、比較対象シーケンスＳ１から伸長素ワードＷexpandとの編集距離が最小となる伸長マッチ部分文字列Ｓmatchを抽出し、当該伸長マッチ部分文字列Ｓmatchと伸長素ワードＷexpandとの距離である最小編集距離Ｌｃを算出する。
【０１２０】
次に、ステップＳ３２において、相同条件判定部３６は、最小編集距離Ｌｃと編集距離閾値Ｄｔｈとを比較し、ＬｃがＤｔｈ以下であるか否かを判定する。
【０１２１】
ここで、Ｌｃ≦Ｄｔｈの場合、相同条件判定部３６は、伸長素ワードＷexpandと伸長マッチ部分文字列Ｓmatchとが相同性条件を充足する（相同性条件充足）と判定し、ステップＳ３３において、マッチ部分文字列の位置ｐmatchを伸長マッチ部分文字列Ｓmatchの先頭位置に更新した後、ステップＳ３４において、｛検索要求ワードＷの位置，伸長素ワードＷexpand，伸長素ワードＷexpandの位置ｐexpand，伸長マッチ部分文字列Ｓmatch，伸長マッチ部分文字列Ｓmatchの位置ｐmatch｝を相同性索出データとして相同テーブル記憶部２０に格納する。
【０１２２】
次いで、ステップＳ３５において、終了条件判定部３７は、現在の降下階数ｎdownが０か否かを判定する。
【０１２３】
ｎdown＝０の場合は、ステップＳ３６において、終了条件判定部３７は、現在の節点のレベルＬｅｖが根節点のレベルＬｅｖｍａｘよりも小さいか否かを判定する。ここで、Ｌｅｖ＝Ｌｅｖｍａｘならば、終了条件判定部３７は素ワード伸長検索処理を終了する。一方、Ｌｅｖ＜Ｌｅｖｍａｘならば、ステップＳ３７において、素ワード更新部３８は、素ワードＷを伸長素ワードＷexpandに更新し素ワード記憶部２６に格納するとともに、ステップＳ３８において、［ｋ／２］の値を相同判定パラメータｋの新たな値としてｋを更新する。そして、ステップＳ３９において、素ワード伸長検索処理制御部４０は、｛伸長マッチ部分文字列の位置ｐmatch，現在の素ワードＷ，現在選択されている節点の親節点のレベルＬｅｖ＋１，現在選択されている節点の祖父節点ｐgrand，現在選択されている節点の親節点の祖父節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝を入力値として、素ワード伸長検索処理部２９による素ワード伸長検索処理を再帰的に実行する。
【０１２４】
ステップＳ３５においてｎdown＞０の場合は、ステップＳ４０において、終了条件判定部３７は、現在の節点のレベルＬｅｖから降下階数ｎdownを引いた値Ｌｅｖ−ｎdownが１より大きい（すなわち、最後に設定された結合候補節点ｐcombが終端節点でない）か否かを判定する。ここで、Ｌｅｖ−ｎdown＝１ならば、終了条件判定部３７は素ワード伸長検索処理を終了する。一方、Ｌｅｖ−ｎdown＞１ならば、ステップＳ４１において、降下階数変更部３９は、降下階数ｎｄを１だけ増加させる。そして、ステップＳ４２において、素ワード伸長検索処理制御部４０は、｛伸長マッチ部分文字列の位置ｐmatch，現在の素ワードＷprime，現在選択されている節点のレベルＬｅｖ，現在選択されている節点の親節点ｐparent，現在選択されている節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝を入力値として、素ワード伸長検索処理部２９による素ワード伸長検索処理を再帰的に実行する。
【０１２５】
ステップＳ３２においてＬｃ＞Ｄｔｈの場合、相同条件判定部３６は、相同条件未充足と判定し、ステップＳ４３において、終了条件判定部３７は、現在の節点のレベルＬｅｖから降下階数ｎdownを引いた値Ｌｅｖ−ｎdownが１より大きい（すなわち、最後に設定された結合候補節点ｐcombが終端節点でない）か否かを判定する。ここで、Ｌｅｖ−ｎdown＝１ならば、終了条件判定部３７は素ワード伸長検索処理を終了する。一方、Ｌｅｖ−ｎdown＞１ならば、ステップＳ４４において、降下階数変更部３９は、降下階数ｎｄを１だけ増加させる。そして、ステップＳ３９において、素ワード伸長検索処理制御部４０は、｛伸長マッチ部分文字列の位置ｐmatch，現在の素ワードＷprime，現在選択されている節点のレベルＬｅｖ，現在選択されている節点の親節点ｐparent，現在選択されている節点の親節点に対するサイドＳｉｄｅ（Left又はRight），最大許容編集距離Ｔ，現在の相同判定パラメータｋ，現在の降下階数ｎdown｝を入力値として、素ワード伸長検索処理部２９による素ワード伸長検索処理を再帰的に実行する。
【０１２６】
以上の一連の処理によって、素ワード伸長検索処理が実行され、伸長された素ワードによるすべてのマッチの相同性索出データが相同テーブル記憶部２０に蓄積される。
【符号の説明】
【０１２７】
１ 相同性探索装置
２ 入力装置
３ シーケンスデータベース
４ 出力装置
１０ 検索対象シーケンス選択部
１１ 検索対象シーケンス記憶部
１２ クエリシーケンス入力部
１３ クエリシーケンス記憶部
１４ 検索要求ワード設定部
１５ 検索要求ワード記憶部
１６ ワード二分木生成部
１７ ワード二分木テーブル記憶部
１８ 最大許容編集距離設定部
１９ 検索実行部
２０ 相同テーブル記憶部
２５ クエリ素ワード設定部
２６ 素ワード記憶部
２７ 完全一致検索部
２８ 完全一致位置記憶部
２９ 素ワード伸長検索処理部
３０ 降下階数初期化部
３１ 結合候補節点設定部
３２ 伸長素ワード設定部
３３ 比較対象シーケンス抽出部
３４ 最小編集距離演算部
３５ 編集距離閾値設定部
３６ 相同条件判定部
３７ 終了条件判定部
３８ 素ワード更新部
３９ 降下階数変更部
４０ 素ワード伸長検索処理制御部
【特許請求の範囲】
【請求項１】
所定の種類の文字又は記号の文字列からなる検索対象シーケンスを記憶する検索対象シーケンス記憶手段と、
前記検索対象シーケンス内の相同な文字列を検索するために検索条件として設定される文字列である検索要求ワードを記憶する検索要求ワード記憶手段と、
前記検索要求ワードを段階的に順次二分割してなる完全二分木又は不完全二分木であるワード二分木のデータを記憶するワード二分木テーブル記憶手段と、
前記検索要求ワードを分割して生成される素ワードを記憶する素ワード記憶手段と、
前記検索対象シーケンス内における前記素ワードに一致するマッチ部分文字列の位置を記憶する完全一致位置記憶手段と、
前記素ワード，前記検索要求ワード内における前記素ワードの位置，前記マッチ部分文字列，及び検索対象シーケンス内における前記マッチ部分文字列の位置を含む相同性索出データを記憶する相同テーブル記憶手段と、
２つの文字列が相同と判定するための許容編集距離の最大値である最大許容編集距離Ｔを入力手段により取得する最大許容編集距離設定手段と、
前記検索要求ワード記憶手段に記憶された前記検索要求ワードを（Ｔ＋１）個の前記素ワードに分割し、終端節点が（Ｔ＋１）個の前記各素ワードに対応する前記ワード二分木を生成し、前記ワード二分木テーブル記憶手段に前記ワード二分木テーブルとして格納するワード二分木生成手段と、
前記ワード二分木の各終端節点を順次選択し、選択した終端節点に対応する素ワードを前記素ワード記憶手段に格納するクエリ素ワード設定手段と、
前記素ワード記憶手段に記憶された前記素ワードに基づき、前記検索対象シーケンス内における当該素ワードと完全に一致するマッチ部分文字列の位置をすべて索出し、当該マッチ部分文字列の位置を完全一致位置記憶手段に格納するとともに、当該素ワード，当該素ワードの位置，当該マッチ部分文字列，及び当該マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納する完全一致検索手段と、
前記完全一致位置記憶手段に記憶された前記各マッチ部分文字列について、前記素ワード記憶手段に記憶された前記素ワードに対し、前記ワード二分木に従って、当該素ワードの節点に双対する節点に対応する部分ワードを当該素ワードに結合した伸長素ワード、及び前記伸長素ワードに対応する節点に双対する節点又はその子孫節点に対応する部分ワードを当該伸長ワードに結合した伸長素ワードを順次生成し、前記各伸長素ワードのうち、当該マッチ部分文字列を当該伸長素ワードと同方向に伸長した文字列である伸長マッチ部分文字列が当該伸長素ワードと相同な場合に、当該伸長素ワード，当該伸長素ワードの位置，当該伸長マッチ部分文字列，及び当該伸長マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納するワード伸長検索処理を行うワード伸長検索処理手段と、を備えたことを特徴とする相同性検索装置。
【請求項２】
前記最大許容編集距離設定手段は、前記最大許容編集距離Ｔに１を加えた値を相同判定パラメータｋの初期値に設定するものであり、
前記ワード伸長検索処理手段は、
前記ワード伸長検索処理の開始時に、降下階数ｎｄを０に初期化するとともに、［ｋ／２］（［ ］はガウス記号）の値を前記相同判定パラメータｋの新たな値に更新する降下階数初期化手段と、
前記素ワード記憶手段に記憶された現在の前記素ワードに対応する前記ワード二分木の節点が、左側子節点の場合にはそれに双対する右側子節点から左枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定し、右側子節点の場合にはそれに双対する左側子節点から右枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定する結合候補節点設定手段と、
前記結合候補節点に対応する結合候補素ワードを前記検索要求ワード記憶手段から読み出し、現在の前記素ワードに前記結合候補素ワードを結合した結合ワードを前記伸長素ワードに設定する伸長素ワード設定手段と、
前記伸長素ワードに対応して、前記マッチ部分文字列を伸長した部分文字列を前記検索対象シーケンスから抽出し、比較対象シーケンスに設定する比較対象シーケンス抽出手段と、
前記比較対象シーケンスから前記伸長素ワードとの距離が最小となる前記伸長マッチ部分文字列を抽出し、当該伸長マッチ部分文字列と前記伸長素ワードとの距離である最小編集距離Ｌｃを算出する最小編集距離演算手段と、
前記最大許容編集距離Ｔと前記相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］に設定する編集距離閾値設定手段と、
前記最小編集距離Ｌｃと前記編集距離閾値Ｄｔｈとを比較し、Ｌｃ≦Ｄｔｈの場合には相同条件充足と判定し、前記伸長素ワード，前記伸長素ワードの位置，前記伸長マッチ部分文字列，及び前記伸長マッチ部分文字列の位置を前記相同性索出データとして前記相同テーブル記憶手段に格納する一方、Ｌｃ＞Ｄｔｈの場合には相同条件未充足と判定する相同条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードに対応する前記ワード二分木の節点の親節点が根節点であればワード伸長検索処理を終了し、前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、最後に設定された前記結合候補節点が終端節点であればワード伸長検索処理を終了する終了条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードを前記伸長素ワードに更新し前記素ワード記憶手段に格納するとともに、［ｋ／２］の値を前記相同判定パラメータｋの新たな値に更新する素ワード更新手段と、
前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、降下階数ｎｄを１だけ増加させる降下階数変更手段と、
前記終了条件判定手段によりワード伸長検索処理が終了されるまで、前記結合候補節点設定手段、前記伸長素ワード設定手段、前記比較対象シーケンス抽出手段、前記最小編集距離演算手段、前記編集距離閾値設定手段、前記相同条件判定手段、前記終了条件判定手段、前記素ワード更新手段、及び前記降下階数変更手段によるワード伸長検索処理を反復実行する制御を行うワード伸長検索処理制御手段と、を備えたことを特徴とする請求項１に記載の相同性検索装置。
【請求項３】
前記検索対象シーケンスを構成する文字記号と同種の文字記号の文字列からなるクエリシーケンスを記憶するクエリシーケンス記憶手段と、
前記クエリシーケンスから前記クエリシーケンス内の所定の長さの部分文字列を切り出し、前記検索要求ワードとして前記検索要求ワード記憶手段に格納する検索要求ワード設定手段と、を備え、
前記検索要求ワード設定手段は、前記部分文字列の先頭位置を、前記クエリシーケンスの先頭から１文字ずつ移動させながら前記部分文字列を順次切り出し、前記検索要求ワード記憶手段に格納された前記検索要求ワードを逐次更新するものであり、
前記ワード二分木生成手段は、前記検索要求ワード記憶手段に格納された前記検索要求ワードが更新される毎に、前記ワード二分木を生成し、前記ワード二分木テーブルの更新を行うことを特徴とする請求項１乃至３のいずれか一に記載の相同性検索装置。
【請求項４】
コンピュータに読み込ませて実行させることにより、当該コンピュータを請求項１乃至３のいずれかに記載の相同性検索装置として動作させることを特徴とするプログラム。
【請求項１】
所定の種類の文字又は記号の文字列からなる検索対象シーケンスを記憶する検索対象シーケンス記憶手段と、
前記検索対象シーケンス内の相同な文字列を検索するために検索条件として設定される文字列である検索要求ワードを記憶する検索要求ワード記憶手段と、
前記検索要求ワードを段階的に順次二分割してなる完全二分木又は不完全二分木であるワード二分木のデータを記憶するワード二分木テーブル記憶手段と、
前記検索要求ワードを分割して生成される素ワードを記憶する素ワード記憶手段と、
前記検索対象シーケンス内における前記素ワードに一致するマッチ部分文字列の位置を記憶する完全一致位置記憶手段と、
前記素ワード，前記検索要求ワード内における前記素ワードの位置，前記マッチ部分文字列，及び検索対象シーケンス内における前記マッチ部分文字列の位置を含む相同性索出データを記憶する相同テーブル記憶手段と、
２つの文字列が相同と判定するための許容編集距離の最大値である最大許容編集距離Ｔを入力手段により取得する最大許容編集距離設定手段と、
前記検索要求ワード記憶手段に記憶された前記検索要求ワードを（Ｔ＋１）個の前記素ワードに分割し、終端節点が（Ｔ＋１）個の前記各素ワードに対応する前記ワード二分木を生成し、前記ワード二分木テーブル記憶手段に前記ワード二分木テーブルとして格納するワード二分木生成手段と、
前記ワード二分木の各終端節点を順次選択し、選択した終端節点に対応する素ワードを前記素ワード記憶手段に格納するクエリ素ワード設定手段と、
前記素ワード記憶手段に記憶された前記素ワードに基づき、前記検索対象シーケンス内における当該素ワードと完全に一致するマッチ部分文字列の位置をすべて索出し、当該マッチ部分文字列の位置を完全一致位置記憶手段に格納するとともに、当該素ワード，当該素ワードの位置，当該マッチ部分文字列，及び当該マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納する完全一致検索手段と、
前記完全一致位置記憶手段に記憶された前記各マッチ部分文字列について、前記素ワード記憶手段に記憶された前記素ワードに対し、前記ワード二分木に従って、当該素ワードの節点に双対する節点に対応する部分ワードを当該素ワードに結合した伸長素ワード、及び前記伸長素ワードに対応する節点に双対する節点又はその子孫節点に対応する部分ワードを当該伸長ワードに結合した伸長素ワードを順次生成し、前記各伸長素ワードのうち、当該マッチ部分文字列を当該伸長素ワードと同方向に伸長した文字列である伸長マッチ部分文字列が当該伸長素ワードと相同な場合に、当該伸長素ワード，当該伸長素ワードの位置，当該伸長マッチ部分文字列，及び当該伸長マッチ部分文字列の位置を含む前記相同性索出データを前記相同テーブル記憶手段に格納するワード伸長検索処理を行うワード伸長検索処理手段と、を備えたことを特徴とする相同性検索装置。
【請求項２】
前記最大許容編集距離設定手段は、前記最大許容編集距離Ｔに１を加えた値を相同判定パラメータｋの初期値に設定するものであり、
前記ワード伸長検索処理手段は、
前記ワード伸長検索処理の開始時に、降下階数ｎｄを０に初期化するとともに、［ｋ／２］（［ ］はガウス記号）の値を前記相同判定パラメータｋの新たな値に更新する降下階数初期化手段と、
前記素ワード記憶手段に記憶された現在の前記素ワードに対応する前記ワード二分木の節点が、左側子節点の場合にはそれに双対する右側子節点から左枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定し、右側子節点の場合にはそれに双対する左側子節点から右枝を辿り降下階数ｎｄだけ降下した節点を結合候補節点に設定する結合候補節点設定手段と、
前記結合候補節点に対応する結合候補素ワードを前記検索要求ワード記憶手段から読み出し、現在の前記素ワードに前記結合候補素ワードを結合した結合ワードを前記伸長素ワードに設定する伸長素ワード設定手段と、
前記伸長素ワードに対応して、前記マッチ部分文字列を伸長した部分文字列を前記検索対象シーケンスから抽出し、比較対象シーケンスに設定する比較対象シーケンス抽出手段と、
前記比較対象シーケンスから前記伸長素ワードとの距離が最小となる前記伸長マッチ部分文字列を抽出し、当該伸長マッチ部分文字列と前記伸長素ワードとの距離である最小編集距離Ｌｃを算出する最小編集距離演算手段と、
前記最大許容編集距離Ｔと前記相同判定パラメータｋに基づき、編集距離閾値Ｄｔｈの値を［Ｔ／ｋ］に設定する編集距離閾値設定手段と、
前記最小編集距離Ｌｃと前記編集距離閾値Ｄｔｈとを比較し、Ｌｃ≦Ｄｔｈの場合には相同条件充足と判定し、前記伸長素ワード，前記伸長素ワードの位置，前記伸長マッチ部分文字列，及び前記伸長マッチ部分文字列の位置を前記相同性索出データとして前記相同テーブル記憶手段に格納する一方、Ｌｃ＞Ｄｔｈの場合には相同条件未充足と判定する相同条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードに対応する前記ワード二分木の節点の親節点が根節点であればワード伸長検索処理を終了し、前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、最後に設定された前記結合候補節点が終端節点であればワード伸長検索処理を終了する終了条件判定手段と、
前記相同条件判定手段が相同条件充足と判定し且つ降下階数ｎｄが０の場合、現在の前記素ワードを前記伸長素ワードに更新し前記素ワード記憶手段に格納するとともに、［ｋ／２］の値を前記相同判定パラメータｋの新たな値に更新する素ワード更新手段と、
前記相同条件判定手段が相同条件未充足と判定した場合又は降下階数ｎｄが１以上の場合、降下階数ｎｄを１だけ増加させる降下階数変更手段と、
前記終了条件判定手段によりワード伸長検索処理が終了されるまで、前記結合候補節点設定手段、前記伸長素ワード設定手段、前記比較対象シーケンス抽出手段、前記最小編集距離演算手段、前記編集距離閾値設定手段、前記相同条件判定手段、前記終了条件判定手段、前記素ワード更新手段、及び前記降下階数変更手段によるワード伸長検索処理を反復実行する制御を行うワード伸長検索処理制御手段と、を備えたことを特徴とする請求項１に記載の相同性検索装置。
【請求項３】
前記検索対象シーケンスを構成する文字記号と同種の文字記号の文字列からなるクエリシーケンスを記憶するクエリシーケンス記憶手段と、
前記クエリシーケンスから前記クエリシーケンス内の所定の長さの部分文字列を切り出し、前記検索要求ワードとして前記検索要求ワード記憶手段に格納する検索要求ワード設定手段と、を備え、
前記検索要求ワード設定手段は、前記部分文字列の先頭位置を、前記クエリシーケンスの先頭から１文字ずつ移動させながら前記部分文字列を順次切り出し、前記検索要求ワード記憶手段に格納された前記検索要求ワードを逐次更新するものであり、
前記ワード二分木生成手段は、前記検索要求ワード記憶手段に格納された前記検索要求ワードが更新される毎に、前記ワード二分木を生成し、前記ワード二分木テーブルの更新を行うことを特徴とする請求項１乃至３のいずれか一に記載の相同性検索装置。
【請求項４】
コンピュータに読み込ませて実行させることにより、当該コンピュータを請求項１乃至３のいずれかに記載の相同性検索装置として動作させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−１２８６７２（Ｐ２０１２−１２８６７２Ａ）
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願番号】特願２０１０−２７９６５８（Ｐ２０１０−２７９６５８）
【出願日】平成２２年１２月１５日（２０１０．１２．１５）
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【出願人】（５０４１７４１３５）国立大学法人九州工業大学 (489)
【Ｆターム（参考）】
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願日】平成２２年１２月１５日（２０１０．１２．１５）
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【出願人】（５０４１７４１３５）国立大学法人九州工業大学 (489)
【Ｆターム（参考）】
[ Back to top ]