(57)【要約】【課題】本発明は、反復配列を含むゲノム配列決定の際に既知反復配列データベースを用いることなく、全ゲノムショットガン法による断片配列データから正しい併合と誤った併合および本質的に正誤が判断できない併合を分類し実用的なコンティグを作成することを目的とする。【解決手段】各断片配列が他の断片配列に近似的に包含されるか検査し、どの断片配列にも包含されない断片配列ｘおよびその相補配列について、併合を行った際に該断片配列を３’方向へ延長可能な別の断片配列またはその相補配列の中から、断片配列ｘとの間に共有される部分断片配列から計算されるスコアに基づいて断片配列ｘを３’方向へ延長する断片配列またはその部分を決定する。【選択図】図１
2005218421.tif 000002
【特許請求の範囲】
【請求項１】
全ゲノムショットガン方式によって獲得されたランダムなＤＮＡ断片の塩基配列情報を含むデータ集合に対して（ａ）各断片配列が他の断片配列に近似的に包含されるか検査し（ｂ）どの断片配列にも包含されない断片配列ｘおよびその相補配列について、併合を行った際に該断片配列を３’方向へ延長可能な別の断片配列またはその相補配列の中から、断片配列ｘとの間に共有される部分断片配列から計算されるアラインメントスコアに基づいて、断片配列ｘを３’方向へ延長する断片配列またはその部分を決定する方法。
【請求項２】
（ｂ）のアラインメントスコアに代えて相同部分の長さに比例するスコアを用いる請求項１に記載の方法。
【請求項３】
請求項１又は請求項２に記載の方法で、各断片配列ｘに対し、断片配列ｘを３’方向へ延長する断片配列の中で潜在的な共有配列長が長い断片配列から順にスコアの計算処理を行う方法。
【請求項４】
断片配列中に出現する連続または非連続の部分塩基配列とその断片配列先頭からの部分塩基配列の位置の両方を同時に索引として断片配列の集合に関連付けるハッシュテーブルを有するデータが記録されたコンピュータ読み取り可能な記録媒体。
【請求項５】
請求項１から３のうちいずれか一項記載の方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明はゲノム塩基配列決定方法の領域に関し、より詳細には全ゲノムショットガン法によるＤＮＡ断片の配列を含むデータ集合からコンティグを作成するための方法及び記録媒体に関する。
【背景技術】
【０００２】  ゲノム塩基配列決定のために全ゲノムショットガン法が広く使われている。全ショットガン法ではまずゲノムを物理的に細かい断片に分断し、得られた断片をランダムにクローニングし、得られた各クローンについて塩基配列を決定する。このようにして得られた断片配列はゲノム配列中でランダムな位置の塩基配列を含む。次に、断片配列同士で共有される配列を検出し、配列を共有する断片配列を併合しコンティグを作り、元のゲノム塩基配列またはその一部を復元する。【０００３】  しかしながら、ゲノム配列は多数の反復配列を含むことがあり、共通する配列を持っている断片配列を無秩序に併合していくと矛盾が発生することがある。そこでゲノム配列中に反復配列が存在しても矛盾を生じないような断片配列の併合の方法が必要であった。【０００４】  非特許文献１においてＭｙｅｒｓらは、既知の反復配列についてのデータベースを用いて既知の反復配列と相同性を持つ断片配列中の反復配列をマスクし、マスクされている領域をアラインメントしないことで誤った配列併合を行わないようにする手法を提案している。また、その際には反復配列と非反復配列の境界すなわち反復配列境界を検出し、境界をまたぐ断片配列の併合を禁止する方法を併用し、矛盾を生じない断片配列の併合を行っている。【０００５】  非特許文献２のＢａｔｚｏｇｌｏｕらのグループは、反復配列境界の検出とともに、対で重なりを持つメイトペアを優先的に併合することにより、反復配列による誤った併合を削減する方法を考案している。【０００６】  非特許文献３においてＷａｎｇらのグループは断片配列中に現れるｋ−ｍｅｒ（ｋ文字の塩基配列）の出現頻度を求めて一定以上の出現頻度があるｋ−ｍｅｒに関しては反復配列由来のものであると見なし、反復配列由来であるとされたｋ−ｍｅｒを断片配列中でマスクし、マスクされた領域にアラインメントスコアを与えないことで誤った併合を削減する方法を提案している。【０００７】
【非特許文献１】Ｅｕｇｅｎｅ  Ｗ．Ｍｙｅｒｓ，  Ｇｒａｎｇｅｒ  Ｇ．Ｓｕｔｔｏｎ  ｅｔ  ａｌ，Ａ  Ｗｈｏｌｅ  Ｇｅｎｏｍｅ  Ａｓｓｅｍｂｌｙ  ｏｆ  Ｄｒｏｓｏｐｈｉｌａ，Ｓｃｉｅｎｃｅ誌（２０００年）（２８７）２１９６−２２０４ページ
【非特許文献２】Ｓｅｒａｆｉｍ  Ｂａｔｚｏｇｌｏｕ  ｅｔ  ａｌ，ＡＲＡＣＨＮＥ：Ａ  Ｗｈｏｌｅ−Ｇｅｎｏｍｅ  Ｓｈｏｔｇｕｎ  Ａｓｓｅｍｂｌｅｒ，Ｇｅｎｏｍｅ  Ｒｅｓｅａｒｃｈ誌２００２年１月号（１）：１７７−１８９ページ
【非特許文献３】Ｊｕｎ  Ｗａｎｇ  ｅｔ  ａｌ，Ａ  Ｓｅｑｕｅｎｃｅ  Ａｓｓｅｍｂｌｅｒ  Ｔｈａｔ  Ｍａｓｋｓ  Ｅｘａｃｔ  Ｒｅｐｅａｔｓ  Ｉｄｅｎｔｉｆｉｅｄ  ｆｒｏｍ  ｔｈｅ  Ｓｈｏｔｇｕｎ  Ｄａｔａ，  Ｇｅｎｏｍｅ  Ｒｅｓｅａｒｃｈ誌２００２年３月号（５）：８２４−８３１ページ
【発明の開示】
【発明が解決しようとする課題】
【０００８】  しかしながら反復配列をマスクする方法は反復配列が既知でなくては適用できない。新しくゲノム配列を決定する生物については、その生物に存在する反復配列は未知であり既知の反復配列についてのデータベースは存在しないことも多い。また、既知の反復配列についてのデータベースが整備されている生物種においても、その反復配列データベースがゲノム配列の一部を決定した結果に基づいて作られているために、反復配列全てではなく一部分の反復配列のみがデータベースに含まれているのが普通であり、データベースに記載されていない反復配列が誤った断片併合を引き起こすことがあった。【０００９】  断片配列中に出現するｋ−ｍｅｒの頻度を用いて反復配列をマスクする方法は反復配列データベースを必要としない。しかしながら非特許文献３に述べられているようにゲノム中に出現する回数が非常に高い反復配列に対しては高い確率でマスクを行うことができるものの比較的出現回数が少ない反復配列に関して判定を誤ることがしばしばあり、誤った断片併合を引き起こすことがあった。【００１０】  また、反復配列境界を検出する方法も、反復配列が高頻度に散在しているゲノム配列に対して適用するのが難しかった。反復配列境界が高頻度で出現することによって、断片配列がほとんど併合されず、結果としてコンティグの数が非常に多くなり実用的ではないからである。また、低頻度でゲノム中に現れる反復配列に対しても本質的に可能な併合をも抑制してしまいコンティグの数を増やしてしまうことがあった。【００１１】  非特許文獸１のＭｙｅｒｓの場合には反復配列をマスクする方法によって高頻度に散在する反復配列をマスクし、マスクされずに残存する反復配列を低頻度に抑えたうえで反復配列境界を検出する方法を用いることで対処しているが、反復配列データベースを必要とする。【００１２】  非特許文献２のＢａｔｚｏｇｌｏｕらのグループは、対で重なりを持つメイトペアを優先的に併合することによって高頻度な反復配列の影響を低減しているが、非特許文献２で述べられているようにメイトペア対のどちらか片方が非反復配列を含んでいないときには誤った併合を行う可能性があるなど効果は限定的であると考えられる。【００１３】  高等な生物は高頻度な散在反復配列を含むゲノム配列を持っていることが多いために、これらの生物についてゲノム配列を決定する際には、既知の反復配列についてのデータベースを必要とせず、高頻度に散在する反復配列がゲノム配列中に存在しても誤った併合を行わずにコンティグを作成することが求められていた。
【課題を解決するための手段】
【００１４】  全ゲノムショットガン方式によって獲得されたランダムなＤＮＡ断片の塩基配列情報を含むデータ集合を元に、各断片配列が他の断片配列に近似的に包含されるか検査し、どの断片配列にも包含されない断片配列ｘおよびその相補配列について、併合を行った際に該断片配列を３’方向へ延長可能な別の断片配列またはその相補配列の中から、断片配列ｘとの間に共有される部分断片配列から計算されるアラインメントスコアに基づいて、断片配列ｘを３’方向へ延長する断片配列またはその部分を決定する方法により課題が解決される。【００１５】  より好ましくは前記のアラインメントスコアに代えて相同部分の長さに比例するスコアを用いる。【００１６】  より好ましくは各断片配列ｘに対し、断片配列ｘを３’方向へ延長する断片配列の中で潜在的な共有配列長が長い断片配列から順にスコアの計算処理を行う方法によって処理速度を向上させることができる。【００１７】  より好ましくは断片配列中に出現する連続または非連続の部分塩基配列とその断片配列先頭からの部分塩基配列の位置の両方を同時に索引として断片配列の集合に関連付けるハッシュテーブルを有するデータが記録されたコンピュータ読み取り可能な記録媒体を用いることで必要な潜在的共有配列長の断片配列を求めるのに必要な時間を削減することができる。
【発明の効果】
【００１８】  本発明は既知の反復配列についてのデータベースの有無および反復配列のゲノム中での出現回数の大小および反復配列のゲノム中での分布にかかわらず、ａ）反復配列に因る誤りの併合ｂ）誤りでない併合ｃ）断片配列情報からでは本質的にどちらとも特定できない併合の３種類を分類することができ、それにより誤りの少ないコンティグを生成できる。
【発明を実施するための最良の形態】
【００１９】  以下に添付図面を参照して、この発明の一実施形態を示す。【００２０】［定義］
「リード」とは、ゲノムからランダムな位置に由来するＤＮＡ配列情報の短い配列を意味する。リードの配列は５’末端から３’末端への方向を持った配列とし、５’側を先頭とする。【００２１】  「相補リード」あるいは、ある２つのリード同士が「相補」の関係にあるとは、それらがＤＮＡの二重鎖の関係にあることである。【００２２】  本実施例で用いられる全てのリードに対して一意な「リード番号」を振る。相補の関係にあるリード同士は何らかの方法により各々を一意に識別できることが望ましく、本実施例ではその一つの方法としてリード番号の差が入力リード数に等しいとき、２本のリードは互いに相補となるようにリード番号を定めた。【００２３】  塩基配列中の連続した部分塩基配列または非連続な部分塩基配列を「シード」とよぶ。【００２４】  ２つのリードが「重複」するとは、２つのリード配列がアラインする部分配列を有し、そのアラインする部分配列はいずれかのリードの末端で終結していることである。アラインする部分配列は完全な一致でなくともよく、処理ごとに与えられる相違度のパラメータによってアラインしているか否かが判断される。【００２５】  ある２つのリードをｘとｙとし、この２つのリードｘ、ｙが重複する場合、以下の５つの状態が考えられる。【００２６】  図２に示すように、ｘの５’末端よりｙの５’末端が内側（３’側）にあり、ｘの３’末端よりｙの３’末端が外側（３’側）にある状態。この状態にあるとき、「ｘの（３’方向の）重複先はｙである」とよぶ。【００２７】  図３に示すように、ｘの５’末端よりｙの５’末端が外側（５’側）にあり、ｘの３’末端よりｙの３’末端が内側（５’側）にある状態。この状態はｘとｙのそれぞれの相補リードｘｃ、ｙｃからみると、ｘｃの５’末端よりｙｃの５’末端が内側（３’側）にあり、ｘｃの３’末端よりｙｃの３’末端が外側（３’側）にある状態であるので、「ｘｃの重複先はｙｃである」とよぶこととする。【００２８】  図４に示すように、ｘの５’末端よりｙの５’末端が内側（３’側）にあり、ｘの３’末端よりｙの３’末端が内側（５’側）にある状態。このとき、２つのリードの５’末端３’末端のいずれか一方のみが一致している場合もこの状態に含める。この状態にあるとき、「ｘはｙを包含している」あるいは「ｙはｚに包含される」とよび、ｘをｙの「親リード」、ｙをｘの「子リード」とよぶ。すなわち親リードは子リードを含む。【００２９】  図５に示すように、ｘの５’末端よりｙの５’末端が外側（５’側）にあり、ｘの３’末端よりｙの３’末端が外側（３’側）にある状態。このとき、２つのリードの５’末端３’末端のいずれか一方のみが一致している場合もこの状態に含める。この状態にあるとき、「ｙはｘを包含している」あるいは「ｘはｙに包含される」とよび、ｙをｘの「親リード」、ｘをｙの「子リード」とよぶ。【００３０】  図６に示すように、ｘの５’末端とｙの５’末端が一致し、かつｘの３’末端とｙの３’末端も一致するような状態。このような状態も上で述べた「包含」の一種とし、リード番号が小さい方のリードを親リード、大きい方のリードを子リードとすることとする。【００３１】  上記の包含関係については、それ��れの相補リードについても等しい関係が一般的に成り立つ。「ｘがｙを包含する」場合、「ｘｃもｙｃを包含する」。ただし、相補リード間のリード番号の振り方によっては図６のようなリード同士が一致する場合に必ずしもそうならないことがあるが、本実施例のリード番号の振り方はこの関係が成り立つようになっている。【００３２】［ハッシュテーブルの構築］
全ゲノムショットガン法によって獲得された、各リードに対してリード番号を振る。各リードに対して、前記リード配列中のシード配列と、そのシード配列のリード配列における先頭からの位置を同時に索引として、該部分塩基配列を前記の位置に保持するリード配列のリード番号の集合が取得できるハッシュテーブルを構築する。説明のために簡略化した図を図７に示す。このとき、位置はリードの先頭（５’側）から数える。前記シード配列の長さは６から１４塩基であることが望ましい。前記ハッシュテーブルは配列構造を用いて実現されることがより好ましい。【００３３】［高頻度反復配列の排除］
ゲノム配列中に普遍的に高頻度で出現すると予想されるような配列については、ハッシュテーブルにリード番号を追加しないようにする。実施例の一つとしては、例えば「ＡＡＡＡＡＡＡＡＡＡ」や「ＡＴＡＴＡＴＡＴＡＴ」などの１塩基、２塩基、３塩基から成る単純反復配列であるようなシード配列についてはハッシュテーブルからリード番号を除外する方法が考えられるが、各部分塩基配列が断片配列中に現れる頻度を実際に求めて、一定以上の頻度で現れる部分塩基配列についてリード番号をハッシュテーブルから排除するなどの他の実施方法も考えられる。【００３４】  まず検査対象のリードを一つ選びａとする。この検査対象配列は全てのリードにわたって反復される。変数ｗを１に初期化し、ａに対し３’方向へｗ塩基分ずれてａの重複先となるようなリードの候補をハッシュテーブルから検索する。具体的にはａ中のｗ＋１塩基目以降に存在するシード配列についてａ中に現れる位置よりｗだけ５’方向へ位置を移動した位置に該シード配列が出現するようなリードのリード番号の集合を求める。【００３５】［シードを核としたアラインメントの精緻化］
求めた各リード番号が示すリードをｂとする。図８で示すように、このｂに対してａとｂの間に共有されているシード群を核として５’および３’両方向についてアラインメントを精緻化する。このステップはスミス＝ウォーターマン法やその拡張などの動的計画法により行われるのが望ましいがスパース動的計画法などで実施しても構わない。【００３６】［複数シードによる処理の絞り込み］
上記のステップの単純な実行方法として単一のシードをアラインメントの核とする方法がある。このような方法の場合、ゲノム配列中の反復領域中に核となるシード配列を選択してしまった場合は、実際は有為なアラインメントを持たないリードの組についての処理も行ってしまうこととなる。これを避け、処理の効率を上げるために単一のシードではなく複数のシードをまとめるという方法も考えられる。この複数のシードをまとめる方法の一つとしては、シードが各々のリード中に出現している位置座標の差が、それらのリードの重複のずれを近似していると考えることも出来るので、図９で示すようにその各リードでの出現位置の差によってシードをまとめるという方法も考えられる。【００３７】  前述したステップによるｂの選び方により、多くの場合においてａとｂの関係は「ａの重複先はｂ」という関係か、「ａがｂを包含する」関係であるが、逆の２つの関係となることもある。【００３８】［重複先の評価］
あるリードｘの（３’方向の）重複先がリードｙであったとする。このようなリードｙは、一つのｘに対して複数存在しうる。また一つも存在しないこともある。このような複数の重複先に対して、それぞれの「重複先としての良さ」を評価する尺度を設け、それを計算する。このような尺度としては、リードｘとｙの重複の共有配列長や、ｘとｙのアラインメントスコアなどが考えられる。【００３９】［最良の重複先の選択］
前記のステップにより、あるリードａに対する重複先ｂが得られた場合、リードａの重複先がｂしか存在していない場合は、そのリードｂをリードａの現時点での最良の重複先とする。ａに対する重複先ｂを得た時点で、それまでの最良の重複先ｃがすでに存在している場合は、ａとｂとの重複と、ａとｃとの重複を上記の尺度に従って比較し、より良い重複の方をこの時点のａの最良の重複先とする。【００４０】［包含されたリードの除外］
アラインメントの精緻化によって「リードａがリードｂを包含する」あるいは「リードｂがリードａを包含する」という状況となった場合は、以降のステップでは「包含された」リードは、その「包含された」リードの重複先は計算せず、また重複先としても直接は採用しないので、「包含された」リードには、これを表現する情報を付加する。【００４１】［潜在的共有配列長］
また、図１０が示すように、上記の方法ではリードａの先頭より約ｗ塩基分ずれたアラインメントを持つと近似的に予想されるリード番号をハッシュテーブルにより得ていることとなり、このようなアラインメントは、およそ「ａの配列長−ｗ」という長さの共有配列を持つと予想される。これをアラインメントを取る２つのリードの「潜在的共有配列長」とよぶ。【００４２】［得られる重複の良さの推定］
ｗを１から開始することにより、ａに対する潜在的共有配列長が長いリード群から順に処理を行う。したがって、この処理の継続によって現時点での最良の重複先よりも良い重複先が得られるか判定を行う。例えば、重複の比較尺度としてアラインメントの共有配列長を用いている場合には、潜在的共有配列長がこのアラインメントの正確な共有配列長の近似となっていると考えることができ、処理の継続に従って、処理の対象となるリードのリードａとの潜在的共有配列長は単調に短くなっていくので、これ以降処理を継続しても現時点での最良の重複先よりも良い重複先が得られないと判断することが出来る。具体的には潜在的共有配列長×（１＋誤り許容率）×アラインメントマッチスコアまたは１（前記尺度に共有配列長を採用したとき）が現時点の最良の重複先についてのスコアを下回った時に、これ以上良い重複先は無いと判定する。誤り許容率は対象ゲノム中に予想されるポリモルフィズムの割合の上限値の見積もりを予め与えておく。【００４３】［反復の終了］
これ以上処理を継続しても現時点の最良の重複先よりも良い重複先は得られないだろうと判断された場合は、ｗについての処理ループを終了する。これによって、不要な計算処理を省略することが出来る。【００４４】  重複先がまだ得られていない場合あるいは処理を継続することでより良い重複先が得られる可能性があると判断された場合は、ｗを増加させて上記のステップを反復する。このとき、ｗの増分としては、ハッシュテーブルの構築の際に用いたシードの配列長が好ましいが、得られている現時点の最良の重複のアラインメントによって増分を変更することが考えられる。【００４５】  またリードａ自体が「包含されるリード」であると判定された場合は、重複先を得る必要がないので、すぐにａについてのステップを終了し、次の検索対象配列を新しいａとしてステップを反復する。【００４６】［真の親リード、真の子リード］
上記のステップによっても「包含されたリード」であると判定されなかったリードは、一度も「子リード」であると判定されなかったリードである。このようなリードを「真の親リード」とよぶ。また一度以上「子リード」であると判定されたリードは「真の子リード」とよぶ。【００４７】［包含関係の計算］
次に、上記のステップにより真の子リードであると判定されたものについて、そのリードを包含する真の親リードを計算する処理を行う。【００４８】  このステップは、上記の重複先を検索するステップとほぼ同様な処理を行うが、検査対象配列はすでに真の子リードのみとし、ハッシュテーブルを検索して得られたリード番号の集合が示すアラインメント対象のリードは、真の親リードのみとする。【００４９】  このステップでは、真の親リードと真の子リードの関係を示すデータ構造を前述のステップと同様の処理によって計算するが、このステップでは１つの「自分を包含する真の親リード」を発見した時点で反復を終了せず、全ての「自分を包含する真の親リード」を発見するまで処理を継続する。【００５０】  このステップにより、ある真の子リードをｃとすると、ｃは１つ以上の「ｃの真の親リード」の情報を持ち、ある真の親リードをｐとすると、ｐは「真の子リードを持たない」か［１つ以上の真の子リード」の情報を持つ。【００５１】  以上のようにして、各真の親リードであるリードに対して、真の親リードの重複先をそれが存在する場合には決定する。【００５２】［真の子リードへの重複の対処］
図１１に示すように、各真の親リードであるリードに対して、真の親リードの重複先が存在しないが、真の子リードが重複先として存在する場合、図１２で示すようにアラインメントの精緻化の処理のパラメータを緩和し、検査対象配列に対して途中からアラインメントするような真の親リードとの重なり合いを計算するステップを行い、そのようなアラインメントの中で最も良い重複を持つ真の親リードの、該検査対象リードと共有している部分を重複先の配列とする。【００５３】  以上の処理によって、全ての真の親リードおよびその相補配列について図１２のように１個あるいは０個の３’方向の重複先配列が決定される。これは、各配列を点とし、３’方向の重複先を示す関係を辺とした有向グラフであると見ることができる。【００５４】［相補配列についてのグラフの統合］
図１に示すように、各配列について相補配列の情報と統合することによって各塩基配列の３’方向および５’方向の両方の重複関係を示すグラフを導く。この統合において、ある配列ｊの３’方向の重複先が配列ｋであり、ｋの相補配列の３’方向の重複先がｊの相補配列であったような場合は、ｊとｋを結ぶ辺は１つに併合される。【００５５】［参照数の計算］
上記の処理により構築されたグラフについて、塩基配列に相当する各点が３’方向および５’方向のそれぞれについて、いくつの辺を保持しているかを計算する。３’方向および５’方向の少なくとも片方に２つ以上の辺を持つ点は「分岐点」とよぶ。【００５６】［３’方向の併合検査］
図１３に示すように、この統合後のグラフにおいて、以下のステップで未到達かつ分岐点ではない任意の点を起点として、その３’方向についての辺を辿り、分岐点でない部分までを１つの連続した組とする。【００５７】［５’方向の併合検査］
また、図１４に示すように上記と同様の処理を５’方向についても行う。このとき、分岐点については分岐点の５’方向および３’方向のそれぞれの辺の本数によりこの処理の組に併合するかが決定される。分岐点から見て２本以上の辺がある方向からの処理の場合は、分岐点はその組に含めない。【００５８】［真の子リードの復元］
以上のステップにより、真の親リードあるいはその部分配列を、グラフ上で分岐のない部分ごとの組に分けることが出来る。短い反復配列に対しては図１６のようなグラフが生成され、上下の２種類のリード群が混じることは無い。長い反復配列に対しては図１７のようなグラフが生成され、上下の２種類のリードが分岐点を通して接続される。分岐点が生じる場合には分岐点の位置において併合が行えない。たとえば図１７の例においては配列Ａと配列Ｃがたとえ逆であったとしても、ショットガン法により得られる断片配列は同一になる可能性があり曖昧性が生じている。以上のステップにより得られた配列の組はグラフの辺、重複関係による列を構成している。この配列の列に対して以前の処理で真の子リードと判定されたリードについても、その真の親リードが単一であるが、あるいは真の親リードの全てが同じ組に分類され隣り合った配列である場合のみ、図１５のようにこの配列の組に加える。【００５９】  上記のステップにより分けられた配列の組は、それらが持っている位置を表す情報を用いることによって５’方向から３’方向へと整列させることが出来、それらをマルチプルアラインメントすることによりコンティグ列を生成する。
【図面の簡単な説明】
【００６０】
【００６１】
【図１】リードの分岐を示すグラフ構造を表す図である。
【図２】リードｘからリードｙに重複している状態を表す図である。
【図３】リードｙからリードｘに重複している状態を表す図である。
【図４】リードｘがリードｙを包含する状態を表す図である。
【図５】リードｙがリードｘを包含する状態を表す図である。
【図６】リードｘがリードｙと等しい状態を表す図である。
【図７】シード配列と配列内位置を索引とするハッシュテーブルを表す図である。
【図８】リードａとリードｂの核によるアラインメントの精緻化を表す図である。
【図９】シード群の分類を表す図である。
【図１０】潜在的強雨配列長を表す図である。
【図１１】真の子リードへの重複状態および真の親リードへの重複の検出を表す図である。
【図１２】リードの重複関係のグラフを表す図である。
【図１３】起点から３’方向への処理を表す図である。
【図１４】起点から５’方向への処理を表す図である。
【図１５】真の子リードの復元を表す図である。
【図１６】短い反復配列を超える正しい重複先が決定される例。
【図１７】長い反復配列があり本質的に曖昧性がある例。
【図１】
2005218421.tif 000003
【図２】
2005218421.tif 000004
【図３】
2005218421.tif 000005
【図４】
2005218421.tif 000006
【図５】
2005218421.tif 000007
【図６】
2005218421.tif 000008
【図７】
2005218421.tif 000009
【図８】
2005218421.tif 000010
【図９】
2005218421.tif 000011
【図１０】
2005218421.tif 000012
【図１１】
2005218421.tif 000013
【図１２】
2005218421.tif 000014
【図１３】
2005218421.tif 000015
【図１４】
2005218421.tif 000016
【図１５】
2005218421.tif 000017
【図１６】
2005218421.tif 000018
【図１７】
2005218421.tif 000019