(57)【要約】【課題】ＤＮＡ塩基配列を読みとることを「シークエンシング」という。１回のシークエンシングで読むことができる配列は数百程度である。シークエンシングによって得られた短い配列をつなぎ合わせて一本の長い配列を構築することをアセンブリングという。本出願の発明はＳＢＨ法（Ｓｅｑｕｅｎｃｉｎｇ  Ｂｙ  Ｈｙｂｒｉｄｉｚａｔｉｏｎ、ハイブリッド形成によるシークエンシング）によってシークエンシングされた配列のアセンブリング方法を提供する。【解決手段】従来の方法は組み合わせ問題を効率的に解決する方法に主眼があったが、本出願の発明では実験エラーを含む連結を行うとより短い完成配列しか得られないという知見に基づいて、左右プローブの重複区間において完全に一致する塩基がもっとも多いペア・プローブから優先して連結して得られるもっとも長い配列を効率よく探索する方法を提供する。【選択図】図１
2004215640.tif 000002
【特許請求の範囲】
【請求項１】
同一の２塩基対を共有する２つのプローブを上下に並べ、同一の２塩基対の先頭位置を合わせると、プローブ左端が塩基２個以内でずれるとき、先行するプローブを左プローブとし、もう１つのプローブを右プローブとし、左右プローブの重複区間では両方の塩基が完全に一致するペア・プローブのみを抽出するアセンブリング方法。
【請求項２】
請求項１に記載のペア・プローブを抽出する検索キーは２塩基対の種類を第１キーとし、プローブ左端からの２塩基対の先頭位置により３塩基ずつ半重ねのグループを第２キーとし、２塩基対の右側から右端までの塩基配列と２塩基対のすぐ左側から順に左端までの塩基配列を連結して第３キーとし、元のプローブを取り出すためのプローブ一連番号を第４キーとし、第１から第４の順に優先する検索キーの構成方法。
【請求項３】
請求項２に記載の検索キーのすべてを一括してソートし、ソート順序にしたがって第４キーをもとに元のプローブを取り出し、左右プローブの重複区間において請求項１に記載の条件を満足し、左プローブ一連番号が同一のペア・プローブ群の中で第２キーの２塩基対の先頭位置差が１のチャンピオン・ペアを優先的に抽出し、チャンピオン・ペアが存在しないとき先頭位置差が２の次点ペアを抽出する方法。
【請求項４】
請求項３に記載のチャンピオン・ペアの左プローブ一連番号をキーとしてソートし、重複区間をあわせて左プローブと右プローブを連結し、次に右プローブが左プローブとなるようなペア・プローブをバイナリ・サーチして逐次的にペア・プローブを連結する方法。
【請求項５】
請求項４に記載の連結方法により作成した左から右への重複配列において同じ列の塩基を種類ごとに合計し、もっとも合計数の多い塩基により当該位置の塩基を確定する方法。
【請求項６】
請求項１から請求項５までに記載の一連の処理をランダムにシャッフルした入力プローブ配列に適用し、得られたもっとも長い配列を完成配列とする情報処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
ＤＮＡチップから得られたハイブリッド形成によるシークエンシングによってシークエンシングされた配列のアセンブリング方法に関する。
【０００２】
【従来の技術】
この分野における最新の文献として次のものが開示されている。
Ｚｈａｎｇ  ＪＨ、Ｗｕ  ＬＹ、ＺｈａｎｇＸＳ：Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ＤＮＡ  ｓｅｑｕｅｎｃｉｎｇ  ｂｙ  ｈｙｂｒｉｄｉｚａｔｉｏｎ．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ  ２００３  Ｊａｎ；１９（１）１４−２１
実験エラーを含む場合のアッセンブリングは巡回セールスマン問題と同じように無限に近い組み合わせ問題を解くことに等しい。本文献は塩基の繰り返しの多いケースに適用できる組み合わせ問題を解くアルゴリズムを提案している。
【０００３】
本出願の発明において組み合わせ問題を避け、実験エラーを含む連結を行うとより短い完成配列しか得られないという知見に基づいて、重複区間で完全に一致する配列のみを連結して得られるもっとも長い配列を効率よく探索する方法を提供する。
【０００４】
【発明が解決しようとする課題】
ＤＮＡ塩基配列を読みとることを「シークエンシング」という。１回のシークエンシングで読むことができる配列は数百程度である。シークエンシングによって得られた短い配列をつなぎ合わせて一本の長い配列を構築することをアセンブリングという。本出願の発明はＳＢＨ法（Ｓｅｑｕｅｎｃｉｎｇ  Ｂｙ  Ｈｙｂｒｉｄｉｚａｔｉｏｎ、ハイブリッド形成によるシークエンシング）によってシークエンシングされた配列のアセンブリング方法を提供する。
【０００５】
【課題を解決するための方法】
ＳＢＨ法はＤＮＡチップを使用することにより、８から１２塩基程度の長さのすべての配列の有無を一回の実験により判別できるという特徴を有する。ＳＢＨ法はＤＮＡチップ上のすべての配列について読みとり対象の配列中にそれらが含まれているか否かが判別できる。ＤＮＡチップから得られたデータには実験エラーを含む。本出願の発明は実験エラーを解決する方法を提供する。
【０００６】
【発明の実施の形態】
ＤＮＡチップは別名ＳＢＨチップとも呼ばれるが、このチップから得られる短い塩基列をプローブという。プローブ長さが１０塩基、ハイブリダイゼーションにより存在が確認されたプローブ数が約６００個のデータを利用して完成配列長が約５００以上の配列をアセンブルする実施例を説明する。図１は実施例を要約したものである。
【０００７】
図２は本出願の発明の原理を説明したものである。短いプローブをつなぎ合わせて長い配列を完成させるには符号１、２、３のようなペア、または符号４、５、６のようなグループが示す重複区間を利用して配列を連結する必要がある。符号１の重複は連結に必要な情報を与えない。符号２は９個の重複区間、符号３は８個の重複区間を持つ。符号２は符号３よりもより信頼性の高い連結を行うことができる。したがって、本発明では符号２の連結を優先し、実験エラー等により符号２が存在しないときのみ符号３の連結を使用する。
【０００８】
逐次的に連結するためには符号４、５、６のようなグループ化が必要である。符号４は左から右へ重複したプローブを連結する方法であり、左プローブ先行型という。符号６は逆に右から左への重複したプローブを連結する方法であり、右プローブ先行型という。符号４は左から右へ後尾追加型となるため左右プローブの連結が簡単である。符号６は右から左への先頭挿入型となるためプローブの連結が複雑となるが、符号４と符号６は鏡像の関係にあり、符号６の配列を逆転させると符号４と同じ処理となる。符号５は１０個の塩基すべてが重複区間であるので、連結に必要な情報が得られず抽出の対象としない。したがって、本出願の発明では左プローブ先行型を使用する。
【０００９】
１個の実験エラーを許容することは不可欠であるが、９個の重複区間に１個の不一致があるとき、実験エラーに由来するものか、本来ペア・プローブを構成しないはずのペアを誤認したものか、判別がつかない。したがって、本発明は９個の重複区間または８個の重複区間において塩基が完全に一致するペア・プローブのみを抽出する方法を採用する。さらに９個のペアを優先して連結し、９個のペアがないときのみ８個のペアの連結を行う。
【００１０】
プローブに存在するディヌクレオチド（ＡＡ、ＡＣ、ＡＧ、ＡＴ・・・ＴＴ  以下では２塩基対という）を核とし、２つのプローブに含まれる同一の２塩基対の位置を合わせると、図３のとおり先行するプローブを左プローブと定義できる。符号１は２塩基対、符号２は一致塩基、符号３は不一致塩基、符号４は検索キーの桁数を統一するためのダミー塩基である。同一のプローブから抽出した検索キーには同じ一連番号をつける。
【００１１】
左プローブ先行型についての数式を求める。
本出願の発明では重複区間の塩基数（Ｎ０）、重複区間の不一致個数（Ｎ１）を次のとおり設定する。
【００１２】
【数１】
プローブ塩基数：Ｌ
Ｎ０＞＝Ｌ−２  ＡＮＤ  Ｎ０＜＝Ｌ−１
Ｎ１＝０
【００１３】
図３のとおり、ペア・プローブは同じ２塩基対の先頭位置をそろえて検索する。符号Ａは２塩基対の先頭位置差が１のチャンピオン・ペアという。符号Ｂは２塩基対の先頭位置差が２の次点ペアである。チャンピオン・ペアはペア・プローブの連結に関する信頼性が高いので優先的に抽出する。次点ペアはチャンピオン・ペアが実験エラー等により存在しないとき代替する。
【００１４】
図４において、符号ＡＡは２塩基対を示す。符号○は重複区間の塩基を、●は重複区間外の塩基位置を示す。２塩基対の１６種類を第１キーとし、１６進法で表す。プローブの左端からの２塩基対の先頭位置を半重ねで８つのグループを作り第２キーとする。各グループの中間キー（Ｉ−１、ＩＩ−２、ＶＩ−６等）は左プローブにも右プローブにもなるので、８つの塩基位置をすべてキーに含める。中間キー以外は左または右の２個が重複区間外となる。半重ねにより必要な組み合わせをすべて実現できる。第３キーは８個の塩基列で順位は中央から両端方向に昇順とし、２塩基対の右側から右端までの塩基配列と２塩基対のすぐ左側から順に左端までの塩基配列を連結して作る。検索キーの構成は第１キーが核２塩基対１６進番号（１）、第２キーが８個の先頭位置グループ（１）、第３キーが検索キー文字列（８）、第４キーが一連番号（４）である。（）内は桁数を示す。
【００１５】
【表１】
2004215640.tif 000003
2004215640.tif 000004
【００１６】
第２キーの各グループにおいて左右プローブの２塩基対の先頭番号差は中間キーを含むとき１であり、中間キーを含まないとき２となり、この差が小さなペアほどシークエンシングの信頼性が高いことは前述のとおりである。同じ左プローブ一連番号を共有するペアのうち、先頭位置差が１のペアがチャンピオン・ペアである。
【００１７】
キー配列群すべてを一括してソートする。１６組の２塩基対を核とし、上述のキーを設定し、検索キーのソートを行う。次に検索キーの順序に従って同じ一連番号のプローブを取り出す。上下に並んだプローブについて２塩基対の先頭位置が異なり、両者の重複区間の塩基が完全に一致するペア・プローブを抽出する。
【００１８】
抽出したペア・プローブには左プローブ番号を共有する複数のペア・プローブが含まれるので、左プローブ番号をキーとしてソートした後、キーごとのチャンピオン・ペアを抽出する。チャンピオン・ペアが存在しないとき先頭差が２の次点ペア・プローブを抽出する。
【００１９】
チャンピオン・ペアを抽出するためペア・プローブを抽出するとき、左プローブ番号を第１キーとし、左右プローブ先頭位置の差を第２キーとして差の小さなペア・プローブが左プローブ番号を共有する複数のペア・プローブ群の先頭にくるように設定する。第１キー、第２キーをもとにソートすると、チャンピオン・ペアが常に同一左ペア・グループの先頭にあるので、各グループの先頭ペアのみを抽出すると、ユニークなソート配列ができあがる。
【００２０】
図５のとおり、左プローブ番号とペアをなす右プローブ番号とりだし、つぎに右プローブ番号が左プローブ番号となるペア・プローブをバイナリー検索する。
左右のプローブの重複区間を利用して連結をくり返すと重複配列ができる。この過程で「同一プローブの２回出現」または「相手なしプローブ」が発生する。そのときは入力プローブの初期配列をシャッフルして一連の操作をくり返す。常に最長の完成配列を保存しておき、一定時間経過しても最長配列長が更新されなくなるまでくり返す。表２は重複配列の一部分を示す。最後の行は重複配列から多数決により確定した完成配列を示す。列方向に異なった塩基をもつとき多数決により塩基を確定する。
【００２１】
【表２】
2004215640.tif 000005
【００２２】
図５のとおり符号Ａはチャンピオン・プローブの連結が完了するケースであり、符号Ｂは「ペアリング相手なし」であり、符号Ｃは「同一プローブの２回重複」であり、符号Ｂ、Ｃは連結を中止せざるを得なくなる。符号Ｂ、Ｃを解決するには入力プローブの初期順序をシャッフルすることが必要である。
【００２３】
実験エラーが皆無のとき、第１キーから第３キーまでが完全に一致する検索キーは必ず２組出現する。しかし、実験エラーがあると、２つ以上同じキーがあるケースや、１つしかないケースが存在する。２個以上の同一検索キーが存在するとき、ペア・プローブは第４キーの一連番号順になる。この順序を変更し、正しい組み合わせを行うにはシャッフルが解決策を与える。
【００２４】
【発明の効果】
本出願の発明により、従来、計算資源を長時間使用していたＳＢＨ法を短時間で正確に効率よく探索する方法を提供できる。
【図面の簡単な説明】
【図１】アセンブリングの全体手順を示す図である。
【図２】プローブのペアおよびグループ化の方法を示す図である。
【符号の説明】
符号１：１０個の重複区間で１０個の塩基が一致する。
符号２：９個の重複区間で９個の塩基が一致する。
符号３：８個の重複区間で８個の塩基が一致する。
符号４：左先行型のグループを示す。
符号５：１０個の塩基が完全に一致する。
符号６：右先行型のグループを示す。
【図３】２塩基対をもとに２つのプローブの重複区間の塩基の一致数を示す図である。
【符号の説明】
符号Ａ：２塩基対の先頭位置差が１のチャンピオン・ペアである。
符号Ｂ：２塩基対の先頭位置差が２の次点ペアである。
符号１：同一の２塩基対を示す。
符号２：一致塩基を示す。
符号３：不一致塩基を示す。
符号４：ダミー塩基を示す。
【図４】第２検索キーの作成方法を示す図である。
【符号の説明】
第２キー：２塩基対の先頭位置のグループを示す。
○：第３キーに含まれる重複区間の塩基を示す。
●：第３キーに含まれない重複区間外の塩基を示す。
【図５】左右プローブを連結する方法を示す図である。
【符号の説明】
Ａ：完全に連結が終了する例である。
Ｂ：相手なしのプローブ発生により連結が中止される例である。
Ｃ：同じプローブの２回連結により連結が中止される例である。
【図１】
2004215640.tif 000006
【図２】
2004215640.tif 000007
【図３】
2004215640.tif 000008
【図４】
2004215640.tif 000009
【図５】
2004215640.tif 000010