JP3723760B2 - 生物学的な配列情報処理方法および装置 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、生物学的な複数の配列情報の比較によりホモロジーに関する情報を得る装置に関する。生物学的な配列情報は、典型的にはタンパク質のアミノ酸配列およびＤＮＡの塩基配列である。本発明は、典型的には、２つの配列を行方向および列方向にそれぞれ配置したマトリックス情報を用いる処理に適用され、この種の処理を高速化する。本発明は、３つ以上の配列を比較する処理に適用されてもよい。
【０００２】
【従来の技術】
分子生物学の分野では、ＤＮＡ、遺伝子、タンパク質等の解析のための情報処理技術の有用性が高まっている。そして、ホモロジー検索においても、高速な計算で信頼性の高い結果を得るための各種の方法が提案され、また実用化されている。
【０００３】
周知のように、ホモロジー検索とは、アミノ酸等の複数の配列を比較して、それら配列が似ているか否かを判断したり、どのように似ているかを求めるための技術である。ここでは２つの配列の比較について説明する。ホモロジーの表現には、置換およびギャップを用いることが知られている。置換およびギャップは配列間の変異を表す。タンパク質の場合、置換は、２つの配列の対応する箇所に異なるアミノ酸があることをいう。ギャップは、１方の配列中のあるアミノ酸が他方の配列の対応箇所にないことをいい、アミノ酸の挿入および欠損により生じる。
【０００４】
ホモロジー検索のための情報処理方法およびそのアルゴリズムとしては、動的計画法、ブラスト法およびファスタ法（ＦａｓｔＡ）が知られている。
【０００５】
動的計画法は、最も変異の量が少なくなるような２つの配列の並べ方（アライメント）を求めるために、経路探索技術の原理を適用する。２種類のアミノ酸の変異コストおよびギャップコストを用いて、コストが小さくなる並べ方が求められる。
【０００６】
ブラスト法は、ギャップの挿入を行うことなく、２つの配列間で局所的によく一致する部位（高スコア断片）を探索する。そして、探索された高スコア断片が、その前後に伸長される。
【０００７】
ファスタ法は、２つの配列を行方向および列方向にそれぞれ配置したマトリックスを用いる。このマトリックスは、両配列の一致する箇所を表す要素をもつ。一般には、この要素を点で表す画像情報であるドットマトリックスが用いられる。例えば、タンパク質の場合に、一方の配列のｉ番目のアミノ酸と、他方の配列のｊ番目のアミノ酸が一致するとき、ｉ行ｊ列の位置がプロットされる。そして、ドットマトリックスから、局所的に一致する部分が求められる（ブラスト法の高スコア断片）。この一致部分の周辺領域に対して動的計画法によるアライメントが行われる。そして、長くつながる点列だけを抽出し、表示する処理が行われる。
【０００８】
これらのホモロジー検索は、例えば、「遺伝子とコンピュータ」（小長谷明彦、共立出版株式会社、６７〜７９ページ、２０００年）に説明されている。
【０００９】
これら３つの方法のうち、従来の動的計画法は、計算速度の点で不利である。ブラスト法は、高速な処理ではあるものの、弱いホモロジーを見逃さないといった信頼性の点で不利といわれている。そして、ファスタ法は、ブラスト法ほどではないものの動的計画法より速く、かつ、ブラスト法より信頼性が高い、という特徴を有する。
【００１０】
【発明が解決しようとする課題】
上述のように、ファスタ法は、比較的高い速度と信頼性を提供する。しかし、配列データ量の増大に伴い、さらなる高速化が恒常的に求められる。そして、高速化のためには、計算量を少なくすることが有効と考えられる。もちろん、十分な信頼性を確保しつつ、少ない計算量でのホモロジー検索を可能することが求められる。
【００１１】
本発明は、上記課題に鑑みてなされたものであり、その目的は、高速なホモロジー検索を可能にする配列情報処理装置を提供することにある。
【００１２】
【課題を解決するための手段】
本発明は、上記目的を達成するため、従来のファスタ法で用いられるようなマトリックス情報を用いる。しかし、本発明は、以下のように、ファスタ法とは異なる新たなデータ処理によってホモロジーの情報を得る。また、本発明は、２つの配列を比較する２次元の処理に限定されず、３つ以上の数の配列を比較する処理に適用されてよい。
【００１３】
本発明のある態様は、アミノ酸配列、ＤＮＡ配列等の生物学的な複数の配列情報の比較によりホモロジーに関する情報を得る配列情報処理装置である。本発明の装置は、比較対象の２つの配列情報を受け付ける配列情報取得部と、２次元マトリックス画像情報生成部と、第１抽出処理部および第２抽出処理部と、第２抽出処理部による処理を経た２次元マトリックス画像情報を出力する出力処理部と、を含む。
【００１４】
２次元マトリックス画像情報生成部は、比較対象の２つの配列情報を異なる方向に配置して２次元マトリックス画像情報を生成する２次元マトリックス画像情報生成部であって、２つの配列を比較し、２つの配列の全組合せに対して、２つの配列が一致するとき行列要素として第一の値を設定し、両配列が一致しないとき行列要素として前記第一の値と異なる第二の値を設定する処理を行うことにより、２つの配列の一致箇所を表す要素群で構成される２次元マトリックス画像情報を得る。
第１抽出処理部は、２次元マトリックス画像情報について、２つの配列の一致箇所に対応する要素が斜め方向に所定数以上連続するかどうかを判定し、連続すると判定された要素が抽出された２次元マトリックス画像情報を生成する。
【００１５】
第２抽出処理部は、第１抽出処理部による処理を経た２次元マトリックス画像情報に設定される隣接して並べられた複数の斜め方向の平行四辺形の判定領域を用いて、各判定領域ごとの処理として、判定領域の平行四辺形における一の配列の配置方向の辺の長さである領域幅数と、判定領域内に並ぶ段のうちで配置方向に配列一致箇所の要素が存在しない空段の箇所の数と、の合計が、所定のしきい変異数以下であるかどうかを判定し、しきい変異数以下であると判定された判定領域の要素が抽出された２次元マトリックス画像情報を生成する。
【００１６】
このようにして、配列が一致する箇所が連続するときに要素が並ぶ方向に長く連なる要素群、すなわち、比較対象の配列のホモロジーを表す要素群が抽出される。そして、本発明によれば、第１抽出処理部、第２抽出処理部共に比較的簡素であり、少ない計算量で実現できるので、ホモロジーを表す情報を高速で求めることができる。そして、本発明によれば、上記の処理により、変異数に基づいた判断を簡素な処理で行えるので、計算量がさらに少なくなり、より一層の高速化が可能となる。
【００１７】
本発明では、２つの配列のマトリックス情報に、マトリックス上で斜め方向の平行四辺形の領域が好適に設定される。上記の判定領域は、ホモロジーを表す要素群と同じ方向に延びる。したがってこの構成によれば、ホモロジーを表す要素群と同方向に延びる判定領域を設定することで、正確に必要な情報が得られる。また、第２抽出処理部による処理を実現するためには、「要素が存在しない箇所の数」が、「しきい変異数と領域幅数の差」と比較されてもよい。
【００１８】
上述の配列情報処理装置において、第１抽出処理部は、２次元マトリックス画像情報について、２つの配列の一致箇所に対応する要素が斜め方向に３以上連続するかどうかを判定してもよい。
【００１９】
上述の配列情報処理装置において、第１抽出処理部は、２つの配置方向の少なくとも一つに関して、２つの配列の一致箇所に対応する３つの要素が連続するかどうかを判定し、連続すると判定された３つの要素のうちの中央の要素を抽出しないように構成してもよい。この構成によれば、第２抽出処理部で処理されるべき要素が減るので、さらなる高速化が可能である。
【００２０】
上述の配列情報処理装置において、第２抽出処理部による処理を経た前記２次元マトリックス画像情報が示すホモロジーを表現した配列情報を生成するホモロジー配列生成処理部をさらに含んでもよい。この構成によれば、高速な計算により抽出された要素群を用いて、複数配列のホモロジーを表現した有用な情報が得られる。
【００２１】
上述の配列情報処理装置において、ホモロジー配列生成処理部は、ギャップおよび置換を含んだ情報を生成してもよい。この構成によれば、高速な計算により抽出された要素群を用いて、複数配列のホモロジーを表現した有用な情報が得られる。
【００２２】
上述の配列情報処理装置において、２次元マトリックス画像情報のうち、判定領域が設定されない縁部に残る２つの配列の一致箇所に対応する要素を削除する縁部調整処理部をさらに含んでもよい。例えば、マトリックスを平行四辺形の領域で分割するとき、マトリックスの縁部には領域が設定されないために、マトリックスの縁部に不要な要素が残ることがある。このような要素が、この構成の縁部調整処理部により削除されるので、ホモロジーを表す情報がより正確に求められる。
【００２３】
上述の配列情報処理装置において、第２抽出処理部による処理を経た２次元マトリックス画像情報において、２つの配置方向の少なくとも一つに関して、その配置方向に複数の抽出された要素が残っているとき、その残った要素が周囲の抽出された要素と形成する連続部分の長さに基づいて不要な要素を削除する長さ比較調整処理部をさらに含んでもよい。この構成によれば、第２抽出処理部にて残った不要な要素が削除されるので、ホモロジーを表す情報がより正確に求められる。
【００２４】
上述の配列情報処理装置において、出力処理部は、第２抽出処理部による処理を経た前記２次元マトリックス画像情報を画面に表示する表示処理部を含んでもよい。この構成によれば、抽出された要素群が描く線が画面表示される。この画面表示は、ホモロジーを視覚的に表す情報として、有用に利用される。
【００２６】
本発明の別の態様の配列情報処理装置は、アミノ酸配列、ＤＮＡ配列等の生物学的な２つの配列情報の比較によりホモロジーに関する情報を得る配列情報処理装置であって、比較対象の２つの配列情報を取得する配列情報取得部と、比較対象の２つの配列情報を異なる方向に配置して２次元マトリックス画像情報を生成する２次元マトリックス画像情報生成部であって、２つの配列を比較し、２つの配列の全組合せに対して、２つの要素が類似するとき行列要素として第一の値を設定し、２つの要素が類似しないとき行列要素として第一の値と異なる第二の値を設定する処理を行うことにより、２つの配列の類似箇所を表す要素群で構成される２次元マトリックス画像情報を得る２次元マトリックス画像情報生成部と、２次元マトリックス画像情報について、２つの配列の類似箇所に対応する要素が斜め方向に所定数以上連続するかどうかを判定し、連続すると判定された要素が抽出された２次元マトリックス画像情報を生成する第１抽出処理部と、第１抽出処理部による処理を経た２次元マトリックス画像情報に設定される隣接して並べられた複数の斜め方向の平行四辺形の判定領域を用いて、各判定領域ごとの処理として、判定領域の平行四辺形における一の配列の配置方向の辺の長さである領域幅数と、判定領域内に並ぶ段のうちで配置方向に配列一致箇所の要素が存在しない空段の箇所の数と、の合計が、所定のしきい変異数以下であるかどうかを判定し、しきい変異数以下であると判定された判定領域の要素が抽出された２次元マトリックス画像情報を生成する第２抽出処理部と、第２抽出処理部による処理を経た２次元マトリックス画像情報を出力する出力処理部と、を含む。この構成では、例えば、アミノ酸等が類似する箇所（一致する箇所を含む）を表す要素をもった２次元マトリックス画像情報を用いる。類似を考慮することで、ホモロジー検索の信頼性が増大する。一致部位に対応する要素のみを使う方法と比べると計算量は増加するものの、それでも従来と比べて少ない計算量でホモロジー検索を実現できる。
【００２７】
本発明は、上述した装置の態様には限定されない。本発明の別の態様は、例えば、上記装置としてコンピュータを機能させるためのプログラムであり、また、そのようなプログラムを記録したコンピュータ可読媒体である。
【００２８】
【発明の実施の形態】
以下、本発明の好適な実施の形態（以下、実施形態という）を説明する。
【００２９】
本実施形態では、生物学的な配列の一形態であるアミノ酸配列の情報処理に本発明が適用される。もちろん、本発明は、別の配列情報、例えば、塩基配列の情報処理に適用されてもよい。
【００３０】
また、本実施形態では、本発明が、２つの配列を比較する情報処理に適用される。この情報処理は、比較対象である第１配列および第２配列を異なる方向に配置したときの両配列の一致箇所を表す要素をもつ２次元マトリックス情報を用いる。
【００３１】
本実施形態では、２つの配列を配置する方向を、行方向および列方向という。また、斜め方向は、第１配列および第２配列が連続して一致するときに要素が並ぶ方向である。本実施形態では、画像情報が用いられ、第１配列と第２配列が直交するように配置され、要素間の間隔が行方向と列方向で同じなので、斜め方向は、行方向および列方向に対して４５度の角度をなす方向である。
【００３２】
図１は、本発明の一形態の配列情報処理装置のハードウエア構成を示す。配列情報処理装置１は、ＣＰＵ３、ＲＯＭ５、ＲＡＭ７、ハードディスク９、媒体装着部１１、キーボード１３、マウス１５、ディスプレイ１７および通信装置１９を含む。
【００３３】
キーボード１３およびマウス１５、ディスプレイ１７および通信装置１９は入出力装置として機能する。さらに他の入出力装置も適宜設けられてよい。また、通信装置１９は、赤外線通信等により近傍の装置と通信する装置でもよく、また、ＬＡＮ、インターネット等の通信を行う装置でもよい。これらの複数種類の通信装置が設けられてもよい。
【００３４】
また、媒体装着部１１は、フレキシブルディスク、コンパクトディスク等の記録媒体が装着される。媒体装着部１１も、記録媒体への情報の入出力装置と見ることができる。
【００３５】
配列情報処理装置１は、汎用のコンピュータであってよい。本実施形態の情報処理機能をコンピュータに実現させるプログラムをインストールすることにより、配列情報処理装置１が構成される。
【００３６】
図２は、配列情報処理装置１の構成を示す機能ブロック図である。図示の各構成要素は、上記プログラムを実行することにより実現される。図示のように、配列情報処理装置１は、配列情報取得部２０、マトリックス情報生成部２２、第１抽出処理部２４、第２抽出処理部２６、縁部調整処理部２８、長さ比較調整処理部３０、ホモロジー配列生成処理部３２および出力処理部３４を含む。以下、これらの各構成要素を、図面を参照して説明する。
【００３７】
図３は、配列情報取得部２０により取得される、比較対象のアミノ酸配列情報の例である。配列情報は、例えば、媒体装着部１１に装着された記録媒体から読み出される。このとき、媒体装着部１１は配列情報の入力装置として機能する。配列情報は、通信装置等の他の手段を用いて取得されてもよい。また配列情報は、ハードディスク９から読み出されてもよい。
【００３８】
マトリックス情報生成部２２は、配列情報取得部２０により取得された２つの配列からマトリックス情報を生成する。マトリックス情報生成部２２は、一方の配列におけるｉ番目の文字（アミノ酸）と、ｊ番目の文字（アミノ酸）を比較する。２つの文字が一致するとき、行列要素（成分）として１が設定される。２つの文字が一致しないとき、行列要素として０が設定される。この処理を両配列の文字の全組合せに対して行うことによりマトリックス情報（ＤＰ行列）が得られる。さらに、マトリックス情報生成部２２は、マトリックス情報を表す２値画像を生成する。画像中で、行列要素１に対応する位置に点（ドット）が打たれる。
【００３９】
図４は、上記のようにして得られたマトリックス情報の画像を示す。図４の例は、ＣＲＥ−ＢＰ１のアミノ酸配列とＭＵＳＭＸＢＰのアミノ酸配列から得られたマトリックスである。
【００４０】
こうして得られたマトリックスは、一方の配列を行方向に、他方の配列を列方向に配置したときの両配列の一致する箇所を表す「要素」をもつ。「要素」は、本実施形態では画像上の点である。
【００４１】
マトリックス情報は、例えば、Ｊａｖａ（登録商標）プログラムを用いて生成される。このプログラムには、２つの配列を比較するための関数が用意される。この関数は、両配列の文字が一致する場合には１を、その他の場合には０を要素にもつマトリックスを返す。さらに、同プログラムにより、１に対応する画像上の位置に点が打たれる。上記の処理は、Ｈａｓｈテーブルを用いることで、より高速に行うことができる。
【００４２】
以下、本実施形態は、図４のマトリックスを用いた画像処理を通じて、「意味のある情報」、すなわち、ホモロジーを表す情報を求める。求められるべき情報は、概略的には、直線上の点群であり、この直線は、（１）なるべく長く、（２）傾きがマイナス４５度（右下がり）である（縦方向と横方向の画素間隔が同一である場合）。
【００４３】
図４では、既に、ホモロジーを表す斜めのラインが比較的明瞭に現れている。このライン上の点が以降の処理で抽出される。ホモロジーのラインが図４ほどに明瞭でない場合でも、以降の処理によってラインが抽出される。
【００４４】
また、上記のように本実施形態では、図４の画像を用いて画像処理が行われる。しかし、好ましい変形例では、前段で得られたマトリックス情報、すなわち１、０の要素をもつマトリックス情報を用いて処理が進められてもよい。
【００４５】
さて、ホモロジーを表すラインは、主として、第１抽出処理部２４および第２抽出処理部２６により抽出される。このうち、第１抽出部２４は、図４のマトリックス画像から、両配列の一致箇所に所定の連続性が見られる部分を抽出する。一致箇所が連続するところでは画像中の点が斜めに並ぶので、第１抽出部２４は、斜め方向に所定の連続性をもった点を抽出する。
【００４６】
図５は、第１抽出処理部２４の処理に用いられるフィルタを示す。このフィルタは、斜め方向に３つの点が続くとき、それらの点を残す。このような点が、本実施形態では、上記の所定の連続性をもった点に相当する。その他の場合には点が削除される。ここで、斜め方向は、既に述べたように、縦方向および横方向に同数の画素だけ進む方向（４５度）である。
【００４７】
図６は、フィルタによる抽出後の画像を示す。ホモロジーに関係ない多くの点が消えている。しかし、依然として多くの不要な点が残っている。このように、第１抽出部２４は、以下の第２抽出部２６による処理の前処理として、ラフな抽出処理を行う。
【００４８】
次に、第２抽出部２６による抽出処理を説明する。
【００４９】
図７に示されるように、第２抽出部２６は、マトリックス上に複数の帯状の判定領域を設定する。各判定領域の形状は平行四辺形である。マトリックスを多数の平行四辺形へと分割することにより判定領域が設定される。判定領域は、マトリックス上に敷き詰めるようにして設けられる。
【００５０】
図８は、一つの判定領域を示している。図示のように、本実施形態の例では、各判定領域の高さ（帯高さ）は１０画素、幅（帯幅）は５画素である。帯幅数（点の数）は、本発明の領域幅数に相当する。平行四辺形の斜辺の角度は４５度である。したがって、判定領域は、本実施形態の斜め方向、すなわち配列情報が連続して一致するときに要素が並ぶ方向へと延びる。
【００５１】
第２抽出処理部２６は、設定された複数の判定領域を用いて抽出処理を行う。抽出処理は、各判定領域ごとに行われる。第２抽出処理部２６は、判定領域内の点の分布に基づき、配列変異に関する所定の分布をもつ判定領域内の点を領域単位で抽出する。所定の分布は、本実施形態では、領域内の変異数が所定のしきい変異数以下であると判断されるような分布である。このような分布をもつ領域内のすべての点が抽出される。変異数がしきい変異数を越えると判断されるときは、領域内のすべての点が消去される。
【００５２】
変異は、周知のように、置換とギャップを含む。置換は、２つの配列の対応する箇所に異なるアミノ酸があることをいう。ギャップは、一方の配列のアミノ酸を他方の配列がもたないことをいう。ギャップは、アミノ酸の挿入または欠損により生じる。本実施形態の変異数は、置換とギャップの総数である。
【００５３】
しきい変異数に関しては、下記の特殊な判定が行われる。領域内で点が存在しない行を、本実施形態では、空行と呼ぶ。空行は、本発明における、判定領域内で一の配列の配置方向に要素が存在しない箇所に相当する。空行数と帯幅数の合計がしきい変異数以下のとき、第２抽出部２６は、領域内の変異数がしきい変異数以下と判定し、領域内の点を残す。実際の処理では、第２抽出処理部２６は、空行の数が、しきい変異数と帯幅数の差以下であるか否かを判定すればよい。
【００５４】
このような簡単な処理によって必要な判定を行える理由を説明する。
【００５５】
図９は、２つの類似する配列の一部を示している。ここでは、説明を簡単にするために、実際のアミノ酸を表す文字の代わりに、文字Ａ〜Ｅを用いる。
【００５６】
図９（ａ）は、変異がない場合を示す。この場合、マトリックス上の点が斜めに並ぶ。図９（ｂ）は、置換がある場合を示す。置換があるとき、図示のように空の行が発生する（空の列も同時に発生する）。図９（ｃ）は、行方向（横方向）の配列にギャップがある場合を示す。この場合は、マトリックス上で空の行が発生する。図９（ｄ）は、列方向の配列にギャップがある場合を示す。この場合は、マトリックス上で空の列が発生するとともに、ラインが幅方向に１画素ずれる。図９（ｄ）については、主にラインのずれに着目する。
【００５７】
ホモロジーを表すラインが判定領域を通過するとして、空行数は、置換数（図９（ｂ））と、行方向の配列のギャップ数（図９（ｃ））との合計を示す。一方、列方向の配列に一つのギャップがあると、図９（ｄ）に示されるように、ラインが行方向に１画素ずれる。したがって、「帯幅数」は、列方向の配列が領域内でもつギャップの最大数に相当する。以上より、空行数と帯幅数の合計がしきい変異数以下であれば、すなわち、空行数が「２」（＝７（しきい変異数）−５（帯幅数））以下であれば、全変異数はしきい変異数であるといえる。
【００５８】
図１０の例では、ホモロジーを表すラインが判定領域を通っている。この場合、置換数が１であり、行方向の配列のギャップ数が１である。空行数が２以下なので、この領域の点は抽出される。
【００５９】
図１１の例では、ホモロジーを表すラインが判定領域を通っていない。この場合、領域内の点は、ラインを形成していない。たまたま、２組の連続点が領域内に存在するだけである。そして、この場合には空行の数が多いので、領域の点は消去される。
【００６０】
ところで、上記の抽出処理には、以下のような限界がある。
【００６１】
図１２を参照する。この例の場合、領域内には、置換が２カ所にある。また、行方向の配列のギャップが１カ所にある。一方、列方向の配列のギャップはない。したがって、空行数は３であり、また、全変異数も３である。この場合、全変異数は７以下であるにも拘わらず、領域が抽出対象から外されてしまう。
【００６２】
本実施形態は、このような状況を許容している。ホモロジーを表すラインが領域を通っていれば、図１２のような状況が生じる可能性は低い。そこで、空行が所定数以下であれば（空行数と帯幅数の合計がしきい変異数以下であれば）、領域の変異数がしきい変異数以下であるとみなしている。
【００６３】
同様に、領域形状およびしきい変異数の設定を変更したとき、逆の状況、すなわち、実際のしきい数がしきい変異数以上であるにも拘わらず領域内の点が抽出される状況が仮にあったとしても、本実施形態はこのような状況を許容する。
【００６４】
図１３は、第２抽出処理部２６による抽出処理が施されたマトリックス画像を示している。本実施形態の例では、上述のように、帯高さは１０であり、帯幅数は５である。また、しきい変異数は７である。したがって、図１３では、空行数が２以下である領域のみの点が残っている。この条件は、比較的ゆるい。それにも拘わらず、図１３に示されるように、殆どの不要な点が効果的に削除される。これは、本実施形態の抽出処理が、簡単な処理であるにも拘わらず、非常に有効であることを示す。
【００６５】
以上、第２抽出処理部２６による抽出処理を説明した。図１３に示されるように、上記の抽出処理を経ても、依然として不要な点が残っている。この不要な点は以下の処理で削除される。この削除処理は、縁部調整処理部２８および長さ比較調整処理部３０により行われる。
【００６６】
まず、縁部調整処理部２８の処理を説明する。
【００６７】
図１４は、マトリックス画像の縁部を部分的に示している。マトリックス画像上には、完全な形状の判定領域のみが設定される。中途半端な形状の判定領域は設定されない。その結果、画像の縁部には、判定領域が設定されない。
【００６８】
例えば画像の上下の縁部を考える。画像の高さが、判定領域の高さの整数倍でないとき、上下の縁の少なくとも一方には、判定領域が設定されない。また、横方向の縁部に着目すると、平行四辺形の判定領域を並べたとき、画像の縁部が判定領域で完全に覆われることはあり得ない。図１４から明らかなように、平行四辺形の集合の端部はギザギザの線を描くからである。
【００６９】
このように縁部に判定領域が設定されないので、縁部に対しては第２抽出処理部２６の処理も行われない。その結果、図１３に示されるように、縁部には、ホモロジーに関係ない不要な点が残っている。そこで、縁部調整処理部２８は、縁部の点を削除する。本実施形態では、判定領域が設定されない場所にある全部の点が削除される。
【００７０】
図１５は、縁部の修正が行われたマトリックス画像を示す。縁部の不要な点が消えている。
【００７１】
次に、長さ比較調整処理部３０の処理を説明する。長さ比較調整処理部３０は、以下に説明するようにして、マトリックス画像において一つの行に対して複数の点が残っているとき、各要素が前後行の点と形成する連続部分の長さに基づいて不要な点を削除する。
【００７２】
図１６を参照する。ホモロジーを表すライン上の点群だけが抽出されたとすると、１つの行には１つの点のみが存在するはずである。したがって、１つの行に複数の点があるときは、それらの中の一つの点のみが、ホモロジーのライン上の点として残されるべきである。残されるべき点は、斜め方向の長いライン（点列）の一部である。図１６では、点Ａが残され、点Ｂが消去されるべきである。
【００７３】
そこで、長さ比較調整処理部３０は、各行ごとに、複数の点があるか否かを調べる。複数の点があるときは、各点ごとに、前後の行の点と共に形成するラインの長さを求める。最も長いラインを形成する点が残される。その他の点は削除する。この際、図１０に示されるような状況では、一続きのラインが形成されているとみなすことが好ましい。そこで、比較調整処理部３０は、所定数（例えば２個）以下の変異（置換およびギャップ／画像中では空行および空列）を挟んで点が続くときは、ラインが途切れていないと判定する。
【００７４】
図１７は、長さ比較調整処理部３０の処理を施されたマトリックス画像を示している。図１５で残っていた不要な点が消去されている。以上のようにして、本ホモロジーのラインが好適に抽出される。
【００７５】
なお、本実施形態では、一つの行に複数の点が残っているときに、不要な点を削除する処理が行われた。変形例では、一つの列に複数の点が残っているときに、同様の処理により、不要な点が削除されてもよい。すなわち、２つの配列の配置方向のどちらを使って修正処理が行われてもよい。また、両方の配列方向に関して上記の処理が行われてもよい。一般に、一つの行に複数の点が残るときは、同時に、一つの列にも複数の点が残る。したがって、行と列のどちらに着目しても、一般にほぼ同じ結果が得られ、実質的に同じ処理であるといえる。
【００７６】
次に、ホモロジー配列生成処理部３２は、図１７のラインが示すホモロジーを表現した配列情報を生成する。図１７のラインは、一方の配列のどの部分が、他方の配列のどの部分と似ているのか、を示している。ラインの上方への写像に対応する配列部分と、同ラインの左方への写像に対応する配列部分とが類似している。類似部分が比較される。この比較を通して、置換およびギャップが求められる。そして、２つの配列が、類似部分の対応関係が分かるように、かつ、置換およびギャップが分かるような状態で並べられる。上記の処理は、コンピュータプログラムにより自動的に行うことができる。
【００７７】
この処理に関し、図９を参照すると明らかなように、マトリックス画像中で空行および空列が同時に発生している所に対応して、置換があり（図９（ａ））、空行のみが発生している所に対応して、行方向の配列にギャップがあり（図９（ｂ））、空列のみが発生している所に対応して、列方向の配列にギャップがある（図９（ｃ））。これらの置換およびギャップが求められ、それらを表現する情報が求められる。空行および空列から得られる変異情報を、該当個所の両配列と照合して、変異情報が適正か否かを確認し、必要な修正を行うことが望ましいと考えられ、この処理も好ましくはコンピュータにより自動的に行われる。
【００７８】
図１８は、上記の処理により得られた配列情報を示す。置換は、対応する文字の相違をもって表される。ギャップは「−」で示される。図中において、ギャップが長く続く箇所が、２つある。これらのギャップ群が発生するのは、図１７でラインが３つに分かれているからである（最も左の部分は極短い）。すなわち、図１７において、横方向に配置された配列は、ラインが途切れる部分に多数のアミノ酸をもつ。これらのアミノ酸は、縦方向の配列には存在しない。そのため、縦方向の配列において多数のギャップが連続する。
【００７９】
配列情報処理装置１は、さらに、出力処理部３４を含む（図２）。出力処理部３４は、表示処理部として機能し、上述の処理を通じて得られる情報をディスプレイ上に表示するための処理を行う。
【００８０】
出力処理部３４は、図１８のギャップ付き配列情報を表示する。また、出力処理部３４は、図１７のマトリックス画像を表示する。この画面表示は、ホモロジーを視覚的に表す情報として、有用に利用される。
【００８１】
出力処理部３４は、上述の処理過程で得られる各段階のマトリックス画像を、ユーザの指示に従って表示してもよい。ユーザの指示は、入力装置を用いて受け付けられる。ユーザは、画面表示を見て、パラメータ等の調整ができる。この調整も入力装置から受け付けられる。この調整に関しては、後述にてさらに説明する。
【００８２】
また、出力処理部３４は、ディスプレイ以外の装置への出力を行ってもよい。プリンタへの出力はもちろん、通信装置を用いて外部へ情報が出力されてもよい。また、フレキシブルディスク等の記録媒体へと情報が格納される。
【００８３】
図１９は、本実施形態による処理の全体概要を示す。配列情報取得部２０が、比較対象の２つの配列情報を取得すると（Ｓ１０）、マトリックス情報生成部２２が、２つの配列情報からマトリックス情報を生成する（Ｓ１２）。マトリックス情報は２値画像へと変換される。第１抽出処理部２４は、マトリックス画像を用いて、斜め方向の連続性に基づいた抽出処理を行う（Ｓ１４）。そして、第２抽出処理部２６が、変異の量に基づいた抽出処理を、複数の判定領域のそれぞれにおいて行う（Ｓ１６）。さらに、縁部調整処理部２８が、マトリックス画像の縁部に残った点を削除する（Ｓ１８）。長さ比較調整処理部３０が、各行に残る複数の点の一つのみを残す調整処理を行う（Ｓ２０）。以上より、ホモロジーを表すラインが得られる。ホモロジー配列生成処理部３２は、得られたラインが示すホモロジーを表現した配列情報（図１８）を生成する（Ｓ２２）。出力処理部３４は、マトリックス画像および配列情報を、ユーザの指示に従って表示する（Ｓ２４）。
【００８４】
図２０は、第１抽出処理部２４の処理で用いられるフィルタの変形例である。前出の図５のフィルタを用いるときは、斜め方向に３つ以上の点が続くとき、それらの点が残される。図２０のフィルタを用いるときは、斜め方向に後側、すなわち斜め下側の画素だけが調べられる。着目する点の斜め下に点があれば、その点は残される。このフィルタを用いるときは、より多くの点が残される。
【００８５】
なお、上記のフィルタの代わりに、斜め上側の画素に点があるか否かを判定するフィルタが用いられてもよい。また、着目点に対して斜め方向の上下のどちらかに点があれば、着目点を残すフィルタ（すなわち、斜めに２つ以上の点がつながれば、それらの点を残すフィルタ）が適用されてもよい。
【００８６】
図２１は、第１抽出処理部２４の処理に適したもう一つのフィルタを示す。このフィルタを用いるとき、３つの点が列方向（縦方向）に並ぶ場合に、中央の点が削除される。図２１のフィルタは、図５のフィルタと組み合わせて用いられる。図５のフィルタの処理に続いて、図２１のフィルタの処理が行われる。図２１のフィルタは、図２０のフィルタと組み合わされてもよい。図２１のフィルタを用いることで、より多くの点が削除されるので、以降の計算量が減り、したがってさらなる高速化が可能となる。
【００８７】
図２２〜図２４を参照して、図２１のフィルタがもつ意味を説明する。図２２に示すように、縦方向配列がＡＡＡＢであり、横方向配列がＡｘｘｘであるとする。Ａ、Ｂ、ｘは一つのアミノ酸であるとする。ｘは、任意のアミノ酸である。このような場合に、縦方向に連続する３点、すなわち、図２１のフィルタの着目する状況が発生する。
【００８８】
図２２の横方向配列に関して、２番目の文字がＢである場合（ＡＢｘｘ）と、３番目の文字がＢである場合（ＡｘＢｘ）を検討する。なお、ＡｘｘｘｘＢのような配列でも、以下の検討においては、結果が同じになる。ＡＡｘｘについては、２番目以降の文字列を考えれば、以下の検討と同じ結果が得られる。
【００８９】
図２３では、横方向配列はＡＢｘｘであり、すなわち２番目の文字がＢである。図示のように点が並び、この範囲での最短経路はラインＬである。そして、この場合、縦方向の３点のうちの中央の点αを削除しても、最短経路は変わらない。したがって、中央の点αは削除されてもよい。
【００９０】
図２４では、横方向配列はＡｘＢｘであり、すなわち３番目の文字がＢである。この範囲での最短経路は、図中の左側に示す３つの経路のいずれかである。図中の右側には、ギャップを使った表現が示されている。どの経路でも、ギャップの数が同じである。変異の量を表すスコアとしてギャップ数を用いるとき、図２２の３つの表現では、スコアが同じである。そして、縦方向の３点の中央の点αを削除したとしても、最短経路は３つのどれかであり、その他の経路にはならない。したがって、中央の点αは削除されてもよい。
【００９１】
以上より、中央の点αを削除したとしても、最短経路が変わらないので、点αは削除されてもよい。そこで、本実施形態は、図２１のフィルタにより、点αを削除する。これにより、以降の処理の計算量が減り、処理を高速化できる。
【００９２】
なお、図２１のフィルタは、列方向の代わりに、行方向の３連続点のうちの中央の点を削除してもよい。また、図２１のフィルタは、列方向に３連続点がある場合と、行方向に３連続点がある場合と、いずれの場合にも、中央の点を削除してもよい。
【００９３】
図２５は、第１抽出処理部２４の好適な構成例を示している。この形態では、第１抽出処理部２４が、複数種類のフィルタを扱える。図２５に示されるように、第１抽出処理部２４は、フィルタ選択部４０、抽出判定部４２および消去処理部４４を有する。
【００９４】
フィルタ選択部４０は、ディスプレイに、選択可能な複数種類のフィルタを提示する。そして、ユーザがキーボードおよびマウスを使って所望のフィルタを選択すると、その選択が受け付けられる。フィルタ選択部４０は、この選択に従って、抽出に使うべきフィルタを設定する。
【００９５】
例えば、図５、図２０および図２１のフィルタが記憶されており、選択可能である。フィルタ選択部４０は、これらの中から、図５、図２０、図５と図２１の組合せ、図２０と図２１の組合せのいずれかを選択、設定する。
【００９６】
抽出判定部４０は、設定されたフィルタを用いて、マトリックス画像中の各点を抽出すべきか否かを判定する。抽出すべき点は残される。その他の点は、消去処理部４４により消去される。
【００９７】
ユーザは、本実施形態の装置を利用するとき、ホモロジー検索に先立ってフィルタを選択する。ユーザが選択しないときは、デフォルトで設定されたフィルタ（例えば図５）が使用される。ユーザは、処理結果を検討して、フィルタを変更できる。このようにして、適切な結果が得られるように適当なフィルタを選ぶことができる。
【００９８】
その他、第１抽出処理部２４は、フィルタ中のパラメータを変更可能に構成されてもよい。例えば、図５のフィルタにおける点の連続数（図５では「３」）が変更されてもよい。
【００９９】
図２６は、第２抽出処理部２６の好適な構成例を示している。この形態では、第２抽出処理部２６が、判定領域の形状を変更可能に構成されている。図２６に示されるように、帯高さ設定部５０、帯幅設定部５２、しきい変異数設定部５４、抽出判定部５６および消去処理部５８を有する。
【０１００】
帯高さ設定部５０、帯幅設定部５２およびしきい変異数設定部５４は、それぞれ、ユーザによる入力操作に従い、帯高さ、帯幅およびしきい変異数といったパラメータを設定する。設定されたパラメータを用いて、抽出判定部５６による処理が行われる。パラメータに従った形状の領域が設定され、領域内の空行数が求められる。そして、抽出判定部５６は、「空行数」が「しきい変異数−帯数」以下か、すなわち、「空行数＋帯幅数」が「しきい変異数」以下かが判定される。判定結果に基づき、抽出すべき点は残される。その他の点は、消去処理部５８により消去される。
【０１０１】
ユーザは、本実施形態の装置を利用するとき、ホモロジー検索に先立って、帯高さ、帯幅、しきい変異数といったパラメータを入力する。しきい変異数の代わりに空行上限数を入力するように構成されてもよい。ユーザが選択しないときは、デフォルト値、例えば、前出の例の通りに帯高さ１０、帯幅５、しきい変異数７が使用される。ユーザは、処理結果を検討して、パラメータを変更できる。このようにして、適切な結果が得られるように適当なパラメータを選ぶことができる。
【０１０２】
パラメータは、第２抽出部処理部２６により自動的に変更されてもよい。一連の処理で適当なホモロジーのラインが得られないとき（各行に１つの点、各列に１つの点が存在し、それらの点が長いラインを描くといった結果が得られないとき）、パラメータを変更する。適当なラインが得られるまで、パラメータを変更しながら、計算が繰り返される。
【０１０３】
図２７は、ホモロジー配列生成処理部３２の構成例を示している。ホモロジー配列生成処理部３２は、対応部分特定部６０、配列作成部６２および修正処理部６４を含む。対応部分特定部６０は、ホモロジーを表すラインから、２つの配列の対応部分を特定する。既に述べたように、図１７のラインを参照して、ラインの上方（横軸）への写像に対応する文字列と、ラインの横方向（縦軸）への写像に対応する文字列（横方向（縦軸）への写像）とが、対応部分として求められる。この対応部分に関して、図１８に示すように、ホモロジーを表現する配列情報が、配列作成部６２により生成される。
【０１０４】
修正処理部６４は、対応部分特定部６０の処理に先立って、ホモロジーのラインを修正する。修正を行うことが望ましい場合の例としては、図１２の場合が挙げられる。図１２では、既に説明したように、実際の変異数が少ないにも拘わらず、領域内の点がすべて削除される。本実施形態は、処理速度を優先する代わりに、このような事態を許容している。ただし、図１２の状況が発生すると、ホモロジーを表すラインが途中で途切れる。この途切れた部分を修復する処理が、修正処理部６２により行われる。修正処理部６２は、例えば、ユーザによる入力操作に従って、途切れた部分を補完する。この補完は、自動的に行われてもよい。例えば、２つの配列の、判定領域に対応する部分が比較され、一致する箇所を表す点の列が再生される。ここでは、従来周知のホモロジー検索技術が適用されてもよい。判定領域が比較的狭いので、補完処理の計算量も比較的少なくてよい。
【０１０５】
修正処理部６２は、ホモロジー配列生成処理部３２に設けられていなくてもよい。ホモロジーのラインを表示するときに、適宜、修正が行われてよい。また、上述の修正に限らず、本装置は、上述の実施形態における任意の段階でユーザの入力操作による指示に応じて（または自動的に）、適切な結果が得られるようにマトリックス画像または配列の適当な修正を行うように構成されてよい。
【０１０６】
本実施形態は、本発明の範囲内で変形可能なことはもちろんである。例えば、本実施形態における各種の処理において、「行」と「列」が入れ替えられてもよいことはもちろんである。例えば、第２抽出処理部２６の処理において、行数の代わりに列数が用いられてもよい。この場合、判定領域の平行四辺形は、縦方向の線および斜め方向の線で構成され、縦方向の線の長さが帯幅に相当する。
【０１０７】
また、本実施形態は、「斜め方向」という表現を用いている。これは、マトリックス上で行方向と列方向に共に進む方向であり、本実施形態のマトリックス画像中では４５であり、そして、マトリックスの成分を基準にしたときの斜め方向である。斜め方向は、上述のように、配列同士が連続して一致するときに点が並ぶ方向である。この点に関し、「配列同士が連続して一致するときに点が並ぶ方向」は、画像の表現によっては、画面上で斜めでないこともあり得る。例えば、マトリックス画像全体を変形し、平行四辺形にしたときは、上記のマトリックス上の「斜め方向」が、画面上では鉛直方向になり得る。このような場合も、マトリックスの成分で見たときに斜め方向であるので、本実施形態では「斜め方向」と呼んでよい。その他の構成も、画像の表現によって視覚的には変更可能であったとしても、本実施形態のようなマトリックスの上で見たときに本発明の範囲内であれば、そのような構成は本発明の範囲内である。
【０１０８】
本実施形態では、隣り合う判定領域は重なっていなかったが、本発明の範囲内で、隣り合う判定領域が重なってもよい。
【０１０９】
本実施形態では、マトリックス情報は、２つの配列におけるアミノ酸の一致を表す要素（成分１、および、画像中の点）をもっていた。別の実施形態形態では、アミノ酸が類似する（一致を含む）ことを表す要素がマトリックス情報に与えられる。アミノ酸の類似度を表すものとして、置換配列（例えばブロッサム６２）が知られている。この置換配列は、アミノ酸の組合せの変異コストを表す。この変異コストが所定値以上のとき、マトリックス情報に成分１が与えられる。その他の場合には、成分０が与えられる。このようにして得られたマトリックス情報、およびそれから得られるマトリックス画像（２値画像）は、上述の実施形態と同じように処理される。
【０１１０】
本変形例では、マトリックス画像中の点の数が上述の実施形態よりも増加するので、計算速度は少し遅くなる可能性がある。しかし、従来と比べれば、計算速度は大幅に増大し、本発明の利点が得られる。また、類似を考慮することによる信頼性の向上が期待できる。
【０１１１】
また、本実施形態では、配列情報の取得から、マトリックスの生成、ホモロジーのラインの抽出、ホモロジーを表現する配列の生成までが、一貫して行われた。これに対し、配列情報処理装置１は、既にできあがったマトリックス情報を外部から取得してもよい。また、配列情報処理装置１は、ホモロジーを表現した配列を作る機能はもっていなくてもよい。図１７のような画像だけでも相当に有用な情報が視覚的に得られる。
【０１１２】
また、本実施形態ではアミノ酸配列が処理されたが、アミノ酸以外の配列情報の処理にも本発明は適用可能である。典型的には、塩基配列の処理に本発明を適用可能である。
【０１１３】
また、本実施形態の配列情報処理装置１は、インターネット等のネットワークに接続されてもよい。あるコンピュータからネットワークを経由して配列情報が検索依頼とともに送られてくる。配列情報処理装置１は、配列情報からホモロジーの処理を行って、処理結果を返す。各種の条件、例えば、領域形状に関するパラメータも、ネットワークを通じて取得される。
【０１１４】
以上、本発明の好適な実施形態を説明した。本実施形態においては、上述のように、第１抽出処理部２４による第１抽出ステップは、マトリックス情報から、斜め方向に連続する要素を抽出する。次に、第２抽出処理部２６による第２抽出ステップは、マトリックス情報に設定される複数の判定領域を用いて、各判定領域ごとに抽出処理を行い、変異の少ない判定領域内の要素が抽出する。このようにして、マトリックス上で斜め方向に長く連なる要素群が抽出される。第１抽出ステップ、第２抽出ステップ共に比較的簡素であり、少ない計算量で実現できるので、ホモロジーを表す情報を高速で求めることができる。
【０１１５】
また、第２抽出ステップは、マトリックス情報上に斜め方向に延びる帯状の判定領域、本実施形態では平行四辺形の領域を設定する。斜め方向、すなわち、配列一致箇所が連続するときに要素が並ぶ方向に延びる判定領域が用いられる。ホモロジーを表す要素群と同方向に延びる判定領域が設定されるので、正確に必要な情報が得られる。
【０１１６】
また、第２抽出ステップは、領域幅数と、幅方向に要素がない箇所の数との合計（上述の処理では帯幅数と空行数との合計）がしきい変異数以下のときに、判定領域内の要素を抽出する。変異数に関する判定が簡単なので、計算量が少なく、したがって一層の高速化が可能となる。
【０１１７】
また、第１抽出ステップは、図２１のフィルタを用いて、配列の配置方向に連続する３要素のうちの中央の要素を抽出しない。これにより、第２抽出ステップで処理されるべき要素が減るので、さらなる高速化が可能である。
【０１１８】
また、本発明は、抽出された要素群が示すホモロジーを表現した配列情報を生成する。好ましくは、ギャップおよび置換を含んだ情報が生成される。高速な計算により抽出された要素群を用いて、両配列のホモロジーを表現した有用な情報が得られる。
【０１１９】
また、本発明は、マトリックスの縁部に判定領域を設定するのが困難なことに配慮して、第２抽出ステップを経たマトリックス情報から縁部に残る要素を削除する。これにより、不要な点が効果的に削除され、ホモロジーを表す情報がより正確に求められる。
【０１２０】
また、本発明は、第２抽出ステップを経たマトリックス情報において配列の配置方向に複数の要素が残っているとき、その残った要素が周囲の要素と形成する連続部分の長さに基づいて不要な要素を削除する。より短い連続部分を形成する方の要素が削除される。そして、最も長い連続部分を形成する要素が残される。本発明によれば、第２抽出ステップにて残った不要な要素が削除されるので、ホモロジーを表す情報がより正確に求められる。
【０１２１】
また、本発明は、抽出された要素群をもったマトリックス情報を画面に表示する。これにより、抽出された要素群が描く線が画面表示される。この画面表示は、ホモロジーを視覚的に表す情報として、有用に利用される。
【０１２２】
本実施形態では、２つの配列が比較された。しかし、本発明の範囲内で、３つ以上の配列が比較されてもよいことはもちろんである。
【０１２３】
ｎ個の配列を比較するとき、例えば、ｎ個のうちの２つの配列の２次元マトリックス情報が、本発明の複数次元要素群情報（比較対象の複数の配列情報を異なる方向に配列したときのそれらの一致箇所を表す要素群で構成される情報）として、利用される。この２次元マトリックス情報を用いて、上述の実施形態で説明した２次元の処理が行われる。
【０１２４】
ここでは、一つの配列が基準に設定されてもよい。基準の配列と、残りの複数配列の各々との組合せによる２次元マトリックス情報からホモロジー検索が行われる。また、ｎ個の配列から選ばれる種々の２配列の組合せ関して、２次元マトリックス情報を用いたホモロジー検索が行われてもよい。このような処理は、上述した２次元の処理の組合せであり、本発明に含まれる。
【０１２５】
また、ｎ個の配列を比較するとき、ｎ個の配列の一致箇所を表す要素をもつｎ次元の情報が、本発明の複数次元要素群情報として用いられてもよい。例えば、ｎ＝３のとき、３つの配列を異なる方向に配置したときの、それらの一致箇所を表す要素群で構成される情報が用いられる。より詳細な例では、３つの配列が、それぞれ、直交するｘ軸、ｙ軸、ｚ軸にそって配置される。ｘ軸、ｙ軸、ｚ軸が形成する空間内で、３つの配列が一致する箇所に対応する位置に点が設定される。これにより、２次元マトリックス情報を３次元に拡張した、立体的な情報が得られる。この３次元の要素群情報を対象として、上述の実施形態に従い、ホモロジー検索の処理が行われる。ホモロジーを表すライン（点列）は、ｘ軸、ｙ軸およびｚ軸に対して４５度をなす。このように、本発明の範囲内で、上述の２次元の処理がｎ次元の処理へと拡張されてもよく、そして、本発明を構成する各種処理について、上述の２次元の処理と同様の原理をｎ次元に適用した処理が行われてよく、このような処理を行う構成も本発明に含まれる。
【０１２６】
以上のように、本発明の範囲内で、３つ以上の配列が比較されてもよい。この点は、上述した、複数配列の類似箇所を表す要素をもつマトリックス情報を使う実施形態においても同様である。
【０１２７】
【発明の効果】
以上に説明したように、本発明によれば、高速なホモロジー検索を可能にする配列情報処理装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の実施形態における配列情報処理装置のハードウエア構成を示す図である。
【図２】配列情報処理装置のソフトウエア構成を示す機能ブロック図である。
【図３】配列情報取得部により取得される比較対象のアミノ酸配列情報の例を示す図である。
【図４】図３の２つの配列から作られるマトリックス情報の画像を示す図である。
【図５】図２の第１抽出処理部に用いられるフィルタを示す図である。
【図６】第１抽出処理部による処理後のマトリックス画像を示す図である。
【図７】マトリックス画像上に設定される複数の帯状の判定領域を示す図である。
【図８】図７に示される複数の判定領域の一つを示す図である。
【図９】変異が画像に及ぼす影響を示す図である。
【図１０】第２抽出処理部による抽出対象になる場合の例を示す図である。
【図１１】第２抽出処理部による抽出対象にならない場合の例を示す図である。
【図１２】例外的に、第２抽出処理部による抽出対象にならない場合の例を示す図である。
【図１３】第２抽出処理部による処理後のマトリックス画像を示す図である。
【図１４】マトリックス画像の縁部における判定領域の配置を示す図である。
【図１５】縁部の修正が行われたマトリックス画像を示す図である。
【図１６】１つの行に複数の点があるときの調整処理を示す図である。
【図１７】図１６の処理が施されたマトリックス画像を示す図である。
【図１８】図１７の抽出結果から作られる、ホモロジーを表現する配列情報を示す図である。
【図１９】配列情報処理装置による処理の全体概要を示す図である。
【図２０】第１抽出処理部により用いられるフィルタの変形例を示す図である。
【図２１】第１抽出処理部により付加的に用いられる好適なフィルタを示す図である。
【図２２】図２１のフィルタが適用可能なことを説明するための図である。
【図２３】図２１のフィルタが適用可能なことを説明するための図である。
【図２４】図２１のフィルタが適用可能なことを説明するための図である。
【図２５】第１抽出処理部の好適な構成例を示す図である。
【図２６】第２抽出処理部の好適な構成例を示す図である。
【図２７】ホモロジー配列生成処理部の好適な構成例を示す図である。
【符号の説明】
１ 配列情報処理装置
２０ 配列情報取得部
２２ マトリックス情報生成部
２４ 第１抽出処理部
２６ 第２抽出処理部
２８ 縁部調整処理部
３０ 長さ比較調整処理部
３２ ホモロジー配列生成処理部
３４ 出力処理部

Claims (9)

1. アミノ酸配列、ＤＮＡ配列等の生物学的な２つの配列情報の比較によりホモロジーに関する情報を得る配列情報処理装置であって、
   比較対象の２つの配列情報を受け付ける配列情報取得部と、
   前記比較対象の２つの配列情報を異なる方向に配置して２次元マトリックス画像情報を生成する２次元マトリックス画像情報生成部であって、前記２つの配列を比較し、前記２つの配列の全組合せに対して、前記２つの配列が一致するとき行列要素として第一の値を設定し、両配列が一致しないとき行列要素として前記第一の値と異なる第二の値を設定する処理を行うことにより、前記２つの配列の一致箇所を表す要素群で構成される２次元マトリックス画像情報を得る２次元マトリックス画像情報生成部と、
   前記２次元マトリックス画像情報について、前記２つの配列の一致箇所に対応する要素が斜め方向に所定数以上連続するかどうかを判定し、前記連続すると判定された要素が抽出された２次元マトリックス画像情報を生成する第１抽出処理部と、
   前記第１抽出処理部による処理を経た２次元マトリックス画像情報に設定される隣接して並べられた複数の前記斜め方向の平行四辺形の判定領域を用いて、各判定領域ごとの処理として、前記判定領域の平行四辺形における一の配列の配置方向の辺の長さである領域幅数と、前記判定領域内に並ぶ段のうちで前記配置方向に配列一致箇所の要素が存在しない空段の箇所の数と、の合計が、所定のしきい変異数以下であるかどうかを判定し、前記しきい変異数以下であると判定された判定領域の要素が抽出された２次元マトリックス画像情報を生成する第２抽出処理部と、
   前記第２抽出処理部による処理を経た前記２次元マトリックス画像情報を出力する出力処理部と、
   を含むことを特徴とする配列情報処理装置。
2. 請求項１に記載の配列情報処理装置において、
   前記第１抽出処理部は、前記２次元マトリックス画像情報について、前記２つの配列の一致箇所に対応する要素が斜め方向に３以上連続するかどうかを判定することを特徴とする配列情報処理装置。
3. 請求項１または２に記載の配列情報処理装置において、
   前記第１抽出処理部は、２つの配置方向の少なくとも一つに関して、前記２つの配列の一致箇所に対応する３つの要素が連続するかどうかを判定し、連続すると判定された３つの要素のうちの中央の要素を抽出しないことを特徴とする配列情報処理装置。
4. 請求項１乃至３いずれかに記載の配列情報処理装置において、
   前記第２抽出処理部による処理を経た前記２次元マトリックス画像情報が示すホモロジーを表現した配列情報を生成するホモロジー配列生成処理部をさらに含むことを特徴とする配列情報処理装置。
5. 請求項４に記載の配列情報処理装置において、
   前記ホモロジー配列生成処理部は、ギャップおよび置換を含んだ情報を生成することを特徴とする配列情報処理装置。
6. 請求項１乃至５いずれかに記載の配列情報処理装置において、
   前記２次元マトリックス画像情報のうち、前記判定領域が設定されない縁部に残る前記２つの配列の一致箇所に対応する要素を削除する縁部調整処理部をさらに含むことを特徴とする配列情報処理装置。
7. 請求項１乃至６いずれかに記載の配列情報処理装置において、
   前記第２抽出処理部による処理を経た前記２次元マトリックス画像情報において、２つの配置方向の少なくとも一つに関して、その配置方向に複数の抽出された要素が残っているとき、その残った要素が周囲の抽出された要素と形成する連続部分の長さに基づいて不要な要素を削除する長さ比較調整処理部をさらに含むことを特徴とする配列情報処理装置。
8. 請求項１乃至７いずれかに記載の配列情報処理装置において、
   前記出力処理部は、前記第２抽出処理部による処理を経た前記２次元マトリックス画像 情報を画面に表示する表示処理部を含むことを特徴とする配列情報処理装置。
9. アミノ酸配列、ＤＮＡ配列等の生物学的な２つの配列情報の比較によりホモロジーに関する情報を得る配列情報処理装置であって、
   比較対象の２つの配列情報を取得する配列情報取得部と、
   前記比較対象の２つの配列情報を異なる方向に配置して２次元マトリックス画像情報を生成する２次元マトリックス画像情報生成部であって、前記２つの配列を比較し、前記２つの配列の全組合せに対して、前記２つの要素が類似するとき行列要素として第一の値を設定し、前記２つの要素が類似しないとき行列要素として前記第一の値と異なる第二の値を設定する処理を行うことにより、前記２つの配列の類似箇所を表す要素群で構成される２次元マトリックス画像情報を得る２次元マトリックス画像情報生成部と、
   前記２次元マトリックス画像情報について、前記２つの配列の類似箇所に対応する要素が斜め方向に所定数以上連続するかどうかを判定し、前記連続すると判定された要素が抽出された２次元マトリックス画像情報を生成する第１抽出処理部と、
   前記第１抽出処理部による処理を経た２次元マトリックス画像情報に設定される隣接して並べられた複数の前記斜め方向の平行四辺形の判定領域を用いて、各判定領域ごとの処理として、前記判定領域の平行四辺形における一の配列の配置方向の辺の長さである領域幅数と、前記判定領域内に並ぶ段のうちで前記配置方向に配列一致箇所の要素が存在しない空段の箇所の数と、の合計が、所定のしきい変異数以下であるかどうかを判定し、前記しきい変異数以下であると判定された判定領域の要素が抽出された２次元マトリックス画像情報を生成する第２抽出処理部と、
   前記第２抽出処理部による処理を経た前記２次元マトリックス画像情報を出力する出力処理部と、
   を含むことを特徴とする配列情報処理装置。

Images