進化過程を考慮した保存領域検出システム
【課題】ゲノム解析の対象となる種のゲノム配列から保存領域を検出し、各々の種間の関係や各保存領域の関係を明確に表示することが可能な進化過程を考慮した保存領域検出システムを提供すること。
【解決手段】ゲノム配列に基づいて得られる系統樹を参照して、この系統樹を構成している中間ノードに属するゲノム配列を認識する配列認識手段と、中間ノードに属するゲノム配列において存在する同一の文字列の位置から開始してゲノム配列内の保存領域を検出する保存検出手段を備えたことを特徴とする。
【解決手段】ゲノム配列に基づいて得られる系統樹を参照して、この系統樹を構成している中間ノードに属するゲノム配列を認識する配列認識手段と、中間ノードに属するゲノム配列において存在する同一の文字列の位置から開始してゲノム配列内の保存領域を検出する保存検出手段を備えたことを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のＤＮＡ（またはアミノ酸）配列から、ゲノム配列を比較してゲノム配列中における意味を調べるゲノム解析に関し、特に、進化の過程で保存されている保存領域を見つけ、表示する進化過程を考慮した保存領域検出システムに関する。
【背景技術】
【０００２】
従来技術においては、世界中の配列解析プロジェクトによって、ヒトや動植物のゲノム解析が進み、それらの情報は公共データベース等を通して容易に入手できるようになっている。さまざまな生物における種間や種内のＤＮＡ配列のうちゲノム解析の対象となるゲノム配列同士を比較することによって、ゲノム配列中で各々の種の特異的な部分や、または全ての種に共通な部分を明らかにすることができ、このような特異的な部分、共通な部分に関する情報を用いることで進化のプロセスや、生物学的意味の解釈に役立てることが可能である。例えば、哺乳類のMHC（the Major
Histocompatibility Complex）領域について調べた文献（Hughes
AL, Yeager M. Natural selection at major histocompatibility complex loci of
vertebrates.Annu Rev Genet.
1998;32:415-35やMcConnell TJ,
Talbot WS, McIndoe RA, Wakeland EK. The origin of MHC class II gene
polymorphism within the genus Mus.Nature.
1988 14;332(6165):651-4.やLawlor DA, Ward
FE, Ennis PD, Jackson AP, Parham P. HLA-A and B polymorphisms predate the
divergence of humans and chimpanzees.Nature.
1988 15;335(6187):268-71.など）では、数百年にわたってＭＨＣがゲノム配列中に存続し機能していることが、各ゲノムを比較することによって明らかとなっている。
【０００３】
さて、ゲノム配列を比較するとは、進化の過程においてゲノム配列中に起こる変化（変異）を捉える、即ち、把握することであるが、進化におけるゲノム配列の変化（変異）とは、具体的にはsubstitution・deletion・insertion・inversionが挙げられる。図１乃至４は、これらの変化の様子を示した説明図である。図１は、substitutionの変化の様子を示しており、ゲノム配列中の塩基ＡがＣに置換されている。図２は、insertionの変化の様子を示しており、ゲノム配列中の塩基ＡとＴとの間に、新たに塩基Ｃ追加され挿入されている。図３は、deletionの変化の様子を示しており、塩基Ｔが削除されている。図４は、inversionの変化の様子を示しており、ゲノム配列中のＡＴＴがＴＴＡとなっており順序が逆となるように並び替えられている。
【０００４】
これらの４種類の変化のうち、substitutionは一塩基単位の変化で起こるが、deletion・insertion・inversionは数百から数万塩基を含むブロック単位の全体で一度に起こることがあり、生物の種の進化の過程でこれらの変化が起こるとゲノム配列中で蓄積してゲノム配列全体に変化を与え、結果的にそれぞれ異なる生物の種を生まれさせていくこととなっている。
【０００５】
ゲノム配列を比較してゲノム解析が行われたことにより明らかとなっている重要な事実のひとつは、生物にとって重要なゲノム領域（遺伝子など）では、ゲノム配列の変化を受けていないことが多いことである。これは、そのような部分で変化を受けると、ほとんどの場合にはそのような部分の変化を受けた生物は絶滅することが多いため、結果的に、そのような重要なゲノム領域で変化を受けなかった生物が絶滅せずに現在まで残っており、重要なゲノム領域で変化を受けないことが現在まで存在するために必要であると考えられているからである。異なる種類の生物の種のＤＮＡ配列を比較すると、生物の種類によっては変化を受けて互いに異なるＤＮＡ配列を有していることもあるがこれらをアミノ酸毎のレベルで調べてみると変化していないことが多い。
【０００６】
このような重要なゲノム領域等のゲノム配列の変化を受けていない領域は、保存領域と呼ばれている。研究者は、この保存領域においてゲノム配列の変化を受けていない事実を利用しており、異なる種類の生物の種のゲノム配列を相互に比較して保存領域を見つけこの保存領域に基づいて生物学的な意味を推測するための手がかりとしている。
【０００７】
また、別の重要な事実として、ゲノム配列は進化の歴史をとどめており示していることが挙げられる。一般的に近縁の種（ヒトとチンパンジー等）は、遠縁の種（ヒトと酵母等）よりも、ゲノム配列として類似している部分が多い。これは種が分化してから、近縁の種同士ではそれほど時間が経過しておらず、遠縁の種同士では、長時間経過しているからである。また、特定のＤＮＡ配列を含む遺伝子の状態の推移を追跡することで進化の歴史を把握することも可能である。
【０００８】
図５はこのような遺伝子の状態の推移による進化の歴史を示した説明図である。図５では種１と種２の祖先においてＤＮＡ配列を含む或る遺伝子ａが重複されて一列に配置されたタンデム（縦列）遺伝子ａ１とａ２を生じ、その後、別々の種類の生物の種に種文化した様子を示している。種１の遺伝子ａ１と種２の遺伝子ａ１（または種１の遺伝子ａ２と種２の遺伝子ａ２）は共通の祖先のタンデム遺伝子ａ１（またはタンデム遺伝子ａ２）を共有することとなっておりこれはオーソログと呼ばれている。一方、種１または種２における遺伝子ａ１とａ２とは遺伝子ａの重複によって発生したものであり、これはパラログと呼ばれている。
【０００９】
また、図５に示す以外にも遺伝子の状態の推移による進化としてゼノログ（外来）と呼ばれるタイプのものもある。このゼノログでは或る遺伝子がその他のどの遺伝子とも進化的起源を共有していな状態で進化していく場合であり、共生やウィルスによって、類縁のない生物種からもたらされたもの、すなわち水平伝播によって引き起こされたものといわれている。
【００１０】
更に、遺伝子以外にも、遺伝子に含まれる配列においてSINEs（short
interspersed repetitive elements）やLINEs（long
interspersed repetitive elements）と呼ばれる特殊な配列がある。これらはゲノム配列中で自分自身を複製し、他の位置にこの複製した配列を挿入する性質を持っており、更に、一旦挿入されると欠失しない性質があるため、これらの特殊な配列も進化の歴史を把握するための手がかりとして利用されている。過去の報告（Verneau O, Catzeflis F, Furano AV. Determination of the evolutionary
relationships in Rattus sensu lato (Rodentia : Muridae) using L1 (LINE-1)
amplification events. J Mol Evol.
1997 45(4):424-36. や Furano AV,
Hayward BE, Chevret P, Catzeflis F, Usdin K. Amplification of the ancient
murine Lx family of long interspersed repeated DNA occurred during the murine
radiation. J Mol Evol. 1994
38(1):18-27.やMurata S, Takasaki N,
Saitoh M, Okada N. Determination of the phylogenetic relationships among
Pacific salmonids by using short interspersed elements (SINEs) as temporal
landmarks of evolution. Proc Natl Acad
Sci U S A. 1993 1;90(15):6995-9.など）によれば、種の文化が起こった後５０００万年以内なら、これらの配列は進化を調べるためのマーカーとして使うことができ、研究者はこれらの特殊な配列を用いたマーカーとしての情報を手がかりとして進化の歴史上での出来事を推測することを行っている。
【００１１】
実際にゲノム配列内の保存領域や進化の歴史を調べるための手法としては、主に３種類の方法が使用されている。１つ目の手法はドットマトリックス解析と呼ばれる手法で、二つのゲノム配列の間で変化を受けずに共通して存在している保存領域を見つけるために行われる。図６は、ドットマトリックス解析によりＡＴＧＧＣＡの配列１とＣＡＴＴＧＧＣＴの配列２に存在する保存領域を解析した様子を示す説明図である。このドットマトリックス解析では、二つの配列の長さに対応した縦６個×横８個のマトリックスを作成しこのマトリックスの縦軸と横軸のそれぞれに沿って配列１と配列２を並べる。そして、縦軸の配列の各要素と横軸の配列の各要素を比較し、縦軸および横軸に同じ要素である塩基（または残基）がある場合にはその同じ塩基の縦軸および横軸の座標に該当するドットに印を付していく。
【００１２】
図６においては該当するドットを印として濃色（強調）表示する。そして、配列１および配列２の間で保存領域が存在する場合には印を付したドットが対角線方向に並んで構成されこれを視覚的に確認することで保存領域を把握することができるようになっている。図６の点線で囲まれた部分で示すように、濃色（強調）表示したドットが対角線方向に並んでおり配列１のＡＴＧＧＣと配列２のＡＴＴＧＧＣが類似しており保存領域となっていることが明らかとなっている。なお、配列１の塩基を相補鎖の塩基に変換する、すなわち、ＡをＴ、ＴをＡ、ＧをＣ、ＣをＧに変換することによりｒｅｖｅｒｓｅ ｃｏｍｐｌｅｍｅｎｔ配列と配列２との間の保存領域を明らかとすることも可能である。この場合には、印を付したドットが、配列１の場合とは逆の対角線方向に並んで構成されこれを視覚的に確認することで保存領域を把握することができるようになっている。
【００１３】
２つ目の手法は、マルチプルアライメントと呼ばれる手法で、複数の配列を並べたとき同じ要素が１つの列にできるだけ多く集まるような最適な並べ替えを行う手法である。図７は、マルチプルアライメントによる手法を示した説明図である。図７では１５個のゲノム配列としてのアミノ酸配列に対してマルチプルアライメントを実行した結果で、各列に同じアミノ酸（類似したアミノ酸）が並ぶように、ギャップ文字（−）を配列中に挿入している。マルチプルアライメントは、そこに含まれるゲノム配列の間の進化的な歴史を表現したものとみることができる。
【００１４】
もしミスマッチとして相互に異なるアミノ酸の個数が少なく、非常に良いマルチプルアライメントが得られるならば、それらのアミノ酸配列は共通の祖先から、比較的最近分かれてきたものと推測される。反対に、ミスマッチの個数が多く良いアライメントが得られないグループの間には、より複雑で遠い進化上の関係が存在する。あるゲノム配列はミスマッチの個数が少なく良く似ており、あるゲノム配列はミスマッチの個数が多く似ていない一群のゲノム配列のマルチプルアライメントを求められれば、それらのゲノム配列間の進化的関係を見出すことが可能である。
【００１５】
最後に、３つ目の手法は、系統樹解析と呼ばれる手法である。これは互いに類縁のある塩基配列（あるいはアミノ酸配列）が含まれているファミリーの系統を解析し、進化過程でそのファミリーが派生してきた道筋を決定することである。図８は８つの種から得られたファミリーに含まれるゲノム配列に対して系統樹解析を行った様子を示す説明図である。ゲノム配列間の関係を、各ゲノム配列を枝先に配置したツリー構造の木として表し、木の内部における分岐関係を、異なるゲノム配列がどの程度の類縁関係にあるかを反映させて表示している。枝の長さは近縁／遠縁の度合いに対応しており、枝の長さが短いほど近縁の関係であることを示している。
【００１６】
この系統樹解析では、類縁関係や近縁／遠縁の度合いを見ることにより個々の生物の種の進化において生じてきた変化の解析のみならず、ゲノム配列のファミリーの進化についても調べることが出来る。それにより、系統樹上の隣り合った枝を占めるゲノム配列が、最も近縁なゲノム配列だと決定できる。ある生物あるいは生物群においてゲノム配列としての遺伝子ファミリーが見出される場合、その遺伝子間の系統関係を調べれば、同じ機能をもつ遺伝子がどれかを予測するのに役立つ。これらの機能予測が得られれば、遺伝学的実験によってその機能を確認できる。系統樹解析は、例えばウィルスのような、急速に変化している生物種のおいて生じている変化を追うためにも使われる。ある集団内での変化の型の系統樹解析は、例えば、ある特定の遺伝子が自然選択を受けているかどうかといった、疫学などの応用にあたって大切な情報を明らかにする。また、従来のバイオチップにおいては、系統樹のノード等に対応して、複数の異なるターゲットの塩基配列に共通して存在する部分配列と特異的にはハイブリダイズするプローブを設計し、スポットしたものが提案されている（例えば、特許文献１参照。）。
【００１７】
【特許文献１】特開２００２−３３０７６８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従来の技術においては、ゲノム配列同士を比較して、そこから生物学的な意味を読み取るためには、上に示したような複数のゲノム配列間で保存されている保存領域を見つけ、そして、それがどのような種で共有されているか、つまりどのような進化を歩んできたかを調べることが必要である。
【００１９】
しかしながら、上述のような従来の技術を用いても上に示した三つの方法を駆使しても、保存領域とその進化的な関係について、両者を包括的に理解するのは困難・あるいは非常に煩雑な手間を伴う。ドットマトリックス解析では二つのゲノム配列間の保存領域は分かるが、それはどの進化の段階から保存されているのかわからない。マルチプルアライメント解析では、inversionになって保存されていてもそれを検出することができない。また系統樹解析では、進化の過程は分かるが、具体的にどのようなゲノム配列が類縁関係で保存されているのか、そしてどの進化のレベルでinversionやinsertion、deletionが起こったのかどうかわからない。
【００２０】
例えば、比較対象のゲノム配列のうち、進化的に近い生物種のファミリーで、共通した保存領域にはどのようなものがあるかを従来の方法で調べる場合を考える。研究者は、まず系統樹解析を行い、進化的に近いファミリーをみつける。そしてマルチプルアライメントを実行するか、あるいはドットマトリックス解析を行う。しかし、マルチプルアライメントを実行する場合、長い配列（数千塩基以上）を比較するには、実際的な問題として多大な時間を要する。また、マルチプルアライメントは、ある程度類似したゲノム配列を入力とすることが想定されているので、イントロン配列を多く含む場合や、入力配列が遺伝子以外の領域である場合、アライメントはうまくいかない。更にこの解析は、上にも述べたように、ゲノム配列中にinversionが起こっていてもそれを検出することができない。したがって、比較対象となるゲノム配列は非常に限られたものとなってくるという問題があった。
【００２１】
またゲノム配列が、マルチプルアライメントに適した配列であったとしても、ファミリーの配列に共通して存在し、ファミリーでない配列には存在しない保存領域を目視で確認する必要がある。一方、ドットマトリックス解析では、この解析手法の性質上、一度に二つのゲノム配列しか比較できない。したがって、ファミリーの生物種で共通した保存領域を見つける場合、ファミリーの配列同士で繰り返しドットマトリックス解析を行って保存領域をみつけ、更にファミリーに属していない配列でその領域が保存されていないことを確かめなければならない。これはファミリーの数や全体の比較するゲノム配列数が大きくなると、ドットマトリックス解析で比較を行う作業量が膨大なものとなり、手に負えないものとなってしまうという問題があった。
【００２２】
それ故本発明では、従来技術の問題点を鑑みてなされたものであり、その目的とするところは、ゲノム解析の対象となる種のゲノム配列から保存領域を検出し、各々の種間の関係や各保存領域の関係を明確に表示することが可能な進化過程を考慮した保存領域検出システムを提供することを目的とする。
【課題を解決するための手段】
【００２３】
上記課題を解決するために、本発明は、複数のＤＮＡ配列のうちゲノム解析の対象となるゲノム配列の中に配列の変化を受けておらず進化的に保存されている保存領域を見つける進化過程を考慮した保存領域検出システムにおいて、
ゲノム配列に基づいて得られる系統樹を参照して、この系統樹を構成している中間ノードに属するゲノム配列を認識する配列認識手段と、
中間ノードに属するゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していく保存検出手段とを備えたことを特徴とする。
【００２４】
このような発明においては、配列認識手段が系統樹を構成している中間ノードに属するゲノム配列を認識し、保存検出手段が中間ノードに属するゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していくので、正確にゲノム解析の対象となる種のゲノム配列から配列の変化を受けていない保存領域を検出することができる。
【００２５】
また、上述の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する２つのゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していき、ミスマッチの文字の個数が所定の個数に達するまでの領域を保存領域として検出することとしても良い。
【００２６】
このような発明においては、保存検出手段は、中間ノードに属する２つのゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していき、ミスマッチの文字の個数が所定の個数に達するまでの領域を保存領域として検出するので、全体的に略同一で配列の変化を受けておらず保存領域とみなすことができる領域を適切に保存領域として検出することができる。
【００２７】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する複数のゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内で検出した保存領域に基づいて、中間ノードを変えながら繰り返しこの検出した同一の保存領域を検出していき、全ての中間ノードに属するゲノム配列内の保存領域を検出しても良い。
【００２８】
このような発明においては、保存検出手段は、中間ノードを変えながら繰り返しこの検出した同一の保存領域を検出していき、全ての中間ノードに属するゲノム配列内の保存領域を検出するので、系統樹を構成する全ての中間ノードに属するゲノム配列内の保存領域を検出できる。
【００２９】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段が検出したゲノム配列内の各保存領域をそれぞれ毎に異なる形態の線により構成し、前記系統樹上の中間ノードを形成する枝を、中間ノードに属するゲノム配列内の各保存領域に対応させた形態の線により構成し、前記各保存領域と系統樹を同時に表示する解析結果表示手段を備えたこととしても良い。
【００３０】
このような発明においては、解析結果表示手段が各保存領域をそれぞれ毎に異なる形態の線により構成し、系統樹上の中間ノードを形成する枝を、中間ノードに属するゲノム配列内の各保存領域に対応させた形態の線により構成し、各保存領域と系統樹を同時に表示するので、研究者は各保存領域を明確に区別して参照することができ、また、各保存領域と系統樹上の中間ノードとの対応関係を参照して進化的に保存された保存領域を確認し、進化過程を推測することが可能である。
【００３１】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、既知のゲノム配列に関する情報と組み合わせて同時に表示することとしてもよい。
【００３２】
このような発明においては、各保存領域に組み合わされた既知のゲノム配列に関する情報を参照して進化過程を推測することが可能である。
【００３３】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、各保存領域が含まれるゲノム配列と組み合わせ、各ゲノム配列間に含まれる同一の保存領域を関連付けて表示しても良い。
【００３４】
このような発明においては、関連付けて表示された同一の保存領域の状況を参照して進化的に保存された保存領域を確認し、進化過程を推測することが可能である。
【００３５】
上述の進化過程を考慮した保存領域検出システムにおいて、
任意の配列に基づいて、前記系統樹を構成している中間ノードに属するゲノム配列を検索する配列検索手段と、
前記配列検索手段が検索した結果得られたゲノム配列の情報を参照して、前記系統樹を構成している中間ノードに属するゲノム配列に関する情報を特定の表示方法で表示する特定表示手段を備えても良い。
【００３６】
このような発明においては、特定の表示方法で表示されたゲノム配列に関する情報を参照して任意の配列が進化的に保存されている様子を確認し、進化過程を推測することが可能である。
【００３７】
上述の進化過程を考慮した保存領域検出システムにおいて、
特定表示手段は、
前記配列検索手段が検索した結果得られたゲノム配列を、当該任意の配列部分を関連付けて表示することとしても良い。
【００３８】
このような発明においては、関連付けて表示された当該任意の配列部分を参照して保存されている状況を確認し、進化過程を推測することが可能である。
【発明の効果】
【００３９】
以上説明したように、本発明によれば、ゲノム解析の対象となる種のゲノム配列から保存領域を検出し、各々の種間の関係や各保存領域の関係を明確に表示することが可能である。
【発明を実施するための最良の形態】
【００４０】
以下、図面を参照して本発明の実施の形態を説明する。
【００４１】
図１４は、本発明にかかる進化過程を考慮した保存領域検出システムの全体構成を示す説明図である。この保存領域検出システム１００は、ゲノム解析において、比較される対象となるゲノム配列のデータである対象配列１４０１と、それらの各対象配列１４０１を用いて系統樹を構成するための情報である構成情報１４１３と、ゲノム解析の解析結果を画像等により表示するための表示装置１４０２と、保存領域検出システム１００での数値や文書情報等の情報の入力や選択の操作を行うための入力手段であるキーボード１４０３やマウス１４０４と、ゲノム解析の解析結果のデータに参考情報として注釈付けする既知のゲノム配列及びこの既知のゲノム配列に付属する情報が格納されている配列ＤＢ１４０５と、後述するプログラムメモリ１４０７や図示しない記憶装置に格納されたプログラムを実行することにより保存領域の検出や系統樹のデータの構築や解析結果の表示等の各処理を行う中央処理装置１４０６（以下、ＣＰＵ１４０６という。）と、中央処理装置１４０６が行う各処理に必要なプログラムを格納するプログラムメモリ１４０７と、中央処理装置１４０６での処理の際に必要な演算結果等のデータを一時的に格納するデータメモリ１４１１とを備えて構成されている。
【００４２】
プログラムメモリ１４０７は、図１４に示すように、入力された各対象配列１４０１からそれらの対象配列１４０１間で保存されている保存領域を検出する処理を行うための保存領域計算処理部１４０８と、各対象配列１４０１を用いて系統樹を構築する処理を行う系統樹計算処理部１４０９と、これら解析・計算結果を表示する処理を行うための分析結果表示処理プログラム１４１０とを備えている。これらのプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＭＯ、フロッピー（登録商標）ディスク等の記録媒体に格納し、ＣＰＵ１４０６がこれらの記録媒体から読み出すことにより提供することもできるし、インターネット等の公衆網のネットワークを介してサーバからダウンロードして提供することもできる。
【００４３】
配列ＤＢ１４０５は、ＣＰＵ１４０６に接続された記憶装置に格納されていてもよいし、遠隔地に設置されたサーバコンピュータが管理する構成とし、そのサーバコンピュータ内のデータベースからインターネット等の公衆網のネットワーク等を介して配列ＤＢ１４０５に含まれている遺伝子データを取得するようにしてもよい。また、データメモリ１４１１は、プログラムの実行において入力データとして用いられる入力データ１４１２を含んでいる。
【００４４】
図１５は、対象配列１４０１の一例を示す説明図である。ここでは対象配列１４０１に該当する各ゲノム配列をＦＡＳＴＡ形式により表示しており、ゲノム配列を識別するための名称等を「＞」の後に表示し、その次の行から、ゲノム配列そのものを表示している。この他にも、ゲノム配列を表す形式として、ＧｅｎＢａｎｋ形式やＥＭＢＬ形式で表示することとしてもよい。
【００４５】
図１６は、各対象配列１４０１を用いて系統樹を構成するための構成情報１４１３の一例を示す説明図である。この構成情報１４１３では系統樹のリーフと枝の長さを対象配列１４０１の各ゲノム配列の名称に対応付けており一組の括弧及び数値により一つの中間ノードに関する情報を形成している（数値はその中間ノードの上位の位置の中間ノードまでの枝の長さを示している）。そしてその中間ノードが自己の位置よりも下位側に（系統樹上でリーフに近い）更に中間ノードを有しているときは、入れ子構造で表現する形式をとっている。すなわち、ＢＮＦ記法で表示すると次のようになる。
【００４６】
ノード::=(ノード,ノード):この中間ノードからその上位中間ノードまでの枝長|配列名:この葉から上位中間ノードまでの枝長
【００４７】
そして、この構成情報１４１３では、一組の括弧に囲まれた２つの名称または中間ノードによりゲノム配列の近縁関係を示しており、この系統樹のルートに対応する中間ノード間の相対関係に関する情報が構成されている。例えば「（種１：１５，種２：１０）：２０」は後述する図９に表示された系統樹の９０２の部分の中間ノードを示しており、種１（リーフ）から種１と種２の分岐点までの枝長が１５、種２から種１と種２の分岐点までの枝長が１０、そして、この分岐点とその上の中間ノード（９０１に対応するノード）までの枝長が２０であることを示している。この他にも、系統樹間の関係を表す形式として、Ｐｈｙｌｉｐ形式・ＣＬＵＳＴＡＬ形式・Ｄｉｓｔａｎｃｅ Ｍａｔｒｉｘ形式により表示することとしても良い。
【００４８】
図１７は、対象配列１４０１に該当する全てのＤＮＡ（またはアミノ酸）配列に関する索引情報を作成するためのデータ構造を示す構成図である。この索引情報に含まれる配列KtupleArrayDはpk個の要素からなる配列で、ｐは配列を構成する要素の種類数を示しており、すなわちＤＮＡ配列の場合は４、アミノ酸配列の場合は２０となる。ｋはｔｕｐｌｅ（文字列）の長さを示している。配列KtupleArrayDの配列の各要素には各tupleが割り当てられる。例えば対象配列１４０１がＤＮＡ配列で、ｋが２のとき、配列KtupleArrayDは１６個の要素からなり、それぞれの要素には、AA・AT・AG・AC・TA・TT・TG・TC・GA・GT・GG・GC・CA・CT・CG・CCの１６種類のtupleが割り当てられる。
【００４９】
また、この配列KtupleArrayDの各要素には、その要素に割り当てられたtupleが対象配列１４０１中に最も後側に現れたtupleの位置を表す。その要素に割り当てられたtupleが配列中にない場合は、０で表す。
【００５０】
配列IdxArrayDは対象配列１４０１と等しい長さの配列であり対象配列１４０１の各要素に割り当てられた要素からなる配列である。配列IdxArrayDの各要素は対象配列１４０１上の各位置に割り当てられており、それら各要素に割り当てられた文字から始まるtupleと同じtupleがその要素より前側の配列中に現れた場合には、その現れたもののうちそれら各要素の最も直前に現れた要素の位置を表す。また、もしそれら各要素と同じtupleが前に現れない場合には０で表す。
【００５１】
図２８は、対象配列１４０１としての配列GTCTCACGACACTCに対して作成された配列KtupleArrayDとIdxArrayDを表示した説明図である。この配列ではtuple TCは配列中の２番目、４番目、１３番目に現れており、配列KtupleArrayDのTCに対応する要素（KtupleArrayD[８]）に、tuple TCが対象配列１４０１中に最後に現れた位置１３が表示されている。またIdxArrayD[１３]には位置１３に現れたtuple TCと同一のTCがその直前に現れた位置である「４」、IdxArrayD[４]には位置４に現れたtuple TCと同一のTCがその直前に現れた位置である「２」が表示されている。したがって、ここで示したように、特定のtupleが配列中のどこにあるかを、二つの配列KtupleArrayDとIdxArrayDを用いることで、高速に検索することが出来る。配列KtupleArrayRおよびIdxArrayRは、配列KtupleArrayDとIdxArrayDと同様に対象配列１４０１としてのDNA配列（またはアミノ酸配列）のreverse complement配列に対して、作成される。
【００５２】
図１８は、対象配列１４０１の保存領域を記録するためのデータ構造を示す説明図である。このデータ構造で示す構造体配列ConservedRegは、各対象配列１４０１毎に、保存領域が存在していれば作成されるものであり、保存領域を示す位置１８００、保存領域の長さ１８０１、保存領域の向き（順方向か逆方向か）１８０２の各データから構成されている。
【００５３】
図１９は、各対象配列１４０１間の保存領域同士の関係を記録するためのデータ構造体ListOfConservedRegを示す説明図である。このデータ構造体は、構成情報１４１３上の各中間ノードで、保存領域毎に作られるものである。対象配列１４０１を識別するための配列名１９００、この対象配列１４０１において作成されているいずれのConservedRegが対応しているかを示すために、配列名１９００毎に作成された各構造体配列ConservedRegを識別するためのindex１９０１の各データから作成されている。
【００５４】
図２０は、図１９で述べた関連する保存領域の集合を表す配列ListOfConservedRegを集めた配列AllOfConservedRegのデータ構造を示す説明図である。この配列AllOfConservedRegの各要素はListOfConservedRegへリンクしたポインタが表示されており、構成情報１４１３上の各中間ノード毎に、この配列AllOfConservedRegが１つ作成される。この配列AllOfConservedRegに該当する中間ノードに属するゲノム配列で保存されている異なる種類の保存領域のそれぞれを、各要素とListOfConservedRegとでリンクさせてこの配列によって表示している。なお、本実施の形態における進化過程を考慮した保存領域検出システムは、一般に使用されている各種の情報処理を行うための情報処理装置であるパーソナルコンピュータを用いて実現することも可能である。
【００５５】
続いて、上述のような構成を有する本実施形態の進化過程を考慮した保存領域検出システムの動作について図２１乃至図２７に示すフローチャートを用いて詳細に説明する。図２１乃至図２７に示すフローチャートでは、ＣＰＵ１４０６が処理を行うことにより、図９、図１０、図１１、図１２、図１３に示す画像のデータを表示させるために必要となる系統樹１４１３の各リーフに対するConservedRegと、保存領域の関連を保持する配列ListOfConservedRegと、配列AllOfConservedRegを求めるようになっている。以下に説明する動作では、対象配列１４０１および系統樹１４１３から、系統樹１４１３の各中間ノードに対して、これらの三つの配列を得るためのアルゴリズムを説明する。
【００５６】
本実施の形態における進化過程を考慮した保存領域検出システム１００の概略的な処理の流れを図２１に示すフローチャートを用いて説明する。まず、進化過程を考慮した保存領域検出システム１００のＣＰＵ１４０６は、研究者がフロッピー（登録商標）ディスクやＣＤ−ＲＯＭ等の外部記録媒体を用いて入力した対象配列１４０１と系統樹の構成情報１４１３のデータを読み込み、データメモリ１４１１内に格納して入力データ１４１２として保持する（ステップ２１００）。このとき、構成情報１４１３については系統樹自体の情報を読み込まなくても、系統樹を構成するために必要となるパラメータ情報のみを入力しこのパラメータ情報に基づいてＣＰＵ１４０６が構成情報１４１３のデータを作成することとしても良い。
【００５７】
次に、ＣＰＵ１４０６は、保存領域を検出するためのパラメータk, w, mを読み込み、データメモリ１４１１の入力データ１４１２として保持する処理を行う（ステップ２１０１）。ここで、kはtupleの文字列の長さ、wはウィンドウの長さ、mはウィンドウ内で許容されるミスマッチの数、即ち保存領域を検出する２つのゲノム配列で相互に異なる文字の最大限度数を示している。保存領域を検出する際に保存領域として検出を行っている領域中の連続するｗ個の文字（塩基または残基）に対し、２つの配列で相互に異なる文字であるミスマッチの個数が最大m個までを許容するようになっている。例えば、図２９では、ウィンドウサイズｗを５、許容されるミスマッチｍの数を１としたときの配列Aと配列Bの２つのゲノム配列間の保存領域の場所を示している。この場合、連続する５個の文字のペア毎に同一の文字の配列を検出して保存領域を検出していった際にミスマッチの個数が全ての５個の文字のペア毎で１個以内となっており領域２６０１は二つの配列間の保存領域になっている。
【００５８】
次に、ＣＰＵ１４０６は、対象配列１４０１がＤＮＡ配列であり、それをアミノ酸配列として比較したい場合、全てのＤＮＡ配列をアミノ酸配列に変換する処理を行う（ステップ２１０２）。
【００５９】
次に、ＣＰＵ１４０６は、各対象配列１４０１に対して上述のように図１７乃至図２０に示す索引情報、すなわちKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ] を作成する処理を行う（ステップ２１０３）。この処理の詳細については後述する。
【００６０】
次に、ＣＰＵ１４０６は、構成情報１４１３により構成される系統樹の全ての中間ノードに対して、その中間ノードに属するゲノム配列から全ての保存領域を検出したか否かを判定する処理を行う（ステップ２１０４）。
【００６１】
次に、ＣＰＵ１４０６は、全ての保存領域を検出していない場合には（ステップ２１０４のＮＯ）、構成情報１４１３により構成される系統樹の全ての中間ノードに対して、その中間ノードに属するゲノム配列のうち保存領域を未だ検出していないものを選択する処理を行う（ステップ２１０５）。
【００６２】
次に、ＣＰＵ１４０６は、この選択した各ゲノム配列の間で保存されている保存領域を検出する処理を行う（ステップ２１０６）。この保存領域を検出する処理は後で詳しく述べる。この保存領域を検出する処理が終了すると次にステップ２１０４の処理を実行する。
【００６３】
次に、ＣＰＵ１４０６は、全ての保存領域を検出した場合には（ステップ２１０４のＹＥＳ）、保存領域に基づいて配列ＤＢ１４０５内を検索し、同一の保存領域を有する種のゲノム配列の情報等の保存領域に関連する情報等があればこの関連情報を以上のゲノム解析の結果に付与する。そして、ゲノム解析の結果を表示装置１４０２に表示する処理を行い（ステップ２１０７）、全体の処理を終了する。
【００６４】
続いて、上述のステップ２１０３における、各対象配列１４０１に対して索引情報、すなわちKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ] を作成する処理について図２２に示すフローチャートを用いて詳細に説明する。まず、ＣＰＵ１４０６は、個々の対象配列１４０１に対応するKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ]の全要素を0で初期化する処理を行う（ステップ２２００）。
【００６５】
次に、ＣＰＵ１４０６は、変数ｊ=1を設定する処理を行う（ステップ２２０１）。
【００６６】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の配列終端側で最も後側のtupleに該当する要素の位置を示す数値、すなわちj=配列長−kとなっているか否かを判定する（ステップ２２０２）。j=配列長−kとなっている場合には（ステップ２２０２のＹＥＳ）、ステップ２２０７の処理を実行する。
【００６７】
次に、ＣＰＵ１４０６は、j=配列長−kとなっていない場合には（ステップ２２０２のＮＯ）、対象配列１４０１のj番目からはじまるk個の文字列からなるtupleをKと設定し、このKに割り当てられている配列KtupleArrayD[ ]の要素インデックス（即ち配列KtupleArrayD[ ]内の要素の位置を示す要素番号）を iと設定し、配列KtupleArrayD[ ]の配列中の各要素を構成していく処理を行う（ステップ２２０３）。例えば図２８に示す配列KtupleArrayD[
]では、tuple KがTCの場合には、i は８番目の要素インデックスを示す「８」となっている。
【００６８】
次に、ＣＰＵ１４０６は、IndexArrayD[j]にKtupleArrayD[i]の数値を代入し、また、KtupleArrayD[i] に j を入力する（ステップ２２０４、２２０５）。KtupleArrayD[i]には、常に対象配列１４０１の配列中の最も後側に現れたtupleの位置を表示するため、この二つのステップ（２２０４，２２０５）は、変数ｊの数値をインクリメントしていき（ステップ２２０６）、配列中に新しくＫに該当するtupleが後側に現れるたびに、KtupleArrayD[i]の数値を更新し、IdxArrayD[j]にその更新前のKtupleArrayD[i]の数値を表示していき、更新していく処理となっている。
【００６９】
次に、以上のステップ２２０２〜２２０６の処理を全ての変数jに対して実行することにより、図２８に示すような、配列IndexArrayD[j]とKtupleArrayD[i]の索引情報を作成する。
【００７０】
次に、ＣＰＵ１４０６は、以上のステップ２２０２〜２２０６の処理を全ての変数jに対して実行し、j=配列長−kとなっている場合には（ステップ２２０２のＹＥＳ）、対象配列１４０１のreverse complement配列を改めて対象配列に設定する処理を行う（ステップ２２０７）。
【００７１】
次に、ＣＰＵ１４０６は、このreverse
complement配列に対する索引情報の配列IndexArrayR[j]とKtupleArrayR[i]を作成する処理を行う（ステップ２２０８〜２２１３）。ＣＰＵ１４０６は、上述の対象配列１４０１に対して以上のステップ２２０２〜２２０６の処理と同様の処理を実行していき配列IndexArrayR[j]とKtupleArrayR[i]を作成する。以上のステップ２２０８〜２２１３の処理を全ての変数jに対して実行し、j=配列長−kとなっている場合には（ステップ２２０９のＹＥＳ）、処理を終了する。
【００７２】
続いて、上述のステップ２１０６における、選択した各ゲノム配列の間で保存されている保存領域を検出する処理について図２３〜図２６で一体的に構成されたフローチャートを用いて詳細に説明する。まず、ＣＰＵ１４０６は、上述のステップ２１０５で選択した保存領域の検出対象となる各対象配列１４０１のそれぞれに対して、対象配列１４０１を識別する情報seq1, seq2, …, seqMを設定する処理を行う（ステップ２３００）。
【００７３】
次に、ＣＰＵ１４０６は、変数ｉ=1を設定する処理を行う（ステップ２３０１）。
【００７４】
次に、ＣＰＵ１４０６は、変数ｉが配列KtupleArrayDの終端位置を示す数値、すなわちｉ＞ pkとなっているか否かを判定する（ステップ２３０２）。ｉ＞ pkとなっている場合には（ステップ２３０２のＹＥＳ）、処理を終了する。
【００７５】
次に、ＣＰＵ１４０６は、定数c1にseq1の配列の配列KtupleArrayD[i]の数値を代入する処理を行う（ステップ２３０３）。上述の２１０３においてseq1の配列に対して作成したKtupleArrayD[i]の数値をc1に代入する。
【００７６】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２３０４）。c1が０である場合には（ステップ２３０４のＹＥＳ）、ステップ２３２８の処理を実行する。
【００７７】
次に、ＣＰＵ１４０６は、c1が０でない場合には（ステップ２３０４のＮＯ）、定数c2にseq2の配列の配列KtupleArrayD[i]の数値を代入する処理を行う（ステップ２３０５）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayD[i]の数値をc2に代入する。
【００７８】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３０６）。c2が０である場合には（ステップ２３０６のＹＥＳ）、ステップ２３１７の処理を実行する。
【００７９】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３０６のＮＯ）、配列seq1のKtupleArrayD[i]に割り当てられたtupleがseq1およびseq2の配列中に存在することとなっており、これら２つのゲノム配列seq1のc1番目とseq2のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３０７）。これら２つのゲノム配列seq1、seq2内の検出していく処理の開始位置からアライメントの連続するw個の文字列（塩基または残基）毎に保存領域を検出していき、seq1のc1番目とseq2のc2番目からアライメントを伸張させ保存領域として一致している文字列の個数を伸張させていく。そして、ゲノム配列seq1およびseq2間で相互に異なる文字であるミスマッチの個数がm個以下となっている文字列となっている領域の範囲内で保存領域を拡大させ、ミスマッチの個数がm個より多い文字列が存在した時点でその位置を保存領域の境界位置とする。このようにして保存領域を検出していき保存領域が存在する場合にはこれをCと設定する処理を行う。
【００８０】
次に、ＣＰＵ１４０６は、ステップ２３０７において保存領域が存在したか否かを判定する処理を行う（ステップ２３０８）。保存領域が存在しなかった場合には（ステップ２３０８のＮＯ）、ステップ２３１６の処理を実行し、ＣＰＵ１４０６は、c2にseq2のKtupleArrayD[c2]を代入する処理を行い、ステップ２３０６以降の処理を実行する（ステップ２３１６）。
【００８１】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３０８のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３０９）。変数jに対してｊ＝３と設定する処理を行う。
【００８２】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３１０）。
【００８３】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３１０のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３１１）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【００８４】
次に、ＣＰＵ１４０６は、ステップ２３１１において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３１２）。保存領域Ｃが存在しなかった場合には（ステップ２３１２のＮＯ）、ステップ２３１６の処理を実行し、ＣＰＵ１４０６は、c2にseq2のKtupleArrayD[c2]を代入する処理を行い、ステップ２３０６以降の処理を実行する（ステップ２３１６）。
【００８５】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３１２のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３１０以降の処理を再度実行する（ステップ２３１３）。そして、ステップ２３１０において、ｊ＞Ｍとなっている場合には（ステップ２３１０のＹＥＳ）、ステップ２３１４の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３１６の処理を実行する。
【００８６】
次に、ＣＰＵ１４０６は、ステップ２３０６においてc2が０である場合には（ステップ２３０６のＹＥＳ）、c2にseq2のKtupleArrayＲ[ｉ]を代入する処理を行う（ステップ２３１７）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayＲ[i]の数値をc2に代入する。
【００８７】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３１８）。c2が０である場合には（ステップ２３１８のＹＥＳ）、ステップ２３１５の処理を実行し、ＣＰＵ１４０６は、c1にseq1のIdxArrayD[c1]を代入する処理を行い、ステップ２３０４以降の処理を実行する（ステップ２３１５）。
【００８８】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３１８のＮＯ）、配列seq1のKtupleArrayD[i]に割り当てられたtupleがseq1の配列およびseq2のreverse complement配列中に存在することとなっており、これら２つのゲノム配列seq1のc1番目とseq2のreverse complement配列中のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３１９）。これは上述のステップ２３０７の処理と同様であり説明を省略する。
【００８９】
次に、ＣＰＵ１４０６は、ステップ２３１９において保存領域が存在したか否かを判定する処理を行う（ステップ２３２０）。保存領域が存在しなかった場合には（ステップ２３２０のＮＯ）、ステップ２３２７の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayR[c2]を代入する処理を行い、ステップ２３１８以降の処理を実行する（ステップ２３２７）。
【００９０】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３２０のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３２１）。変数jに対してｊ＝３と設定する処理を行う。
【００９１】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３２２）。
【００９２】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３２２のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３２３）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【００９３】
次に、ＣＰＵ１４０６は、ステップ２３２３において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３２４）。保存領域Ｃが存在しなかった場合には（ステップ２３２４のＮＯ）、ステップ２３２７の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayR[c2]を代入する処理を行い、ステップ２３１８以降の処理を実行する（ステップ２３２７）。
【００９４】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３２４のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３２２以降の処理を再度実行する（ステップ２３２５）。そして、ステップ２３２２において、ｊ＞Ｍとなっている場合には（ステップ２３２２のＹＥＳ）、ステップ２３２６の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３２７の処理を実行する。
【００９５】
次に、ＣＰＵ１４０６は、ステップ２３０４においてc1が０である場合には（ステップ２３０４のＹＥＳ）、c1にseq1のKtupleArrayＲ[i]を代入する処理を行う（ステップ２３２８）。上述の２１０３においてseq1の配列に対して作成したKtupleArrayＲ[i]の数値をc1に代入する。
【００９６】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２３２９）。c1が０である場合には（ステップ２３２９のＹＥＳ）、ステップ２３４２の処理を実行し、ＣＰＵ１４０６は、変数iをひとつインクリメントし、ステップ２３０２以降の処理を実行する（ステップ２３４２）。
【００９７】
次に、ＣＰＵ１４０６は、c2にseq2のKtupleArrayD[i]を代入する処理を行う（ステップ２３３０）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayD[i]の数値をc2に代入する。
【００９８】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３３１）。C2が０である場合には（ステップ２３３１のＹＥＳ）、ステップ２３４３以降の処理を実行する。
【００９９】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３３１のＮＯ）、seq1のreverse complement配列のKtupleArrayR[i]に割り当てられたtupleがseq1のreverse
complement配列中およびseq2の配列に存在することとなっており、これら２つのゲノム配列seq1のreverse complement配列中のc1番目とseq2のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３３２）。これは上述のステップ２３０７の処理と同様であり説明を省略する。
【０１００】
次に、ＣＰＵ１４０６は、ステップ２３３２において保存領域が存在したか否かを判定する処理を行う（ステップ２３３３）。保存領域が存在しなかった場合には（ステップ２３３３のＮＯ）、ステップ２３４１の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayD[c2]を代入する処理を行い、ステップ２３３１以降の処理を実行する（ステップ２３４１）。
【０１０１】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３３３のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３３３）。変数jに対してｊ＝３と設定する処理を行う（ステップ２３３４）。
【０１０２】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３３５）。
【０１０３】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３３５のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３３６）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【０１０４】
次に、ＣＰＵ１４０６は、ステップ２３３６において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３３７）。保存領域Ｃが存在しなかった場合には（ステップ２３３７のＮＯ）、ステップ２３４１以降の処理を実行する。
【０１０５】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３３７のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３３５以降の処理を再度実行する（ステップ２３３８）。そして、ステップ２３３５において、ｊ＞Ｍとなっている場合には（ステップ２３３５のＹＥＳ）、ステップ２３３９の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３４１の処理を実行する。
【０１０６】
次に、ＣＰＵ１４０６は、ステップ２３３１においてc2が０である場合には（ステップ２３３１のＹＥＳ）、c2にseq2のKtupleArrayＲ[i]を代入する処理を行う（ステップ２３４３）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayＲ[i]の数値をc2に代入する。
【０１０７】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３４４）。c2が０である場合には（ステップ２３４４のＹＥＳ）、ステップ２３４０の処理を実行し、ＣＰＵ１４０６は、c1にseq1のIdxArrayR[c1]を代入する処理を行い、ステップ２３２９以降の処理を実行する（ステップ２３４０）。
【０１０８】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３４４のＮＯ）、seq1のreverse complement配列のKtupleArrayR[i]に割り当てられたtupleがseq1のreverse
complement配列中およびseq2のreverse complement配列中に存在することとなっており、これら２つのゲノム配列seq1のreverse complement配列中のc1番目とseq2のreverse
complement配列中のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３４５）。これは上述のステップ２３０７の処理と同様であり説明を省略する。
【０１０９】
次に、ＣＰＵ１４０６は、ステップ２３４５において保存領域が存在したか否かを判定する処理を行う（ステップ２３４６）。保存領域が存在しなかった場合には（ステップ２３４６のＮＯ）、ステップ２３５３の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayR[c2]を代入する処理を行い、ステップ２３４４以降の処理を実行する（ステップ２３５３）。
【０１１０】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３４６のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３４７）。変数jに対してｊ＝３と設定する処理を行う。
【０１１１】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３４８）。
【０１１２】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３４８のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３４９）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【０１１３】
次に、ＣＰＵ１４０６は、ステップ２３４９において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３５０）。保存領域Ｃが存在しなかった場合には（ステップ２３５０のＮＯ）、ステップ２３５３以降の処理を実行する。
【０１１４】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３５０のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３４８以降の処理を再度実行する（ステップ２３５１）。そして、ステップ２３４８において、ｊ＞Ｍとなっている場合には（ステップ２３４８のＹＥＳ）、ステップ２３５２の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３５３の処理を実行する。以上のようにして、選択した各ゲノム配列の間で保存されている保存領域を検出する処理を行う。
【０１１５】
続いて、上述のステップ２３１１、２３２３、２３３６、２３４９における、ゲノム配列seq jの配列中に存在する保存領域Cを検出するについて図２７で示すフローチャートを用いて詳細に説明する。まず、ＣＰＵ１４０６は、保存領域C内の最も前側に位置する先頭tupleに該当するindexに変数iを設定する処理を行う（ステップ２４００）。
【０１１６】
次に、ＣＰＵ１４０６は、ゲノム配列seq j のKtupleArrayD[i]の値をc1と設定する処理を行う（ステップ２４０１）。
【０１１７】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２４０２）。c1が０である場合には（ステップ２４０２のＹＥＳ）、ステップ２４０６の処理を実行し、ＣＰＵ１４０６は、c1にseqｊのKtupleArrayＲ[i]を代入する処理を行い、ステップ２４０７以降の処理を実行する（ステップ２４０６）。
【０１１８】
次に、ＣＰＵ１４０６は、c1が０でない場合には（ステップ２４０２のＮＯ）、保存領域Cの先頭tupleがseqｊの配列中に存在することとなっており、ゲノム配列seqｊのc1番目から開始して、ステップ２３０７、２３１９、２３３２、２３４５で検出した保存領域Ｃのデータに基づいて保存領域を検出していく処理を行う（ステップ２４０３、２４０４）。これらゲノム配列seqｊ内の検出していく処理の開始位置および保存領域Ｃ内の先頭位置から文字列を比較していき、アライメントの連続するw個の文字列（塩基または残基）毎に保存領域を検出していき、seqｊのc1番目からアライメントを伸張させ保存領域Ｃと一致している文字列の個数を伸張させていく。そして、ゲノム配列seqｊおよび保存領域Ｃ間で相互に異なる文字であるミスマッチの個数がm個以下となっている文字列となっている領域の範囲内で保存領域を拡大させ、ミスマッチの個数がm個より多い文字列が存在した時点でその位置をゲノム配列seqｊ内での保存領域の境界位置とする。このようにして保存領域を検出していき保存領域が存在する場合にはこれを一時的にデータメモリ１４１１に格納する処理を行う。この検出した保存領域が保存領域Ｃよりも短い場合であっても、この検出した保存領域を改めてゲノム配列seqｊにおける保存領域Ｃとして設定しデータメモリ１４１１に格納する処理を行う。
【０１１９】
次に、ＣＰＵ１４０６は、c1にseqｊのIdxArrayD[c1]を代入する処理を行い、ステップ２４０２以降の処理を実行する（ステップ２４０５）。
【０１２０】
次に、ＣＰＵ１４０６は、ステップ２４０２においてc1が０である場合には（ステップ２４０２のＹＥＳ）、ステップ２４０６の処理を実行し、ＣＰＵ１４０６は、c1にseqｊのKtupleArrayＲ[i]を代入する処理を行う（ステップ２４０６）。
【０１２１】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２４０７）。c1が０である場合には（ステップ２４０７のＹＥＳ）、処理を終了する。
【０１２２】
次に、ＣＰＵ１４０６は、c1が０でない場合には（ステップ２４０７のＮＯ）、保存領域Cの先頭tupleがseqｊのreverse
complement配列中に存在することとなっており、ゲノム配列seqｊのreverse complement配列中のc1番目から開始して、ステップ２３０７、２３１９、２３３２、２３４５で検出した保存領域Ｃのデータに基づいて保存領域を検出していく処理を行う（ステップ２４０８、２４０９）。これは上述のステップ２４０３、２４０４の処理と同様であり説明を省略する。
【０１２３】
次に、ＣＰＵ１４０６は、c1にseqｊのIdxArrayＲ[c1]を代入する処理を行い、ステップ２４０７以降の処理を実行する（ステップ２４１０）。
【０１２４】
ＣＰＵ１４０６が以上説明した進化過程を考慮した保存領域検出システム１００の動作を行うことにより、構成情報１４１３により構成される系統樹に属する中間ノードに属する各リーフに対する対象配列１４０１内で保存されている保存領域を検出し構造体配列ConservedRegと、保存領域の関連を保持する配列ListOfConservedRegと、配列AllOfConservedRegが求められる。そして、ＣＰＵ１４０６は、以下に説明するような図９、図１０、図１１、図１２、図１３に示す画像のデータを作成し表示装置１４０２に表示させる処理を行う。
【０１２５】
図９は、構造体配列ConservedRegと、配列ListOfConservedRegと、配列AllOfConservedRegのデータを用いて作成した系統樹の様子を示す説明図である。この系統樹では、表示画面の左半分に対象配列１４０１の名称（例えば種１〜種６）を用いて構成された系統樹、右半分に各対象配列１４０１に対応するゲノム配列上の保存領域が表示されている。系統樹の各枝は、各対象配列１４０１毎に異なる色や実線、点線、一点鎖線等の異なる形態の線で表示されている。これにより配列ファミリーを識別するようになっており、例えば、線９０１は種１、種２、種３、種４のファミリーを表し、線９０２は種１、種２のファミリーを表している。図９では、各枝を識別するために色と線の形態を変えているが、実際にはこれ以外の表現方法でもよく、例えば、線の近くにタグや番号、名称等を表示する実現方法を用いても良い。
【０１２６】
また図９の系統樹の右側には、各対象配列１４０１に対して、保存領域の位置と、その保存領域が系統樹で保存されているレベルを模式的に表示している。系統樹のレベルは、左半分の系統樹の枝の色・線の形態に対応しており、例えば種１と種２でのみ保存されている領域は種１と種２が属している中間ノードを形成する線９０２と同一の色および形態の線を用いて示した９０５の部分となっている。同様に、種１、種２、種３、種４でのみ保存されている領域は線９０１と同一の色および形態の線を用いて示した９０３に示された部分で、全ての対象配列１４０１（種１〜種６）で保存されている領域は線９０１の上位側の線と同一の色および形態の線を用いて示した９０４に示された部分である。遠縁の種同士で保存されているものは、近縁の種同士でも保存されているはずであり、図９の表示結果では、系統樹において根に近いところの線で表された保存領域は、葉に近いところの全ての対象配列１４０１内に存在していることが表示されている。
【０１２７】
図１０は、図９で示した対象配列１４０１としての種１の保存領域を実際の塩基配列（またはアミノ酸配列）として表示した説明図である。図１０により研究者は、対象配列１４０１の保存領域のDNA（またはアミノ酸）配列を知ることが可能となっている。図１０の図中で矢印の領域は、種１の配列をインターネット等の公衆網やローカルネットワーク上に設置されたデータベースに対して、このDNA（またはアミノ酸）配列に基づいて検索し、その結果をマッピングすることによって表示したものである（矢印の向きは検索配列の方向）。研究者は、この結果を参照してこの保存領域のDNA（またはアミノ酸）配列と既知の情報の対応関係を知ることもできる。図中では、保存領域で既知の結果が見つかった状況を示しており、研究者はこれにより、保存領域の生物学的意味を知ることができるようになっている。
【０１２８】
図１１は、図９で示した各対象配列１４０１内の各保存領域の間の関係を示した説明図である。線の色・形状は図９の右半分において保存領域を表示した線に対応している。表示対象となる対象配列１４０１（図１１の場合、種１・種２・種３・種４）を選ぶためには、例えば図９の表示画面上において９０１等の保存領域が表示されている線をマウス１４０４により選択操作して、このような表示をするかどうかのメニューを出せばよい。あるいは任意の配列集合を、入力メニューから選択操作して表示させることとしても良い。図１１では、画面左寄りのの保存領域１１０１は種１、種２、種３では同じ向きだが、種４では向きが異なっている。これを参照することにより研究者は、進化のある時点で、種４でのみinversionが起こって向きが変わったか、あるいは種１・種２・種３の全てがinversionによって向きが変わった事実等を推測することが可能となり、これから進化の過程を知る手がかりとすることができる。
【０１２９】
図１２も、図１１と同様に図９で示した各対象配列１４０１内の各保存領域の間の関係を示した説明図である。図１２では、図９の系統樹内の種５と種６を対象として表示している。この図１２の画面を参照することにより研究者は、領域１２０１が、種５では２つ、種６ではひとつありこのことから種５が過去に領域１２０１を重複した事実等を推測できる。同様に領域１２０２は、過去に種６で同領域が重複した事実等を推測できる。
【０１３０】
図１３は、図９で示した系統樹内の種に対応する保存領域について他の種にも存在している状況を示した説明図である。図１３では、種５の１３０１領域について、これと同様の配列が他の種にあるかどうか検索し、種３と種６でそれが発見された状況を示している。見つかった配列については、種の名称を強調して明確に表示している。ここで図１３の画面を参照して研究者は、領域１３０１が種３でみつかったことの原因として、ひとつは進化系統樹そのものが間違っていたこと、そしてもうひとつは、SINE配列やLINE配列などレトロトランスポゾン配列が挿入されたことが考えられる等の推測を行うことができる。逆にこのことを用いて、系統樹が正しいかどうかを、見つかった保存領域に対して繰り返し検索を行うことで確認する利用形態も実現できる。
【０１３１】
以上説明したように、本実施の形態における進化過程を考慮した保存領域検出システム１００では、ＣＰＵ１４０６がゲノム解析の対象となる対象配列１４０１のデータに対してKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ]の索引情報を作成する処理を行い、構成情報１４１３により構成される系統樹に属する中間ノードに属する各リーフに対する対象配列１４０１内で保存されている保存領域を検出し構造体配列ConservedRegと、保存領域の関連を保持する配列ListOfConservedRegと、配列AllOfConservedRegを求める処理を行う。
【０１３２】
そして、ＣＰＵ１４０６は、構造体配列ConservedRegと、配列ListOfConservedRegと、配列AllOfConservedRegのデータを用いて系統樹や系統樹を構成する各対象配列１４０１の実際のゲノム配列、各対象配列１４０１内の各保存領域の間の関係を示した表示データを作成し、ゲノム配列同士の保存領域を進化過程と対応付けて系統樹の情報と併せて表示画面１４０２に表示するので、研究者は、これを参照して各対象配列１４０１の種の保存領域の進化の過程を推測し、進化の過程を手がかりとして利用することが可能である。そして、より本質的な生物学の理解を得られることが期待される。
【０１３３】
(他の実施の形態)
図２１および図２２で示すフローチャートを用いて行った処理では、対象配列１４０１や構成情報１４１３のデータをもちいて、保存領域の検出対象となるゲノム配列を選択しているが、これに限られず、対象配列１４０１以外の任意のゲノム配列の集合に対しても、この処理を実行することが可能である。その場合には、図２１のステップ２１０４の処理を実行せずスキップし、ステップ２１０５の処理で保存領域の検出対象となるゲノム配列として、対象配列１４０１以外の「任意の配列の集合」を選ぶようにすれば良い。
【０１３４】
また、図１３のような解析結果を得るには、これは図２４に示すフローチャートを用いた処理で説明した「配列seq j内に存在する保存領域Cを検出する処理」を全ての対象配列１４０１に対して実行すればよい。この処理によって保存領域Cが他の対象配列１４０１としてのゲノム配列でも検出されれば、そのゲノム配列中の保存領域Cの位置を記録することによって、図１３で示す表示結果を得ることができる。
【産業上の利用可能性】
【０１３５】
複数のＤＮＡ（またはアミノ酸）配列から、ゲノム配列を比較してゲノム配列中における意味を調べるゲノム解析に関し、特に、進化の過程で保存されている保存領域を見つけ、表示する進化過程を考慮した保存領域検出システムにおいて利用することが可能である。
【図面の簡単な説明】
【０１３６】
【図１】進化におけるゲノム配列の変化のうちsubstitutionについて説明する説明図である。
【図２】進化におけるゲノム配列の変化のうちinsertionについて説明する説明図である。
【図３】進化におけるゲノム配列の変化のうちdeletionについて説明する説明図である。
【図４】進化におけるゲノム配列の変化のうちinversionについて説明する説明図である。
【図５】祖先配列のタイプであるオーソログとパラログについて説明する説明図である。
【図６】ドットマトリックス解析の例を示す説明図である。
【図７】マルチプルアライメント解析の例を示す説明図である。
【図８】系統樹解析の例を示す説明図である。
【図９】系統樹と保存領域の関係を組み合わせて表示した画面を示す説明図である。
【図１０】保存領域と既知の情報を組み合わせて表示した画面を示す説明図である。
【図１１】複数の配列で保存領域を対応付けて表示した画面を示す説明図である。
【図１２】複数の配列で保存領域を対応付けて表示した画面を示す説明図である。
【図１３】ある配列で見つかった保存領域を、他の配列に対して検索し、その検索結果を表示する、本発明の表示例のひとつである。
【図１４】本実施の形態における進化過程を考慮した保存領域検出システム１００のシステム構成を概略的に示す機能ブロック図である。
【図１５】本実施の形態における進化過程を考慮した保存領域検出システム１００の対象配列１４０１のデータ構成を示す説明図である。
【図１６】本実施の形態における進化過程を考慮した保存領域検出システム１００の構成情報１４１３のデータ構成を示す説明図である。
【図１７】本実施の形態における進化過程を考慮した保存領域検出システム１００において、対象配列１４０１の索引情報を表示するためのデータ構造を示す説明図である。
【図１８】本実施の形態における進化過程を考慮した保存領域検出システム１００において、対象配列１４０１の保存領域を記録するためのデータ構造を示す説明図である。
【図１９】本実施の形態における進化過程を考慮した保存領域検出システム１００において、対象配列１４０１間の保存領域同士の対応関係を記録するためのデータ構造体を示す説明図である。
【図２０】本実施の形態における進化過程を考慮した保存領域検出システム１００において、異なる種類の保存領域を記録するためのデータ構造を示す説明図である。
【図２１】本実施の形態における進化過程を考慮した保存領域検出システム１００において、全体の処理の流れを概略的に示すフローチャートである。
【図２２】本実施の形態における進化過程を考慮した保存領域検出システム１００において、各対象配列１４０１に対して索引情報を作成する処理を詳細に示すフローチャートである。
【図２３】本実施の形態における進化過程を考慮した保存領域検出システム１００において、保存領域を検出する処理を詳細に示すフローチャートである。
【図２４】本実施の形態における進化過程を考慮した保存領域検出システム１００において、保存領域を検出する処理を詳細に示すフローチャートである。
【図２５】本発明の進化過程を考慮した保存領域検出システムにおいて、保存領域を算出する処理を詳細に示すフローチャートである。
【図２６】本実施の形態における進化過程を考慮した保存領域検出システム１００において、保存領域を検出する処理を詳細に示すフローチャートである。
【図２７】本実施の形態における進化過程を考慮した保存領域検出システム１００において、ゲノム配列の中の保存領域を検出する処理の流れを詳細に示すフローチャートである。
【図２８】本実施の形態における進化過程を考慮した保存領域検出システム１００において、配列データKtupleArrayDとIdxArrayDの一例を示した説明図である。
【図２９】本実施の形態における進化過程を考慮した保存領域検出システム１００において、二つの配列間の保存領域を検出した状態を示した説明図である。
【符号の説明】
【０１３７】
１００ 保存領域検出システム
１４０１ 対象配列
１４０２ 表示装置
１４０３ キーボード
１４０４ マウス
１４０５ 配列DB
１４０６ 中央処理装置
１４０７ プログラムメモリ
１４０８ 保存領域計算処理部
１４０９ 系統樹計算処理部
１４１０ 分析結果表示処理部
１４１１ データメモリ
１４１２ 入力データ
１４１３ 系統樹
２６０１ 保存領域
【技術分野】
【０００１】
本発明は、複数のＤＮＡ（またはアミノ酸）配列から、ゲノム配列を比較してゲノム配列中における意味を調べるゲノム解析に関し、特に、進化の過程で保存されている保存領域を見つけ、表示する進化過程を考慮した保存領域検出システムに関する。
【背景技術】
【０００２】
従来技術においては、世界中の配列解析プロジェクトによって、ヒトや動植物のゲノム解析が進み、それらの情報は公共データベース等を通して容易に入手できるようになっている。さまざまな生物における種間や種内のＤＮＡ配列のうちゲノム解析の対象となるゲノム配列同士を比較することによって、ゲノム配列中で各々の種の特異的な部分や、または全ての種に共通な部分を明らかにすることができ、このような特異的な部分、共通な部分に関する情報を用いることで進化のプロセスや、生物学的意味の解釈に役立てることが可能である。例えば、哺乳類のMHC（the Major
Histocompatibility Complex）領域について調べた文献（Hughes
AL, Yeager M. Natural selection at major histocompatibility complex loci of
vertebrates.Annu Rev Genet.
1998;32:415-35やMcConnell TJ,
Talbot WS, McIndoe RA, Wakeland EK. The origin of MHC class II gene
polymorphism within the genus Mus.Nature.
1988 14;332(6165):651-4.やLawlor DA, Ward
FE, Ennis PD, Jackson AP, Parham P. HLA-A and B polymorphisms predate the
divergence of humans and chimpanzees.Nature.
1988 15;335(6187):268-71.など）では、数百年にわたってＭＨＣがゲノム配列中に存続し機能していることが、各ゲノムを比較することによって明らかとなっている。
【０００３】
さて、ゲノム配列を比較するとは、進化の過程においてゲノム配列中に起こる変化（変異）を捉える、即ち、把握することであるが、進化におけるゲノム配列の変化（変異）とは、具体的にはsubstitution・deletion・insertion・inversionが挙げられる。図１乃至４は、これらの変化の様子を示した説明図である。図１は、substitutionの変化の様子を示しており、ゲノム配列中の塩基ＡがＣに置換されている。図２は、insertionの変化の様子を示しており、ゲノム配列中の塩基ＡとＴとの間に、新たに塩基Ｃ追加され挿入されている。図３は、deletionの変化の様子を示しており、塩基Ｔが削除されている。図４は、inversionの変化の様子を示しており、ゲノム配列中のＡＴＴがＴＴＡとなっており順序が逆となるように並び替えられている。
【０００４】
これらの４種類の変化のうち、substitutionは一塩基単位の変化で起こるが、deletion・insertion・inversionは数百から数万塩基を含むブロック単位の全体で一度に起こることがあり、生物の種の進化の過程でこれらの変化が起こるとゲノム配列中で蓄積してゲノム配列全体に変化を与え、結果的にそれぞれ異なる生物の種を生まれさせていくこととなっている。
【０００５】
ゲノム配列を比較してゲノム解析が行われたことにより明らかとなっている重要な事実のひとつは、生物にとって重要なゲノム領域（遺伝子など）では、ゲノム配列の変化を受けていないことが多いことである。これは、そのような部分で変化を受けると、ほとんどの場合にはそのような部分の変化を受けた生物は絶滅することが多いため、結果的に、そのような重要なゲノム領域で変化を受けなかった生物が絶滅せずに現在まで残っており、重要なゲノム領域で変化を受けないことが現在まで存在するために必要であると考えられているからである。異なる種類の生物の種のＤＮＡ配列を比較すると、生物の種類によっては変化を受けて互いに異なるＤＮＡ配列を有していることもあるがこれらをアミノ酸毎のレベルで調べてみると変化していないことが多い。
【０００６】
このような重要なゲノム領域等のゲノム配列の変化を受けていない領域は、保存領域と呼ばれている。研究者は、この保存領域においてゲノム配列の変化を受けていない事実を利用しており、異なる種類の生物の種のゲノム配列を相互に比較して保存領域を見つけこの保存領域に基づいて生物学的な意味を推測するための手がかりとしている。
【０００７】
また、別の重要な事実として、ゲノム配列は進化の歴史をとどめており示していることが挙げられる。一般的に近縁の種（ヒトとチンパンジー等）は、遠縁の種（ヒトと酵母等）よりも、ゲノム配列として類似している部分が多い。これは種が分化してから、近縁の種同士ではそれほど時間が経過しておらず、遠縁の種同士では、長時間経過しているからである。また、特定のＤＮＡ配列を含む遺伝子の状態の推移を追跡することで進化の歴史を把握することも可能である。
【０００８】
図５はこのような遺伝子の状態の推移による進化の歴史を示した説明図である。図５では種１と種２の祖先においてＤＮＡ配列を含む或る遺伝子ａが重複されて一列に配置されたタンデム（縦列）遺伝子ａ１とａ２を生じ、その後、別々の種類の生物の種に種文化した様子を示している。種１の遺伝子ａ１と種２の遺伝子ａ１（または種１の遺伝子ａ２と種２の遺伝子ａ２）は共通の祖先のタンデム遺伝子ａ１（またはタンデム遺伝子ａ２）を共有することとなっておりこれはオーソログと呼ばれている。一方、種１または種２における遺伝子ａ１とａ２とは遺伝子ａの重複によって発生したものであり、これはパラログと呼ばれている。
【０００９】
また、図５に示す以外にも遺伝子の状態の推移による進化としてゼノログ（外来）と呼ばれるタイプのものもある。このゼノログでは或る遺伝子がその他のどの遺伝子とも進化的起源を共有していな状態で進化していく場合であり、共生やウィルスによって、類縁のない生物種からもたらされたもの、すなわち水平伝播によって引き起こされたものといわれている。
【００１０】
更に、遺伝子以外にも、遺伝子に含まれる配列においてSINEs（short
interspersed repetitive elements）やLINEs（long
interspersed repetitive elements）と呼ばれる特殊な配列がある。これらはゲノム配列中で自分自身を複製し、他の位置にこの複製した配列を挿入する性質を持っており、更に、一旦挿入されると欠失しない性質があるため、これらの特殊な配列も進化の歴史を把握するための手がかりとして利用されている。過去の報告（Verneau O, Catzeflis F, Furano AV. Determination of the evolutionary
relationships in Rattus sensu lato (Rodentia : Muridae) using L1 (LINE-1)
amplification events. J Mol Evol.
1997 45(4):424-36. や Furano AV,
Hayward BE, Chevret P, Catzeflis F, Usdin K. Amplification of the ancient
murine Lx family of long interspersed repeated DNA occurred during the murine
radiation. J Mol Evol. 1994
38(1):18-27.やMurata S, Takasaki N,
Saitoh M, Okada N. Determination of the phylogenetic relationships among
Pacific salmonids by using short interspersed elements (SINEs) as temporal
landmarks of evolution. Proc Natl Acad
Sci U S A. 1993 1;90(15):6995-9.など）によれば、種の文化が起こった後５０００万年以内なら、これらの配列は進化を調べるためのマーカーとして使うことができ、研究者はこれらの特殊な配列を用いたマーカーとしての情報を手がかりとして進化の歴史上での出来事を推測することを行っている。
【００１１】
実際にゲノム配列内の保存領域や進化の歴史を調べるための手法としては、主に３種類の方法が使用されている。１つ目の手法はドットマトリックス解析と呼ばれる手法で、二つのゲノム配列の間で変化を受けずに共通して存在している保存領域を見つけるために行われる。図６は、ドットマトリックス解析によりＡＴＧＧＣＡの配列１とＣＡＴＴＧＧＣＴの配列２に存在する保存領域を解析した様子を示す説明図である。このドットマトリックス解析では、二つの配列の長さに対応した縦６個×横８個のマトリックスを作成しこのマトリックスの縦軸と横軸のそれぞれに沿って配列１と配列２を並べる。そして、縦軸の配列の各要素と横軸の配列の各要素を比較し、縦軸および横軸に同じ要素である塩基（または残基）がある場合にはその同じ塩基の縦軸および横軸の座標に該当するドットに印を付していく。
【００１２】
図６においては該当するドットを印として濃色（強調）表示する。そして、配列１および配列２の間で保存領域が存在する場合には印を付したドットが対角線方向に並んで構成されこれを視覚的に確認することで保存領域を把握することができるようになっている。図６の点線で囲まれた部分で示すように、濃色（強調）表示したドットが対角線方向に並んでおり配列１のＡＴＧＧＣと配列２のＡＴＴＧＧＣが類似しており保存領域となっていることが明らかとなっている。なお、配列１の塩基を相補鎖の塩基に変換する、すなわち、ＡをＴ、ＴをＡ、ＧをＣ、ＣをＧに変換することによりｒｅｖｅｒｓｅ ｃｏｍｐｌｅｍｅｎｔ配列と配列２との間の保存領域を明らかとすることも可能である。この場合には、印を付したドットが、配列１の場合とは逆の対角線方向に並んで構成されこれを視覚的に確認することで保存領域を把握することができるようになっている。
【００１３】
２つ目の手法は、マルチプルアライメントと呼ばれる手法で、複数の配列を並べたとき同じ要素が１つの列にできるだけ多く集まるような最適な並べ替えを行う手法である。図７は、マルチプルアライメントによる手法を示した説明図である。図７では１５個のゲノム配列としてのアミノ酸配列に対してマルチプルアライメントを実行した結果で、各列に同じアミノ酸（類似したアミノ酸）が並ぶように、ギャップ文字（−）を配列中に挿入している。マルチプルアライメントは、そこに含まれるゲノム配列の間の進化的な歴史を表現したものとみることができる。
【００１４】
もしミスマッチとして相互に異なるアミノ酸の個数が少なく、非常に良いマルチプルアライメントが得られるならば、それらのアミノ酸配列は共通の祖先から、比較的最近分かれてきたものと推測される。反対に、ミスマッチの個数が多く良いアライメントが得られないグループの間には、より複雑で遠い進化上の関係が存在する。あるゲノム配列はミスマッチの個数が少なく良く似ており、あるゲノム配列はミスマッチの個数が多く似ていない一群のゲノム配列のマルチプルアライメントを求められれば、それらのゲノム配列間の進化的関係を見出すことが可能である。
【００１５】
最後に、３つ目の手法は、系統樹解析と呼ばれる手法である。これは互いに類縁のある塩基配列（あるいはアミノ酸配列）が含まれているファミリーの系統を解析し、進化過程でそのファミリーが派生してきた道筋を決定することである。図８は８つの種から得られたファミリーに含まれるゲノム配列に対して系統樹解析を行った様子を示す説明図である。ゲノム配列間の関係を、各ゲノム配列を枝先に配置したツリー構造の木として表し、木の内部における分岐関係を、異なるゲノム配列がどの程度の類縁関係にあるかを反映させて表示している。枝の長さは近縁／遠縁の度合いに対応しており、枝の長さが短いほど近縁の関係であることを示している。
【００１６】
この系統樹解析では、類縁関係や近縁／遠縁の度合いを見ることにより個々の生物の種の進化において生じてきた変化の解析のみならず、ゲノム配列のファミリーの進化についても調べることが出来る。それにより、系統樹上の隣り合った枝を占めるゲノム配列が、最も近縁なゲノム配列だと決定できる。ある生物あるいは生物群においてゲノム配列としての遺伝子ファミリーが見出される場合、その遺伝子間の系統関係を調べれば、同じ機能をもつ遺伝子がどれかを予測するのに役立つ。これらの機能予測が得られれば、遺伝学的実験によってその機能を確認できる。系統樹解析は、例えばウィルスのような、急速に変化している生物種のおいて生じている変化を追うためにも使われる。ある集団内での変化の型の系統樹解析は、例えば、ある特定の遺伝子が自然選択を受けているかどうかといった、疫学などの応用にあたって大切な情報を明らかにする。また、従来のバイオチップにおいては、系統樹のノード等に対応して、複数の異なるターゲットの塩基配列に共通して存在する部分配列と特異的にはハイブリダイズするプローブを設計し、スポットしたものが提案されている（例えば、特許文献１参照。）。
【００１７】
【特許文献１】特開２００２−３３０７６８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従来の技術においては、ゲノム配列同士を比較して、そこから生物学的な意味を読み取るためには、上に示したような複数のゲノム配列間で保存されている保存領域を見つけ、そして、それがどのような種で共有されているか、つまりどのような進化を歩んできたかを調べることが必要である。
【００１９】
しかしながら、上述のような従来の技術を用いても上に示した三つの方法を駆使しても、保存領域とその進化的な関係について、両者を包括的に理解するのは困難・あるいは非常に煩雑な手間を伴う。ドットマトリックス解析では二つのゲノム配列間の保存領域は分かるが、それはどの進化の段階から保存されているのかわからない。マルチプルアライメント解析では、inversionになって保存されていてもそれを検出することができない。また系統樹解析では、進化の過程は分かるが、具体的にどのようなゲノム配列が類縁関係で保存されているのか、そしてどの進化のレベルでinversionやinsertion、deletionが起こったのかどうかわからない。
【００２０】
例えば、比較対象のゲノム配列のうち、進化的に近い生物種のファミリーで、共通した保存領域にはどのようなものがあるかを従来の方法で調べる場合を考える。研究者は、まず系統樹解析を行い、進化的に近いファミリーをみつける。そしてマルチプルアライメントを実行するか、あるいはドットマトリックス解析を行う。しかし、マルチプルアライメントを実行する場合、長い配列（数千塩基以上）を比較するには、実際的な問題として多大な時間を要する。また、マルチプルアライメントは、ある程度類似したゲノム配列を入力とすることが想定されているので、イントロン配列を多く含む場合や、入力配列が遺伝子以外の領域である場合、アライメントはうまくいかない。更にこの解析は、上にも述べたように、ゲノム配列中にinversionが起こっていてもそれを検出することができない。したがって、比較対象となるゲノム配列は非常に限られたものとなってくるという問題があった。
【００２１】
またゲノム配列が、マルチプルアライメントに適した配列であったとしても、ファミリーの配列に共通して存在し、ファミリーでない配列には存在しない保存領域を目視で確認する必要がある。一方、ドットマトリックス解析では、この解析手法の性質上、一度に二つのゲノム配列しか比較できない。したがって、ファミリーの生物種で共通した保存領域を見つける場合、ファミリーの配列同士で繰り返しドットマトリックス解析を行って保存領域をみつけ、更にファミリーに属していない配列でその領域が保存されていないことを確かめなければならない。これはファミリーの数や全体の比較するゲノム配列数が大きくなると、ドットマトリックス解析で比較を行う作業量が膨大なものとなり、手に負えないものとなってしまうという問題があった。
【００２２】
それ故本発明では、従来技術の問題点を鑑みてなされたものであり、その目的とするところは、ゲノム解析の対象となる種のゲノム配列から保存領域を検出し、各々の種間の関係や各保存領域の関係を明確に表示することが可能な進化過程を考慮した保存領域検出システムを提供することを目的とする。
【課題を解決するための手段】
【００２３】
上記課題を解決するために、本発明は、複数のＤＮＡ配列のうちゲノム解析の対象となるゲノム配列の中に配列の変化を受けておらず進化的に保存されている保存領域を見つける進化過程を考慮した保存領域検出システムにおいて、
ゲノム配列に基づいて得られる系統樹を参照して、この系統樹を構成している中間ノードに属するゲノム配列を認識する配列認識手段と、
中間ノードに属するゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していく保存検出手段とを備えたことを特徴とする。
【００２４】
このような発明においては、配列認識手段が系統樹を構成している中間ノードに属するゲノム配列を認識し、保存検出手段が中間ノードに属するゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していくので、正確にゲノム解析の対象となる種のゲノム配列から配列の変化を受けていない保存領域を検出することができる。
【００２５】
また、上述の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する２つのゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していき、ミスマッチの文字の個数が所定の個数に達するまでの領域を保存領域として検出することとしても良い。
【００２６】
このような発明においては、保存検出手段は、中間ノードに属する２つのゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していき、ミスマッチの文字の個数が所定の個数に達するまでの領域を保存領域として検出するので、全体的に略同一で配列の変化を受けておらず保存領域とみなすことができる領域を適切に保存領域として検出することができる。
【００２７】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する複数のゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内で検出した保存領域に基づいて、中間ノードを変えながら繰り返しこの検出した同一の保存領域を検出していき、全ての中間ノードに属するゲノム配列内の保存領域を検出しても良い。
【００２８】
このような発明においては、保存検出手段は、中間ノードを変えながら繰り返しこの検出した同一の保存領域を検出していき、全ての中間ノードに属するゲノム配列内の保存領域を検出するので、系統樹を構成する全ての中間ノードに属するゲノム配列内の保存領域を検出できる。
【００２９】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段が検出したゲノム配列内の各保存領域をそれぞれ毎に異なる形態の線により構成し、前記系統樹上の中間ノードを形成する枝を、中間ノードに属するゲノム配列内の各保存領域に対応させた形態の線により構成し、前記各保存領域と系統樹を同時に表示する解析結果表示手段を備えたこととしても良い。
【００３０】
このような発明においては、解析結果表示手段が各保存領域をそれぞれ毎に異なる形態の線により構成し、系統樹上の中間ノードを形成する枝を、中間ノードに属するゲノム配列内の各保存領域に対応させた形態の線により構成し、各保存領域と系統樹を同時に表示するので、研究者は各保存領域を明確に区別して参照することができ、また、各保存領域と系統樹上の中間ノードとの対応関係を参照して進化的に保存された保存領域を確認し、進化過程を推測することが可能である。
【００３１】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、既知のゲノム配列に関する情報と組み合わせて同時に表示することとしてもよい。
【００３２】
このような発明においては、各保存領域に組み合わされた既知のゲノム配列に関する情報を参照して進化過程を推測することが可能である。
【００３３】
上述の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、各保存領域が含まれるゲノム配列と組み合わせ、各ゲノム配列間に含まれる同一の保存領域を関連付けて表示しても良い。
【００３４】
このような発明においては、関連付けて表示された同一の保存領域の状況を参照して進化的に保存された保存領域を確認し、進化過程を推測することが可能である。
【００３５】
上述の進化過程を考慮した保存領域検出システムにおいて、
任意の配列に基づいて、前記系統樹を構成している中間ノードに属するゲノム配列を検索する配列検索手段と、
前記配列検索手段が検索した結果得られたゲノム配列の情報を参照して、前記系統樹を構成している中間ノードに属するゲノム配列に関する情報を特定の表示方法で表示する特定表示手段を備えても良い。
【００３６】
このような発明においては、特定の表示方法で表示されたゲノム配列に関する情報を参照して任意の配列が進化的に保存されている様子を確認し、進化過程を推測することが可能である。
【００３７】
上述の進化過程を考慮した保存領域検出システムにおいて、
特定表示手段は、
前記配列検索手段が検索した結果得られたゲノム配列を、当該任意の配列部分を関連付けて表示することとしても良い。
【００３８】
このような発明においては、関連付けて表示された当該任意の配列部分を参照して保存されている状況を確認し、進化過程を推測することが可能である。
【発明の効果】
【００３９】
以上説明したように、本発明によれば、ゲノム解析の対象となる種のゲノム配列から保存領域を検出し、各々の種間の関係や各保存領域の関係を明確に表示することが可能である。
【発明を実施するための最良の形態】
【００４０】
以下、図面を参照して本発明の実施の形態を説明する。
【００４１】
図１４は、本発明にかかる進化過程を考慮した保存領域検出システムの全体構成を示す説明図である。この保存領域検出システム１００は、ゲノム解析において、比較される対象となるゲノム配列のデータである対象配列１４０１と、それらの各対象配列１４０１を用いて系統樹を構成するための情報である構成情報１４１３と、ゲノム解析の解析結果を画像等により表示するための表示装置１４０２と、保存領域検出システム１００での数値や文書情報等の情報の入力や選択の操作を行うための入力手段であるキーボード１４０３やマウス１４０４と、ゲノム解析の解析結果のデータに参考情報として注釈付けする既知のゲノム配列及びこの既知のゲノム配列に付属する情報が格納されている配列ＤＢ１４０５と、後述するプログラムメモリ１４０７や図示しない記憶装置に格納されたプログラムを実行することにより保存領域の検出や系統樹のデータの構築や解析結果の表示等の各処理を行う中央処理装置１４０６（以下、ＣＰＵ１４０６という。）と、中央処理装置１４０６が行う各処理に必要なプログラムを格納するプログラムメモリ１４０７と、中央処理装置１４０６での処理の際に必要な演算結果等のデータを一時的に格納するデータメモリ１４１１とを備えて構成されている。
【００４２】
プログラムメモリ１４０７は、図１４に示すように、入力された各対象配列１４０１からそれらの対象配列１４０１間で保存されている保存領域を検出する処理を行うための保存領域計算処理部１４０８と、各対象配列１４０１を用いて系統樹を構築する処理を行う系統樹計算処理部１４０９と、これら解析・計算結果を表示する処理を行うための分析結果表示処理プログラム１４１０とを備えている。これらのプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＭＯ、フロッピー（登録商標）ディスク等の記録媒体に格納し、ＣＰＵ１４０６がこれらの記録媒体から読み出すことにより提供することもできるし、インターネット等の公衆網のネットワークを介してサーバからダウンロードして提供することもできる。
【００４３】
配列ＤＢ１４０５は、ＣＰＵ１４０６に接続された記憶装置に格納されていてもよいし、遠隔地に設置されたサーバコンピュータが管理する構成とし、そのサーバコンピュータ内のデータベースからインターネット等の公衆網のネットワーク等を介して配列ＤＢ１４０５に含まれている遺伝子データを取得するようにしてもよい。また、データメモリ１４１１は、プログラムの実行において入力データとして用いられる入力データ１４１２を含んでいる。
【００４４】
図１５は、対象配列１４０１の一例を示す説明図である。ここでは対象配列１４０１に該当する各ゲノム配列をＦＡＳＴＡ形式により表示しており、ゲノム配列を識別するための名称等を「＞」の後に表示し、その次の行から、ゲノム配列そのものを表示している。この他にも、ゲノム配列を表す形式として、ＧｅｎＢａｎｋ形式やＥＭＢＬ形式で表示することとしてもよい。
【００４５】
図１６は、各対象配列１４０１を用いて系統樹を構成するための構成情報１４１３の一例を示す説明図である。この構成情報１４１３では系統樹のリーフと枝の長さを対象配列１４０１の各ゲノム配列の名称に対応付けており一組の括弧及び数値により一つの中間ノードに関する情報を形成している（数値はその中間ノードの上位の位置の中間ノードまでの枝の長さを示している）。そしてその中間ノードが自己の位置よりも下位側に（系統樹上でリーフに近い）更に中間ノードを有しているときは、入れ子構造で表現する形式をとっている。すなわち、ＢＮＦ記法で表示すると次のようになる。
【００４６】
ノード::=(ノード,ノード):この中間ノードからその上位中間ノードまでの枝長|配列名:この葉から上位中間ノードまでの枝長
【００４７】
そして、この構成情報１４１３では、一組の括弧に囲まれた２つの名称または中間ノードによりゲノム配列の近縁関係を示しており、この系統樹のルートに対応する中間ノード間の相対関係に関する情報が構成されている。例えば「（種１：１５，種２：１０）：２０」は後述する図９に表示された系統樹の９０２の部分の中間ノードを示しており、種１（リーフ）から種１と種２の分岐点までの枝長が１５、種２から種１と種２の分岐点までの枝長が１０、そして、この分岐点とその上の中間ノード（９０１に対応するノード）までの枝長が２０であることを示している。この他にも、系統樹間の関係を表す形式として、Ｐｈｙｌｉｐ形式・ＣＬＵＳＴＡＬ形式・Ｄｉｓｔａｎｃｅ Ｍａｔｒｉｘ形式により表示することとしても良い。
【００４８】
図１７は、対象配列１４０１に該当する全てのＤＮＡ（またはアミノ酸）配列に関する索引情報を作成するためのデータ構造を示す構成図である。この索引情報に含まれる配列KtupleArrayDはpk個の要素からなる配列で、ｐは配列を構成する要素の種類数を示しており、すなわちＤＮＡ配列の場合は４、アミノ酸配列の場合は２０となる。ｋはｔｕｐｌｅ（文字列）の長さを示している。配列KtupleArrayDの配列の各要素には各tupleが割り当てられる。例えば対象配列１４０１がＤＮＡ配列で、ｋが２のとき、配列KtupleArrayDは１６個の要素からなり、それぞれの要素には、AA・AT・AG・AC・TA・TT・TG・TC・GA・GT・GG・GC・CA・CT・CG・CCの１６種類のtupleが割り当てられる。
【００４９】
また、この配列KtupleArrayDの各要素には、その要素に割り当てられたtupleが対象配列１４０１中に最も後側に現れたtupleの位置を表す。その要素に割り当てられたtupleが配列中にない場合は、０で表す。
【００５０】
配列IdxArrayDは対象配列１４０１と等しい長さの配列であり対象配列１４０１の各要素に割り当てられた要素からなる配列である。配列IdxArrayDの各要素は対象配列１４０１上の各位置に割り当てられており、それら各要素に割り当てられた文字から始まるtupleと同じtupleがその要素より前側の配列中に現れた場合には、その現れたもののうちそれら各要素の最も直前に現れた要素の位置を表す。また、もしそれら各要素と同じtupleが前に現れない場合には０で表す。
【００５１】
図２８は、対象配列１４０１としての配列GTCTCACGACACTCに対して作成された配列KtupleArrayDとIdxArrayDを表示した説明図である。この配列ではtuple TCは配列中の２番目、４番目、１３番目に現れており、配列KtupleArrayDのTCに対応する要素（KtupleArrayD[８]）に、tuple TCが対象配列１４０１中に最後に現れた位置１３が表示されている。またIdxArrayD[１３]には位置１３に現れたtuple TCと同一のTCがその直前に現れた位置である「４」、IdxArrayD[４]には位置４に現れたtuple TCと同一のTCがその直前に現れた位置である「２」が表示されている。したがって、ここで示したように、特定のtupleが配列中のどこにあるかを、二つの配列KtupleArrayDとIdxArrayDを用いることで、高速に検索することが出来る。配列KtupleArrayRおよびIdxArrayRは、配列KtupleArrayDとIdxArrayDと同様に対象配列１４０１としてのDNA配列（またはアミノ酸配列）のreverse complement配列に対して、作成される。
【００５２】
図１８は、対象配列１４０１の保存領域を記録するためのデータ構造を示す説明図である。このデータ構造で示す構造体配列ConservedRegは、各対象配列１４０１毎に、保存領域が存在していれば作成されるものであり、保存領域を示す位置１８００、保存領域の長さ１８０１、保存領域の向き（順方向か逆方向か）１８０２の各データから構成されている。
【００５３】
図１９は、各対象配列１４０１間の保存領域同士の関係を記録するためのデータ構造体ListOfConservedRegを示す説明図である。このデータ構造体は、構成情報１４１３上の各中間ノードで、保存領域毎に作られるものである。対象配列１４０１を識別するための配列名１９００、この対象配列１４０１において作成されているいずれのConservedRegが対応しているかを示すために、配列名１９００毎に作成された各構造体配列ConservedRegを識別するためのindex１９０１の各データから作成されている。
【００５４】
図２０は、図１９で述べた関連する保存領域の集合を表す配列ListOfConservedRegを集めた配列AllOfConservedRegのデータ構造を示す説明図である。この配列AllOfConservedRegの各要素はListOfConservedRegへリンクしたポインタが表示されており、構成情報１４１３上の各中間ノード毎に、この配列AllOfConservedRegが１つ作成される。この配列AllOfConservedRegに該当する中間ノードに属するゲノム配列で保存されている異なる種類の保存領域のそれぞれを、各要素とListOfConservedRegとでリンクさせてこの配列によって表示している。なお、本実施の形態における進化過程を考慮した保存領域検出システムは、一般に使用されている各種の情報処理を行うための情報処理装置であるパーソナルコンピュータを用いて実現することも可能である。
【００５５】
続いて、上述のような構成を有する本実施形態の進化過程を考慮した保存領域検出システムの動作について図２１乃至図２７に示すフローチャートを用いて詳細に説明する。図２１乃至図２７に示すフローチャートでは、ＣＰＵ１４０６が処理を行うことにより、図９、図１０、図１１、図１２、図１３に示す画像のデータを表示させるために必要となる系統樹１４１３の各リーフに対するConservedRegと、保存領域の関連を保持する配列ListOfConservedRegと、配列AllOfConservedRegを求めるようになっている。以下に説明する動作では、対象配列１４０１および系統樹１４１３から、系統樹１４１３の各中間ノードに対して、これらの三つの配列を得るためのアルゴリズムを説明する。
【００５６】
本実施の形態における進化過程を考慮した保存領域検出システム１００の概略的な処理の流れを図２１に示すフローチャートを用いて説明する。まず、進化過程を考慮した保存領域検出システム１００のＣＰＵ１４０６は、研究者がフロッピー（登録商標）ディスクやＣＤ−ＲＯＭ等の外部記録媒体を用いて入力した対象配列１４０１と系統樹の構成情報１４１３のデータを読み込み、データメモリ１４１１内に格納して入力データ１４１２として保持する（ステップ２１００）。このとき、構成情報１４１３については系統樹自体の情報を読み込まなくても、系統樹を構成するために必要となるパラメータ情報のみを入力しこのパラメータ情報に基づいてＣＰＵ１４０６が構成情報１４１３のデータを作成することとしても良い。
【００５７】
次に、ＣＰＵ１４０６は、保存領域を検出するためのパラメータk, w, mを読み込み、データメモリ１４１１の入力データ１４１２として保持する処理を行う（ステップ２１０１）。ここで、kはtupleの文字列の長さ、wはウィンドウの長さ、mはウィンドウ内で許容されるミスマッチの数、即ち保存領域を検出する２つのゲノム配列で相互に異なる文字の最大限度数を示している。保存領域を検出する際に保存領域として検出を行っている領域中の連続するｗ個の文字（塩基または残基）に対し、２つの配列で相互に異なる文字であるミスマッチの個数が最大m個までを許容するようになっている。例えば、図２９では、ウィンドウサイズｗを５、許容されるミスマッチｍの数を１としたときの配列Aと配列Bの２つのゲノム配列間の保存領域の場所を示している。この場合、連続する５個の文字のペア毎に同一の文字の配列を検出して保存領域を検出していった際にミスマッチの個数が全ての５個の文字のペア毎で１個以内となっており領域２６０１は二つの配列間の保存領域になっている。
【００５８】
次に、ＣＰＵ１４０６は、対象配列１４０１がＤＮＡ配列であり、それをアミノ酸配列として比較したい場合、全てのＤＮＡ配列をアミノ酸配列に変換する処理を行う（ステップ２１０２）。
【００５９】
次に、ＣＰＵ１４０６は、各対象配列１４０１に対して上述のように図１７乃至図２０に示す索引情報、すなわちKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ] を作成する処理を行う（ステップ２１０３）。この処理の詳細については後述する。
【００６０】
次に、ＣＰＵ１４０６は、構成情報１４１３により構成される系統樹の全ての中間ノードに対して、その中間ノードに属するゲノム配列から全ての保存領域を検出したか否かを判定する処理を行う（ステップ２１０４）。
【００６１】
次に、ＣＰＵ１４０６は、全ての保存領域を検出していない場合には（ステップ２１０４のＮＯ）、構成情報１４１３により構成される系統樹の全ての中間ノードに対して、その中間ノードに属するゲノム配列のうち保存領域を未だ検出していないものを選択する処理を行う（ステップ２１０５）。
【００６２】
次に、ＣＰＵ１４０６は、この選択した各ゲノム配列の間で保存されている保存領域を検出する処理を行う（ステップ２１０６）。この保存領域を検出する処理は後で詳しく述べる。この保存領域を検出する処理が終了すると次にステップ２１０４の処理を実行する。
【００６３】
次に、ＣＰＵ１４０６は、全ての保存領域を検出した場合には（ステップ２１０４のＹＥＳ）、保存領域に基づいて配列ＤＢ１４０５内を検索し、同一の保存領域を有する種のゲノム配列の情報等の保存領域に関連する情報等があればこの関連情報を以上のゲノム解析の結果に付与する。そして、ゲノム解析の結果を表示装置１４０２に表示する処理を行い（ステップ２１０７）、全体の処理を終了する。
【００６４】
続いて、上述のステップ２１０３における、各対象配列１４０１に対して索引情報、すなわちKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ] を作成する処理について図２２に示すフローチャートを用いて詳細に説明する。まず、ＣＰＵ１４０６は、個々の対象配列１４０１に対応するKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ]の全要素を0で初期化する処理を行う（ステップ２２００）。
【００６５】
次に、ＣＰＵ１４０６は、変数ｊ=1を設定する処理を行う（ステップ２２０１）。
【００６６】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の配列終端側で最も後側のtupleに該当する要素の位置を示す数値、すなわちj=配列長−kとなっているか否かを判定する（ステップ２２０２）。j=配列長−kとなっている場合には（ステップ２２０２のＹＥＳ）、ステップ２２０７の処理を実行する。
【００６７】
次に、ＣＰＵ１４０６は、j=配列長−kとなっていない場合には（ステップ２２０２のＮＯ）、対象配列１４０１のj番目からはじまるk個の文字列からなるtupleをKと設定し、このKに割り当てられている配列KtupleArrayD[ ]の要素インデックス（即ち配列KtupleArrayD[ ]内の要素の位置を示す要素番号）を iと設定し、配列KtupleArrayD[ ]の配列中の各要素を構成していく処理を行う（ステップ２２０３）。例えば図２８に示す配列KtupleArrayD[
]では、tuple KがTCの場合には、i は８番目の要素インデックスを示す「８」となっている。
【００６８】
次に、ＣＰＵ１４０６は、IndexArrayD[j]にKtupleArrayD[i]の数値を代入し、また、KtupleArrayD[i] に j を入力する（ステップ２２０４、２２０５）。KtupleArrayD[i]には、常に対象配列１４０１の配列中の最も後側に現れたtupleの位置を表示するため、この二つのステップ（２２０４，２２０５）は、変数ｊの数値をインクリメントしていき（ステップ２２０６）、配列中に新しくＫに該当するtupleが後側に現れるたびに、KtupleArrayD[i]の数値を更新し、IdxArrayD[j]にその更新前のKtupleArrayD[i]の数値を表示していき、更新していく処理となっている。
【００６９】
次に、以上のステップ２２０２〜２２０６の処理を全ての変数jに対して実行することにより、図２８に示すような、配列IndexArrayD[j]とKtupleArrayD[i]の索引情報を作成する。
【００７０】
次に、ＣＰＵ１４０６は、以上のステップ２２０２〜２２０６の処理を全ての変数jに対して実行し、j=配列長−kとなっている場合には（ステップ２２０２のＹＥＳ）、対象配列１４０１のreverse complement配列を改めて対象配列に設定する処理を行う（ステップ２２０７）。
【００７１】
次に、ＣＰＵ１４０６は、このreverse
complement配列に対する索引情報の配列IndexArrayR[j]とKtupleArrayR[i]を作成する処理を行う（ステップ２２０８〜２２１３）。ＣＰＵ１４０６は、上述の対象配列１４０１に対して以上のステップ２２０２〜２２０６の処理と同様の処理を実行していき配列IndexArrayR[j]とKtupleArrayR[i]を作成する。以上のステップ２２０８〜２２１３の処理を全ての変数jに対して実行し、j=配列長−kとなっている場合には（ステップ２２０９のＹＥＳ）、処理を終了する。
【００７２】
続いて、上述のステップ２１０６における、選択した各ゲノム配列の間で保存されている保存領域を検出する処理について図２３〜図２６で一体的に構成されたフローチャートを用いて詳細に説明する。まず、ＣＰＵ１４０６は、上述のステップ２１０５で選択した保存領域の検出対象となる各対象配列１４０１のそれぞれに対して、対象配列１４０１を識別する情報seq1, seq2, …, seqMを設定する処理を行う（ステップ２３００）。
【００７３】
次に、ＣＰＵ１４０６は、変数ｉ=1を設定する処理を行う（ステップ２３０１）。
【００７４】
次に、ＣＰＵ１４０６は、変数ｉが配列KtupleArrayDの終端位置を示す数値、すなわちｉ＞ pkとなっているか否かを判定する（ステップ２３０２）。ｉ＞ pkとなっている場合には（ステップ２３０２のＹＥＳ）、処理を終了する。
【００７５】
次に、ＣＰＵ１４０６は、定数c1にseq1の配列の配列KtupleArrayD[i]の数値を代入する処理を行う（ステップ２３０３）。上述の２１０３においてseq1の配列に対して作成したKtupleArrayD[i]の数値をc1に代入する。
【００７６】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２３０４）。c1が０である場合には（ステップ２３０４のＹＥＳ）、ステップ２３２８の処理を実行する。
【００７７】
次に、ＣＰＵ１４０６は、c1が０でない場合には（ステップ２３０４のＮＯ）、定数c2にseq2の配列の配列KtupleArrayD[i]の数値を代入する処理を行う（ステップ２３０５）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayD[i]の数値をc2に代入する。
【００７８】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３０６）。c2が０である場合には（ステップ２３０６のＹＥＳ）、ステップ２３１７の処理を実行する。
【００７９】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３０６のＮＯ）、配列seq1のKtupleArrayD[i]に割り当てられたtupleがseq1およびseq2の配列中に存在することとなっており、これら２つのゲノム配列seq1のc1番目とseq2のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３０７）。これら２つのゲノム配列seq1、seq2内の検出していく処理の開始位置からアライメントの連続するw個の文字列（塩基または残基）毎に保存領域を検出していき、seq1のc1番目とseq2のc2番目からアライメントを伸張させ保存領域として一致している文字列の個数を伸張させていく。そして、ゲノム配列seq1およびseq2間で相互に異なる文字であるミスマッチの個数がm個以下となっている文字列となっている領域の範囲内で保存領域を拡大させ、ミスマッチの個数がm個より多い文字列が存在した時点でその位置を保存領域の境界位置とする。このようにして保存領域を検出していき保存領域が存在する場合にはこれをCと設定する処理を行う。
【００８０】
次に、ＣＰＵ１４０６は、ステップ２３０７において保存領域が存在したか否かを判定する処理を行う（ステップ２３０８）。保存領域が存在しなかった場合には（ステップ２３０８のＮＯ）、ステップ２３１６の処理を実行し、ＣＰＵ１４０６は、c2にseq2のKtupleArrayD[c2]を代入する処理を行い、ステップ２３０６以降の処理を実行する（ステップ２３１６）。
【００８１】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３０８のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３０９）。変数jに対してｊ＝３と設定する処理を行う。
【００８２】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３１０）。
【００８３】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３１０のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３１１）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【００８４】
次に、ＣＰＵ１４０６は、ステップ２３１１において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３１２）。保存領域Ｃが存在しなかった場合には（ステップ２３１２のＮＯ）、ステップ２３１６の処理を実行し、ＣＰＵ１４０６は、c2にseq2のKtupleArrayD[c2]を代入する処理を行い、ステップ２３０６以降の処理を実行する（ステップ２３１６）。
【００８５】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３１２のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３１０以降の処理を再度実行する（ステップ２３１３）。そして、ステップ２３１０において、ｊ＞Ｍとなっている場合には（ステップ２３１０のＹＥＳ）、ステップ２３１４の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３１６の処理を実行する。
【００８６】
次に、ＣＰＵ１４０６は、ステップ２３０６においてc2が０である場合には（ステップ２３０６のＹＥＳ）、c2にseq2のKtupleArrayＲ[ｉ]を代入する処理を行う（ステップ２３１７）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayＲ[i]の数値をc2に代入する。
【００８７】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３１８）。c2が０である場合には（ステップ２３１８のＹＥＳ）、ステップ２３１５の処理を実行し、ＣＰＵ１４０６は、c1にseq1のIdxArrayD[c1]を代入する処理を行い、ステップ２３０４以降の処理を実行する（ステップ２３１５）。
【００８８】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３１８のＮＯ）、配列seq1のKtupleArrayD[i]に割り当てられたtupleがseq1の配列およびseq2のreverse complement配列中に存在することとなっており、これら２つのゲノム配列seq1のc1番目とseq2のreverse complement配列中のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３１９）。これは上述のステップ２３０７の処理と同様であり説明を省略する。
【００８９】
次に、ＣＰＵ１４０６は、ステップ２３１９において保存領域が存在したか否かを判定する処理を行う（ステップ２３２０）。保存領域が存在しなかった場合には（ステップ２３２０のＮＯ）、ステップ２３２７の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayR[c2]を代入する処理を行い、ステップ２３１８以降の処理を実行する（ステップ２３２７）。
【００９０】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３２０のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３２１）。変数jに対してｊ＝３と設定する処理を行う。
【００９１】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３２２）。
【００９２】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３２２のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３２３）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【００９３】
次に、ＣＰＵ１４０６は、ステップ２３２３において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３２４）。保存領域Ｃが存在しなかった場合には（ステップ２３２４のＮＯ）、ステップ２３２７の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayR[c2]を代入する処理を行い、ステップ２３１８以降の処理を実行する（ステップ２３２７）。
【００９４】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３２４のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３２２以降の処理を再度実行する（ステップ２３２５）。そして、ステップ２３２２において、ｊ＞Ｍとなっている場合には（ステップ２３２２のＹＥＳ）、ステップ２３２６の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３２７の処理を実行する。
【００９５】
次に、ＣＰＵ１４０６は、ステップ２３０４においてc1が０である場合には（ステップ２３０４のＹＥＳ）、c1にseq1のKtupleArrayＲ[i]を代入する処理を行う（ステップ２３２８）。上述の２１０３においてseq1の配列に対して作成したKtupleArrayＲ[i]の数値をc1に代入する。
【００９６】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２３２９）。c1が０である場合には（ステップ２３２９のＹＥＳ）、ステップ２３４２の処理を実行し、ＣＰＵ１４０６は、変数iをひとつインクリメントし、ステップ２３０２以降の処理を実行する（ステップ２３４２）。
【００９７】
次に、ＣＰＵ１４０６は、c2にseq2のKtupleArrayD[i]を代入する処理を行う（ステップ２３３０）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayD[i]の数値をc2に代入する。
【００９８】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３３１）。C2が０である場合には（ステップ２３３１のＹＥＳ）、ステップ２３４３以降の処理を実行する。
【００９９】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３３１のＮＯ）、seq1のreverse complement配列のKtupleArrayR[i]に割り当てられたtupleがseq1のreverse
complement配列中およびseq2の配列に存在することとなっており、これら２つのゲノム配列seq1のreverse complement配列中のc1番目とseq2のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３３２）。これは上述のステップ２３０７の処理と同様であり説明を省略する。
【０１００】
次に、ＣＰＵ１４０６は、ステップ２３３２において保存領域が存在したか否かを判定する処理を行う（ステップ２３３３）。保存領域が存在しなかった場合には（ステップ２３３３のＮＯ）、ステップ２３４１の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayD[c2]を代入する処理を行い、ステップ２３３１以降の処理を実行する（ステップ２３４１）。
【０１０１】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３３３のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３３３）。変数jに対してｊ＝３と設定する処理を行う（ステップ２３３４）。
【０１０２】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３３５）。
【０１０３】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３３５のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３３６）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【０１０４】
次に、ＣＰＵ１４０６は、ステップ２３３６において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３３７）。保存領域Ｃが存在しなかった場合には（ステップ２３３７のＮＯ）、ステップ２３４１以降の処理を実行する。
【０１０５】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３３７のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３３５以降の処理を再度実行する（ステップ２３３８）。そして、ステップ２３３５において、ｊ＞Ｍとなっている場合には（ステップ２３３５のＹＥＳ）、ステップ２３３９の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３４１の処理を実行する。
【０１０６】
次に、ＣＰＵ１４０６は、ステップ２３３１においてc2が０である場合には（ステップ２３３１のＹＥＳ）、c2にseq2のKtupleArrayＲ[i]を代入する処理を行う（ステップ２３４３）。上述の２１０３においてseq2の配列に対して作成したKtupleArrayＲ[i]の数値をc2に代入する。
【０１０７】
次に、ＣＰＵ１４０６は、c2が０であるか否かを判定する処理を行う（ステップ２３４４）。c2が０である場合には（ステップ２３４４のＹＥＳ）、ステップ２３４０の処理を実行し、ＣＰＵ１４０６は、c1にseq1のIdxArrayR[c1]を代入する処理を行い、ステップ２３２９以降の処理を実行する（ステップ２３４０）。
【０１０８】
次に、ＣＰＵ１４０６は、c2が０でない場合には（ステップ２３４４のＮＯ）、seq1のreverse complement配列のKtupleArrayR[i]に割り当てられたtupleがseq1のreverse
complement配列中およびseq2のreverse complement配列中に存在することとなっており、これら２つのゲノム配列seq1のreverse complement配列中のc1番目とseq2のreverse
complement配列中のc2番目の位置に存在するこの同一のtupleから開始して保存領域を検出していく処理を行う（ステップ２３４５）。これは上述のステップ２３０７の処理と同様であり説明を省略する。
【０１０９】
次に、ＣＰＵ１４０６は、ステップ２３４５において保存領域が存在したか否かを判定する処理を行う（ステップ２３４６）。保存領域が存在しなかった場合には（ステップ２３４６のＮＯ）、ステップ２３５３の処理を実行し、ＣＰＵ１４０６は、c2にseq2のIdxArrayR[c2]を代入する処理を行い、ステップ２３４４以降の処理を実行する（ステップ２３５３）。
【０１１０】
次に、ＣＰＵ１４０６は、保存領域が存在した場合には（ステップ２３４６のＹＥＳ）、残りの検出対象となる対象配列１４０１、即ちseq3,…,seqMのゲノム配列中で同一の保存領域Cを検出する処理を行う（ステップ２３４７）。変数jに対してｊ＝３と設定する処理を行う。
【０１１１】
次に、ＣＰＵ１４０６は、変数ｊが対象配列１４０１の最後のゲノム配列を示す数値、すなわちｊ＞Ｍとなっているか否かを判定する（ステップ２３４８）。
【０１１２】
次に、ＣＰＵ１４０６は、ｊ＞Ｍとなっていない場合には（ステップ２３４８のＮＯ）、ゲノム配列seq jの配列中に存在する保存領域Cを検出する処理を行う（ステップ２３４９）。このseq jの配列中で保存領域Cを検出する処理については、後で詳しく説明する。
【０１１３】
次に、ＣＰＵ１４０６は、ステップ２３４９において保存領域Ｃが存在したか否かを判定する処理を行う（ステップ２３５０）。保存領域Ｃが存在しなかった場合には（ステップ２３５０のＮＯ）、ステップ２３５３以降の処理を実行する。
【０１１４】
次に、ＣＰＵ１４０６は、保存領域Ｃが存在した場合には（ステップ２３５０のＹＥＳ）、変数jをひとつインクリメントし、ステップ２３４８以降の処理を再度実行する（ステップ２３５１）。そして、ステップ２３４８において、ｊ＞Ｍとなっている場合には（ステップ２３４８のＹＥＳ）、ステップ２３５２の処理を実行し、ＣＰＵ１４０６は、以上の処理で検出した各対象配列１４０１における保存領域ＣおよびＣが配列seq1,…,seqMで現れた位置等の情報をConservedReg[
], ListOfConservedReg[ ], AllOfConservedReg[ ]に登録し、ステップ２３５３の処理を実行する。以上のようにして、選択した各ゲノム配列の間で保存されている保存領域を検出する処理を行う。
【０１１５】
続いて、上述のステップ２３１１、２３２３、２３３６、２３４９における、ゲノム配列seq jの配列中に存在する保存領域Cを検出するについて図２７で示すフローチャートを用いて詳細に説明する。まず、ＣＰＵ１４０６は、保存領域C内の最も前側に位置する先頭tupleに該当するindexに変数iを設定する処理を行う（ステップ２４００）。
【０１１６】
次に、ＣＰＵ１４０６は、ゲノム配列seq j のKtupleArrayD[i]の値をc1と設定する処理を行う（ステップ２４０１）。
【０１１７】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２４０２）。c1が０である場合には（ステップ２４０２のＹＥＳ）、ステップ２４０６の処理を実行し、ＣＰＵ１４０６は、c1にseqｊのKtupleArrayＲ[i]を代入する処理を行い、ステップ２４０７以降の処理を実行する（ステップ２４０６）。
【０１１８】
次に、ＣＰＵ１４０６は、c1が０でない場合には（ステップ２４０２のＮＯ）、保存領域Cの先頭tupleがseqｊの配列中に存在することとなっており、ゲノム配列seqｊのc1番目から開始して、ステップ２３０７、２３１９、２３３２、２３４５で検出した保存領域Ｃのデータに基づいて保存領域を検出していく処理を行う（ステップ２４０３、２４０４）。これらゲノム配列seqｊ内の検出していく処理の開始位置および保存領域Ｃ内の先頭位置から文字列を比較していき、アライメントの連続するw個の文字列（塩基または残基）毎に保存領域を検出していき、seqｊのc1番目からアライメントを伸張させ保存領域Ｃと一致している文字列の個数を伸張させていく。そして、ゲノム配列seqｊおよび保存領域Ｃ間で相互に異なる文字であるミスマッチの個数がm個以下となっている文字列となっている領域の範囲内で保存領域を拡大させ、ミスマッチの個数がm個より多い文字列が存在した時点でその位置をゲノム配列seqｊ内での保存領域の境界位置とする。このようにして保存領域を検出していき保存領域が存在する場合にはこれを一時的にデータメモリ１４１１に格納する処理を行う。この検出した保存領域が保存領域Ｃよりも短い場合であっても、この検出した保存領域を改めてゲノム配列seqｊにおける保存領域Ｃとして設定しデータメモリ１４１１に格納する処理を行う。
【０１１９】
次に、ＣＰＵ１４０６は、c1にseqｊのIdxArrayD[c1]を代入する処理を行い、ステップ２４０２以降の処理を実行する（ステップ２４０５）。
【０１２０】
次に、ＣＰＵ１４０６は、ステップ２４０２においてc1が０である場合には（ステップ２４０２のＹＥＳ）、ステップ２４０６の処理を実行し、ＣＰＵ１４０６は、c1にseqｊのKtupleArrayＲ[i]を代入する処理を行う（ステップ２４０６）。
【０１２１】
次に、ＣＰＵ１４０６は、c1が０であるか否かを判定する処理を行う（ステップ２４０７）。c1が０である場合には（ステップ２４０７のＹＥＳ）、処理を終了する。
【０１２２】
次に、ＣＰＵ１４０６は、c1が０でない場合には（ステップ２４０７のＮＯ）、保存領域Cの先頭tupleがseqｊのreverse
complement配列中に存在することとなっており、ゲノム配列seqｊのreverse complement配列中のc1番目から開始して、ステップ２３０７、２３１９、２３３２、２３４５で検出した保存領域Ｃのデータに基づいて保存領域を検出していく処理を行う（ステップ２４０８、２４０９）。これは上述のステップ２４０３、２４０４の処理と同様であり説明を省略する。
【０１２３】
次に、ＣＰＵ１４０６は、c1にseqｊのIdxArrayＲ[c1]を代入する処理を行い、ステップ２４０７以降の処理を実行する（ステップ２４１０）。
【０１２４】
ＣＰＵ１４０６が以上説明した進化過程を考慮した保存領域検出システム１００の動作を行うことにより、構成情報１４１３により構成される系統樹に属する中間ノードに属する各リーフに対する対象配列１４０１内で保存されている保存領域を検出し構造体配列ConservedRegと、保存領域の関連を保持する配列ListOfConservedRegと、配列AllOfConservedRegが求められる。そして、ＣＰＵ１４０６は、以下に説明するような図９、図１０、図１１、図１２、図１３に示す画像のデータを作成し表示装置１４０２に表示させる処理を行う。
【０１２５】
図９は、構造体配列ConservedRegと、配列ListOfConservedRegと、配列AllOfConservedRegのデータを用いて作成した系統樹の様子を示す説明図である。この系統樹では、表示画面の左半分に対象配列１４０１の名称（例えば種１〜種６）を用いて構成された系統樹、右半分に各対象配列１４０１に対応するゲノム配列上の保存領域が表示されている。系統樹の各枝は、各対象配列１４０１毎に異なる色や実線、点線、一点鎖線等の異なる形態の線で表示されている。これにより配列ファミリーを識別するようになっており、例えば、線９０１は種１、種２、種３、種４のファミリーを表し、線９０２は種１、種２のファミリーを表している。図９では、各枝を識別するために色と線の形態を変えているが、実際にはこれ以外の表現方法でもよく、例えば、線の近くにタグや番号、名称等を表示する実現方法を用いても良い。
【０１２６】
また図９の系統樹の右側には、各対象配列１４０１に対して、保存領域の位置と、その保存領域が系統樹で保存されているレベルを模式的に表示している。系統樹のレベルは、左半分の系統樹の枝の色・線の形態に対応しており、例えば種１と種２でのみ保存されている領域は種１と種２が属している中間ノードを形成する線９０２と同一の色および形態の線を用いて示した９０５の部分となっている。同様に、種１、種２、種３、種４でのみ保存されている領域は線９０１と同一の色および形態の線を用いて示した９０３に示された部分で、全ての対象配列１４０１（種１〜種６）で保存されている領域は線９０１の上位側の線と同一の色および形態の線を用いて示した９０４に示された部分である。遠縁の種同士で保存されているものは、近縁の種同士でも保存されているはずであり、図９の表示結果では、系統樹において根に近いところの線で表された保存領域は、葉に近いところの全ての対象配列１４０１内に存在していることが表示されている。
【０１２７】
図１０は、図９で示した対象配列１４０１としての種１の保存領域を実際の塩基配列（またはアミノ酸配列）として表示した説明図である。図１０により研究者は、対象配列１４０１の保存領域のDNA（またはアミノ酸）配列を知ることが可能となっている。図１０の図中で矢印の領域は、種１の配列をインターネット等の公衆網やローカルネットワーク上に設置されたデータベースに対して、このDNA（またはアミノ酸）配列に基づいて検索し、その結果をマッピングすることによって表示したものである（矢印の向きは検索配列の方向）。研究者は、この結果を参照してこの保存領域のDNA（またはアミノ酸）配列と既知の情報の対応関係を知ることもできる。図中では、保存領域で既知の結果が見つかった状況を示しており、研究者はこれにより、保存領域の生物学的意味を知ることができるようになっている。
【０１２８】
図１１は、図９で示した各対象配列１４０１内の各保存領域の間の関係を示した説明図である。線の色・形状は図９の右半分において保存領域を表示した線に対応している。表示対象となる対象配列１４０１（図１１の場合、種１・種２・種３・種４）を選ぶためには、例えば図９の表示画面上において９０１等の保存領域が表示されている線をマウス１４０４により選択操作して、このような表示をするかどうかのメニューを出せばよい。あるいは任意の配列集合を、入力メニューから選択操作して表示させることとしても良い。図１１では、画面左寄りのの保存領域１１０１は種１、種２、種３では同じ向きだが、種４では向きが異なっている。これを参照することにより研究者は、進化のある時点で、種４でのみinversionが起こって向きが変わったか、あるいは種１・種２・種３の全てがinversionによって向きが変わった事実等を推測することが可能となり、これから進化の過程を知る手がかりとすることができる。
【０１２９】
図１２も、図１１と同様に図９で示した各対象配列１４０１内の各保存領域の間の関係を示した説明図である。図１２では、図９の系統樹内の種５と種６を対象として表示している。この図１２の画面を参照することにより研究者は、領域１２０１が、種５では２つ、種６ではひとつありこのことから種５が過去に領域１２０１を重複した事実等を推測できる。同様に領域１２０２は、過去に種６で同領域が重複した事実等を推測できる。
【０１３０】
図１３は、図９で示した系統樹内の種に対応する保存領域について他の種にも存在している状況を示した説明図である。図１３では、種５の１３０１領域について、これと同様の配列が他の種にあるかどうか検索し、種３と種６でそれが発見された状況を示している。見つかった配列については、種の名称を強調して明確に表示している。ここで図１３の画面を参照して研究者は、領域１３０１が種３でみつかったことの原因として、ひとつは進化系統樹そのものが間違っていたこと、そしてもうひとつは、SINE配列やLINE配列などレトロトランスポゾン配列が挿入されたことが考えられる等の推測を行うことができる。逆にこのことを用いて、系統樹が正しいかどうかを、見つかった保存領域に対して繰り返し検索を行うことで確認する利用形態も実現できる。
【０１３１】
以上説明したように、本実施の形態における進化過程を考慮した保存領域検出システム１００では、ＣＰＵ１４０６がゲノム解析の対象となる対象配列１４０１のデータに対してKtupleArrayD[ ], IdxArrayD[ ], KtupleArrayR[ ], IdxArrayR[ ]の索引情報を作成する処理を行い、構成情報１４１３により構成される系統樹に属する中間ノードに属する各リーフに対する対象配列１４０１内で保存されている保存領域を検出し構造体配列ConservedRegと、保存領域の関連を保持する配列ListOfConservedRegと、配列AllOfConservedRegを求める処理を行う。
【０１３２】
そして、ＣＰＵ１４０６は、構造体配列ConservedRegと、配列ListOfConservedRegと、配列AllOfConservedRegのデータを用いて系統樹や系統樹を構成する各対象配列１４０１の実際のゲノム配列、各対象配列１４０１内の各保存領域の間の関係を示した表示データを作成し、ゲノム配列同士の保存領域を進化過程と対応付けて系統樹の情報と併せて表示画面１４０２に表示するので、研究者は、これを参照して各対象配列１４０１の種の保存領域の進化の過程を推測し、進化の過程を手がかりとして利用することが可能である。そして、より本質的な生物学の理解を得られることが期待される。
【０１３３】
(他の実施の形態)
図２１および図２２で示すフローチャートを用いて行った処理では、対象配列１４０１や構成情報１４１３のデータをもちいて、保存領域の検出対象となるゲノム配列を選択しているが、これに限られず、対象配列１４０１以外の任意のゲノム配列の集合に対しても、この処理を実行することが可能である。その場合には、図２１のステップ２１０４の処理を実行せずスキップし、ステップ２１０５の処理で保存領域の検出対象となるゲノム配列として、対象配列１４０１以外の「任意の配列の集合」を選ぶようにすれば良い。
【０１３４】
また、図１３のような解析結果を得るには、これは図２４に示すフローチャートを用いた処理で説明した「配列seq j内に存在する保存領域Cを検出する処理」を全ての対象配列１４０１に対して実行すればよい。この処理によって保存領域Cが他の対象配列１４０１としてのゲノム配列でも検出されれば、そのゲノム配列中の保存領域Cの位置を記録することによって、図１３で示す表示結果を得ることができる。
【産業上の利用可能性】
【０１３５】
複数のＤＮＡ（またはアミノ酸）配列から、ゲノム配列を比較してゲノム配列中における意味を調べるゲノム解析に関し、特に、進化の過程で保存されている保存領域を見つけ、表示する進化過程を考慮した保存領域検出システムにおいて利用することが可能である。
【図面の簡単な説明】
【０１３６】
【図１】進化におけるゲノム配列の変化のうちsubstitutionについて説明する説明図である。
【図２】進化におけるゲノム配列の変化のうちinsertionについて説明する説明図である。
【図３】進化におけるゲノム配列の変化のうちdeletionについて説明する説明図である。
【図４】進化におけるゲノム配列の変化のうちinversionについて説明する説明図である。
【図５】祖先配列のタイプであるオーソログとパラログについて説明する説明図である。
【図６】ドットマトリックス解析の例を示す説明図である。
【図７】マルチプルアライメント解析の例を示す説明図である。
【図８】系統樹解析の例を示す説明図である。
【図９】系統樹と保存領域の関係を組み合わせて表示した画面を示す説明図である。
【図１０】保存領域と既知の情報を組み合わせて表示した画面を示す説明図である。
【図１１】複数の配列で保存領域を対応付けて表示した画面を示す説明図である。
【図１２】複数の配列で保存領域を対応付けて表示した画面を示す説明図である。
【図１３】ある配列で見つかった保存領域を、他の配列に対して検索し、その検索結果を表示する、本発明の表示例のひとつである。
【図１４】本実施の形態における進化過程を考慮した保存領域検出システム１００のシステム構成を概略的に示す機能ブロック図である。
【図１５】本実施の形態における進化過程を考慮した保存領域検出システム１００の対象配列１４０１のデータ構成を示す説明図である。
【図１６】本実施の形態における進化過程を考慮した保存領域検出システム１００の構成情報１４１３のデータ構成を示す説明図である。
【図１７】本実施の形態における進化過程を考慮した保存領域検出システム１００において、対象配列１４０１の索引情報を表示するためのデータ構造を示す説明図である。
【図１８】本実施の形態における進化過程を考慮した保存領域検出システム１００において、対象配列１４０１の保存領域を記録するためのデータ構造を示す説明図である。
【図１９】本実施の形態における進化過程を考慮した保存領域検出システム１００において、対象配列１４０１間の保存領域同士の対応関係を記録するためのデータ構造体を示す説明図である。
【図２０】本実施の形態における進化過程を考慮した保存領域検出システム１００において、異なる種類の保存領域を記録するためのデータ構造を示す説明図である。
【図２１】本実施の形態における進化過程を考慮した保存領域検出システム１００において、全体の処理の流れを概略的に示すフローチャートである。
【図２２】本実施の形態における進化過程を考慮した保存領域検出システム１００において、各対象配列１４０１に対して索引情報を作成する処理を詳細に示すフローチャートである。
【図２３】本実施の形態における進化過程を考慮した保存領域検出システム１００において、保存領域を検出する処理を詳細に示すフローチャートである。
【図２４】本実施の形態における進化過程を考慮した保存領域検出システム１００において、保存領域を検出する処理を詳細に示すフローチャートである。
【図２５】本発明の進化過程を考慮した保存領域検出システムにおいて、保存領域を算出する処理を詳細に示すフローチャートである。
【図２６】本実施の形態における進化過程を考慮した保存領域検出システム１００において、保存領域を検出する処理を詳細に示すフローチャートである。
【図２７】本実施の形態における進化過程を考慮した保存領域検出システム１００において、ゲノム配列の中の保存領域を検出する処理の流れを詳細に示すフローチャートである。
【図２８】本実施の形態における進化過程を考慮した保存領域検出システム１００において、配列データKtupleArrayDとIdxArrayDの一例を示した説明図である。
【図２９】本実施の形態における進化過程を考慮した保存領域検出システム１００において、二つの配列間の保存領域を検出した状態を示した説明図である。
【符号の説明】
【０１３７】
１００ 保存領域検出システム
１４０１ 対象配列
１４０２ 表示装置
１４０３ キーボード
１４０４ マウス
１４０５ 配列DB
１４０６ 中央処理装置
１４０７ プログラムメモリ
１４０８ 保存領域計算処理部
１４０９ 系統樹計算処理部
１４１０ 分析結果表示処理部
１４１１ データメモリ
１４１２ 入力データ
１４１３ 系統樹
２６０１ 保存領域
【特許請求の範囲】
【請求項１】
複数のＤＮＡ配列のうちゲノム解析の対象となるゲノム配列の中に配列の変化を受けておらず進化的に保存されている保存領域を見つける進化過程を考慮した保存領域検出システムにおいて、
ゲノム配列に基づいて得られる系統樹を参照して、この系統樹を構成している中間ノードに属するゲノム配列を認識する配列認識手段と、
中間ノードに属するゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していく保存検出手段とを備えたことを特徴とする進化過程を考慮した保存領域検出システム。
【請求項２】
請求項１に記載の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する２つのゲノム配列において存在している同一の文字列の位置から開始して一定の文字列毎にゲノム配列内の保存領域を検出していき、ミスマッチの文字の個数が所定の個数以下の文字列が存在している領域を保存領域として検出することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項３】
請求項１に記載の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する複数のゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内で検出した保存領域に基づいて、中間ノードを変えながら繰り返しこの検出した同一の保存領域を検出していき、全ての中間ノードに属するゲノム配列内の保存領域を検出することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項４】
請求項３に記載の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段が検出したゲノム配列内の各保存領域をそれぞれ毎に異なる形態の線により構成し、前記系統樹上の中間ノードを形成する枝を、中間ノードに属するゲノム配列内の各保存領域に対応させた形態の線により構成し、前記各保存領域と系統樹を同時に表示する解析結果表示手段を備えたことを特徴とする進化過程を考慮した保存領域検出システム。
【請求項５】
請求項４に記載の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、既知のゲノム配列に関する情報と組み合わせて同時に表示することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項６】
請求項５に記載の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、各保存領域が含まれるゲノム配列と組み合わせ、各ゲノム配列間に含まれる同一の保存領域を関連付けて表示することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項７】
請求項６に記載の進化過程を考慮した保存領域検出システムにおいて、
任意の配列に基づいて、前記系統樹を構成している中間ノードに属するゲノム配列を検索する配列検索手段と、
前記配列検索手段が検索した結果得られたゲノム配列の情報を参照して、前記系統樹を構成している中間ノードに属するゲノム配列に関する情報を特定の表示方法で表示する特定表示手段を備えたことを特徴とする進化過程を考慮した保存領域検出システム。
【請求項８】
請求項７に記載の進化過程を考慮した保存領域検出システムにおいて、
特定表示手段は、
前記配列検索手段が検索した結果得られたゲノム配列を、当該任意の配列部分を関連付けて表示することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項１】
複数のＤＮＡ配列のうちゲノム解析の対象となるゲノム配列の中に配列の変化を受けておらず進化的に保存されている保存領域を見つける進化過程を考慮した保存領域検出システムにおいて、
ゲノム配列に基づいて得られる系統樹を参照して、この系統樹を構成している中間ノードに属するゲノム配列を認識する配列認識手段と、
中間ノードに属するゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内の保存領域を検出していく保存検出手段とを備えたことを特徴とする進化過程を考慮した保存領域検出システム。
【請求項２】
請求項１に記載の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する２つのゲノム配列において存在している同一の文字列の位置から開始して一定の文字列毎にゲノム配列内の保存領域を検出していき、ミスマッチの文字の個数が所定の個数以下の文字列が存在している領域を保存領域として検出することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項３】
請求項１に記載の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段は、
中間ノードに属する複数のゲノム配列において存在している同一の文字列の位置から開始してゲノム配列内で検出した保存領域に基づいて、中間ノードを変えながら繰り返しこの検出した同一の保存領域を検出していき、全ての中間ノードに属するゲノム配列内の保存領域を検出することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項４】
請求項３に記載の進化過程を考慮した保存領域検出システムにおいて、
前記保存検出手段が検出したゲノム配列内の各保存領域をそれぞれ毎に異なる形態の線により構成し、前記系統樹上の中間ノードを形成する枝を、中間ノードに属するゲノム配列内の各保存領域に対応させた形態の線により構成し、前記各保存領域と系統樹を同時に表示する解析結果表示手段を備えたことを特徴とする進化過程を考慮した保存領域検出システム。
【請求項５】
請求項４に記載の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、既知のゲノム配列に関する情報と組み合わせて同時に表示することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項６】
請求項５に記載の進化過程を考慮した保存領域検出システムにおいて、
前記解析結果表示手段は、
前記各保存領域を、各保存領域が含まれるゲノム配列と組み合わせ、各ゲノム配列間に含まれる同一の保存領域を関連付けて表示することを特徴とする進化過程を考慮した保存領域検出システム。
【請求項７】
請求項６に記載の進化過程を考慮した保存領域検出システムにおいて、
任意の配列に基づいて、前記系統樹を構成している中間ノードに属するゲノム配列を検索する配列検索手段と、
前記配列検索手段が検索した結果得られたゲノム配列の情報を参照して、前記系統樹を構成している中間ノードに属するゲノム配列に関する情報を特定の表示方法で表示する特定表示手段を備えたことを特徴とする進化過程を考慮した保存領域検出システム。
【請求項８】
請求項７に記載の進化過程を考慮した保存領域検出システムにおいて、
特定表示手段は、
前記配列検索手段が検索した結果得られたゲノム配列を、当該任意の配列部分を関連付けて表示することを特徴とする進化過程を考慮した保存領域検出システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２００７−２０９３０５（Ｐ２００７−２０９３０５Ａ）
【公開日】平成１９年８月２３日（２００７．８．２３）
【国際特許分類】
【出願番号】特願２００６−３５４８６（Ｐ２００６−３５４８６）
【出願日】平成１８年２月１３日（２００６．２．１３）
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
【公開日】平成１９年８月２３日（２００７．８．２３）
【国際特許分類】
【出願日】平成１８年２月１３日（２００６．２．１３）
【出願人】（０００２３３０５５）日立ソフトウエアエンジニアリング株式会社 (1,610)
【Ｆターム（参考）】
[ Back to top ]