(57)【要約】  計算機上でペア文字列検索を高速に行うためのインデクス情報のデータ構造を提供し、また、そのインデクス情報を用いて文書中に近接して現れるペア文字列を高速に検索する方法を提供する。  参照文書データのサフィックス・アレイのビットを並べ替えて、局所化可能な、即ち、文書の部分領域に対するインデクスとしても利用可能な、インデクス情報ＬＳＡを作成する。これを利用して、文書全体を初期領域とする領域の二分割処理を繰り返して、クエリー文字列に対するインデクス情報の参照文書データ中の位置を段階的に詳細化し、ペア間の距離を評価して候補を絞り、最終的にペア文字列が近接して出現する位置を確定する。
2010119783.tif 000002
【特許請求の範囲】
【請求項１】
参照文字列を記憶する記憶装置と、
ペアをなす第１の文字列と第２の文字列及び前記第１の文字列と第２の文字列間の距離の上限値を入力する入力装置と、
前記参照文字列のサフィックス・アレイを構築するサフィックス・アレイ構築処理部と、
前記第１の文字列と第２の文字列に対して独立に、前記サフィックス・アレイ内のインデクス領域を計算するインデクス領域検索処理部と、
前記サフィックス・アレイを初期ブロックとして、その最上位ビットが０か１かに従って前記サフィックス・アレイを前記参照文字列の前半と後半の部分領域に対応する２つのブロックに分割し、その際に参照した前記最上位ビットを並べたものをＬＳＡの第一列とし、得られた前記２つのブロックに対して第二位ビットが０か１かに従って更に２つずつのブロックに分割することにより、前記参照ゲノム配列全体を４分割する部分領域に対応する４つのブロックに分割し、その際に参照した前記第二位ビットを並べたものをＬＳＡの第二列とし、以下同様にして前記部分領域の長さが１となるまで処理を繰り返し、その過程でＬＳＡの各列を計算して、局所化可能なインデクス情報ＬＳＡを構築するＬＳＡ構築処理部と、
前記第１の文字列と第２の文字列の各々に対する前記サフィックス・アレイ内のインデクス領域を前記初期ブロック内のインデクス領域として、前記参照文字列の前半と後半の部分領域に対応する２つのブロックへの分割に対応して、前記初期ブロック内のインデクス領域を前記ＬＳＡの第一列の情報を用いてそれぞれのブロック内のインデクス領域に分割し、前記参照文字列全体を４分割する部分領域に対応する４つのブロックへの分割に対応して前記２つのブロック内のインデクス領域を前記ＬＳＡの第二列の情報を用いて前記４つのブロック内のインデクス領域に分割し、以下同様な分割処理を繰り返し、前記初期ブロック内のインデクス領域を、前記参照文字列の部分領域内のインデクス領域に局所化する計算を行うインデクス領域局所化処理部と、
前記部分領域に局所化された前記インデクス領域の前記参照文字列上の位置座標は前記部分領域の長さだけの不確定範囲を残すものとして、前記参照文字列の部分領域に局所化された前記第１の文字列と第２の文字列の前記インデクス領域どうしの距離の上限を評価するインデクス領域間距離評価処理部と、
前記上限値以内の距離でペアをなす前記第１の文字列と第２の文字列の前記参照文字列上の位置を出力する出力装置とを有し、
前記インデクス領域局所化処理部は、前記計算の過程で、空となるインデクス領域の情報、及び、前記インデクス領域間距離評価処理部による評価の結果、前記上限値以下の距離でペアを作れないようなインデクス領域の情報を除去することを特徴とするペア文字列検索システム。
【請求項２】
請求項１に記載のペア文字列検索システムにおいて、前記インデクス領域局所化処理部は、前記ＬＳＡの各列のブロックにランク関数を適用して、当該ブロックが分割された２つのブロックでのインデクス領域の位置を計算することを特徴とするペア文字列検索システム。
【請求項３】
請求項１又は２に記載のペア文字列検索システムにおいて、
前記参照文字列は参照ゲノム配列データであり、
前記ペアをなす第１の文字列と第２の文字列はＤＮＡシーケンサから得られたＤＮＡの第１の塩基配列と第２の塩基配列であることを特徴とするペア文字列検索システム。
【請求項４】
請求項１又は２に記載のペア文字列検索システムにおいて、
前記参照文字列は参照ゲノム配列データであり、
前記ペアをなす第１の文字列と第２の文字列は、ＤＮＡシーケンサから得られたｃＤＮＡの塩基配列を２分割して生成された第１の塩基配列と第２の塩基配列のペアであり、
前記上限値はイントロン長の上限値であり、
前記参照ゲノム配列データ内のスプライス・サイト周辺でコンセンサス配列の検査を行うコンセンサス検査処理部を有し、
前記コンセンサス検査処理部は、前記第１の塩基配列と第２の塩基配列に挟まれた部分をイントロン配列と解釈し、スプライス・サイト周辺にコンセンサス配列が現れないような検索結果を除去することを特徴とするペア文字列検索システム。
【請求項５】
請求項１又は２に記載のペア文字列検索システムにおいて、
蛋白質同定処理部を有し、
前記参照文字列は複数の参照蛋白質配列データであり、
前記ペアをなす第１の文字列と第２の文字列は、質量分析システムから得られた断片化された蛋白質の２つのアミノ酸配列であり、
前記サフィックス・アレイ構築処理部は、前記複数の参照蛋白質配列データ内のアミノ酸配列を区切り文字を介して連結してそのサフィックス・アレイを計算し、
前記蛋白質同定処理部は前記ペアをなす２つのアミノ酸配列を含む蛋白質を同定し、
前記出力装置は、同定された蛋白質の名称と前記ペアをなす２つのアミノ酸配列の出現位置の情報を出力することを特徴とするペア文字列検索システム。
【請求項６】
請求項１又は２に記載のペア文字列検索システムにおいて、
文書同定処理部を有し、
前記参照文字列は複数の文書データを識別可能な区切り文字を介して連結した参照文書データであり、
前記文書同定処理部は、前記ペアをなす第１の文字列と第２の文字列が同一の文書に出現しているかを検査し、
前記出力装置は、前記ペアをなす第１の文字列と第２の文字列が含まれる文書の文書名と前記第１の文字列及び第２の文字列の出現位置の情報を出力することを特徴とするペア文字列検索システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模なゲノム配列データ、又は大量の一般の文書データの中から、近接して現れる二つの文字列を、計算機を利用して高速に検索するための方法に関する。特に、ペア・エンド法を用いて得られた超並列ＤＮＡシーケンサの大量ＤＮＡ配列データに対して、対応するゲノム上の位置を高速に特定するための方法に関する。
【背景技術】
【０００２】
近年、従来型のキャピラリー型ＤＮＡシーケンサとは全く異なる、新しい原理に基づいた超並列ＤＮＡシーケンサが出現した（非特許文献１）。超並列ＤＮＡシーケンサの一回のランでは、一度に数千万本にも及ぶ大量の配列を読み取ることができる。しかし、読取り配列長が数十塩基長程度と比較的短いという短所がある。そこで、その短所を補うためにペア・エンド法が用いられる（非特許文献３）。ペア・エンド法では、ほぼ一定の長さ（百数十塩基から数キロ塩基程度）に揃えられた多数のゲノム配列断片に対して、その両端から数十塩基の部分をシーケンスすることにより、ゲノム上でほぼ一定の間隔だけ離れた塩基配列のペアの情報（ペア・エンド配列）を得ることができる。【０００３】
ゲノムＤＮＡサンプルをシーケンサにより解析して得られたペア・エンド配列データに対して参照ゲノム配列に対するゲノム・マッピング計算を行い、即ち、それらシーケンスして得られた配列が参照ゲノム配列上のどの位置に現れるかの計算を行い、ペアをなす配列の参照ゲノム上のマッピング位置間の距離が期待される間隔だけ離れているかを調べることにより、サンプル・ゲノムと参照ゲノムの間の挿入・欠失などの構造多型を検出できる。即ち、マッピング位置間の距離が期待される間隔より大きければ、サンプル・ゲノム側にはそれらの配列ペア間に欠失が生じていると考えられ、また、逆に、マッピング位置間の距離が期待される間隔より小さければ、サンプル・ゲノム側にはそれらの配列ペア間に挿入が生じていると考えられる（非特許文献３）。【０００４】
シーケンス配列長が短い場合には、ゲノム・マッピング計算において、マッピング位置が一意に定まらず、多数の位置が候補として挙がることがある。そのような場合でも、ペアをなす配列のマッピング位置間隔を制約として用いることにより、即ち、それらのマッピング位置は近接しているという制約を用いることにより、ペア配列としてのマッピング位置を一意に決めるか、或いは、少数の候補に絞り込むことができることが期待できる。  また、転写産物サンプルをシーケンサにより解析して得られたペア・エンド配列データに関しては、ペアをなす配列のマッピング位置の間にイントロンが入り込み、マッピング位置の間隔がイントロン長の分だけ長くなることもある。その場合でも、マッピング位置間の間隔は、ゲノム上の遺伝子領域の長さを超えないという制約を、ペア配列としてのマッピング計算の際に利用することができる。【０００５】
大規模な参照ゲノム配列に対して、大量のシーケンス配列データ（クエリー配列データ）のゲノム・マッピング計算を行う際には、通常、参照ゲノム配列データを予めインデクス化しておく。クエリー配列の検索は、このインデクスを利用することにより、高速化できる。インデクス化の方法として、サフィックス・アレイ（非特許文献２）を利用できる。【０００６】
ペア・エンド法で解析された超並列ＤＮＡシーケンサの大量のペア配列データを参照ゲノム配列上に精度良く高速にマッピングすることが可能なソフトウェアとして、ＭＡＱが知られている（非特許文献６）。ＭＡＱでは、大量のペア配列データに対して予めインデクス情報を作成しておき、参照ゲノム配列上をスキャンしながらインデクス情報を参照してマッピング位置の候補を検索する。ペアをなす２つの配列が距離の制約を満たして近接してマッピングされるという条件を考慮するためには、スキャンの過程では、ゲノム配列のプラス鎖上にマッピングされる位置の候補を各クエリー配列当り最新の２か所まで計算機の記憶領域内に保持し、同時にマイナス鎖上にマッピングされる位置の候補を検索して、見つかったマイナス鎖上のマッピング位置が保持されたプラス鎖上のマッピング位置と距離の制約を満たすペアを作れるか否かを検査する。これにより、ペアをなす２つの配列のマッピング位置の候補の組み合わせの評価を効率的に行っている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Service RF. ”Gene sequencing. The race for the $1000 genome.” Science. 2006 Mar 17;311(5767):1544-6.
【非特許文献２】Manber, U. and Myers, G.: Suffix arrays: A new method for on-line string searches, in 1st ACM-SIAM, Symposium on Discrete Algorithms, pp. 319-327 (1990).
【非特許文献３】Jan O. Korbel, Alexander Eckehart Urban, Jason P. Affourtit, Brian Godwin, Fabian Grubert, Jan Fredrik Simons, Philip M. Kim, Dean Palejev, Nicholas J. Carriero, Lei Du, Bruce E. Taillon, Zhoutao Chen, Andrea Tanzer, A. C. Eugenia Saunders, Jianxiang Chi, Fengtang Yang, Nigel P. Carter, Matthew E. Hurles, Sherman M. Weissman, Timothy T. Harkins, Mark B. Gerstein, Michael Egholm, and Michael Snyder, Paired-End Mapping Reveals Extensive Structural Variation in the Human Genome, Science 19 October 2007: 420-426.
【非特許文献４】Ross Lippert, Space-efficient whole genome comparisons with Burrows-Wheeler transforms, Journal of Computational Biology, 12(4), pp. 407-415, 2005.
【非特許文献５】R. Gonzalez, S. Grabowski, V. Makinen, and G. Navarro. Practical Implementation of Rank and Select Queries. In Proc. WEA'05, pages 27-38, 2005.
【非特許文献６】Heng Li, Jue Ruan and Richard Durbin, Mapping short DNA sequencing reads and calling variants using mapping quality scores. Genome Res. 2008 18: 1851-1858.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ペアをなす２つの配列に対して、指定した間隔以下に近接したマッピング位置を高速に検索する場合は、先ず、各々の配列に対して独立に、インデクスを利用して高速にマッピング位置を求め、次に、それらのマッピング位置の組み合わせの中から、間隔の制約を満たすものを選び出せばよい。しかしながら、配列長が比較的短い場合は、ペアをなす２つの配列に対して、間隔の制約を用いずにそれぞれ独立にマッピング位置を求めると、最初に多数の候補位置が得られ、その後でそれらの中から間隔の制約を満たす少数のものを選び出すことになり、処理速度の低下を招くことがある。一方、サフィックス・アレイなどのインデクスを用いる通常の高速検索方法では、間隔の制約を考慮しながら検索を行うことは困難である。また、ＭＡＱでは、ペアをなす２つの配列のマッピング候補位置が多数あるとき、それらの相対的な位置関係によっては、見落としが生ずる場合もでてくる。【０００９】
本発明の課題は、大規模な参照ゲノム配列データと大量のペア・エンドのシーケンス配列データ（クエリー配列データ）が与えられた時、ペア間のマッピング位置の間隔が予め指定された値以下となるようなペア配列のマッピング位置の組み合わせを高速に求めることである。
【課題を解決するための手段】
【００１０】
ゲノム配列全体に対しては通常のサフィックス・アレイと等価な情報をもち、さらに、種々のスケールで制限されたゲノムの部分領域に対しても、その領域に制限したインデクス情報（局所的なインデクス情報）が得られるような、ゲノム配列データのインデクス化を行う。また、ゲノムの或る領域に対するインデクス情報を、その領域を二分したとき、各々の部分領域に対するインデクス情報に分割する方法を用いる。ペア配列に対しては、先ず、各々の配列に対して独立にゲノム全体領域を検索してインデクス情報を求め、次に、領域の長さが１になるまで二分割を繰り返すことにより、それらのインデクスに対するゲノム上の位置座標を徐々に詳細に決めていく。その過程でペア間の距離の制約を考慮し、制約を満たさないインデクス情報を除去する。【００１１】
本発明によるペア文字列検索システムは、参照文字列を記憶する記憶装置と、ペアをなす第１の文字列と第２の文字列及び第１の文字列と第２の文字列間の距離の上限値を入力する入力装置と、参照文字列のサフィックス・アレイを構築するサフィックス・アレイ構築処理部と、第１の文字列と第２の文字列に対して独立に、サフィックス・アレイ内のインデクス領域を計算するインデクス領域検索処理部と、局所化可能なインデクス情報ＬＳＡを構築するＬＳＡ構築処理部と、インデクス領域局所化処理部と、インデクス領域間距離評価処理部と、上限値以内の距離でペアをなす第１の文字列と第２の文字列の参照文字列上の位置を出力する出力装置とを有し、インデクス領域局所化処理部は、計算の過程で、空となるインデクス領域の情報、及び、インデクス領域間距離評価処理部による評価の結果、上限値以下の距離でペアを作れないようなインデクス領域の情報を除去する。【００１２】
ＬＳＡ構築処理部は、参照文字列のサフィックス・アレイを初期ブロックとして、その最上位ビットが０か１かに従ってサフィックス・アレイを参照文字列の前半と後半の部分領域に対応する２つのブロックに分割し、その際に参照した最上位ビットを並べたものをＬＳＡの第一列とし、得られた２つのブロックに対して第二位ビットが０か１かに従って更に２つずつのブロックに分割することにより、参照ゲノム配列全体を４分割する部分領域に対応する４つのブロックに分割し、その際に参照した第二位ビットを並べたものをＬＳＡの第二列とし、以下同様にして部分領域の長さが１となるまで処理を繰り返し、その過程でＬＳＡの各列を計算してＬＳＡを構築する。【００１３】
インデクス領域局所化処理部は、第１の文字列と第２の文字列の各々に対するサフィックス・アレイ内のインデクス領域を初期ブロック内のインデクス領域として、参照文字列の前半と後半の部分領域に対応する２つのブロックへの分割に対応して、初期ブロック内のインデクス領域をＬＳＡの第一列の情報を用いてそれぞれのブロック内のインデクス領域に分割し、参照文字列全体を４分割する部分領域に対応する４つのブロックへの分割に対応して２つのブロック内のインデクス領域をＬＳＡの第二列の情報を用いて４つのブロック内のインデクス領域に分割し、以下同様な分割処理を繰り返し、初期ブロック内のインデクス領域を、参照文字列の部分領域内のインデクス領域に局所化する計算を行う。インデクス領域局所化処理部は、ＬＳＡの各列のブロックにランク関数を適用して、当該ブロックが分割された２つのブロックでのインデクス領域の位置を計算する。【００１４】
インデクス領域間距離評価処理部は、部分領域に局所化されたインデクス領域の参照文字列上の位置座標は部分領域の長さだけの不確定範囲を残すものとして、参照文字列の部分領域に局所化された第１の文字列と第２の文字列のインデクス領域どうしの距離の上限を評価する。
【発明の効果】
【００１５】
本発明では、部分領域に対するインデクス情報は、領域分割により位置座標を詳細化する過程で、ペア間の距離制約を満たさないものが除去されていくため、マッピング位置の間隔の制約を考慮しながら高速にインデクス検索（マッピング計算）を行うことが可能になる。
【図面の簡単な説明】
【００１６】
【図１】ペア配列のゲノム・マッピング計算を行うシステムの構成例を示す図である。
【図２】領域分割に伴いインデクス情報を分割する方法を説明するための図である。
【図３】ＬＳＡ（localized suffix array）の説明図である。
【図４】インデクス領域どうしの距離の評価方法の説明図である。
【図５】インデクス領域の局所化の過程を説明する図である。
【図６】ＬＳＡの構築方法を説明するためのフローチャートである。
【図７】ＬＳＡの構築方法の説明図である。
【図８】ＬＳＡの構築の具体例を説明する図である。
【図９】ＬＳＡの構築の具体例をビットレベルで詳細に説明するための図である。
【図１０】インデクス領域局所化処理の処理手順を説明するフローチャートである。
【図１１】インデクス領域のリストの更新方法を説明するフローチャートである。
【図１２】スプライシングを含むゲノム・マッピング計算を行うシステムの構成例を示す図である。
【図１３】アミノ酸配列断片から蛋白質を同定するシステムの構成例を示す図である。
【図１４】一般の文書データから二つの文字列が近接して現れるような文書を同定する計算を行うシステムの構成例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施例を、図面を用いて詳細に説明する。
【００１８】
［実施例１］
本実施例では、参照ゲノム配列データと、クエリー配列のペアが与えられた時、指定された間隔以下に近接したマッピング位置を求めるための方法を説明する。本実施例では、クエリー配列とゲノム配列の間のマッピングは完全一致の場合を考えるが、数塩基のミスマッチを許容するような不完全一致の場合への応用は、容易な類推により可能である。また、本実施例では、ペア配列のマッピング位置の間隔の上限のみの制約を考えるが、同時にペア配列のマッピング位置の間隔の下限の制約を考えることも、容易な類推により可能である。
【００１９】
図１は、本実施例のペア配列のマッピング計算を行うシステムの構成例を示す図である。１０１は、このシステムが稼働している計算機であり、外部記憶装置１０２に格納された参照ゲノム配列データ１０３を読み込み、またＤＮＡシーケンサ１１６を用いてＤＮＡサンプル１１５を解析して得られたペア配列データ（クエリー配列のペア）１０７を、入力装置１０６を介して読み込み、また、ユーザにより指定されたパラメータ１１４（ペア間距離の上限値Ｄ）を、入力装置１１８を介して読み込む。計算機１０１は、サフィックス・アレイ構築処理部１０５で、参照ゲノム配列データ１０３内の塩基配列を区切り文字＄を介して連結して、そのサフィックス・アレイを計算し主記憶１０４内に記憶する。主記憶１０４内には、同様に、他の処理部の計算結果も記憶され、その内容は必要に応じて各処理部から参照される。ＬＳＡ構築処理部１０８は、サフィックス・アレイを基に、インデクス情報ＬＳＡ（localized suffix array）を構築する。インデクス領域検索処理部１０９は、ペアをなすクエリー配列のそれぞれに対して独立に、サフィックス・アレイを検索して、インデクス領域の情報を得る。インデクス領域局所化処理部１１０では、クエリー配列のインデクス領域の情報と参照ゲノム配列のＬＳＡをもとにして、ペア間のマッピング位置間隔の制約を満たすようなインデクス領域を局所化（細分化）していき、インデクス領域のゲノム上の位置を、初期のゲノム全体に広がった状態から最終的に塩基レベルで詳細に確定した状態まで詳細化していく。
【００２０】
これにより最終的に、ペア配列のマッピング位置が得られる。ペア間のマッピング位置間隔の制約の成否を調べるために、異なるインデクス領域間のゲノム上の位置の距離が、インデクス領域間距離評価処理部１１７で評価される。出力処理部１１１は、ペア配列のマッピング位置情報（検索結果１１３）を出力装置１１２に出力する。ペア配列のマッピング位置情報（検索結果１１３）は、染色体名とその向き（＋／−何れのストランドか）と出現位置を示す座標の情報を含んでいる。
【００２１】
参照ゲノム配列からサフィックス・アレイを構築するには、Manber-Myersなどの公知の方法を利用すればよい（非特許文献２）。また、クエリー配列のインデクス情報、即ち、サフィックス・アレイ内においてクエリー配列がサフィックスのプレフィックスとして現れるインデクスの範囲を求めるためには、一般的な二分探索法を用いればよい。
【００２２】
図２は、領域の分割に際して、インデクス情報を分割する方法を説明するための説明図である。この方法は、後述するようにインデクス領域局所化処理部１１０を構成するために用いられる。ここでは、説明を容易にするため、ゲノムの長さは２のべき乗（２のｈ乗）マイナス１であると仮定する。ゲノムの長さがそれ以外の一般の場合への拡張は、容易な類推により可能である。クエリー配列と同一の配列が、２０１で示すゲノム配列上に、２０２で示すように多数散在して出現しているとする。このとき、ゲノム配列全体の領域に対するサフィックス・アレイＢ（２０３）上では、サフィックス・アレイの性質により、それら散在した多数の出現位置に対応するインデクスが、２０４に示すように一か所にまとまって現れる。ゲノムの長さを２のｈ乗マイナス１と仮定したので、各々のサフィックスの位置は０以上、２のｈ乗未満の整数で表わされる。空文字列は最終サフィックスとする。ゲノムの前半に対応するサフィックスのインデクスは、二進表記したとき最上位ビット（最下位からｈビット目）が０の整数で表わされ、また、ゲノムの後半に対応するサフィックスのインデクスは、二進表記したとき最上位ビット（最下位からｈビット目）が１の整数で表わされる。そこで、ゲノム全体の領域に対するサフィックス・アレイＢを、内部の相対的な順序を保ったまま、最上位ビットが０か１かにより二分すると、ゲノム前半に対応するサフィックス・アレイの部分列Ｂ０と、ゲノム後半に対応するサフィックス・アレイの部分列Ｂ１が得られる。ゲノム配列全体を二分することにより、クエリー配列と同一の配列は、ゲノム配列前半２０５上とゲノム配列後半２０７上に、それぞれ２０６と２０８で示すように多数散在して出現するが、それらのインデクスは、２１０と２１２で示すように、それぞれＢ０とＢ１内に一か所にまとまって現れる。
【００２３】
ゲノム全体の領域に対するサフィックス・アレイＢにおいて、先頭行を０行目として、クエリー配列に対応するインデクス領域２０４の先頭行をｓ行目、最終行の次の行をｔ行目とする。同様に、ゲノム前半の領域に対するサフィックス・アレイＢ０において、クエリー配列に対応するインデクス領域２１０の先頭行をｓ０行目、最終行の次の行をｔ０行目とし、また、ゲノム後半の領域に対するサフィックス・アレイＢ１において、クエリー配列に対応するインデクス領域２１２の先頭行をｓ１行目、最終行の次の行をｔ１行目とする。ゲノム全体の領域に対するサフィックス・アレイＢの最上位ビット列Ｌにおいて、ｓ行目より前にある０の個数はランク関数rank(Ｌ，ｓ，０)で表わされ、また、ｓ行目より前にある１の個数はランク関数rank(Ｌ，ｓ，１)で表わされ、
ｓ０＝rank(Ｌ，ｓ，０)
ｓ１＝rank(Ｌ，ｓ，１)
となる。ランク関数は公知の方法で高速に計算することができる（非特許文献５）。同様に、
ｔ０＝rank(Ｌ，ｔ，０)
ｔ１＝rank(Ｌ，ｔ，１)
となる。従って、インデクスの最上位ビットによるゲノム全体領域の二分割に際して、クエリー配列に対応するインデクスの範囲（ｓ，ｔ）のゲノム前半とゲノム後半に対応する部分への分割（ｓ０，ｔ０），（ｓ１，ｔ１）は高速に計算される。なお、分割されたうちの一方は空になることもある。
【００２４】
ゲノムの前半と後半のそれぞれに対しても、インデクスの上位から２ビット目（最下位からｈ−１ビット目）の値が０か１かを調べることにより、同様な二分割を行うことができ、それによりゲノム全体は四分割される。続けて、８分割、１６分割なども可能で、最終的には領域の長さが１に達するまで、再帰的に分割を繰り返すことができる。
【００２５】
このようなゲノム領域の再帰的な分割に伴うインデクス領域の分割の計算に必要な、サフィックスのインデクスのビットを並べたものをＬＳＡ（localized suffix array）とよぶ。図３はｈ＝３のときのＬＳＡを説明するための図である。３０１はＬＳＡ全体を表し、３０２は、最初の二分割でゲノム全体の領域を前半と後半の２つの領域に分割する際に参照したＢ内のインデクスの最上位ビットを並べたものである。３０３は、次の４分割において、すなわち、上の２つの領域の二分割において、Ｂ０、Ｂ１内で参照されたインデクスの上位から２ビット目のビットを並べたものである。同様に、３０４は次の８分割において、４分割後の各領域から参照されたインデクスの上位から３ビット目のビットを上下に並べたものである。ｈ＞３のときは、１６分割以降に対しても、同様に４列目以降が構成される。
【００２６】
以上のようなゲノム全体の領域の再帰的な分割の過程で得られる部分領域をブロックとよぶことにする。ブロックの中には、クエリー配列に対応するインデクスの範囲を有するものも有しないものもある。ブロック内のインデクス領域に含まれるインデクスのゲノム上の位置はそのブロック内に限定されるため、インデクス領域のゲノム上の位置座標はブロックの長さに対応する不確定さを残して確定する。従って、そのようなインデクス領域どうしのゲノム上での距離（間隔）を、不確定さを残しつつ評価することが可能になる。
【００２７】
図４は、インデクス領域間距離評価処理部１１７において、異なるブロック内に含まれるインデクス領域どうしのゲノム上の距離の評価方法を説明する図である。後述するように、この評価方法は、インデクス領域局所化処理部１１０を構成する際に用いられる。４０１はブロックを表す。二つのクエリー配列ｐ、ｑに対するインデクス領域４０２，４０３が異なるブロック４０４，４０５に含まれているとする。それらのインデクス領域のゲノム上の位置座標は、４０６，４０７に示すような不確定範囲を残して確定している。また、ブロックの長さは、ゲノムの全長と分割回数に基づき計算される。従って、それらのインデクス領域の間の距離の上限４０９と下限４０８は、ブロック４０４とブロック４０５の間にあるブロックの数を数えることにより計算できる。
【００２８】
（距離の下限）＝（間にあるブロックの数）×（ブロック長）＋１
（距離の上限）＝（（間にあるブロックの数）＋２）×（ブロック長）−１
最終の分割でブロック長が１になると、これらの値は一致する。即ち、不確定さを残さずに、インデクスのゲノム上の位置座標が確定する。
【００２９】
図５は、２つのクエリー配列ｐ、ｑに対するゲノム全体でのインデクス領域が与えられとき、インデクス領域局所化処理部１１０において、ペア配列としてのゲノム配列上の位置座標が、ゲノム領域の分割を再帰的に繰り返すことにより、不確定さを減少させながら、確定していくようすを説明する図である。５０１はゲノム全体の領域（初期ブロック）に対するサフィックス・アレイである。５０２は、ゲノム全体を２分割したときの前半と後半のブロックに対応するサフィックス・アレイの部分列である。５０３は、ゲノム全体を４分割したときの各ブロックに対応するサフィックス・アレイの部分列を上下に並べたものである。同様に、５０４，５０５は、ゲノム全体をそれぞれ８分割、１６分割したときの、各ブロックに対応するサフィックス・アレイの部分列を上下に並べたものである。５０６は、最終的にブロック長が１に達したときのものである。５０１〜５０６の間をつなぐ実線の矢印は、クエリー配列ｐに対するインデクス領域が再帰的な局所化処理（ブロックの細分化処理）により詳細化される様子を示す。
【００３０】
同様に、５０１〜５０６の間をつなぐ破線の矢印は、クエリー配列ｑに対するインデクス領域が局所化処理により詳細化される様子を示す。その過程で、５０７や５０８，５０９に示すように、ペア配列間の距離の制約を満たさないものは、処理を打ち切られる。ペア配列間の距離の制約を満たさないものの中には、５０９のようにペア配列の順序が逆になったものも含まれる。最終的に５０６上まで残った５１０や５１１がペア配列のマッピング位置を与える。
【００３１】
図６に、ＬＳＡの構築処理手順を示す。ステップ６０１では、ブロックＢを、サフィックス・アレイ構築処理部１０５で計算され、主記憶１０４内に記憶されている、参照ゲノム配列全体に対するサフィックス・アレイとする。これまで同様、説明を容易にするため、参照ゲノム配列長は２のｈ乗マイナス１であると仮定する。Ｂはインデクス（ｈビットの整数）を２のｈ乗個並べた配列である。ステップ６０３でｉ＝１として以下の処理を繰り返す。ステップ６０４はその終了判定処理である。ステップ６０５では、０と１からなる長さ（ｉ−１）の文字列ａにより、Ｂａと表わされる各ブロックに対して、ステップ６０６，６０７の処理を行う。ステップ６０６では、ブロックＢａ内に含まれる各インデクス（ｈビットの整数）に対して、それらの上位からｉビット目を並べてできるビット列をＬａとする。ステップ６０７では、それらのビットが０であるか１であるかに従い、Ｂａ内に含まれる各インデクスを、ブロックＢａ０又はＢａ１に分類する。その際、インデクス間の相対順序は保つ。そのような全てのＢａに対して処理が完了したら、ステップ６０８でｉの値を１だけ増やしてステップ６０４の直前に戻る。ステップ６０５で終了条件が成立したら、ステップ６０９でＬａからＬＳＡを主記憶１０４上に構築する。
【００３２】
図７は、ＬａからＬＳＡを構築する方法の説明図である。ＬＳＡ７０１は、２のｈ乗行、ｈ列にビットを並べたものである。その第１列７０２はＬに等しい。その第２列７０３は、Ｌ０とＬ１をつないだものである。その第３列７０４は、Ｌ００，Ｌ０１，Ｌ１０，Ｌ１１をつないだものである。第４列７０５は、Ｌ０００，Ｌ００１，Ｌ０１０，Ｌ０１１，Ｌ１００，Ｌ１０１，Ｌ１１０，Ｌ１１１をつないだものである。第５列以降も同様である。
【００３３】
ゲノム配列は実際には塩基を表す文字Ａ，Ｃ，Ｇ，Ｔ，Ｎからなるが、本発明による方法は一般のアルファベットからなる文字列に対して適用可能である。図８は、ｈ＝３で、参照ゲノム配列を“ａｂｒａｃａｄ”としたときにＬＳＡを構築する例を説明する図である。８０１は、“ａｂｒａｃａｄ”の全てのサフィックスとそのインデクスのリスト（空文字列を含む）である。８０２は、それらを辞書式順番にソートしたもので、サフィックス・アレイである。８０３は、サフィックス・アレイのインデクスの値を２進表記したものであり、ゲノム全体に対応するＢである。８０４は、図６で説明した方法でＢから構築したＬＳＡであり、図７に対応する。
【００３４】
図９は、参照ゲノム配列を“ａｂｒａｃａｄ”としたときに、図６で説明した方法に従って、ゲノム全体に対応するＢからＬＳＡを構築する過程を説明するための説明図である。９０１は、ゲノム全体に対応するＢである。９０２は、ゲノムの前半と後半に対応するＢ０とＢ１を破線で区切って並べたものである。ＢからＢ０とＢ１への分割に際しては、Ｂの最上位ビット（太字）を参照する。これらのビットを並べたものがＬ０であり、９０５で示すＬＳＡの第１列目となっている。同様に、９０３は、ゲノムの４分割に対応するＢ００，Ｂ０１，Ｂ１０，Ｂ１１を破線で区切って並べたものである。Ｂ０とＢ１からＢ００，Ｂ０１，Ｂ１０，Ｂ１１への分割に際しては、Ｂ０とＢ１の上から２番目のビット（太字）を参照する。それらのビットを並べたものがＬ０とＬ１であり、９０５で示すＬＳＡの第２列目となっている。同様に、９０４は、ゲノムの８分割に対応するＢ０００，Ｂ００１，Ｂ０１０，Ｂ０１１，Ｂ１００，Ｂ１０１，Ｂ１１０，Ｂ１１１を破線で区切って並べたものである。Ｂ００，Ｂ０１，Ｂ１０，Ｂ１１からこれら８個への分割に際しては、Ｂ００，Ｂ０１，Ｂ１０，Ｂ１１の上から３番目のビット（太字）を参照する。それらのビットを並べたものがＬ００，Ｌ０１，Ｌ１０，Ｌ１１であり、９０５で示すＬＳＡの第３列目となっている。９０４においてブロック長は１となり、ここで再帰的な分割は終了する。従って、９０５に示す８行３列のビット行列がＬＳＡである。
【００３５】
図１０は、インデクス領域局所化処理１１０の内部の処理の流れを説明する図である。ステップ１００１でユーザから入力装置１０６を介して距離の上限値Ｄを読み込み、ステップ１００２でゲノム配列全体のサフィックス・アレイＢ内におけるクエリー配列ｐの出現範囲（ｓp，ｔp）とクエリー配列ｑの出現範囲（ｓq，ｔq）を主記憶１０４内から読み込む。Ｂはサフィックス・アレイ構築処理部１０５で既に構築済みであり、（ｓp，ｔp）と（ｓq，ｔq）の値はインデクス領域検索部１０９で計算済みであり、これらは主記憶１０４内に保持されている。ステップ１００３では、クエリー配列ｐのマッピング位置の候補リスト示す情報List(ｐ)と、クエリー配列ｑのマッピング位置の候補リスト示す情報List(ｑ)を、次式に示すように初期化する。
【００３６】
List(ｐ)＝｛（Ｂ，ｓp，ｔp）｝，
List(ｑ)＝｛（Ｂ，ｓq，ｔq）｝
これらのリストは、マッピング位置座標を詳細に決めていくために、以下の反復処理により更新される。ステップ１００４は、この反復処理の終了判定処理であり、ブロック長が１になったら終了と判定する。ステップ１００５では、図１１を用いて以下に説明する方法に従い、リストList(ｐ)に属する各要素を細分化してリストList(ｐ)を更新し、同様にList(ｑ)に属する各要素を細分化してリストList(ｑ)を更新する。
【００３７】
図４を用いて説明したように、各クエリー配列のインデクス領域のマッピング位置は、ブロック長だけの不確定さを残して確定し、それに基づいて、異なるブロックに属するインデクス領域のマッピング位置どうしの距離の上限や下限を評価できる。ステップ１００６では、リストList(ｐ)とList(ｑ)の要素を組み合わせて評価し、ペア間の距離の上限がＤ以下となるようなペアを作れないような、リストList(ｐ)とList(ｑ)の要素を削除する。リストList(ｐ)とList(ｑ)の要素の組み合わせを考える際には、それらの要素をマッピング位置の順にソートしておくと効率的である。反復処理が終了したとき、ステップ１００７においてリストList(ｐ)とList(ｑ)を回答として、主記憶１０４内に返す。
【００３８】
図１１は、クエリー配列のマッピング位置の候補リスト示す情報List_inを更新して新しいリストList_outを回答するリストの細分化処理１００５の処理手順を説明する図である。この処理手順は、図２を用いて説明した方法と同様な方法である。ステップ１１０１で、リストList_inを入力し、リストList_outを空リストとする。List_inは、ステップ１００５の細分化される前のList(ｐ)又はList(ｑ)である。ステップ１１０２では、リストList_inの各要素（Ｂａ，ｓ，ｔ）に対して以下の処理を行う。ここで、ａは０と１からなる文字列を表し、ｓとｔはクエリー配列のブロックＢａ内のインデクス領域を示す整数である。ステップ１１０３では、次式に従い、細分化されたブロックＢａ０とＢａ１内のインデクス領域を示す整数であるｓ０，ｔ０，ｓ１，ｔ１を計算する。
【００３９】
ｓ０＝rank(Ｌａ，ｓ，０)
ｔ０＝rank(Ｌａ，ｔ，０)
ｓ１＝rank(Ｌａ，ｓ，１)
ｔ１＝rank(Ｌａ，ｔ，１)
ここで、rank(Ｌａ，ｓ，０)はランク関数で、ＬＳＡ内のビット列Ｌａにおいて、ｓ行目の位置より前に現れる０の個数を表し、また、rank(Ｌａ，ｓ，１)もランク関数で、ＬＳＡ内のビット列Ｌａにおいて、ｓ行目の位置より前に現れる１の個数を表す。ランク関数は公知の方法で効率的に計算できる（非特許文献５）。rank(Ｌａ，ｔ，０)とrank(Ｌａ，ｔ，１)についても同様である。ステップ１１０４では、ＬＳＡ内の対応するビット列Ｌａ内の各ビットが０か１かに応じて、（Ｂａ，ｓ，ｔ）を２つのブロック（Ｂａ０，ｓ０，ｔ０）と（Ｂａ１，ｓ１，ｔ１）に分割して、これらをリストList_outに追加する。ステップ１１０５では、得られたリストList_outを回答として、主記憶１０４内に返す。これは、ステップ１００５の細分化された後のList(ｐ)又はList(ｑ)となる。
【００４０】
本発明では、クエリー配列に対する多数のマッピング位置候補が各ブロック内のインデクス領域（二つの整数ｓとｔ）としてコンパクトに表現される。また、ブロックの分割とそれに伴うインデクス領域の分割を繰り返し行うことにより、インデクス領域のマッピング位置を、不確定範囲を徐々に減少させながら、最終的に塩基レベルまで詳細に決められる。その際、不確定範囲を残したマッピング位置間の距離の上限を評価して、ペア間で指定されたマッピング位置の間隔の制約（距離Ｄ以下）を満たし得ないようなマッピング位置に対するインデクス情報を除去して、無駄な計算を避ける。また、ＬＳＡを参照することにより、ブロック分割に伴うインデクス領域の分割は効率的に計算される。ＬＳＡを効率的に構築する処理手順も与えた。
【００４１】
以上により、大規模な参照ゲノム配列データと大量のペア・エンドのシーケンス配列データ（クエリー配列データ）が与えられた時、ペア間のマッピング位置の間隔が予め指定された値以下となるようなペア配列のマッピング位置の組み合わせを高速に求めることが可能となる。
【００４２】
［実施例２］
前記実施例では、ペア・エンド法で得られたクエリー配列のゲノム・マッピングの計算法を示したが、スプライシングを受けたｍＲＮＡから作られたｃＤＮＡ配列の断片配列をシーケンシングして得られたクエリー配列のゲノム・マッピング計算する問題に対しても本発明を実施することができる。
【００４３】
図１２は、本実施例のスプライシングを含むマッピング計算を行うシステムの構成例を示す図である。１２０１は、このシステムが稼働している計算機であり、外部記憶装置１２０２に格納された参照ゲノム配列データ１２０３を読み込み、また、ＤＮＡシーケンサ１２１７を用いてｃＤＮＡサンプル１２１６を解析して得られたクエリー配列データ１２０７を、入力装置１２０６を介して読み込み、また、ユーザにより指定されたパラメータ１２１９（イントロン長の上限値Ｄ）を、入力装置１２１８を介して読み込む。計算機１２０１は、サフィックス・アレイ構築処理部１２０５で、参照ゲノム配列データ１２０３内の塩基配列を区切り文字＄を介して連結して、そのサフィックス・アレイを計算し主記憶１２０４内に記憶する。主記憶１２０４内には、同様に、他の処理部の計算結果も記憶され、その内容は必要に応じて各処理部から参照される。
【００４４】
ＬＳＡ構築処理部１２０８は、サフィックス・アレイを基に、新たなインデクス情報ＬＳＡ（localized suffix array）を構築する。ペア配列生成処理部１２０９は、クエリー配列を種々の位置で二分割して種々のペア配列を作成する。インデクス領域検索処理部１２１０は、ペア配列のそれぞれに対して独立に、サフィックス・アレイを検索して、インデクス情報を得る。インデクス領域局所化処理部１２１１では、ペア配列のインデクス情報と参照ゲノム配列のＬＳＡをもとにして、ペア間のマッピング位置間隔がイントロン長上限値以下となる制約を満たすようなインデクスに対応する座標を、ゲノム全体から徐々に局所化しながら決めていく。これにより、ペア配列としてのマッピング位置が得られる。
【００４５】
コンセンサス配列検査処理部１２１２では、スプライス・サイト周辺のゲノム配列を調べて、コンセンサスを満たさないようなマッピング結果を除去する。出力処理部１２１３は、マッピング位置情報（検索結果１２１５）を出力装置１２１４に出力する。スプライシングを受けた配列のマッピング情報（検索結果１２１５）は、染色体名とその向き（＋／−何れのストランドか）と分断された二つの出現位置を示す座標の情報を含んでいる。
【００４６】
サフィックス・アレイ構築処理部１２０５、ＬＳＡ構築処理部１２０８、インデクス領域検索処理部１２１０、インデクス領域局所化処理部１２１１等の処理内容は、実施例１と同様である。ペア配列生成処理部１２０９では、分割して得られるペア配列の配列長の下限値を予め指定しておいて、その条件を満たすペア配列を全て生成する。それらはペア配列データとして、インデクス領域検索処理部１２１０、インデクス領域局所化処理部１２１１で処理されるが、コンセンサス配列検査処理部１２１２で、スプライシングを受けたマッピングとして解釈され検査される。スプライス・サイト周辺のゲノム配列のコンセンサスとしては、ペア配列としてのゲノム・マッピング位置にはさまれた部分をイントロン配列と解釈して、イントロン配列がＧＴで始まりＡＧで終わるという条件を課す。この条件を満たさないペア配列のマッピング結果は除去される。
【００４７】
大規模な参照ゲノム配列データとｃＤＮＡをシーケンスした大量のクエリー配列データが与えられた時、前記実施例で示した、ペア間のマッピング位置の間隔が予め指定された値以下となるようなペア配列のマッピング位置の組み合わせを高速に求める方法を上記のようにして利用することにより、妥当な長さのイントロン配列長（例えば、数百キロ塩基以下）をもつスプライシングを含むゲノム・マッピングを高速に計算することが可能となる。
【００４８】
［実施例３］
前記実施例では、Ａ，Ｃ，Ｇ，Ｔ，Ｎからなる塩基配列データに対する実施例を説明した。本発明は、塩基配列データとは限らない一般の文字列データに対しても適用可能である。ここでは、アミノ酸断片配列データに対する実施例を説明する。アミノ酸配列は、２０種類程のアミノ酸からなる配列である。
【００４９】
図１３に、本実施例のアミノ酸断片配列から蛋白質を同定する計算を行うシステムの構成例を示す図である。１３０１は、このシステムが稼働している計算機であり、外部記憶装置１３０２に格納された参照蛋白質配列データ１３０３を読み込み、また、質量分析システム１３０５を用いて蛋白質サンプル１３０６を解析して得られた複数のクエリー配列データ１３０７を、入力装置１３０８を介して読み込み、また、ユーザにより指定されたパラメータ１３１８（蛋白質配列長の上限値Ｄ）を、入力装置１３１９を介して読み込む。計算機１３０１は、サフィックス・アレイ構築処理部１３１０で、参照蛋白質配列データ１３０３内のアミノ酸配列を区切り文字＄を介して連結して、そのサフィックス・アレイを計算し主記憶１３０９内に記憶する。主記憶１３０９内には、同様に、他の処理部の計算結果も記憶され、その内容は必要に応じて各処理部から参照される。
【００５０】
ＬＳＡ構築処理部１３１１は、サフィックス・アレイを基にインデクス情報ＬＳＡ（localized suffix array）を構築する。インデクス領域検索処理部１３１２は、クエリー配列のそれぞれに対して独立に、サフィックス・アレイを検索して、インデクス情報を得る。インデクス領域局所化処理部１３１３では、クエリー配列のインデクス情報と参照ゲノム配列のＬＳＡをもとにして、参照蛋白質配列データ１３０３内に近接して現れるようなインデクスの出現位置を、参照蛋白質配列データ全体から徐々に局所化しながら決めていく。これにより、クエリー配列の集団としての参照蛋白質配列データ中の出現位置が得られる。蛋白質同定処理部１３１４では、クエリー配列の参照蛋白質配列データ中の出現位置に基づきクエリー配列を含む蛋白質を同定し、複数のクエリー配列を含むような蛋白質を同定する。出力処理部１３１５では、同定された蛋白質の名称とクエリー配列の出現位置（断片位置）の情報を含む検索結果１３１７を出力装置１３１６に出力する。
【００５１】
サフィックス・アレイ構築処理部１３１０、ＬＳＡ構築処理部１３１１、インデクス領域検索処理部１３１２、インデクス領域局所化処理部１３１３等における処理内容は、前記実施例と同様である。
【００５２】
大規模な参照蛋白質配列データと蛋白質サンプルを質量分析システムで解析して得られた大量のクエリー配列データ（アミノ酸配列データ）が与えられた時、前記実施例で示した、ペア間のマッピング位置の間隔が予め指定された値以下となるようなペア配列のマッピング位置の組み合わせを高速に求める方法を上記のようにして利用することにより、互いに近接して現れるようなクエリー配列の参照蛋白質配列データ中の出現位置が求まり、さらに、それらのクエリー配列の出現位置を複数含むような信頼性の高い蛋白質を高速に同定することが可能となる。
【００５３】
［実施例４］
前記実施例では、塩基配列やアミノ酸配列などの生物学的な配列データを扱ってきたが、本発明は、一般の文書データへの適用も可能である。
【００５４】
図１４に、本実施例の一般の文書データの中から二つの検索文字列が近接して現れるような文書を同定する計算を行うシステムの構成例を示す図である。１４０１は、このシステムが稼働している計算機であり、外部記憶装置１４０２に格納された参照文書データ１４０３を読み込み、また、検索文字列のペア（クエリー）１４０７を、入力装置１４０６を介して読み込み、また、ユーザにより指定されたパラメータ１４１１（ペア間距離の上限値Ｄ）を、入力装置１４１６を介して読み込む。本実施例では、参照文書データ１４０３は、文書名を付けられた文字列本文からなる文書の集まりと仮定するが、階層的な構造をもつ一般の構造化文書に対しても、容易な類推により本発明を適用することができる。
【００５５】
計算機１４０１は、サフィックス・アレイ構築処理部１４０５で、文書データ１４０３内の文字列を識別可能な区切り文字を介して連結して、そのサフィックス・アレイを計算し主記憶１４０４内に記憶する。主記憶１４０４内には、同様に、他の処理部の計算結果も記憶され、その内容は必要に応じて各処理部から参照される。ＬＳＡ構築処理部１４０８は、サフィックス・アレイを基にインデクス情報ＬＳＡ（localized suffix array）を構築する。インデクス領域検索処理部１４０９は、検索文字列のそれぞれに対して独立に、サフィックス・アレイを検索して、インデクス情報を得る。インデクス領域局所化処理部１４１０では、検索文字列のインデクス情報と文書データのＬＳＡをもとにして、文書データ１４０３内に近接して現れるようなインデクスに対する文書中の出現位置を、文書全体から徐々に局所化しながら決めていく。これにより、検索文字列ペアとしての文書中の出現位置が得られる。文書同定処理部１４１２では、二つの検索文字列が文書データ内の同一の文書に出現しているかを検査する。出力処理部１４１３では、二つの検索文字列が近接して出現するような文書の文書名と各々の検索文字列の出現位置の情報を含む検索結果１４１５を出力装置１４１４に出力する。
【００５６】
サフィックス・アレイ構築処理部１４０５、ＬＳＡ構築処理部１４０８、インデクス領域検索部１４０９、インデクス領域局所化処理部１４１０等の処理内容は、前記実施例と同様である。
【００５７】
大規模な文書データと大量の検索文字列ペアが与えられた時、前記実施例で示した、ペア間の出現位置の間隔が予め指定された値以下となるような文字列ペアの出現位置の組み合わせを高速に求める方法を上記のようにして利用することにより、互いに近接して現れるような検索文字列の文書データ中の出現位置が求まり、それらが出現する文書を高速に同定することが可能となる。
【符号の説明】
【００５８】
２０１  参照ゲノム配列
２０２  クエリー配列と同一の配列が参照ゲノム配列上に出現する位置
２０４  参照ゲノム全体に対するサフィックス・アレイ内で、クエリー配列に対応するインデクス領域
２０５  参照ゲノムの前半の配列
２０６  クエリー配列と同一の配列が参照ゲノムの前半の配列上に出現する位置
２０７  参照ゲノムの後半の配列
２０８  クエリー配列と同一の配列が参照ゲノムの後半の配列上に出現する位置
２１０  参照ゲノムの前半に対するサフィックス・アレイ内で、クエリー配列に対応するインデクス領域
２１２  参照ゲノムの後半に対するサフィックス・アレイ内で、クエリー配列に対応するインデクス領域
【図１】
2010119783.tif 000003
【図２】
2010119783.tif 000004
【図３】
2010119783.tif 000005
【図４】
2010119783.tif 000006
【図５】
2010119783.tif 000007
【図６】
2010119783.tif 000008
【図７】
2010119783.tif 000009
【図８】
2010119783.tif 000010
【図９】
2010119783.tif 000011
【図１０】
2010119783.tif 000012
【図１１】
2010119783.tif 000013
【図１２】
2010119783.tif 000014
【図１３】
2010119783.tif 000015
【図１４】
2010119783.tif 000016
【国際調査報告】
2010119783.tif 000017
2010119783.tif 000018
2010119783.tif 000019
2010119783.tif 000020