(57)【要約】【課題】        ゲノム配列の１本鎖には逆方向繰り返しが多数見られる。これをパリンドローム、すなわち前から読んでも後ろから読んでも同じであるから回文構造という。回文構造は酵素やｍｉＲＮＡ、ｓｉＲＮＡにより特異的に認識され、切断部分となるので、遺伝子操作や再生医療において回文構造の位置を正確・高速に検出するためのコンピュータ・アルゴリズムを作成する。【解決手段】        ５００万塩基以上の大容量配列を高速に解析する目的でギャップと不一致を含まない回文構造を検出する。中間のヘアピン状の非回文区間を介して第１回文片と第２回文片が相補的に結合する回文構造を検出するため、相補ペア合計チェック処理と最小回文長さ検査処理と回文延長処理の３つの処理を行う手段を提供する。【選択図】図１
2005316924.tif 000002
【特許請求の範囲】
【請求項１】
中間のヘアピン状の非回文区間を介して第１回文片と第２回文片を検出するため、第１回文片に含まれる相補ペア塩基ａ、ｔ（またはｃ、ｇ）のそれぞれの合計数（ａ合計１、ｔ合計１）（またはｃ合計１、ｇ合計１）と第２回文片に含まれる同じ相補ペア塩基の合計数（ａ合計２、ｔ合計２）がａ合計１＝ｔ合計２、ｔ合計１＝ａ合計２（またはｃ合計１＝ｇ合計２、ｇ合計１＝ｃ合計２）となるような区間を求め、さらに第１回文片の１つ先の塩基と第２回文片の１つ前の塩基が相補関係にない区間を回文候補区間として抽出することを特徴とする相補ペア合計チェック処理方法。
【請求項２】
請求項１に記載の相補ペア合計チェック処理方法で抽出した回文候補区間において、第１回文片の最後尾が第２回文片の先頭と相補であるかの検査を始め、設定した最小回文塩基数すべてが候補区間内で相補関係にあるときに限り次の回文延長処理に移り、候補区間の中間で非相補関係の塩基を検出すると、処理を中断することを特徴とする最小回文長さ検査処理方法。
【請求項３】
請求項２に記載した最小回文長さ検査処理方法により抽出した第１回文片の先頭から１つ前の塩基と第２回文片の最後尾の次の塩基が相補関係にあるとき、それぞれの塩基を回文片に追加する回文延長処理方法。
【請求項４】
請求項１から３まで記載の相補ペア合計チェック処理と最小回文長さ検査処理と回文延長処理の３つの処理を行う回文構造検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】        遺伝子操作等のためにゲノム配列に含まれる回文構造を高速に網羅的に検出するコンピュータ・アルゴリズムに関する。
【背景技術】
【０００２】        欧州分子生物学ソフトパケッジ（ＥＭＢＯＳＳ）にはｅｉｎｖｅｒｔｅｄ，  ｐａｌｉｎｄｒｏｍｅが登録（非特許文献１参照）されており、配列にギャップ、不一致を含む場合でもダイナミックプログラミングにより最適な回文解が得られる。しかし、処理速度が遅いので大容量配列の回文解析には不向きである。
【非特許文献１】ｈｔｔｐ：／／ｗｗｗ．ｈｇｍｐ．ｍｒｃ．ａｃ．ｕｋ／ｓｏｆｔｗａｒｅ／ＥＭＢＯＳＳ／Ａｐｐｓ／
【発明の開示】
【発明が解決しようとする課題】
【０００３】        ゲノム配列の１本鎖には逆方向繰り返しが多数見られる。これは左から読んでも、右から読んでも同じ言葉になるような「しんぶんし」のような例である。配列には対称の中心部があり、そこで折り返して戻ると相補関係にある塩基列が並んでいる。これをパリンドローム、すなわち前から読んでも後ろから読んでも同じであるから回文構造という。回文構造は酵素やｍｉＲＮＡ、ｓｉＲＮＡにより特異的に認識され、切断部分となるので、遺伝子操作や再生医療において回文構造の位置を正確・高速に検出する課題がある。
【課題を解決するための手段】
【０００４】        ５００万塩基以上の大容量配列を高速に解析する目的でギャップと不一致を含まない回文構造を検出するコンピュータ・アルゴリズムである。中間のヘアピン状の非回文区間を介して第１回文片と第２回文片が相補的に結合する回文構造を検出するため、相補ペア合計チェック処理と最小回文長さ検査処理と回文延長処理の３っの処理を行う手段を提供する。
【発明の効果】
【０００５】        ３つの処理を行うことにより従来の回文検出方法と比較し、実施例のとおり高速処理を実現できるので大容量塩基配列の回文解析に適している。
【発明を実施するための最良の形態】
【実施例】
【０００６】        図１は１つの回文候補区間に対する処理の流れを示したものであり、図４も参照すると、最小回文塩基数が１０以下のとき、２相補ペア合計チェックを行うと従来の方法より４．２５倍の高速処理が可能になり、塩基数が１０以上では１相補ペア合計チェックを行うと、８．２８倍の高速処理が可能になる。【０００７】        （１）概要
図２は最小回文塩基数が５の回文構造である。符号２は第１最小回文片（Ａｉ）、符号４は第２最小回文片（Ｂｉ）であり、後尾のＡ５塩基と先頭のＢ１塩基は相補ペア塩基であり、それぞれ「ａ」と「ｔ」、または「ｃ」と「ｇ」である。ただし、ＲＮＡ配列では「ｔ」が「ｕ」に代わる。符号３は中間の非回文区間であり、先頭のＡ＋と後尾のＢ−は相補塩基ではない。符号１と符号５は回文延長可能区間であり、最小回文塩基数が満足されたとき、Ａ−とＢ＋が相補塩基であれば、回文片に追加され、もっとも長い回文片が求められる。表１に大腸菌の塩基配列の先頭部分において最小回文塩基数を６としたときの回文例を示す。【０００８】
【表１】
2005316924.tif 000003
【０００９】        （２）パラメータ
回文構造を決定するパラメータは２種類である。１つは最小回文塩基数であり、たとえば、６から１４である。大腸菌の先頭から４８万塩基の範囲でギャップや不一致を含まない完全な回文構造は意外に多く、最小回文塩基数６で１１３２個、塩基数８で１３６、塩基数１０で３６、塩基数１２で１２、塩基数１４で４個もある。もう１つは非回文区間塩基数であり、表２の例示では４から１１まで分布している。表２のとおり非回文区間塩基はａ、ｔがｃ、ｇよりも多いので本実施例ではａ、ｔを優先的に１相補ペア塩基として選ぶ。【００１０】
【表２】
2005316924.tif 000004
【００１１】        （３）従来の方法
図３は図２を展開して回文構造の検出方法を説明したものである。符号は図２と同一である。はじめに符号２の候補片（Ａ１−Ａ５）が仮定されると、中間の非回文区間の塩基数は不明であるからこの個数（Ｎ：図ではＮ＝５）をパラメータとして符号４の候補片は（Ｂ１１−Ｂ１５））から（ＢＮ１−ＢＮ５）まで相補関係を調べる。これは事前に全配列の相補配列を求めておくことにより（Ａ１−Ａ５）と（ＢＮ１−ＢＮ５）との一致、不一致を調べる方法に帰結され、相補関係を調べるよりも計算時間が少なくなる。最小回文塩基数のすべてが一致すると、非回文区間のＡ＋とＢ−が相補関係にないことが検査される。回文検査の途中で不一致が検出されるか、Ａ＋と−が相補関係にあると，その時点で回文候補区間は捨てられる。回文検査回数の合計（Ｔｏｔａｌ）は【００１２】
【数１】
2005316924.tif 000005
【００１３】        従来の方法は回文候補区間に対しすべて回文検査を行う「全数検査型」である。回文検査はさらに区間の塩基を１個ずつ一致、不一致を調べる。確率的に区間の第１塩基が一致する確率は１／４あるので、従来の方法は計算回数がＴｏｔａｌ／４以上（表３参照）となる。しかも、これは最小回文塩基数とはほとんど無関係である。【００１４】        （４）本発明の方法
本発明は「１相補ペア合計チェック」と「２相補ペア合計チェック」により、あらかじめ最小回文長さ検査を行う候補回文区間数を絞り込む。１相補ペア合計チェックは符号２区間の「ａ」塩基の合計数が符号４区間の「ｔ」塩基の合計数と等しく、符号２区間の「ｔ」塩基の合計数が符号４区間の「ａ」塩基の合計数に等しい候補回文区間のみを対象に最小回文長さ検査を行う。（ここで「ａ」と「ｔ」は例示であり、「ｃ」と「ｇ」でも同じである。また、ＲＮＡ配列では「ｔ」の代わりに「ｕ」を使用する。）２相補ペア合計チェックはさらに「ｃ」と「ｇ」のペアを上記と同じように加えて候補回文区間の絞り込みを行う。【００１５】        １相補ペア合計チェックでは全配列にわたって「ａ」と「ｔ」塩基の累積合計数をもとめる。２相補ペア合計チェックではさらに「ｃ」と「ｇ」の累積合計数を求める。最小回文塩基数（ｌｅｎ）に応じて区間差分配列を求める。【００１６】
【数２】
2005316924.tif 000006
【００１７】        区間差分配列を求める計算は最小回文塩基数に無関係にオーバヘッドを与える。従来の方法では全配列の相補配列を求める計算がオーバヘッドになる。４８万塩基の配列のオーバヘッドは、１相補ペア合計チェックの区間差分配列計算では１２５ｍｓ、２相補ペア合計チェックの区間差分配列計算では２６６ｍｓ、全配列の相補配列の計算時間では２１９ｍｓである。（計算時間はＰｅｎｔｉｕｍ４、ＣＰＵ２．８ＧＨｚによる実測値である。）【００１８】        最小回文塩基数が多いと相補ペア合計チェックの効果が大きくなる。逆に、塩基数が少ないと効果が少ない。図４は測定結果のグラフであり、表３に数値を示す。符号１は従来の方法でＴｏｔａｌ／４となり最小回文塩基数とはほとんど無関係である。符号２は１相補ペア合計チェック後の個数であり、符号３は２相補ペア合計チェックの個数であり、いずれも最小回文長さ検査処理への入力個数である。符号２と符号３は最小回文塩基数が多くなるほど個数は少なくなり、また符合３の入力個数が符号２の入力個数よりも少なくなるのは当然である。【００１９】
【表３】
2005316924.tif 000007
【００２０】        符号３は入力個数を絞り込む効果が符号２よりも大きいがオーバヘッドも大きいので、計算時間で見ると図５のとおり最小回文塩基数１０以下で符号２よりも約１０％所要時間が短くなるが、最小回文塩基数が１４になると、符号２が符号３よりも約１０％以上有利となる。
【産業上の利用可能性】
【００２１】        遺伝子操作や再生医療に関連する製薬産業で利用できる。
【図面の簡単な説明】
【図１】        １つの回文候補区間に対する３つの処理の流れを示す図である。
【図２】        回文の構成内容を示す図である。
【符号の説明】
１：第１延長可能区間
２：第１最小回文片
３：非回文区間（ヘアピン区間）
４：第２最小回文片
５：第２延長可能区間
【図３】
回文の検出方法を示す図である。
【符号の説明】
図２と同じ。
【図４】
最小回文塩基数と最小回文長さ検査処理への入力個数の関係を示す図である。
【符号の説明】
１：従来の方法（相補ペア合計チェックなし）
２：１相補ペア合計チェック
３：２相補ペア合計チェック
４：大腸菌の先頭４８万塩基に含まれる回文個数
【図５】
最小回文塩基数と計算時間の関係を示すグラフである。
【符号の説明】
図４と同じ。
【図１】
2005316924.tif 000008
【図２】
2005316924.tif 000009
【図３】
2005316924.tif 000010
【図４】
2005316924.tif 000011
【図５】
2005316924.tif 000012