(57)【要約】本発明は、ユニークなプライマーの設計を支援する。ゲノム配列中の配列の出現頻度を示す指標を算出するために、所定長の部分列の各々に関して、前記ゲノム配列中の出現頻度を算出し、所定長の部分列に関する出現頻度を、頻度／孤立度テーブル１６に記憶する。また、所定長の部分列の各々に関して、ｊ個の塩基を変換したｊミューテーション（ｊ≦ｉ−１）が、ゲノム配列中には表れないが、ｉ個の塩基を変換したｉミューテーションが、ゲノム配列中に現れるような孤立度ｉを算出し、所定長の部分列に関して、孤立度を、頻度／孤立度テーブル１６に記憶する。可視化処理部１８は、塩基の出現頻度および／または孤立度に基づき、塩基の各々に所定の色彩を付与してゲノム配列を表したような画像を生成する。
2003056460.tif 000002
【特許請求の範囲】
【請求項１】
ゲノム配列中の配列の出現頻度を示す指標を算出する方法であって、
所定長の部分列の各々に関して、前記ゲノム配列中の出現頻度を算出するステップと、
前記所定長の部分列に関する出現頻度を、頻度テーブルに記憶するステップとを備えたことを特徴とする方法。
【請求項２】
前記頻度テーブルに記憶するステップが、
出現頻度が０（ゼロ）である部分列に関して、頻度テーブルへの記憶を省略するステップと、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を、第２のテーブルに記憶するステップとを有することを特徴とする請求項１に記載の方法。
【請求項３】
ゲノム配列中の配列の孤立度を示す指標を算出する方法であって、
所定長の部分列の各々に関して、ｊ個の塩基を変換したｊミューテーション（ｊ＝１，２，・・・，ｉ−１）が、前記ゲノム配列中には表れないが、ｉ個の塩基を変換したｉミューテーションが、前記ゲノム配列中に現れるような孤立度ｉを算出するステップと、
前記所定長の部分列に関して、前記孤立度を、孤立度テーブルに記憶するステップとを備えたことを特徴とする方法。
【請求項４】
前記孤立度を算出するステップが、
前記所定長の部分列に関して、当該部分列のｋ個の塩基を変換したｋミューテーションについて、所定長の部分列の各々に関してゲノム配列中の出現頻度を記憶した頻度テーブルを参照して、当該ｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋを孤立度とするステップと、
前記ｋミューテーションが存在しない場合に、ｋをインクリメントして、前記ｋミューテーションの存在の有無を判断するステップを繰り返し実行するステップとを有することを特徴とする請求項３に記載の方法。
【請求項５】
前記孤立度を算出するステップが、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を記憶した第２のテーブルを参照して、前記所定長の部分列のうち先頭から第２の所定長にあるｋ個の塩基を変換したような、前記所定長のｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋミューテーションと、前記所定長の配列との間のハミング距離を見出すステップと、
前記ハミング距離の最小値がｋである場合に、当該ｋを孤立度とするステップと、
最小値がｋより大きい場合には、ｋをインクリメントして、前記所定長のｋミューテーションの存在の有無、および、ハミング距離の最小値を用いた判断をなすステップを繰り返し実行するステップを有することを特徴とする請求項３または４に記載の方法。
【請求項６】
前記ゲノム配列中に現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを備えたことを特徴とする請求項３または４に記載の方法。
【請求項７】
ゲノム配列の孤立度を示す指標を算出する方法であって、
所定長の部分列に関して、当該部分列のｋ番目の文字から始まる部分配列が、ゲノム配列中に出現しなくなる最短の部分列を求めるステップと、
当該部分列中に重複せずに含まれる部分列の最大の個数ｍを算出し、当該ｍを孤立度の下界として、孤立度を示す指標とするステップとを備えたことを特徴とする方法。
【請求項８】
前記部分配列が現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを備えたことを特徴とする請求項７に記載の方法。
【請求項９】
請求項１または２に記載の方法を用いて生成された頻度テーブルを利用して、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第１の指標を算出する方法であって、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップとを備えたことを特徴とする方法。
【請求項１０】
請求項３ないし８の何れか一項に記載の方法を用いて生成された孤立度テーブルを利用して、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第２の指標を算出する方法であって、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを備えたことを特徴とする方法。
【請求項１１】
請求項１または２に記載の方法を用いて生成された頻度テーブル、および、請求項３ないし８の何れか一項に記載の方法を用いて生成された孤立度テーブルを用いて、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第３の指標を算出する方法であって、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップと、前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを備えたことを特徴とする方法。
【請求項１２】
請求項９ないし１１の何れか一項に記載の方法を用いて得られた指標に基づき、当該指標の値或いは範囲にしたがって異なる表示態様を割り当てるステップと、
前記割り当てられた表示態様にしたがって、ゲノム配列中の各塩基を表したような画像を生成するステップとを備えたことを特徴とする方法。
【請求項１３】
前記表示態様が、色彩であることを特徴とする請求項１２に記載の方法。
【請求項１４】
ゲノム配列中の配列の出現頻度を示す指標を算出するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
所定長の部分列の各々に関して、前記ゲノム配列中の出現頻度を算出するステップと、
前記所定長の部分列に関する出現頻度を、頻度テーブルに記憶するステップとを前記コンピュータに実行させることを特徴とするプログラム。
【請求項１５】
前記頻度テーブルに記憶するステップにおいて、
出現頻度が０（ゼロ）である部分列に関して、頻度テーブルへの記憶を省略するステップと、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を、第２のテーブルに記憶するステップとを、前記コンピュータに実行させることを特徴とする請求項１４に記載のプログラム。
【請求項１６】
ゲノム配列中の配列の孤立度を示す指標を算出するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
所定長の部分列の各々に関して、ｊ個の塩基を変換したｊミューテーション（ｊ＝１，２，・・・，ｉ−１）が、前記ゲノム配列中には表れないが、ｉ個の塩基を変換したｉミューテーションが、前記ゲノム配列中に現れるような孤立度ｉを算出するステップと、
前記所定長の部分列に関して、前記孤立度を、孤立度テーブルに記憶するステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項１７】
前記孤立度を算出するステップにおいて、
前記所定長の部分列に関して、当該部分列のｋ個の塩基を変換したｋミューテーションについて、所定長の部分列の各々に関してゲノム配列中の出現頻度を記憶した頻度テーブルを参照して、当該ｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋを孤立度とするステップと、
前記ｋミューテーションが存在しない場合に、ｋをインクリメントして、前記ｋミューテーションの存在の有無を判断するステップを繰り返し実行するステップとを、前記コンピュータに実行させることを特徴とする請求項１６に記載のプログラム。
【請求項１８】
前記孤立度を算出するステップにおいて、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を記憶した第２のテーブルを参照して、前記所定長の部分列のうち先頭から第２の所定長にあるｋ個の塩基を変換したような、前記所定長のｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋミューテーションと、前記所定長の配列との間のハミング距離を見出すステップと、
前記ハミング距離の最小値がｋである場合に、当該ｋを孤立度とするステップと、
最小値がｋより大きい場合には、ｋをインクリメントして、前記所定長のｋミューテーションの存在の有無、および、ハミング距離の最小値を用いた判断をなすステップを繰り返し実行するステップを、前記コンピュータに実行させることを特徴とする請求項１６または１７に記載のプログラム。
【請求項１９】
前記ゲノム配列中に現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを、前記コンピュータに実行させることを特徴とする請求項１６または１７に記載のプログラム。
【請求項２０】
ゲノム配列の孤立度を示す指標を算出するために、コンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
所定長の部分列に関して、当該部分列のｋ番目の文字から始まる部分配列が、ゲノム配列中に出現しなくなる最短の部分列を求めるステップと、
当該部分列中に重複せずに含まれる部分列の最大の個数ｍを算出し、当該ｍを孤立度の下界として、孤立度を示す指標とするステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項２１】
前記部分配列が現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを、前記コンピュータに実行させることを特徴とする請求項２０に記載のプログラム。
【請求項２２】
請求項１４または１５に記載のプログラムを、コンピュータに実行させることにより生成された頻度テーブルを利用して、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第１の指標を算出するために、コンピュータを動作させる、コンピュータにより読み取り可能なプログラムであって、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項２３】
請求項１６ないし２１の何れか一項に記載のプログラムを、コンピュータに実行させることにより生成された孤立度テーブルを利用して、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第２の指標を算出するために、コンピュータを動作させる、コンピュータにより読み取り可能なプログラムであって、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項２４】
請求項１４または１５に記載のプログラムを、コンピュータに実行させることにより生成された頻度テーブル、および、請求項１６ないし２１の何れか一項に記載のプログラムを、コンピュータに実行させることにより生成された孤立度テーブルを用いて、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第３の指標を算出するために、コンピュータを動作させる、コンピュータにより読み取り可能なプログラムであって、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップと、前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを、前記コンピュータにより実行させることを特徴とするプログラム。
【請求項２５】
請求項２２ないし２４の何れか一項に記載のプログラムを、コンピュータに実行させることにより、得られた指標に基づき、当該指標の値或いは範囲にしたがって異なる表示態様を割り当てるステップと、
前記割り当てられた表示態様にしたがって、ゲノム配列中の各塩基を表したような画像を生成するステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
発明の属する技術分野
本発明は、プライマーの選択を支援する手法に関する。
背景技術
これまでに多くのプライマーデザインの方法が提案されたが、一つの場所にしかアニールしないようなプライマーを設計するのは困難なのが現状である。データベースに登録されたＥＳＴ配列に対して、比較的短い配列（Ｋ−タプル：Ｋ−ｔｕｐｐｌｅ）のあらゆる可能な塩基配列の組み合わせの出現回数を計算すること、たとえば、４８（６５５３６）種類ある８−ｍｅｒの塩基配列の出現回数を計算することで、高頻度に出てくる配列と、低頻度で出てくる配列を見つけることができる。このような手法は、たとえば、「Ｎｕｃｌｅｉｃ  Ａｃｉｄｓ  Ｒｅｓ．１９  ３８８７−３８９１（Ｒ．Ｇｒｉｆｆａｉｓ，Ｐ．Ｍ．ＡｎｄｒｅおよびＭ．Ｔｈｉｂｏｎ：１９９１年）」に開示されている。
しかしながら、いくつかの著名なＥＳＴデータベースには、多くの研究者から投稿された類似配列が多数存在するため、このままでは配列の出現頻度を議論することができない。
また、遺伝子をはさむようなプライマーを設計する場合には、プロモーター領域の配列が必要となるため、ＥＳＴデータベースだけではプライマーを設計することができないという問題点があった。
ＤＮＡポリメラーゼは、いくつかのミスマッチが入ったようなオリゴヌクレオチドであっても、プライマーとして認識することが知られている（たとえば、「Ｍｏｌｅｃｕｌａｒ  Ｂｉｏｌｏｇｙ  Ｖｏｌ．２８  Ｎｏ．５，Ｐａｒｔ  Ｉ  ６６１−６６３（Ｌ．Ｂ．Ｄ’ｙａｃｈｅｎｋｏ，Ａ．Ａ．Ｃｈｅｎｃｈｉｃｋ，Ｇ．Ｌ．Ｋｈａｓｐｅｋｏｖ，Ａ．Ｏ．ＴａｔａｒｅｎｋｏおよびＲ．Ｓｈ．Ｂｉｂｉｌａｓｈｖｉｌｉ：１９９４年）」参照）。しかしながら、これまでのプライマーデザインの方法においては、ゲノムワイドなミスマッチ耐性について考慮されていなかった。また、これまでのプライマーデザインの方法においては、プライマーの塩基配列を決定した後に、ミスマッチ耐性をデータベースに対して検索していたため、検索に時間がかかるという問題点もあった。
本発明は、ユニークなプライマーの設計を支援することを目的とする。
発明の開示
本発明においては、ゲノム配列中の所定長（Ｎ−ｍｅｒ）の配列の出現回数を計数するとともに、ミスマッチ耐性を評価する値として、配列特異性のもう一つの側面としての孤立度を導入し、評価した。孤立度は、たとえば、配列同士の最小ハミング距離として定義した。孤立度を導入することにより、塩基配列の特異性をさらに精密に分類できるようになった。
より詳細には、本発明の目的は、ゲノム配列中の配列の出現頻度を示す指標を算出する方法であって、所定長の部分列の各々に関して、前記ゲノム配列中の出現頻度を算出するステップと、前記所定長の部分列に関する出現頻度を、頻度テーブルに記憶するステップとを備えたことを特徴とする方法により達成される。上記頻度テーブルに記憶するステップは、出現頻度が０（ゼロ）である部分列に関して、頻度テーブルへの記憶を省略するステップと、前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を、第２のテーブルに記憶するステップとを有するのが、メモリ容量の削減および処理時間の短縮のために望ましい。
また、本発明の目的は、ゲノム配列中の配列の孤立度を示す指標を算出する方法であって、所定長の部分列の各々に関して、ｊ個の塩基を変換したｊミューテーション（ｊ＝１，２，・・・，ｉ−１）が、前記ゲノム配列中には表れないが、ｉ個の塩基を変換したｉミューテーションが、前記ゲノム配列中に現れるような孤立度ｉを算出するステップと、前記所定長の部分列に関して、前記孤立度を、孤立度テーブルに記憶するステップとを備えたことを特徴とする方法によっても達成される。
上記出現頻度および／または孤立度を用いて、ゲノム配列において特異性のある部分を特定することが容易になり、よりユニークなプライマーを設計することが可能となる。
好ましい実施態様においては、前記孤立度を算出するステップが、前記所定長の部分列に関して、当該部分列のｋ個の塩基を変換したｋミューテーションについて、所定長の部分列の各々に関してゲノム配列中の出現頻度を記憶した頻度テーブルを参照して、当該ｋミューテーションが存在するか否かを判断するステップと、前記ｋミューテーションが存在する場合に、当該ｋを孤立度とするステップと、前記ｋミューテーションが存在しない場合に、ｋをインクリメントして、前記ｋミューテーションの存在の有無を判断するステップを繰り返し実行するステップとを有する。
より好ましい実施態様においては、前記孤立度を算出するステップが、前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を記憶した第２のテーブルを参照して、前記所定長の部分列のうち先頭から第２の所定長にあるｋ個の塩基を変換したような、前記所定長のｋミューテーションが存在するか否かを判断するステップと、前記ｋミューテーションが存在する場合に、当該ｋミューテーションと、前記所定長の配列との間のハミング距離を見出すステップと、前記ハミング距離の最小値がｋである場合に、当該ｋを孤立度とするステップと、最小値がｋより大きい場合には、ｋをインクリメントして、前記所定長のｋミューテーションの存在の有無、および、ハミング距離の最小値を用いた判断をなすステップを繰り返し実行するステップを有する。
また、別の好ましい実施態様においては、前記ゲノム配列中に現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを備えている。ゲノム配列が整備されていないなどの理由がある場合、或いは、実際に同様の遺伝子の配列がゲノム配列中に２回だけ出現する場合に、たとえば、出現回数が３回以下か否かに基づいて拡大された孤立度（第２の孤立度）を求めている。これにより、３回以下の回数だけ、ゲノム配列中に出現するが、類似する配列は他には存在しないような部分配列についても、プライマー設計をできるようにするためである。
別の好ましい実施態様において、ゲノム配列の孤立度を示す指標を算出する方法は、所定長の部分列に関して、当該部分列のｋ番目の文字から始まる部分配列が、ゲノム配列中に出現しなくなる最短の部分列を求めるステップと、当該部分列中に重複せずに含まれる部分列の最大の個数ｍを算出し、当該ｍを孤立度の下界として、孤立度を示す指標とするステップとを備えている。
比較的長い配列（たとえば、ヒトゲノム配列中の５０ｍｅｒの配列）の正確な孤立度を、プライマー選択の孤立度の下界さえわかれば、類似の配列が存在しないことが保証される。たとえば、５０ｍｅｒの配列中で、孤立度の下界が「７」であれば、９０パーセント以上のシミラリティを持つ配列は存在しないこととなる。このため、６０パーセント以上のシミラリティを持つ配列が存在しないことを正確に示すまでもなく、９０パーセント以上のシミラリティを持つ配列が存在しないことさえわかれば、プライマー選択の指標として十分である。
上記実施態様においても、部分配列が現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行して良い。
また、本発明の目的は、上記方法を用いて生成された頻度テーブルを利用して、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第１の指標を算出する方法であって、ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、前記特定された出現頻度の総和に基づき、第１の指標を算出するステップとを備えたことを特徴とする方法によっても達成される。
また、本発明の目的は、上記方法を用いて生成された孤立度テーブルを利用して、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第２の指標を算出する方法であって、ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを備えたことを特徴とする方法によっても達成される。
さらに、本発明の目的は、上記方法を用いて生成された頻度テーブル、および、孤立度テーブルを用いて、ゲノム配列中の塩基に関して、当該塩基を含む配列のプライマーへの適性を示す第３の指標を算出する方法であって、ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、前記特定された出現頻度の総和に基づき、第１の指標を算出するステップと、前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを備えたことを特徴とする方法によっても達成される。これらの方法により、ゲノム配列中の塩基レベルでの指標を得ることが可能となり、よりユニークなプライマーの設計を支援することが可能となる。
さらに、本発明の目的は、上記方法を用いて得られた指標に基づき、当該指標の値或いは範囲にしたがって異なる表示態様を割り当てるステップと、前記割り当てられた表示態様にしたがって、ゲノム配列中の各塩基を表したような画像を生成するステップとを備えたことを特徴とする方法によっても達成される。たとえば、上記表示態様は、色彩であっても良い。
また、本発明の目的は、ゲノム配列中の配列の出現頻度を示す指標を算出するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、所定長の部分列の各々に関して、前記ゲノム配列中の出現頻度を算出するステップと、前記所定長の部分列に関する出現頻度を、頻度テーブルに記憶するステップとを前記コンピュータに実行させることを特徴とするプログラムによっても達成される。
さらに、本発明の目的は、ゲノム配列中の配列の孤立度を示す指標を算出するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、所定長の部分列の各々に関して、ｊ個の塩基を変換したｊミューテーション（ｊ＝１，２，・・・，ｉ−１）が、前記ゲノム配列中には表れないが、ｉ個の塩基を変換したｉミューテーションが、前記ゲノム配列中に現れるような孤立度ｉを算出するステップと、前記所定長の部分列に関して、前記孤立度を、孤立度テーブルに記憶するステップとを、前記コンピュータに実行させることを特徴とするプログラムによっても達成される。
発明を実施するための望ましい形態
以下、添付図面を参照して、本発明の実施の形態につき説明を加える。図１は、本発明の実施の形態にかかるプライマー設計支援システムの概略を示すブロックダイヤグラムである。図１に示すように、このプライマー設計支援システム１０は、プライマー設計のために利用するゲノム配列を参照して、当該ゲノム配列中の、所定長の部分列（Ｎ−ｍｅｒ配列）の出現頻度を算出する出現頻度算出部１２と、後述するような、ゲノム配列に対する、各部分列の孤立度を算出する孤立度算出部１４と、各部分列に関する出現頻度および孤立度を記憶する頻度／孤立度テーブル１６と、頻度／孤立度テーブル１６を参照して、ゲノム配列を可視化して表示するために必要な処理を実行する可視化処理部１８と、可視化処理部１８による処理により表示装置２４の画面上に表示された画像を参照して、ユーザが入力装置（図示せず）を操作することに応答して、プライマーとする領域を選択する処理を実行するプライマー作成支援部２０とを有している。
プライマー設計支援システム１０は、コンピュータに、設計支援プログラムをインストールすることにより実現できる。また、本実施の形態においては、ゲノム配列データベース（ＤＢ）２２からゲノム配列を読み出すようになっている。ゲノム配列ＤＢ２２は、上記パーソナルコンピュータのハードディスク上にあっても良いし、或いは、上記パーソナルコンピュータとは離間した配置されたサーバに搭載されていても良い。後者の場合には、パーソナルコンピュータが、ＬＡＮやインターネットなどのネットワークを介して、サーバにアクセスして、ゲノム配列ＤＢ中のデータを参照するように構成すればよい。
上記プライマー設計支援システム１０による処理を説明するのに先立って、本発明の原理について、以下に簡単に説明を加える。
図２Ａは、ゲノム配列の出現頻度を説明するための図である。ここでは、「ＡＴＡＴＧＧＧＡＴＣ」という極めて短いゲノム配列を考え、また、部分列として、２−ｍｅｒ配列を考えた。図２Ａに示すように、「ＡＴ」という２−ｍｅｒ配列は、上記ゲノム配列において３回出現し、また、「ＧＧ」という２−ｍｅｒ配列は２回出現していることがわかる。他の２−ｍｅｒ配列（「ＴＡ」、「ＴＧ」、「ＧＡ」、「ＴＣ」）は、それぞれ１回ずつ出現し、さらに他の配列（たとえば、「ＡＡ」、「ＡＣ」など）は一度も出現していないことがわかる。
出現頻度算出部１２は、このように、２−ｍｅｒ配列の各々が、ゲノム配列中に何回出現するか（出現頻度）を算出する。
次に、孤立度について、図２Ａの例と同じゲノム配列および２−ｍｅｒ配列を引用して説明を加える。図３は、上記ゲノム配列に対する各２−ｍｅｒ配列（部分列）の孤立度を説明するための図である。本明細書においては、孤立度を、配列同士の最小ハミング距離として定義した。すなわち、あるｉ箇所（ｉ＜ｎ）の塩基を別の塩基に入れ替えても、入れ替えられた部分列が、ゲノム配列中に現れないが、ｎ箇所の塩基を別の塩基に入れ替えた場合に、入れ替えられた部分列が、ゲノム配列中に出現する場合に、当該部分列の孤立度を「ｎ」とする。
図３に示す例において、部分列「ＡＴ」の１箇所の塩基を入れ替えたもの（１ミューテーション：符号３０２参照）、つまり、「ＡＡ」、「ＡＧ」、「ＡＣ」、「ＴＴ」、「ＧＴ」、「ＣＴ」は、ゲノム配列（符号３００参照）中に表れない。これに対して、２箇所の塩基を入れ替えたもの（２ミューテーション：符号３０３参照）、つまり、「ＴＡ」、「ＴＧ」、「ＴＣ」、「ＧＡ」、「ＧＧ」、「ＧＣ」、「ＣＡ」、「ＣＧ」、「ＣＣ」のうち、図３において下線を付したもの（「ＴＡ」、「ＴＣ」、「ＧＡ」、「ＧＧ」）は、ゲノム配列（符号３００参照）中に現れる。したがって、部分列「ＡＴ」の孤立度は「２」となる。
同様に、他の部分列「ＴＡ」、「ＴＧ」、「ＧＧ」、「ＧＡ」、「ＴＣ」については、その１ミューテーションが、ゲノム配列中に現れるため、それぞれ、孤立度が「１」となる。
本実施の形態においては、たとえば、１８−ｍｅｒの部分列を用いて、出現頻度および孤立度を算出している。図４は、本実施の形態にかかる出現頻度の算出に際して実行される処理の概略を示すフローチャートである。図４に示すように、出現頻度算出部１２は、Ｎ−ｍｅｒ配列（たとえば、１８−ｍｅｒ配列）を選択して（ステップ４０１）、ゲノム配列ＤＢ２２から取得したゲノム配列を走査する（ステップ４０２）。これにより、ゲノム配列中で、Ｎ−ｍｅｒ配列が出現する位置が特定され、また、これをカウントすることにより出現頻度を得ることができる（ステップ４０３）。
出現頻度算出部１２は、ステップ４０３にて得られた出現頻度等を、処理対象となったＮ−ｍｅｒ配列をキーとして、頻度／孤立度テーブル１６中に記憶する（ステップ４０４）。このような処理を、考えられ得る全てのＮ−ｍｅｒ配列に関して実行する（ステップ４０５参照）。このようにしてテーブルを生成することができる。
実際には、本実施の形態においては、出現頻度が０であるようなＮ−ｍｅｒ配列を表さないようにすることで、テーブルのサイズを小さくしている。たとえば、図２Ａに示す例において、出現頻度を含むテーブルは、そのままでは、図５Ａに示すようなものとなるが、本実施の形態においては、図５Ｂに示すようにサイズを圧縮している。上記テーブルを、場合によって「マップサイズテーブル」とも称する。
さらに、テーブルの参照箇所を限定する形態を採用することにより、処理の高速化を図っている。たとえば、図２Ａに示す例において、２−ｍｅｒ配列自体をキーとすれば、図５Ｂに示すようなテーブル５０１が得られるが、処理の高速化を図るため、図５Ｂに示すように、より小さな長さ（これを、場合によって「ハッシュサイズ」とも称する。）の塩基配列をキーとする補助テーブル５０２を設け、これにより、テーブル中の配列のおおよその位置を特定できるようにしている。このような補助テーブルを、場合によって、「ハッシュサイズテーブル」とも称する。Ｎ＝１８としたマップサイズテーブルを利用する場合には、たとえば、ハッシュサイズ≦１４とするのが望ましい。
次いで、孤立度算出部１４は、図４の処理により得られたＮ−ｍｅｒ配列と頻度とが対応したマップサイズテーブルおよび補助テーブル（ハッシュサイズテーブル）を参照することで、孤立度を算出している。図６は、孤立度の算出処理を示すフローチャートである。
孤立度算出部１４は、まず、Ｎ−ｍｅｒ配列を選択する（ステップ６０１）とともに、ミューテーションの個数を示すｉを１に初期化する（ステップ６０２）。次いで、Ｎ−ｍｅｒ配列のｉミューテーションとなる他のＮ−ｍｅｒ配列が選択される（ステップ６０３）。孤立度算出部１４は、上記ハッシュサイズテーブルを参照して（ステップ６０４）、他のＮ−ｍｅｒ配列が、先頭のハッシュサイズ長の塩基配列が、ゲノム配列中に出現しているか否かを判断する（ステップ６０５）。
ステップ６０５においてノー（Ｎｏ）と判断された場合に、ｉミューテーションとなる他のＮ−ｍｅｒ配列があるときには（ステップ６０６でノー（Ｎｏ））、当該他のＮ−ｍｅｒ配列に関してステップ６０３〜６０５の処理が実行される。或いは、ｉミューテーションとなる全ての他のＮ−ｍｅｒ配列について、ゲノム配列における出現の有無が判断された場合には、ｉをインクリメントして（ステップ６０７）、当該インクリメントされたｉに関するｉミューテーションについて、同様の処理（ステップ６０３〜６０６）を繰り返す。
ここに、ｉミューテーションとなるＮ−ｍｅｒ配列の特定およびテーブル参照（ステップ６０３、６０４）の手法につき説明を加える。本実施の形態においては、実際に、ステップ６０３においては、ステップ６０１で選択されたＮ−ｍｅｒ配列の先頭から所定数の塩基が同一であるようなハッシュサイズの配列（ハッシュ配列）を特定し、その塩基のうち、ｉ個の塩基を変換した配列を生成し、ハッシュサイズテーブル、次いで、マップサイズテーブルを参照して、当該ハッシュ配列を先頭に含むＮ−ｍｅｒ配列がどれだけ存在するかを求める。これにより、Ｎ−ｍｅｒ配列のリストが得られる。
次いで、孤立度算出部１４は、得られたＮ−ｍｅｒ配列の各々と、処理対象となったＮ−ｍｅｒ配列（ステップ６０１で選択されたもの）との間のハミング距離を算出し、ハミング距離の最小値＝ｉであるか否かを判断する（ステップ６０８）。これは、上記リストされたＮ−ｍｅｒ配列には、処理対象となったＮ−ｍｅｒ配列のｉミューテーションが全て含まれているため、その最小値がｉであれば、残りの計算をするまでもないからである。
ステップ６０８においてイエス（Ｙｅｓ）と判断された場合には、ｉが、処理対象となったＮ−ｍｅｒ配列の孤立度としてテーブルに記憶される。その一方、ステップ６０８においてノー（Ｎｏ）と判断された場合には、ハミング距離の最小値がｉより大きかった場合、つまり、（ｉ＋ｘ）ミューテーション（ｘ≧１）が存在することになる。そこで、ｉをインクリメントして、ステップ６０３、６０４を繰り返して、リストされたＮ−ｍｅｒ配列と処理対象となったＮ−ｍｅｒ配列とのハミング距離の最小値がｉに等しいかどうかを判断する。このようにして、膨大な処理時間を要することなく、各Ｎ−ｍｅｒ配列の孤立度を算出することができる。
可視化処理部１８は、上記図４および図５Ａ〜Ｃの処理により得られた頻度／孤立度テーブル１６を利用して、ゲノム配列中の各塩基を可視化して画像を生成する。この手法につき以下に説明を加える。たとえば、本実施の形態においては、上記Ｎ−ｍｅｒ配列の出現頻度に基づいて、塩基ごとに出現頻度に関する指標を得るようにしている。図２Ｂは、Ｎ＝６である場合に、あるゲノム配列（符号２１１）中の要素「Ａ（矢印２１２参照）」の指標の算出法を例示する図である。ここでは、要素「Ａ」を含むようなＮ個の配列を考え、（Ｎ個の配列の出現頻度の総和）／Ｎを算出することにより第１の指標を求めている。
図２Ｂの例では、６−ｍｅｒ配列「ＡＴＧＣＣＡ」、「ＴＧＣＣＡＧ」、「ＧＣＣＡＧＴ」、「ＣＣＡＴＧＣ」、「ＣＡＧＴＣＡ」および「ＡＧＴＣＡＧ」が、ゲノム配列中に、それぞれ、８回、２回、３回、１回、３回および４回出現している。したがって、求めるべき指標は、（８＋２＋３＋１＋３＋４）／６となる。このような指標の算出は、頻度／孤立度テーブルを参照することにより、高速に実現できる。
また、孤立度についても同様の手法で、塩基ごとの孤立度に関する第２の指標を求めることが可能である。この場合にも頻度／孤立度テーブルを参照すれば、高速な指標の算出を実現することができる。
可視化処理部１８は、たとえば、上記第１の指標、第２の指標、或いは、第１の指標および第２の指標を組み合わせた第３の指標に基づいて、ゲノム配列を表示する際の各塩基に割り当てる色彩を決定する。本実施の形態によれば、出現頻度が小さければ小さいほど、つまり、第１の指標の値が小さいほど、当該塩基を含む配列がユニークなプライマーである可能性が高く、その一方、孤立度が大きいほど、つまり、第２の指標の値が大きいほど、当該塩基を含む配列がユニークなプライマーである可能性が高い。これらを利用して、第３の指標＝（第２の指標／第１の指標）として、第３の指標が大きいほど、当該塩基を含む配列がユニークなプライマーである可能性が高くなるように設定しても良い。
可視化処理部１２は、図７に示すように、第１の指標の値が小さいほど寒色となり、値が大きくなるのに従って暖色となるように設定し、或いは、第２の指標の値が大きいほど寒色となり、その値が小さくなるのにしたがって暖色となるように設定して、当該設定にしたがって、塩基ごとに色を割り当てる。上述した第３の指標については、図７に示すように、その値が大きいほど寒色になることが理解できる。
このように、ゲノム配列の塩基ごとに出現頻度および／または孤立度を考慮した色彩が付与されたような画像が表示装置２４の画面上に表示されると、オペレータはこれを参照して、よりユニークであると考えられるプライマーの候補を特定することができる。ユーザは、ゲノム配列に付された色彩を参照することで、直感的に、ユニークであると考えられるプライマーの候補を見出すことが可能となる。プライマー作成支援部２０は、配列内の相補鎖の形成の有無や、融解温度の選択をなすためのツール、最適なＧＣ含有量、短いリピート配列や回文配列を避けるためのツール（プログラム）を含み、ユーザが選択したプライマー候補について、ユーザの指示にしたがって必要な処理を施すことが出来るようになっている。このようにして、ユーザは所定のプライマーをデザインすることが可能となる。
本実施の形態によれば、所定長（Ｎ）の配列のゲノム配列中の出現頻度、および、当該ゲノム配列に対する上記所定長の配列の孤立度に基づいて、ゲノム配列を構成する各塩基を可視化している。したがって、ユーザはよりユニークな塩基を含むような配列を直感的に視認することが可能となる。また、出現頻度および孤立度の計算のために、頻度／孤立度テーブルを利用することにより、上記可視化に要する処理時間を短縮している。さらに、所定長の配列に関する孤立度を生成する際に、上記Ｎよりも短い長さの配列に関するハッシュテーブルを利用することで、処理時間の短縮化を図っている。
本発明は、以上の実施の形態に限定されることなく、特許請求の範囲に記載された発明の範囲内で、種々の変更が可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
たとえば、前記実施の形態においては、出現頻度に関するテーブルにおいて、所定長（Ｎ）の配列に関するマップサイズテーブルと、それより短い長さの配列に関するハッシュテーブルの双方を生成している。これを利用して、たとえば、所定長の配列に関する孤立度の算出や、指標の生成に際する出現頻度の特定を実現している。しかしながら、このような構成に限定されるものではなく、マップサイズテーブルのみを備え、いわゆる２分探索で処理を実行しても良い。
また、前記実施の形態において、マップサイズを１８（Ｎ＝１４）として、かつ、ハッシュサイズ≦１４としているが、このようなものに限定されず、他のサイズの配列に関してテーブルを生成しても良いことは言うまでもない。
さらに、塩基ごとの指標も上記実施の形態のものに限定されず、また、指標に基づく可視化の手法も、上記実施の形態のものに限定されないことも明らかである。
また、前記実施の形態においては、指標に応じて異なる色彩を割り当てているが、これに限定されるものではなく、グレイスケールの異なる明度を割り当てても良いし、さらに、指標に応じて異なる表示態様を割り当てても良い。
さらに、前記実施の形態において、プライマー設計支援システムは、出現頻度算出部１２および孤立度算出部１４を備え、ゲノム配列ＤＢ２２からの配列に基づいて、頻度や孤立度を示すテーブルを生成している。また、生成されたテーブルを可視化処理部１８が利用している。しかしながら、これら全てを備えている必要はなく、たとえば、出現頻度算出部１２および孤立度算出部１４を備えたシステムによりテーブルが作られ、当該テーブルがＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの記録媒体に記録されても良い。この場合には、可視化処理部１８を有するシステムが、上記記録媒体を読み取り、塩基に関する指標に沿って異なる色彩を割り当てるなどの処理を実行すればよい。
また、前記実施の形態においては、プライマー、たとえば、ＰＣＲプライマーの設計を支援するために本発明を適用している。しかしながら、本発明は、マイクロアレーオリゴヌクレオチドの設計、ＲＮＡｉのための配列設計、遺伝子スクリーニングのための配列設計、ゲノムタイピング用ン配列設計をする際にも利用することができる。したがって、本明細書において、「プライマー」は、オリゴマーなどの配列を含み得る。
［第２の実施の形態］
次に、本発明の第２の実施の形態について説明する。システムの構成およびその処理を説明するのに先立って、第２の実施の形態の原理について、以下に説明する。第２の実施の形態においては、孤立度の概念を拡張した第２の孤立度（拡張された孤立度）を導入し、第２の孤立度を利用して種々の演算を実行している。再度、孤立度を簡単に説明するとともに、これを拡張した第２の孤立度を説明する。
［第２の孤立度］
「Ｇ」を長さ｜Ｇ｜のゲノム配列とする。たとえば、ヒトゲノムの場合には｜Ｇ｜＝約３Ｇｂｐとなる。また、その部分配列「Ｅ」を長さ｜Ｅ｜のゲノム配列とする。ここで、ゲノム配列Ｅは短い配列と考える。たとえば、ゲノム配列Ｇの部分配列Ｅが、ゲノム配列Ｇの中に１回だけ現れるとき、「Ｅ」の「Ｇ」に対する孤立度は、「Ｅ」と、「Ｇ」の部分配列全て（ただし元の配列を除く）を比較した際の、ミスマッチした塩基の個数の最小値となる。孤立度が高ければ高いほど、Ｅが間違った場所（適切でない場所）に結合する可能性が低くなる。
ゲノム配列Ｇの「ｌ（エル）」番目の文字から始まり「ｒ」番目の文字までの部分配列をＧ［ｌ，ｒ］と記述する。また、配列Ｓと配列Ｔとの間のハミング距離をｄＨ（Ｓ，Ｔ）と記述する。したがって、ハミング距離ｄＨ（Ｓ，Ｔ）は、以下のように表すことができる。
2003056460.tif 000003
ここで、部分配列Ｅの、ゲノム配列Ｇに対する孤立度ｉｓｏｌ（Ｅ，Ｇ）は、以下のように定義され得る。
2003056460.tif 000004
たとえば、ゲノム配列Ｓを「ＡＴＧＣＴＧＣＧＡＴＣＧＴＡ」、ゲノム配列Ｔを「ＡＴＧＴＴＧＣＧＡＴＣＣＴＡ」と考えると、ゲノム配列Ｓとゲノム配列Ｔとの間のハミング距離は「２」となる。また、ゲノム配列Ｇを、上記配列Ｓと同じものとし、部分配列Ｅを、ゲノム配列Ｓの先頭の５つの要素からなる配列「ＡＴＧＣＴ」とすると、ｉｓｏｌ（Ｅ，Ｇ）＝２となる。
次に、拡張された第２の孤立度について説明する。ゲノム配列Ｇに含まれる長さ｜Ｅ｜の配列全てが、部分配列Ｅとのハミング距離が小さい順にソートされたときに、「ｎ」番目にくる配列を、配列Ｅのｎ近傍（ｎ−ｎｅｉｇｈｂｏｒ）とし、これをｎｅｉｇｈｂｏｒｎ（Ｅ，Ｇ）と書く。ここで第２の孤立度、つまり、拡張された孤立度ｉｓｏｌｎ（Ｅ，Ｇ）を以下のように定義する。
2003056460.tif 000005
なお、ｉｓｏｌ１（Ｅ，Ｇ）は、先に説明した孤立度である。
上記第２の孤立度を算出するため、接尾辞配列（Ｓｕｆｆｉｘ  Ａｒｒａｙ）を用いる。これについて簡単に説明を加える。配列Ｇ［１，・・・，ｎ］＝Ｇ［１］Ｇ［２］・・・Ｇ［ｎ］を考える。ここで、Ｇ［ｎ］＝＄は、他のどの要素より大きな終端文字である。Ｇのｊ番目の接尾辞は、Ｇ［ｊ，・・・ｎ］で定義される。こをＧｊと記述する。文字列Ｇ［ｊ・・・ｌ］は、Ｇｊの接頭語と呼ぶ。接尾辞配列ＳＡ［１，・・・，ｎ］は、Ｇｊに対応する整数ｊからなる配列であり、それぞれの接頭語を辞書順（この例ではアルファベット順）にソートしたものである。文字列ｓとｔの最長共通接頭語（Ｌｏｎｇｅｓｔ  Ｃｏｍｍｏｎ  Ｐｒｅｆｉｘ）の長さを｜ｌｃｐ（ｓ，ｔ）｜で表すと、高さ配列Ｈｇｔ［１，・・・，ｎ］は、次のように定義される。
2003056460.tif 000006
ここで、Ｈｇｔ［１］＝０と定義した。この配列を用いると、ＴＳＡ［ｉ］の接頭語の出願頻度が文字列Ｇの中で初めて「１」回となる長さを求めることが可能となる。この長さをｍａｘＨｇｔ［ｉ］とすると、
2003056460.tif 000007
となる。ここで、ｍａｘＨｔｇ［１］＝１＋Ｈｇｔ［１］とした。
［孤立度の計算手法］
部分列Ｅのゲノム配列Ｇに対する孤立度は、Ｇを一回だけスキャンすることで求められる。この計算には、Ｏ（｜Ｇ｜（｜Ｅ｜ｌｏｇ｜Ｅ｜）１／２の時間が必要である。ミスマッチの最大数ｋが与えられた場合でも、計算時間は、Ｏ（｜Ｇ｜（ｋｌｏｇｋ）１／２）である。本発明者らは、第２の孤立度ｉｓｏｌｎ（Ｅ，Ｇ）がＯ（｜Ｇ｜（｜Ｅ｜ｌｏｇ｜Ｅ｜）１／２）の時間で計算できることを知見している。しかしながら、ヒトゲノムの場合、｜Ｇ｜は約３×１０９の大きさを有するため、より計算時間の短縮が求められる。
そこで、本発明者らは、孤立度を短い部分配列に対して求め、メモリに入る限り格納する補助テーブルを用いて、与えられた配列ＥのＧに対する孤立度の下界を求めることを考案した。
［分割された文字列の導入］
配列Ｅについて、Ｅの分割ｄｅｃ（Ｅ，Ｌ）は、Ｅを重複せずに、それぞれの部分列の長さをＬｉ（ｉ＝１，・・・，ｍ）になるようにｍ個に分割した部分列の集合で定義する。
2003056460.tif 000008
また、ｉ番目の部分列をｄｅｃｉ（Ｅ，Ｌ）とする。
本発明者らは、配列Ｅが与えられたときに、任意の分割ｄｅｃ（Ｅ，Ｌ）において、以下の式が成立することを見出した。
2003056460.tif 000009
さらに、長さｐ（たとえば、１８ｍｅｒ）以下の部分列に関しての孤立度のテーブルをシステムが保持しているとする。このとき、上式より以下の式が成り立つ。
2003056460.tif 000010
ここで、等号は、ｐ＝｜Ｅ｜のときに成立する。
上記不等式の左辺を求めるために以下の手法を採用することができる。
関数ｆ（Ｅ）を以下のように定義する。
2003056460.tif 000011
これに基づいて、以下の再帰式が得られ、孤立度の下界ｆ（Ｅ）を、Ｏ（｜Ｅ｜｜ｐ｜）の時間で計算することができる。
2003056460.tif 000012
配列Ｅに関して上記再帰式を解くことにより、孤立度ｉｓｏｌｎ（Ｅ，Ｇ）を求めることができる。さらに、後述する補助テーブルを用いてｉｓｏｌｎ（Ｅ［ｉ，ｉ］，Ｇ）（ｉ＝１，・・・，ｐ）を定数時間で求められる場合、上記再帰式は、Ｏ（｜Ｅ｜｜Ｐ｜）の時間で計算することができる。
［補助テーブル］
配列Ｅの孤立度の下界を算出するために、長さ｜ｐ｜以下の部分配列の全ての孤立度を計算しておく必要がある。本実施の形態では、接尾辞配列と高さ配列を用いる。先に最大高さ配列ｍａｘＨｇｔ［ｉ］について延べたが、これは、接尾辞配列中のｉ番目の接頭語の出現頻度が始めて配列Ｇ中で１回以下になる長さと見ることができる。この最大高さ配列の定義を拡張して、「接尾辞配列のｉ番目の接頭語の出願頻度が、はじめて配列Ｇ中でｋ本以下になる長さ」ｍａｘＨｇｔｋ［ｉ］として定義する。この最大高さ配列を求めるために、高再配列の定義を以下のように拡張する。
2003056460.tif 000013
この高さ配列ｈｇｔｋを用いて、最大高さ配列ｍａｘＨｇｔｋ［ｉ］を得ることができる。
2003056460.tif 000014
接尾辞木の各ノードに、ノード以下の要素の個数を記述しておくようなデータ構造を用いれば、最大高さ配列ｍａｘＨｇｔｋは、ツリーを深さ優先で巡回することにより、Ｏ（｜Ｇ｜）の時間で計算できる。しかしながら、接尾辞木の格納は、１６ｎバイト必要なため、ヒトゲノムの配列（３Ｇ（ギガ））の接尾辞木の場合、４８Ｇバイトのメモリ容量を要し、この接尾辞木の各ノードに、ノード以下の葉の個数を２８個以下に限定して格納しても６Ｇバイトを必要とするため、合計で５４Ｇバイトが必要となる。これに対して、接尾辞配列の場合には４ｎバイト必要であり、ヒトゲノム配列（３Ｇ（ギガ））の場合には、１２Ｇバイトに格納することができる。高さ配列を２８以下の長さについて保存しても、合計１５Ｇバイトですむ。したがって、メモリ容量の面では、接尾辞配列を用いるのが望ましい。
最大高さ配列ｍａｘＨｇｔｋを用いると、ゲノム配列Ｇ上の位置ｉから始まる長さｌの部分配列Ｅと、その孤立度ｉｓｏｌｋ（Ｅ，Ｇ）は、以下のように分類することができる。
2003056460.tif 000015
ゲノム配列Ｇの全ての位置から始まる長さ｜ｐ｜以下の部分配列Ｅの孤立度ｉｓｏｌｋ（Ｅ，Ｇ）の全てを求めるべきであるが、ｍａｘＨｇｔｎ［ＳＡ［ｉ］］≧｜ｐ｜の場合には、孤立度は「０」または「１」であり、最大高さ配列ｍａｘＨｇｔｋと接尾辞配列とから定数時間で求めることができる。長さ｜ｐ｜以下の部分配列Ｅ全てに対して、最大高さを正確に計算するためには、ｍａｘＨｇｔｋ［ＳＡ［ｉ］］＜｜ｐ｜の場合を別途計算する必要があるが、孤立度の下界を求めることを考慮すればこのステップを省略することができる。
最大高さの正確な計算を行わない場合には、長さ｜ｐ｜以下の部分配列Ｅの孤立度ｉｓｏｌｋ（Ｅ，Ｇ）が上記分類で得られた値をほぼ一致するような長さ｜ｐ｜を用いるのが望ましい。
図８は、ヒトゲノム配列中の最大高さＨｇｔの分布を示すグラフである。図８においては、横軸として、最大高さ配列ｍａｘＨｇｔの値をとり、実線のグラフの縦軸として、最大高さがｘとなるヒトゲノム配列中での位置の個数をとっている。また、点線のグラフのための縦軸として、最大高さがｘ以下のとなるようなヒトゲノム配列での位置の個数の配列全体に占める割合をとっている。
図８を参照すると、ヒトゲノム配列では、長さ１６（１６ｍｅｒ）の任意の配列を選択すると、２２パーセントの確率でユニーク（出現頻度が１回）であるのに対して、長さ２０（２０ｍｅｒ）の配列では、ユニークである確率は７４パーセントであり、特異性を示す指標として配列全体の出現回数を使用するのは、長さ２０ｍｅｒ以上の配列に対しては不適切であることがわかる。
図８を参照すると、最大高さが１７ｍｅｒの場合に、ほとんどの配列が集まっていることがわかる。ここから、最大高さがはじめて「２」となる長さを計算する場合に、パターンのピークは１８ｍｅｒもしくはそれ以上長い場合になると予想される。ｍａｘＨｇｔｋを用いて、孤立度が「０」もしくは「１」になる者の一部は正確に計算できるので、望ましい長さ｜ｐ｜は、長さ｜ｐ｜以下のほとんどの配列の孤立度が「０」もしくは「１」となる場合である。ヒトゲノム配列の場合、｜ｐ｜＝１８が最適であると考えられる。このような｜ｐ｜を探すために、再帰式のｐを１＜｜ｐ｜＜｜Ｅ｜の範囲で移動させて下界を計算する。ただし、それぞれの長さ｜ｐ｜での孤立度は正確に計算せず、ｍａｘＨｇｔｋから下界を求める。この方法は、先の述べた再帰式を、ｐ＝｜Ｅ｜である場合に、ｍａｘＨｇｔｋから得られたちを用いて解くことと同値である。下界の時間計算量はＯ（Ｅ２）となるが、Ｇ＞１０９である場合には、｜Ｅ｜≒６０であることを考えると、十分に高速に計算できることがわかる。
［処理例］
図９は、第２の実施の形態にかかる設計支援装置にて実行される処理の概略を示すフローチャートである。図９に示すように、設計支援装置においては、まず、最大高さ配列（ｍａｘＨｇｔ１（ｉ），ｍａｘＨｇｔ２（ｉ），・・・）が算出される（ステップ９０１）。たとえば、ｍａｘＨｇｔ１（ｉ）、ｍａｘＨｇｔ２（ｉ）は、以下の式から得ることができる。なお、前述したように、ｍａｘＨｇｔｋ（ｉ）は、位置ｉから始まる文字列（部分配列）で、ゲノム配列Ｇ中にてはいじめて出現回数がｋ回以下になる最大の長さを意味する。
2003056460.tif 000016
次いで、｜ｐ｜（たとえば、｜ｐ｜＝１８）以下の長さを有する部分配列の第２の孤立度を算出したテーブルが用意される（ステップ９０２）。その後、先に述べた再帰式
2003056460.tif 000017
を利用して、下界ｆ（Ｅ）が求められる（ステップ９０３）。
産業上の利用分野
本発明は、特異的な配列を用いたオリゴヌクレオチド配列などの設計を支援することに適用できる。このような特異な配列を大規模な配列情報（たとえばヒトゲノム配列）から取得することは、ＰＣＲプライマーの設計、マイクロアレーオリゴヌクレオチドの設計、ＲＮＡｉのための配列設計、遺伝子スクリーニングのための配列設計、ゲノムタイピング用の配列設計に役立てることができる。
【図面の簡単な説明】
図１は、本発明の実施の形態にかかるプライマー設計支援システムの概略を示すブロックダイヤグラムである。
図２Ａは、本実施の形態において、ゲノム配列の出現頻度を説明するための図、図２Ｂは、出現頻度に基づく第１の指標を説明するための図である。
図３は、本実施の形態における孤立度を説明するための図である。
図４は、本実施の形態にかかる出現頻度算出の処理を示すフローチャートである。
図５Ａないし図５Ｃは、本実施の形態にかかる出現頻度に関するテーブルを説明するための図である。
図６は、本実施の形態にかかる孤立度算出の処理を示すフローチャートである。
図７は、本実施の形態にかかる可視化処理にて割り当てられる色彩を説明するための図である。
図８は、第２の実施の形態に関して算出された、ヒトゲノム配列の最大高さを示すグラフである。
図９は、第２の実施の形態にかかる設計支援装置にて実行される処理の概略を示すフローチャートである。
【図１】
2003056460.tif 000018
【図７】
2003056460.tif 000019
【図２Ａ】
2003056460.tif 000020
【図２Ｂ】
2003056460.tif 000021
【図３】
2003056460.tif 000022
【図４】
2003056460.tif 000023
【図５Ａ】
2003056460.tif 000024
【図５Ｂ】
2003056460.tif 000025
【図５Ｃ】
2003056460.tif 000026
【図６】
2003056460.tif 000027
【図８】
2003056460.tif 000028
【図９】
2003056460.tif 000029
【手続補正書】
【提出日】平成15年5月26日(2003.5.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するための方法であって、
所定長の部分列の各々に関して、前記ゲノム配列中の出現頻度を算出するステップと、
前記所定長の部分列に関する出現頻度を、頻度テーブルに記憶するステップとを備えたことを特徴とする方法。
【請求項２】
前記頻度テーブルに記憶するステップが、
出現頻度が０（ゼロ）である部分列に関して、頻度テーブルへの記憶を省略するステップと、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を、第２のテーブルに記憶するステップとを有することを特徴とする請求項１に記載の方法。
【請求項３】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するための方法であって、
所定長の部分列の各々に関して、ｊ個の塩基を変換したｊミューテーション（ｊ＝１，２，・・・，ｉ−１）が、前記ゲノム配列中には表れないが、ｉ個の塩基を変換したｉミューテーションが、前記ゲノム配列中に現れるような孤立度ｉを算出するステップと、
前記所定長の部分列に関して、前記孤立度を、孤立度テーブルに記憶するステップとを備えたことを特徴とする方法。
【請求項４】
前記孤立度を算出するステップが、
前記所定長の部分列に関して、当該部分列のｋ個の塩基を変換したｋミューテーションについて、所定長の部分列の各々に関してゲノム配列中の出現頻度を記憶した頻度テーブルを参照して、当該ｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋを孤立度とするステップと、
前記ｋミューテーションが存在しない場合に、ｋをインクリメントして、前記ｋミューテーションの存在の有無を判断するステップを繰り返し実行するステップとを有することを特徴とする請求項３に記載の方法。
【請求項５】
前記孤立度を算出するステップが、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を記憶した第２のテーブルを参照して、前記所定長の部分列のうち先頭から第２の所定長にあるｋ個の塩基を変換したような、前記所定長のｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋミューテーションと、前記所定長の配列との間のハミング距離を見出すステップと、
前記ハミング距離の最小値がｋである場合に、当該ｋを孤立度とするステップと、
最小値がｋより大きい場合には、ｋをインクリメントして、前記所定長のｋミューテーションの存在の有無、および、ハミング距離の最小値を用いた判断をなすステップを繰り返し実行するステップを有することを特徴とする請求項３または４に記載の方法。
【請求項６】
前記ゲノム配列中に現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを備えたことを特徴とする請求項３または４に記載の方法。
【請求項７】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するための方法であって、
所定長の部分列に関して、当該部分列のｋ番目の文字から始まる部分配列が、ゲノム配列中に出現しなくなる最短の部分列を求めるステップと、
当該部分列中に重複せずに含まれる部分列の最大の個数ｍを算出し、当該ｍを孤立度の下界として、孤立度を示す指標とするステップとを備えたことを特徴とする方法。
【請求項８】
前記部分配列が現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを備えたことを特徴とする請求項７に記載の方法。
【請求項９】
（補正後）ゲノム配列中の塩基を含む、配列設計への適正度を判断するための方法であって、
請求項１または２に記載の方法を用いて頻度テーブルを生成するステップと、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップとを備えたことを特徴とする方法。
【請求項１０】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するための方法であって、
請求項３ないし８の何れか一項に記載の方法を用いて生成された孤立度テーブルを利用するステップと、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを備えたことを特徴とする方法。
【請求項１１】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するための方法であって、
請求項１または２に記載の方法を用いて生成された頻度テーブルを利用するステップと、
請求項３ないし８の何れか一項に記載の方法を用いて生成された孤立度テーブルを利用するステップと、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップと、前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを備えたことを特徴とする方法。
【請求項１２】
（補正後）さらに、算出された指標に基づき、当該指標の値或いは範囲にしたがって異なる表示態様を割り当てるステップと、
前記割り当てられた表示態様にしたがって、ゲノム配列中の各塩基を表したような画像を生成するステップとを備えたことを特徴とする請求項９ないし１１の何れか一項に記載の方法。
【請求項１３】
前記表示態様が、色彩であることを特徴とする請求項１２に記載の方法。
【請求項１４】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
所定長の部分列の各々に関して、前記ゲノム配列中の出現頻度を算出するステップと、
前記所定長の部分列に関する出現頻度を、頻度テーブルに記憶するステップとを前記コンピュータに実行させることを特徴とするプログラム。
【請求項１５】
前記頻度テーブルに記憶するステップにおいて、
出現頻度が０（ゼロ）である部分列に関して、頻度テーブルへの記憶を省略するステップと、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を、第２のテーブルに記憶するステップとを、前記コンピュータに実行させることを特徴とする請求項１４に記載のプログラム。
【請求項１６】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
所定長の部分列の各々に関して、ｊ個の塩基を変換したｊミューテーション（ｊ＝１，２，・・・，ｉ−１）が、前記ゲノム配列中には表れないが、ｉ個の塩基を変換したｉミューテーションが、前記ゲノム配列中に現れるような孤立度ｉを算出するステップと、
前記所定長の部分列に関して、前記孤立度を、孤立度テーブルに記憶するステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項１７】
前記孤立度を算出するステップにおいて、
前記所定長の部分列に関して、当該部分列のｋ個の塩基を変換したｋミューテーションについて、所定長の部分列の各々に関してゲノム配列中の出現頻度を記憶した頻度テーブルを参照して、当該ｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋを孤立度とするステップと、
前記ｋミューテーションが存在しない場合に、ｋをインクリメントして、前記ｋミューテーションの存在の有無を判断するステップを繰り返し実行するステップとを、前記コンピュータに実行させることを特徴とする請求項１６に記載のプログラム。
【請求項１８】
前記孤立度を算出するステップにおいて、
前記所定長より短い第２の所定長を有するような第２の部分列の各々を用いて、前記第２の部分列を先頭から含む所定長の部分列の、前記頻度テーブル中の位置を記憶した第２のテーブルを参照して、前記所定長の部分列のうち先頭から第２の所定長にあるｋ個の塩基を変換したような、前記所定長のｋミューテーションが存在するか否かを判断するステップと、
前記ｋミューテーションが存在する場合に、当該ｋミューテーションと、前記所定長の配列との間のハミング距離を見出すステップと、
前記ハミング距離の最小値がｋである場合に、当該ｋを孤立度とするステップと、
最小値がｋより大きい場合には、ｋをインクリメントして、前記所定長のｋミューテーションの存在の有無、および、ハミング距離の最小値を用いた判断をなすステップを繰り返し実行するステップを、前記コンピュータに実行させることを特徴とする請求項１６または１７に記載のプログラム。
【請求項１９】
前記ゲノム配列中に現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを、前記コンピュータに実行させることを特徴とする請求項１６または１７に記載のプログラム。
【請求項２０】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するために、コンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
所定長の部分列に関して、当該部分列のｋ番目の文字から始まる部分配列が、ゲノム配列中に出現しなくなる最短の部分列を求めるステップと、
当該部分列中に重複せずに含まれる部分列の最大の個数ｍを算出し、当該ｍを孤立度の下界として、孤立度を示す指標とするステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項２１】
前記部分配列が現れるか否かの判断を、前記ゲノム配列中での出現頻度がｎ回以下であるかに基づいて実行するステップを、前記コンピュータに実行させることを特徴とする請求項２０に記載のプログラム。
【請求項２２】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
請求項１４または１５に記載のプログラムを、コンピュータに実行させることにより生成された頻度テーブルを利用するステップと、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項２３】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
請求項１６ないし２１の何れか一項に記載のプログラムを、コンピュータに実行させることにより生成された孤立度テーブルを利用するステップと、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを、前記コンピュータに実行させることを特徴とするプログラム。
【請求項２４】
（補正後）ゲノム配列中の塩基を含む配列の、配列設計への適正度を判断するためにコンピュータを動作させる、当該コンピュータにより読み取り可能なプログラムであって、
請求項１４または１５に記載のプログラムを、コンピュータに実行させることにより生成された頻度テーブルを利用するステップと、
請求項１６ないし２１の何れか一項に記載のプログラムを、コンピュータに実行させることにより生成された孤立度テーブルを利用するステップと、
ゲノム配列を構成する各塩基に関して、当該塩基を含む所定長と同数の配列を特定するステップと、
前記頻度テーブルを参照して、特定された配列の各々に関する出現頻度を特定するステップと、
前記特定された出現頻度の総和に基づき、第１の指標を算出するステップと、前記孤立度テーブルを参照して、特定された配列の各々に関する孤立度を特定するステップと、
前記特定された孤立度の総和に基づき、第２の指標を算出するステップとを、前記コンピュータにより実行させることを特徴とするプログラム。
【請求項２５】
（補正後）さらに、算出された指標に基づき、当該指標の値或いは範囲にしたがって異なる表示態様を割り当てるステップと、
前記割り当てられた表示態様にしたがって、ゲノム配列中の各塩基を表したような画像を生成するステップとを、前記コンピュータに実行させることを特徴とする請求項２２ないし２４の何れか一項に記載のプログラム。
【国際調査報告】
2003056460.tif 000030
2003056460.tif 000031
2003056460.tif 000032
2003056460.tif 000033
2003056460.tif 000034
2003056460.tif 000035
2003056460.tif 000036