(57)【要約】      （修正有）【課題】ＳＢＨ法（Ｓｅｑｕｅｎｃｉｎｇ  Ｂｙ  Ｈｙｂｒｉｄｉｚａｔｉｏｎ、ハイブリッド形成によるシーケンシング）によってシーケンシングする情報処理方法を提供する。ＳＢＨ法はＤＮＡアレイを使用することにより、８から１２塩基程度の長さのすべての配列の有無を一回の実験により判別できるという特徴を有する。しかし、ＤＮＡアレイから得られたデータにはエラーを含むのでエラーを解決する方法を提供する。【解決手段】エラーを含む連結を行うと短い完成配列しか得られないという知見に基づいて、プローブ長さがＬ塩基とすると、（Ｌ−１）ペアの連結ではエラーのため相手が存在しないときに限り（Ｌ−２）ペアで代替し、あるいは（Ｌ−２）ペアにより（Ｌ−１）ペアをバイパスしこれを繰り返してもっとも長い連結配列が得られるように探索する方法を提供し、エラーによる同じプローブを２回使用して無限ループを作ることを防ぐ。【選択図】図１
2005058187.tif 000002
【特許請求の範囲】
【請求項１】
ＤＮＡアレイのハイブリッド形成したプローブを集めるシーケンシング方法において、長さＬ個の塩基のプローブから左プローブと右プローブを作り上下に並べ、左プローブの右端から（Ｌ−１）個の部分列と右プローブの左端から（Ｌ−１）個の部分列がすべて一致するような左右のペア・プローブを逐次的な順位をつけて連結して一致塩基列を伸長させるとき、Ｌ／２より小さな正の整数Ｍを設定し、（Ｌ−１）ペア・プローブが存在しないｎ連結順位に対し、（Ｌ−Ｍ）個の部分列のペア・プローブで代替し、（Ｌ−Ｍ）個の部分列のペア・プローブも存在しなければ（ｎ−１）連結順位の（Ｌ−Ｍ）個の部分列のペア・プローブによりｎ連結順位をバイパスすることにより連結を継続する情報処理方法。
【請求項２】
請求項１に記載の連結方法において、（Ｌ−１）個の部分列のペア・プローブはｎ連結順位から１個の空白をおいて連結し、（Ｌ−Ｍ）個の部分列のペア・プローブで代替するとき、ｎ連結順位からＭ個の空白をおいて連結し、（Ｌ−Ｍ）個の部分列のペア・プローブでバイパスするとき、（ｎ−１）連結順位からＭ個の空白をおいて連結する情報処理方法。
【請求項３】
あらかじめプローブの順位をランダムにシャッフルしたのち、請求項１および２に記載の連結方法を適用し、得られた一致塩基列のうちでもっとも長い塩基列を近似解とする情報処理方法。
【発明の詳細な説明】
【発明の詳細な説明】
【技術分野】
【０００１】ＤＮＡアレイまたはＳＢＨアレイの表面に固定したプローブと未知のＤＮＡ相補配列とのハイブリダイゼーションから情報を集め、シーケンシングを行う情報処理方法に関する。
【背景技術】
【０００２】この分野における最新の文献として次のものが開示されている。
Ｐ．Ａ．Ｐｅｖｚｎｅｒ：Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｍｏｌｅｃｕｌａｒ  Ｂｉｏｌｏｇｙ  ２０００，ｐ６７
文献はハイブリダイゼーション  エラーのようなエラーを含まないとき、巡回セールスマン問題と同じような組み合わせ問題を解くアルゴリズムを提案している。１０塩基程度の短いプローブではエラーを含みやすく、プローブ（長さＬ塩基、これを以下Ｌペアという）の部分配列（（Ｌ−１）ペア）の重複区間がユニークでなく、同一のものが複数個存在するとき、連結経路が複数存在し、その中から正解の経路を特定する方法は存在しないことが明らかにされている。エラーがなく、（Ｌ−１）ペアがすべてユニークであるとき、容易に正解のプローブ連結作業を行うことができる。本出願の発明は（Ｌ−１）ペアがユニークでなくエラーを含むとき、最長近似解を提供することを目的とする。
【発明が解決しようとする課題】
【０００３】ＤＮＡ塩基配列を読みとることを「シーケンシング」という。１回のシーケンシングで読むことができる配列は数百程度である。本出願の発明はＳＢＨ法（Ｓｅｑｕｅｎｃｉｎｇ  Ｂｙ  Ｈｙｂｒｉｄｉｚａｔｉｏｎ、ハイブリッド形成によるシーケンシング）によってシーケンシングする方法を提供する。
【課題を解決するための方法】
【０００４】ＳＢＨ法はＤＮＡアレイを使用することにより、８から１２塩基程度の長さのすべての配列の有無を一回の実験により判別できるという特徴を有する。ＳＢＨ法はＤＮＡアレイ上のすべての配列について読みとり対象の配列中にそれらが含まれているか否かが判別できる。ＤＮＡアレイから得られたデータにはエラーを含む。本出願の発明はエラーを解決する方法を提供する。
【０００５】エラーがあるとプローブの連結の相手が存在しなかったり、同じプローブを２回使用して無限ループを作ることがある。本出願の発明においてエラーを含む連結を行うと短い完成配列しか得られないという知見に基づいて、（Ｌ−１）ペアの連結ではエラーのため相手が存在しないときに限り（Ｌ−２）ペアで代替し、あるいは（Ｌ−２）ペアにより（Ｌ−１）ペアをバイパスしこれを繰り返してもつとも長い連結配列が得られるように探索する方法を提供する。
【発明を実施するための最良の形態】
【０００６】ＤＮＡアレイは別名ＳＢＨアレイとも呼ばれるが、このアレイから得られる短い塩基列をプローブという。プローブ長さが１０塩基、ハイブリダイゼーションにより存在が確認されたプローブ数が６００個のデータを利用して完成配列長が６０９個の配列をアセンブルする実施例を説明する。これらの数値は例示であり、発明の範囲を限定するものではない。図１は本出願の発明の原理を説明したものである。【０００７】長さＬのプローブから左プローブと右プローブを作り上下に並べる。左プローブの右端からＮ個（Ｎ＝Ｌ−１）の塩基列と右プローブの左端からのＮ個の塩基列がすべて一致するような左右のプローブをペアとよび、逐次的につなぎ合わせて一致塩基列を伸長させる。これを表１に示す。プローブ配列の直後に重複区間の個数を「＿９、」「＿８Ａ」「＿８Ｂ」のように示す。Ｎ＝Ｌ−１の重複区間をもつプローブの信頼性が高いので、極力このペアを優先すべきことは公知である。その理由は後述のように重複区間が小さくなると重複ペアが増加し、連結の信頼性が低下する。各プローブは１回だけ使用し、Ｎ個の一致する区間を重複区間という。プローブの重複区間がすべてユニークであり、エラーを含まないとき正解の最長一致配列が求まる。たとえば、プローブ長さ１０のとき、９個の塩基が完全一致するペア９（以下Ｐ９という）に重複プローブがなく、Ｐ９のつなぎ合わせが１つ残らず完了すれば完全な一致塩基列がえられる。【０００８】
【表１】
2005058187.tif 000003
2005058187.tif 000004
【０００９】Ｐ１０はユニークであってもＰ９では同じ塩基列をもった重複ペアが発生することがある。たとえば、プローブ長さ１０塩基、合計６００プローブの例ではＰ９で７個、Ｐ８で１３個の重複プローブが発生する。重複プローブがあると、連結経路の異なる塩基列が複数個生まれ、組み合わせアルゴリズムだけでは正解の塩基列を求めることはできない。これを図２に示す。重複プローブがあれば正解は情報処理ではなく生物学的な検証が必要になる。たとえば、部分的により長いプローブを使用して再試験を行い正しい配列を求める。図２から明らかなように重複ペアが存在するときすべてのプローブが連結されるもっとも長い配列が正解に近い。したがって、本発明では入力プローブ配列をシャッフルして相当の試行回数の中で得られたもっとも長い配列を近似解として採用する。【００１０】ハイブリダイゼーションにエラーがあるとき、逐次的な連結の過程で相手プローブの見つからないケースが発生し、ペアにならない左右プローブが生じる。これを「Ｐ空」という。Ｐ９に存在する「Ｐ９空」もエラーの存在場所によりＰ８ではペアに変わるケースも存在する。このようにＰ９に「Ｐ９空」（ｎ連結順位番号）があれば、その位置でＰ８の左プローブを探す。Ｐ８の左プローブがあればそのペアの右プローブ（ｎ＋２連結順位番号）でもとのＰ９の左プローブに戻ることができる。Ｐ８になければＰ７を探す。低次Ｐになるほど重複が増加し信頼性が低下する。したがって上位ペアがないときのみ下位のペアを探す。この方法を代替法とよぶ。しかし、エラーがプローブ中央付近にあるとき、代替法はペアを見つけることが不可能である。【００１１】代替法を補完するため、エラーを回避するもう１つの方法としてバイパス法を図１に示す。「Ｐ９空」と「Ｐ８空」が同時に発生すると、「Ｐ９空」（ｎ連結順位番号）の１つ前の左プローブ（ｎ−１連結順位番号）に戻り、Ｐ８を試み、存在すればＰ９の（ｎ＋１連結順位番号）にバイパスすることができる。Ｐ８が存在しないこともあるのでＰ７を準備する。一般的に代替法とバイパス法の複合が単独の方法よりも良い結果を与える。これを表３に示す。【００１２】連結の過程でプローブにエラーを含むと、代替法とバイパス法を複合しても「Ｐ空」が発生する。また、同じペア間でループを構成する。図２に未完結例を示す。これらは短い配列を与える結果に終わり、一般的に長い配列長ほど正解に近いことが明らかとなった。結論的にはＰ９、Ｐ８、Ｐ７の代替法、バイパス法の選択は試行錯誤によらざるを得ない。たとえば、表３のように高次のペアが常により長い配列を与える保証はない。したがって、配列長が変化しなくなるまで高次から順に試行する。【００１３】
【表２】
2005058187.tif 000005
2005058187.tif 000006
（注）「８＋７」の意味：ペア９がないとき、ペア８を試行し、ペア８がないとき、ペア７を試行する。「Ａ＋Ｂ」の意味：代替法が不可能なとき、バイパス法を試行する。ペア数８、７はプローブ長１０のケースを例示したものであり、本発明の範囲を限定するものではない。【００１４】
【表３】
2005058187.tif 000007
【００１５】Ｐ、Ｑ、Ｒ、Ｓ、Ｔは同じ母配列をもち、６００プローブ数、プローブ長さは１０塩基、いずれもランダムなエラー３０個所を含む。試行回数はそれぞれ１００とし、もっとも長い配列長を求めた。エラーがなくプローブがユニークなとき完成配列長は６０９となる。【００１６】表１に示したようにプローブの連結作業はプローブの重複塩基数が大部分９個であるから、連結は（１０−９）の１個の塩基がずれて連結される。Ｐ８代替法ではＰ９（ｎ）から２個ずらせる必要があり、Ｐ８バイパス法ではＰ９（ｎ−１）から２個ずらせる必要がある（ｎはプローブ連結順位番号）。
【発明の効果】
【００１７】本出願の発明により、従来、計算資源を長時間使用していたＳＢＨ法を代替法とバイパス法の複合により短時間で正確に効率よく探索する方法を提供できる。
【図面の簡単な説明】
【図１】連結作業の空白区間を代替法とバイパス法を複合して埋め合わせする原理を説明する図である。
【符号の説明】
Ａ：重複区間をキーとしてプローブを連結するプロセスを示し、破線（ｎ、ｎ＋１：プローブ連結順位番号）はエラーの存在により、連結不能プローブを示す。
Ｂ：９塩基の重複区間をもつプローブを「Ｐ９満」という。
Ｃ：重複区間をもたない連結不能プローブを「Ｐ９空」という。
Ｄ：「Ｐ９空」を「Ｐ８満」で代替し。Ｐ９（ｎ＋２）に再連結する。
Ｅ：「Ｐ９空」および「Ｐ８空」をＰ８（ｎ−１）によりバイパスし、Ｐ９（ｎ＋１）に再連結する。
【図２】
重複区間の同じプローブが存在するとき、複数の連結経路が存在することを説明し、より長い経路が良い近似解を与えることを説明する図である。
【図３】
連結作業が完結するケース（Ａ）と相手プローブなし（Ｂ）、同じプローブに戻るループの発生（Ｃ）を説明する図である。（Ｂ）、（Ｃ）は（Ａ）よりも短い連結配列長しか得られない。
【図１】
2005058187.tif 000008
【図２】
2005058187.tif 000009
【図３】
2005058187.tif 000010