(57)【特許請求の範囲】
【請求項１】
旧ゲノム配列と呼ぶ第１のゲノム配列と、新ゲノム配列と呼ぶ第２のゲノム配列と、リード配列と呼ぶ多数のＤＮＡ配列と、前記リード配列を前記旧ゲノム配列にマッピングした結果を記憶する記憶装置と、
前記新ゲノム配列に存在する任意の文字列を探索するためのインデックスを構築する新ゲノムインデックス構築部と、
前記リード配列に存在する前記旧ゲノム配列に対する変異であって、前記旧ゲノム配列上での処理位置の近傍にある変異の組合せを記録したクエリ表と呼ぶデータ構造を、マッピングの前記結果に基づいて構築するクエリ表更新部と、
前記クエリ表に格納されている変異の組合せを前記旧ゲノム配列に適用して構築した配列を前記新ゲノム配列と比較し、前記構築した配列のうちＫ（１以上の自然数）塩基以上が前記新ゲノム配列と完全に一致する箇所を網羅的に出力するマッピング先探索部と
を有するＤＮＡ配列解析装置。
【請求項２】
請求項１に記載のＤＮＡ配列解析装置において、
前記新ゲノムインデックス構築部は、
前記インデックスとして、
FM-indexと、
接尾辞配列において隣り合う数値に対応する接尾辞を比較したときに一致する最長の接頭辞の長さが前記Ｋを超える位置で１、それ以外の箇所で０となるビットベクトルと
を構築することを特徴とするＤＮＡ配列解析装置。
【請求項３】
請求項１に記載のＤＮＡ配列解析装置において、
前記クエリ表更新部は、
Ｌ（１以上の自然数）塩基以内の範囲の変異のアリルの組合せであって、前記リード配列と前記新ゲノム配列の両方に存在するアリルの組合せを前記クエリ表に格納する
ことを特徴とするＤＮＡ配列解析装置。
【請求項４】
請求項２に記載のＤＮＡ配列解析装置において、
前記マッピング先探索部は、
前記ビットベクトルを使用して、前記リード配列のアリルを前記旧ゲノム配列に反映させた配列が、前記新ゲノム配列とＫ塩基以上完全に一致する前記新ゲノム配列上の位置を探索する
ことを特徴とするＤＮＡ配列解析装置。
【請求項５】
旧ゲノム配列と呼ぶ第１のゲノム配列と、新ゲノム配列と呼ぶ第２のゲノム配列と、リード配列と呼ぶ多数のＤＮＡ配列と、前記リード配列を前記旧ゲノム配列にマッピングした結果を記憶する記憶装置と、
前記新ゲノム配列に存在する任意の文字列を探索するためのインデックスを構築する新ゲノムインデックス構築部と、
前記リード配列に存在する前記旧ゲノム配列に対する変異であって、前記旧ゲノム配列上での処理位置の近傍にある変異の組合せを記録したクエリ表と呼ぶデータ構造を、マッピングの前記結果に基づいて構築するクエリ表更新部と、
前記クエリ表に格納されている変異の組合せを前記旧ゲノム配列に適用して構築した配列を前記新ゲノム配列と比較し、前記構築した配列のうちＫ（１以上の自然数）塩基以上が前記新ゲノム配列と完全に一致する箇所を網羅的に出力するマッピング先探索部と、
前記リード配列に出現する変異の内容と位置を対応付けて表示する第１の領域と、前記変異の組合せと、対応するクエリ配列が前記新ゲノム配列上で存在する長さと、対応する前記クエリ配列が前記インデックスに存在する範囲を対応付けて表示する第２の領域とを含む確認画面を表示するユーザインタフェース部と
を有するＤＮＡ配列解析システム。
【請求項６】
請求項５に記載のＤＮＡ配列解析システムにおいて、
前記ユーザインタフェース部は、前記クエリ配列に対応する１又は複数本の直線を、前記旧ゲノム配列に対応する第１の軸に対して平行に表示すると共に、前記直線における前記クエリ表に表示された各変異の位置毎に、前記クエリ配列の変異の内容を表示する
ことを特徴とするＤＮＡ配列解析システム。
【請求項７】
ＤＮＡ配列解析装置が、
処理内容に応じ、旧ゲノム配列と呼ぶ第１のゲノム配列と、新ゲノム配列と呼ぶ第２のゲノム配列と、リード配列と呼ぶ多数のＤＮＡ配列と、前記リード配列を前記旧ゲノム配列にマッピングした結果の一部又は全てを記憶装置から読み出す処理と、
前記新ゲノム配列に存在する任意の文字列を探索するためのインデックスを構築する処理と、
前記リード配列に存在する前記旧ゲノム配列に対する変異であって、前記旧ゲノム配列上での処理位置の近傍にある変異の組合せを記録したクエリ表と呼ぶデータ構造を、マッピングの前記結果に基づいて構築する処理と、
前記クエリ表に格納されている変異の組合せを前記旧ゲノム配列に適用して構築した配列を前記新ゲノム配列と比較し、前記構築した配列のうちＫ（１以上の自然数）塩基以上が前記新ゲノム配列と完全に一致する箇所を網羅的に出力する処理と
を実行するＤＮＡ配列解析方法。
【請求項８】
請求項７に記載のＤＮＡ配列解析方法において、
前記ＤＮＡ配列解析装置が、
前記リード配列に出現する変異の内容と位置を対応付けて表示する第１の領域と、前記変異の組合せと、対応するクエリ配列が前記新ゲノム配列上で存在する長さと、対応する前記クエリ配列が前記インデックスに存在する範囲を対応付けて表示する第２の領域とを含む確認画面を表示する処理を更に実行する
ことを特徴とするＤＮＡ配列解析方法。
【請求項９】
請求項８に記載のＤＮＡ配列解析方法において、
前記ＤＮＡ配列解析装置が、
前記クエリ配列に対応する１又は複数本の直線を、前記旧ゲノム配列に対応する第１の軸に対して平行に表示すると共に、前記直線における前記クエリ表に表示された各変異の位置毎に、前記クエリ配列の変異の内容を表示する処理を更に実行する
ことを特徴とするＤＮＡ配列解析方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＤＮＡ配列解析装置、ＤＮＡ配列解析方法及びＤＮＡ配列解析システムに関する。
【背景技術】
【０００２】
次世代シーケンサによるＤＮＡ配列決定手法（Next Generation Sequencing, NGS）は、サンガー法（従来）に比べ、劇的に低いコストでゲノム配列を決定することができる。例えば2001年に約１億米ドルであったゲノム配列の決定コストは、次世代シーケンサの登場により、2015年には1,245米ドルにまで下がっている(“DNA Sequencing Costs, http://www.genome.gov/sequencingcosts/”参照)。次世代シーケンサは、コストを安くできるだけでなく、短期間で膨大な量の配列データを得ることができる。例えば、一度に１兆塩基を超える膨大な配列データを生成することができる次世代シーケンサも製品化されている。こうした技術により、多数の被験者の個々のゲノム配列を決定することが可能となった。
【０００３】
次世代シーケンサを用いてヒトのゲノム配列を解析する場合、次世代シーケンサによって得られた配列（以下「リード配列」という。）を、ヒトの標準的なゲノム配列である参照ゲノム配列と比較することが必要となる。リード配列と参照ゲノム配列を比較して、リード配列に対応する参照ゲノム配列の位置を特定し、参照ゲノム配列との違いを明らかにする計算処理を「マッピング」という。マッピングにより、被験者のゲノムに特有の配列が明らかになり、その被験者がもつ遺伝子の特徴が分かる。こうして得られた遺伝子の情報は、その被験者の疾患リスクや薬剤応答性を予測する上で極めて有用である。
【０００４】
マッピングは、次世代シーケンサで配列データを処理する上で不可欠であるため、配列データを公共機関のデータベースで公開する際に、ゲノムにマッピングされた結果が公開される場合がある。一方で、近年では、次世代シーケンサで扱う配列データの量が膨大となり問題となっている。そこで、リード配列を参照ゲノム配列にマッピングした結果を使用して参照ゲノム配列との差分だけを記録し、リード配列を圧縮する技術も出現している(Fritz et al., Genome Res. 2011, 21(5):734-40)。
【０００５】
また、参照ゲノム配列にマッピングするリード配列の量が膨大であるため、リード配列をマッピングする処理は、計算機上で配列データを解析する上での主要なボトルネックとなっている。そこで、当該解析処理を計算機上で効率よく実行するための技術が多数開発されている（例えば、非特許文献１）。これらの技術は、与えられたリード配列を、参照ゲノム配列と直接比較する手法を採用する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Li and Durbin 2009, Bioinformatics 2009; 25(14): 1754-1760.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前述したように、参照ゲノム配列にリード配列をマッピングした結果が提供されているが、参照ゲノム配列は唯一の固定された配列ではない。実際、ヒトのゲノム配列には、配列決定が困難な部分（例えば、非常に長い繰返し配列）がある。このため、参照ゲノム配列として完全な配列を提供することは容易でなく、現在でも参照ゲノム配列の改善が続けられている。
【０００８】
また前述したように、昨今では、次世代シーケンサによって多数の個人のゲノム配列を解析できるようになっているが、個人毎のゲノム配列は参照ゲノム配列とは異なる配列である。このため今後は、様々な参照ゲノム配列を扱わなければならないと予想される。これに伴い、今後は、ある参照ゲノム配列にマッピングされたリード配列を、別の参照ゲノム配列にマッピングし直す必要性が生じると予想され、当該マッピング処理を効率化するための仕組みも必要になると考えられる。
【０００９】
しかし、前述の非特許文献１には、ある参照ゲノム配列（以下「旧ゲノム配列」という。）にリード配列が既にマッピングされている場合に、そのマッピング結果を用いて、別の参照ゲノム配列（以下「新ゲノム配列」という。）に効率よくマッピングするための仕組みは提供されていない。
【００１０】
当然のことながら、新旧２つの参照ゲノム配列が一致する領域であれば、既に存在するマッピング結果をそのまま新しい参照ゲノム配列のマッピング結果とすることが考えられる。ところが、新ゲノム配列に、新旧２つの参照ゲノム配列の間で一致する配列と同一の配列が新たに挿入されている場合、リード配列のマッピング先を、旧ゲノム配列に存在していた配列とするべきか、新たに挿入された配列とするべきかを一意に特定することはできない。すなわち、元のマッピング結果をそのまま使えないという問題がある。
【００１１】
そこで、本発明は、旧ゲノム配列にマッピングされた膨大な数のリード配列を、旧ゲノム配列へのマッピング結果を利用して、旧ゲノム配列とは異なる新ゲノム配列に効率よくマッピングするための技術を提供する。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明は、例えば特許請求の範囲に記載の構成を採用する。本明細書は上記課題を解決する手段を複数含んでいるが、その一例を挙げるならば、「(1) 旧ゲノム配列と呼ぶ第１のゲノム配列と、新ゲノム配列と呼ぶ第２のゲノム配列と、リード配列と呼ぶ多数のＤＮＡ配列と、前記リード配列を前記旧ゲノム配列にマッピングした結果を記憶する記憶装置と、(2) 前記新ゲノム配列に存在する任意の文字列を探索するためのインデックスを構築する新ゲノムインデックス構築部と、(3) 前記リード配列に存在する前記旧ゲノム配列に対する変異であって、前記旧ゲノム配列上での処理位置の近傍にある変異の組合せを記録したクエリ表と呼ぶデータ構造を、マッピングの前記結果に基づいて構築するクエリ表更新部と、(4) 前記クエリ表に格納されている変異の組合せを前記旧ゲノム配列に適用して構築した配列を前記新ゲノム配列と比較し、前記構築した配列のうちＫ（１以上の自然数）塩基以上が前記新ゲノム配列と完全に一致する箇所を網羅的に出力するマッピング先探索部と、を有するＤＮＡ配列解析装置。」である。
【発明の効果】
【００１３】
本発明によれば、旧ゲノム配列にマッピングされた膨大な数のリード配列を、旧ゲノム配列へのマッピング結果を利用して、旧ゲノム配列とは異なる新ゲノム配列に効率よくマッピングすることができる。前述した以外の課題、構成及び効果は、以下の実施の形態の説明により明らかにされる。
【図面の簡単な説明】
【００１４】
【図１】従来技術によるリード配列のマッピング手法を説明する図。
【図２】実施例に係るリード配列のマッピング手法の中間段階を説明する図。
【図３】実施例に係るリード配列のマッピング手法を説明する図。
【図４】実施例に係るＤＮＡ配列解析装置の構成例を示す図。
【図５】実施例に係るＤＮＡ配列解析処理の概要を示すフローチャート。
【図６】実施例に係るＤＮＡ配列解析処理のシーケンスを示す図。
【図７】新ゲノムインデックス構築部で実行される処理動作例を示すフローチャート。
【図８】クエリ表の一例を示す図。
【図９】クエリ表更新部で実行される処理動作例を示すフローチャート。
【図１０】クエリ表更新部で実行される既存のクエリアリルの更新処理（Ｓ２１０の詳細）を説明するフローチャート。
【図１１】図８のクエリ表を更新した後のクエリ表を示す図。
【図１２】マッピング先探索部で実行される処理動作例を示すフローチャート。
【図１３】近傍に変異が無い領域におけるクエリ表の一例を示す図。
【図１４】マッピング先探索部で実行される一致領域喪失時の処理（Ｓ３０６の詳細）を説明するフローチャート。
【図１５】マッピング先探索部で実行される一致領域延長時の処理（Ｓ３０７の詳細）を説明するフローチャート。
【図１６】新規の一致領域の探索に用いられる処理部で実行される処理（Ｓ３０９の詳細）を説明するフローチャート。
【図１７】クエリ表の可視化例を示す図。
【発明を実施するための形態】
【００１５】
以下、図面に基づいて、本発明の実施形態を説明する。なお、本発明の実施形態は、後述する実施例に限定されるものではなく、その技術思想の範囲において、種々の変形が可能である。
【００１６】
（１）基本的な考え方
旧ゲノム配列１０８へマッピングされた膨大なリード配列を、新ゲノム配列１１４へマッピングし直す処理を効率よく実行するためには、従来技術で用いるような、リード配列１０７を個別に再マッピングする処理（図１）を避けることが好ましい。この処理は、既知の情報を利用しないために非効率であり、非常に長い処理時間を必要とする。
【００１７】
そこで、以下で説明する実施例では、まず、リード配列１０７に含まれる変異４０１を旧ゲノム配列１０８に適用して得られる配列（図２の例では、旧ゲノム配列１０８について破線で囲んだ領域）を新ゲノム配列１１４と比較することで、旧ゲノム配列１０８と新ゲノム配列１１４で対応する位置を明らかにする。図２の例では、類似する２つの領域のうち、新ゲノム配列１１４で右側の領域の方の類似度合いが高いため、こちらがマッピング先となる。次に、以下で説明する実施例は、旧ゲノム配列１０８にマッピングされていたリード配列１０７を、図３に示すように、新ゲノム配列１１４で対応する位置に一括して移動させることでマッピング効率を高める。
【００１８】
（２）用語
まず、本明細書で用いる用語の定義を説明する。
・「アルファベット」とは、解析対象文字列を構成する文字の集合である。ＤＮＡ配列の場合、アルファベットは｛Ａ，Ｃ，Ｇ，Ｔ｝である。
・「文字列」とは、アルファベットに含まれる文字を連結して得られる列である。例えば「ＡＴＴＧ」は文字列である。
・文字列ｓの長さを｜ｓ｜と表記する。ｓ＝ＡＴＴＧの場合、｜ｓ｜＝４である。
・文字列ｓのｉ番目の文字をｓ［ｉ］と表記する。ｓ＝ＡＴＴＧの場合、ｓ［1］＝Ａである。本明細書では、先頭の文字は１番目とし、０番目としない。
・与えられた文字列の先頭から始まる部分文字列を、接頭辞（prefix）という。「ＡＴＴＧ」、「ＡＴＴ」、「ＡＴ」、「Ａ」は、文字列「ＡＴＴＧ」の接頭辞である。
・与えられた文字列の末尾で終わる部分文字列を、接尾辞（suffix）という。「ＡＴＴＧ」、「ＴＴＧ」、「ＴＧ」、「Ｇ」は、文字列「ＡＴＴＧ」の接尾辞である。
・与えられた文字列ｓの各接尾辞を辞書順にならべたとき、それらの接尾辞が、文字列ｓにおいて何番目から始まっていたかを記録した整数配列を、接尾辞配列（Suffix Array：ＳＡ）という（“Gusfield，Algorithms on Strings, Trees and Sequences，Cambridge University Press，1997”参照）。ｓ＝ＡＴＴＧの場合、接尾辞を辞書順にならべると、「ＡＴＴＧ」、「Ｇ」、「ＴＧ」、「ＴＴＧ」であるから、接尾辞配列はＳＡ＝［１，４，３，２］となる。接尾辞配列ＳＡのｉ番目の要素を、ＳＡ［ｉ］と表記する。
・「ＬＣＰ（Longest common prefix）」とは、２つの文字列を比較したとき、最も長い共通の接頭辞である。
・「ＬＣＰ配列」とは、ＬＣＰの長さを、接尾辞配列で隣り合うすべての接尾辞について計算して得られる整数配列である。先ほどの接尾辞配列の例では、ＬＣＰ配列は［０，０，１］となる。ＬＣＰ配列の計算には、公知の方法（“Kasai et al., Proc. CPM pp.181-192, 2001”参照)を使用できる。
・与えられた文字列ｓの「Burrows‐Wheeler変換（ＢＷＴ）」とは、｜ｓ｜と同じ長さの文字列であって、ｉ番目の文字がｓ［ＳＡ［ｉ］−１］である文字列である（“Navarro&Makkinen，ACM Computing Surveys 39(1):Article No.2,2007”参照）。ただし、ＳＡ［ｉ］＝１の場合、ＢＷＴのｉ番目の文字は「＄」とする。「＄」は終端記号とよばれ、アルファベットに無い新しい文字である。
・「FM-index」とは、ＢＷＴを、元の文字列に含まれる任意の文字列を検索するための検索インデックスとして使えるように拡張したデータ構造である（“Ferragina&Manzini Proc.FOCS pp.390-398,2000”参照）。
・「ビットベクトル」とは、０と１を並べて得られる数列である。例えば「０１００１１０」はビットベクトルである。
・「関数rank（Ｓ，ａ，ｉ）」は、文字列又はビットベクトルＳにおいて、ｉ番目までにａが出現する回数を返す。例えば、rank（ＡＴＴＧ，Ｔ，３）＝２である。
・「関数select（Ｓ，ａ，ｉ）」は、文字列またはビットベクトルＳにおいて、先頭からｉ個目のａが出現する位置を返す。例えば、select（ＡＴＴＧ，Ｔ，２）＝３である。
・ビットベクトルの「辞書（dictionary）」とは、ビットベクトルに対して、rank関数及びselect関数を高速計算するためのデータ構造である（“Navarro&Makkinen,ACM Computing Surveys 39(1):Article No.2,2007”参照）。
・「変異」とは、個体差等に由来するＤＮＡ配列の違いである。
・「アリル」とは、変異によって発生する異なるＤＮＡ配列である。例えばゲノム配列の、ある変異の位置で、旧ゲノム配列のアリルはＡに、リード配列のアリルはＴとなる場合がある。
【００１９】
（３）実施例１
続いて、旧ゲノム配列１０８に対するマッピング結果を使用して、リード配列１０７を新ゲノム配列１１４に効率よくマッピングするための仕組みを説明する。
【００２０】
（３−１）実施例の前提条件
説明を簡単にするために、実施例１では、以下の仮定を採用する。まず、実施例１では、新ゲノム配列１１４が１本の文字列であると仮定する。複数の染色体を扱う場合、この仮定は成り立たないが、例えばアルファベットに新しい文字「＃」を加え、「＃」を挟んで新ゲノム配列の複数の配列を連結して１本の文字列にするといった手法で、この制約を回避することができる。この手法は、接尾辞配列で複数の文字列を扱うときの一般的な手法である。
【００２１】
また、処理中に検出される変異は、１塩基変異であると仮定する。なお、複数塩基の変異を処理する場合には、１塩基変異が連続して複数存在するものとして処理すればよい。
【００２２】
一般に、リード配列１０７を参照ゲノム配列にアラインメントする処理は、参照ゲノム配列上で、リード配列１０７のマッピング先となり得る位置（以下「シード（seed）」という。）を計算する処理と、その後、シード（seed）周辺の文字列がリード配列１０７と一致しているかを若干の配列の差異を許容しつつ比較し、マッピング可能か否かを判定する（以下「extension」という。）処理との２段階で構成される。
【００２３】
以下の実施例では、マッピングにおいてシード（seed）を計算するための処理手順を提供する。Extension処理は、例えば“Smith‐Waterman法（Smith&Waterman，journal of Molecular Biology 147:195-197,1981）”のような公知の方法を利用できる。
【００２４】
解析処理の開始に先立ち、２つのパラメータが与えられるものとする。第１のパラメータＬは、リード配列１０７の長さである。リード配列１０７の長さは、初期の次世代シーケンサでは３０塩基前後であったが、近年は２００塩基を超える場合もある。処理対象となるデータのリード配列長に一致するよう、Ｌを設定する。第２のパラメータは、マッピング先の候補を探す際に要求する、完全一致の長さＫ（１以上の自然数）である。例えばＬ＝１００塩基の場合、５％までのエラーを許すとすれば、少なくとも１箇所は１５塩基の完全一致が存在するから、Ｋ＝１５としてＫ塩基以上の長さの全ての完全一致を発見すれば、５％までエラーを許してマッピング可能な箇所を、網羅的に列挙することができる。
【００２５】
以下の説明では、リード配列１０７には、リード配列１０７を旧ゲノム配列１０８にマッピングした結果も含まれているものとする。さらに、本明細書では、配列と文字列という２つの言葉を、特に区別せずに用いる。同様に、塩基と文字という２つの言葉も、区別せずに用いる。
【００２６】
（３−２）システム構成
図４に、本実施例に係るＤＮＡ配列解析装置１００と、当該装置を用いて構成されるＤＮＡ配列解析システム１１５の構成例を示す。ＤＮＡ配列解析装置１００は、ＣＰＵ（Central Processing Unit）１０１、主記憶装置（メモリ）１０２、補助記憶装置１０３で構成され、必要に応じてリムーバブルメディア１０４を使用する。
【００２７】
主記憶装置１０２は、ＣＰＵ１０１によって実行される各種のプログラムと、これらのプログラムをＣＰＵ１０１で実行するために必要となる各種のデータが保持されるＲＡＭ（Random Access Memory）等のメモリである。主記憶装置１０２には、リード配列(1) １０７−１、旧ゲノム配列(1) １０８−１、新ゲノムに基づき構築する新ゲノムインデックス（1） １０９−１、クエリ表１１０が記憶される。また、主記憶装置１０２には、ＣＰＵ１０１で実行させるプログラムも格納される。当該プログラムの実行を通じ、後述する新ゲノムインデックス構築部１１１、クエリ表更新部１１２、マッピング先探索部１１３の各機能が提供される。
【００２８】
補助記憶装置１０３は、ＨＤＤ（Hard Disk Drive）等の記憶装置であり、リード配列(2) １０７−２、旧ゲノム配列(2) １０８−２、新ゲノムインデックス(2) １０９−２等が記録される。補助記憶装置１０３には、更に、新ゲノム配列(1) １１４−１を記録してもよい。リムーバブルメディア１０４は、ＤＮＡ配列解析装置１００に対して着脱可能なＣＤ、ＤＶＤ等の記憶媒体であり、リード配列(3) １０７−３、旧ゲノム配列(3) １０８−３、新ゲノムインデックス(3) １０９−３、新ゲノム配列(2) １１４−２等が記録される。
【００２９】
ＤＮＡ配列解析装置１００には、ユーザインタフェース部１０６を接続してもよく、ＬＡＮ（Local Area Network）等のネットワーク１０５を介してストレージ装置を接続してもよい。ここで、ネットワーク１０５は、ＬＡＮ（Local Area Network）やインターネットでもかなわない。また、ネットワーク１０５は、有線接続に限る必要は無く、無線接続であってもよい。ユーザインタフェース部１０６は、ユーザインタフェースを提供する入出力装置であり、例えばキーボード、マウス、ディスプレイ等で構成される。ユーザインタフェース部１０６は、ＤＮＡ配列解析装置１００と一体でもよい。
【００３０】
また、ネットワーク１０５を介して接続されるストレージ装置には、リード配列(4) １０７−４、旧ゲノム配列(4) １０８−４、新ゲノムインデックス(4) １０９−４、新ゲノム配列(3) １１４−３を記録することができる。本実施例では、ＤＮＡ配列解析装置１００に対してユーザインタフェース部１０６とこれらのストレージ装置を接続した構成をＤＮＡ配列解析システム１１５と呼ぶ。しかし、この区分は固定的なものではなく、例えばプログラムの一部を、ネットワーク１０５を介して接続された他のコンピュータと連携して実行するものをＤＮＡ配列解析システムと呼んでもよい。また、ユーザ側には、ユーザインタフェース部１０６だけが存在し、ネットワークを通じて接続されたサーバ側で実行される処理の結果を確認する仕組みを採用してもよい。ＤＮＡ解析装置１００とＤＮＡ解析システム１１５の区別は便宜的なもので、装置構成は同じでも良い。
【００３１】
図４では、同じ種類のデータでも、データの格納先に応じて、各データを表す記号(1)〜(4)を付しているが、格納先が関係しない説明では、代表してリード配列１０７、旧ゲノム配列１０８、新ゲノムインデックス１０９、新ゲノム配列１１４と表記する。
【００３２】
これらのデータは、例えばＣＰＵ１０１で読み書きする場合に、必要に応じて主記憶装置１０２に格納してもよいし、ＤＮＡ配列解析装置１００の電源を切る場合又は主記憶装置１０２の空き容量が無くなった場合に、主記憶装置１０２から他の記憶メディアや記憶装置（ストレージ装置を含む。）にコピーしてもよい。また、解析開始前に、不図示の他の装置からリムーバブルメディア１０４や外部のストレージ装置にデータを格納し、当該格納されたデータを、ＤＮＡ配列解析装置１００の起動時や解析開始時に、ＤＮＡ配列解析装置１００内の主記憶装置１０２又は補助記憶装置１０３にコピーしてもよい。
【００３３】
（３−３）処理動作
以下では、図５及び図６を使用して、ＤＮＡ配列解析装置１００で実行される処理動作を説明する。図５は、新ゲノム配列１１４に対するリード配列１０７のマッピング先候補が出力されるまでの処理の概要を示している。図６は、各処理部の協調動作を説明するための処理シーケンスである。これらの図面を参照しつつ、個々の処理を説明する。
【００３４】
（３−３−１）新ゲノムインデックス構築部１１１の処理
新ゲノムインデックス構築部１１１は、新ゲノム配列１１４に含まれる任意の部分配列の探索を容易にするための検索インデックス（すなわち、新ゲノムインデックス１０９）を構築する処理部である。新ゲノムインデックス１０９は、２つのデータで構成される。一つは、一般的な文字列検索用インデックスであるFM-indexである。残る一つは、ＬＣＰ配列に基づくビットベクトルであり、旧ゲノムインデックスと新ゲノムインデックス１０９の一致箇所を漏れなく探索するためのデータである。
【００３５】
図７に、新ゲノムインデックス構築部１１１で実行される処理動作を示す。まず、新ゲノムインデックス構築部１１１は、新ゲノム配列１１４に対し、FM-indexを構築する（Ｓ１０１）。次に、新ゲノムインデックス構築部１１１は、新ゲノム配列１１４に対し、ＬＣＰ配列を計算する（Ｓ１０２）。その後、新ゲノムインデックス構築部１１１は、Ｓ１０２で計算したＬＣＰ配列と同じ長さのビットベクトルＢＬを構築する（Ｓ１０３）。ここで、ＢＬのｉ番目の数値は、ＬＣＰ配列のｉ番目にＫ以上の数値が書かれている場合には「１」、そうでない場合には「０」とする。続いて、新ゲノムインデックス構築部１１１は、ビットベクトルＢＬに対し、rank及びselectを高速に計算するための辞書を構築する（Ｓ１０４）。
【００３６】
（３−３−２）クエリ表更新部１１２の処理
新ゲノムインデックス構築部１１１によって辞書が構築されると、クエリ表更新部１１２の処理が開始される。クエリ表更新部１１２は、旧ゲノム配列１０８を１塩基ずつ読み、変異位置をクエリ表１１０に記録する処理を実行する。ここでのクエリ表１１０の更新（準備）により、旧ゲノム配列１０８の同一箇所にマッピングされている複数のリード配列１０７を、一括して新ゲノム配列１１４にマッピングすることが可能となり、マッピング効率が格段に向上される。
【００３７】
ただし、リード配列１０７は、マッピングされた箇所の旧ゲノム配列１０８と必ずしも完全に一致するわけではなく、変異により違いが生じている場合がある。そこで、本実施例では、リード配列１０７がマッピングされた箇所の旧ゲノム配列１０８そのものではなく、リード配列１０７に含まれる変異のアリルを旧ゲノム配列１０８に反映させて構築した配列を探索に使用する手法を採用する。この手法を実現すべく、クエリ表更新部１１２は、リード配列１０７から発見された変異をクエリ表１１０に記録し、旧ゲノム配列１０８に反映させる変異の情報を管理する。
【００３８】
クエリ表更新部１１２は、クエリ表１１０の構築時（初期状態）と探索時に、クエリ表１１０を更新するために使用される。図８に、クエリ表１１０の一例を示す。なお、図８は、クエリ表１１０のデータそのものではなく、説明のために表形式で表したものである。クエリ表には、旧ゲノム配列１０８上での処理位置からＬ塩基以内に存在する変異のアリルの組合せを格納する。この組合せを、以下ではクエリアリル１１０１と呼ぶ。また、クエリアリル１１０１を反映して旧ゲノム配列１０８を修正した配列を、クエリ配列と呼ぶ。個々のクエリアリル１１０１について、各クエリアリル１１０１に対応するクエリ配列の長さ（列１１０２）、そのクエリ配列が新ゲノムインデックスに存在する範囲（列１１０３）、個々の変異位置でのアリルを列１１０４に記録する。個々の変異位置について、リード配列１０７に出現するアリルの一覧１１０５を記録してもよい。
【００３９】
図９に、クエリ表更新部１１２で実行される処理動作を示す。ここで、クエリ表更新部１１２は、マッピング先探索部１１３の処理位置（旧ゲノム配列１０８上）の近傍にマッピングされているリード配列１０７の変異がクエリ表１１０に記録されるようにクエリ表１１０を適宜更新する。
【００４０】
まず、クエリ表更新部１１２は、近傍から離れた変異を除去する（Ｓ２０１〜Ｓ２０３）。具体的には、Ｓ２０１において、クエリ表更新部１１２は、クエリ表１１０に、処理中の位置からＬ（１以上の自然数）塩基以上離れた位置に変異があるか否かを判定する。そのような変異がある場合、クエリ表更新部１１２はＳ２０２に進み、その変異を記録した列をクエリ表１１０から削除する。次に、クエリ表更新部１１２はＳ２０３に進み、クエリアリル１１０１が同じものを統合する。この際、クエリ表更新部１１２は、クエリ表１１０に記録されている個々のクエリアリル１１０１を比較し、同じアリルの組合せで構成されるクエリアリル１１０１で長さの値が同一のものが存在する場合、それらのうち１つのクエリアリル１１０１のみを残し、他のクエリアリル１１０１を消去する。
【００４１】
続いて、クエリ表更新部１１２は、新しく発見された変異をクエリ表１１０に追加する（Ｓ２０４〜Ｓ２０５）。具体的には、Ｓ２０４において、クエリ表更新部１１２は、クエリ表１１０の新しい列を追加する。また、Ｓ２０５において、クエリ表更新部１１２は、変異があると判定された旧ゲノム配列１０８上の位置を表す番号に対応付けるように、旧ゲノム配列１０８及びリード配列１０７の各アリルを記録する。
【００４２】
これらの処理が終了すると、クエリ表更新部１１２は、処理前のクエリ表１１０が空だった場合には、クエリアリルを追加する処理（Ｓ２０８〜Ｓ２０９）を実行し、空でなかった場合には、クエリアリルを更新する処理（Ｓ２０８、Ｓ２１０）を実行する。具体的には、Ｓ２０８において、クエリ表更新部１１２は、クエリアリル１１０１がクエリ表１１０に１つ以上既に存在しているか否かを判定する。
【００４３】
存在しない場合（Ｓ２０９において）、クエリ表更新部１１２は、発見された変異でリード配列１０７のアリルを持つ新たなクエリアリル１１０１をクエリ表１１０に追加する。ただし、処理中の位置に変異が無い場合には、図１３に例示するように、対応する変異がない行を、クエリアリルの代わりに追加する。ここで、クエリ表の「新ゲノムインデックスの範囲」は全範囲（［１、新ゲノム配列長］）、「長さ」は１とする。一方、Ｓ２０８で既存のクエリアリル１１０１が存在すると判定された場合（Ｓ２１０において）、クエリ表更新部１１２は、既存の各クエリアリル１１０１の更新処理（図１０）を実行する。
【００４４】
図１０に、Ｓ２１０で実行される更新処理の詳細動作を示す。まず、クエリ表更新部１１２は、既存のクエリアリル１１０１の全てを順番に処理対象とする（Ｓ２１０１、Ｓ２１０９）。具体的には、Ｓ２１０１において、クエリ表更新部１１２は、クエリ表１１０から未処理のクエリアリル１１０１を１つ選択する。なお、Ｓ２１０９において、クエリ表更新部１１２は、未処理のクエリアリル１１０１が残っているか否かを判定し、残っている場合にはＳ２１０１に戻る。このループ処理により、全てのクエリアリル１１０１について、１つずつ、後述するＳ２１０２〜Ｓ２１０８の処理が繰り返される。
【００４５】
次に、クエリ表更新部１１２は、新しく追加した変異のアリルの全てを順番に処理対象とする（Ｓ２１０２、Ｓ２１０５）。具体的には、Ｓ２１０２において、クエリ表更新部１１２は、新しい変異のアリルから未処理のアリルを１つ選択する。また、Ｓ２１０５において、クエリ表更新部１１２は、新しい変異のアリルのうち未処理のものが残っているか否かを判定し、残っている場合にはＳ２１０２に戻る。このループ処理により、全ての新しい変異のアリルについて、１つずつ、後述するＳ２１０３〜Ｓ２１０４の処理が繰り返される。
【００４６】
続いて、クエリ表更新部１１２は、新しい変異のアリルと既存のクエリアリル１１０１の両方を含むリード配列１０７があるか否かを判定する（Ｓ２１０３）。そのようなリード配列が有る場合、クエリ表更新部１１２は、新しい変異のアリルと既存のクエリアリル１１０１とを組み合わせた新しいクエリアリル１１０１をクエリ表１１０に追加する（Ｓ２１０４）。一方、Ｓ２１０３において否定結果が得られた場合（新しく追加した変異のアリルのいずれも含むリード配列１０７が存在しない場合）、クエリ表更新部１１２は、Ｓ２１０４をスキップしてＳ２１０５に進む。
【００４７】
Ｓ２１０５で肯定結果が得られた場合、クエリ表更新部１１２は、処理中の既存のクエリアリル１１０１について、新しい変異のアリルのいずれかで、Ｓ２１０４の追加処理が行なわれなかったかを判定する（Ｓ２１０６）。ここで肯定結果が得られた場合、クエリ表更新部１１２は、それまでに見つかっていた一致領域を出力するために一致領域喪失時の処理を実行する（Ｓ２１０７）。一方、Ｓ２１０６で否定結果が得られた場合、又は、Ｓ２１０７の処理が終了した場合、クエリ表更新部１１２は、前述した処理の実行により不要となった既存のクエリアリル１１０１を削除する（Ｓ２１０８）。
【００４８】
図１１を参照して、クエリ表更新部１１２による更新処理によりクエリ表１１０がどのように変化するかを説明する。図１１は、図８に示すクエリ表１１０を更新した後のクエリ表１１０である。図８は、旧ゲノム配列の「１１０４」番目の塩基を処理した後の状態、図１１は「１１０３」番目の塩基を処理した後の状態を想定している。また、Ｌ＝１００、Ｋ＝１５と仮定する。
【００４９】
図８に示すクエリ表１１０の場合、「１１０３」番目の位置からＬ＝１００塩基以上離れた塩基が無いので、Ｓ２０１〜Ｓ２０３で削除される列は無い。次に、旧ゲノム配列１０８の「１１０３」番目の位置に見つかった変異が、新たな列として図１１のクエリ表１１０に追加される（Ｓ２０４〜Ｓ２０５）。さらに、クエリ表の更新処理（Ｓ２０８、Ｓ２１０）により、クエリ表１１０に書かれているクエリアリル１１０１を１つずつ更新する（Ｓ２１０１、Ｓ２１０９）。
【００５０】
まず、図８のクエリ表１１０におけるクエリアリル１１０１のうち最初の行に記載されているＧ、Ａを処理する場合を考える。この例の場合、「１１０３」番目の位置に見つかった新しい変異がＴ又はＣなので、これらを先頭に加えたクエリアリル１１０１には「Ｔ、Ｇ、Ａ」と「Ｃ、Ｇ、Ａ」の２つがある。これらのアリルの組合せがリード配列１０７に存在しないのなら、クエリ表１１０に記録して処理する必要がない。そこで、これらを含むリード配列１０７の有無を判定し（Ｓ２１０３）、「有る」場合に限ってクエリ表１１０に追加する（Ｓ２１０４）。図１１では、「Ｔ、Ｇ、Ａ」と「Ｃ、Ｇ、Ａ」を含むリード配列１０７がいずれも存在していたと想定し、どちらもクエリ表１１０に追加されている。図８のクエリ表１１０に記載されていたクエリアリル１１０１のうちＧ、Ａだけのクエリアリル１１０１はもう不要なので消去する（Ｓ２１０８）。
【００５１】
次に、図１１のクエリ表１１０におけるクエリアリル１１０１のうち２つ目の行に記載されているＣ、Ａを処理する場合を考える。「１１０３」番目の位置に見つかった新しい変異と組み合わせると、「Ｔ、Ｃ、Ａ」と「Ｃ、Ｃ、Ａ」の２通りが考えられる。しかし、これらはいずれもリード配列１０７に存在しないとＳ２１０３で判定され、図１１には残っていない。その代わりＳ２１０６で、新しい変異と共存するリード配列がないと判定されて、一致領域喪失時の処理（Ｓ２１０７）が実行される。
【００５２】
図１１のクエリ表１１０におけるクエリアリル１１０１のうち３つ目の行に記載されているＧ、Ｔからは「Ｃ、Ｇ、Ｔ」のみ、４つ目の行に記載されているＣ、Ｔからは「Ｔ、Ｃ、Ｔ」のみがリード配列１０７に存在するので、図１１に示すように、クエリ表１１０に追加される。図１１のクエリ表１１０には、Ｃだけのクエリアリル１１０１とＴだけのクエリアリル１１０１も追加されている。これは、後述のＳ３０７４（図１５）において、長さＫ＝１５の接頭辞が新ゲノム配列上の新しい箇所と一致することが分かったために、追加されたものである。
【００５３】
（３−３−３）マッピング先探索部１１３の処理
マッピング先探索部１１３は、クエリ表１１０に記載されている変異を旧ゲノム配列１０８に反映して得られた文字列が、新ゲノム配列１１４のどこに含まれるかを、新ゲノムインデックス１０９を用いて探索する。因みに、マッピング先探索部１１３は、旧ゲノム配列１０８の右端から左端へ１塩基ずつ処理を行ない、クエリ表１１０を参照しつつ、クエリ配列と同一の配列が新ゲノム配列１１４に存在する限り、クエリ配列を１塩基ずつ延長する。
【００５４】
図１２に、マッピング先探索部１１３で実行される処理動作を示す。まず、マッピング先探索部１１３は、初期化処理を実行する（Ｓ３０１）。具体的には、変数ｉを、旧ゲノム配列１０８の長さに等しい整数値に初期化する。次に、マッピング先探索部１１３は、クエリ表１１０の更新処理を実行する（Ｓ３０２）。具体的には、旧ゲノム配列１０８のｉ番目の位置について、クエリ表更新部１１２の処理を実行する。
【００５５】
マッピング先探索部１１３は、クエリ表１１０の各クエリアリル１１０１について、新ゲノム配列１１４の中で一致している箇所を１塩基ずつ延長する処理を実行する（Ｓ３０３〜Ｓ３０８）。具体的には、Ｓ３０３において、マッピング先探索部１１３は、クエリ表１１０に記録されているクエリアリル１１０１の中から未処理のクエリアリル１１０１を１つ選び、そのクエリアリル１１０１を用いて旧ゲノム配列１０８のｉ番目の塩基から始まる、クエリ表１１０の「長さ」の列１１０２に記録された長さの配列を修正することにより、クエリ配列を生成する。
【００５６】
ただし、処理中の位置の近傍に変異がない場合には、図１３に示すクエリ表１１０のように変異が無いことがある。その場合には、旧ゲノム配列１０８のｉ番目の塩基から始まる、クエリ表１１０の列１１０２に記録された「長さ」の配列を、そのままクエリ配列として使用する。本明細書ではこのような、変異がなく旧ゲノム配列１０８に一致するクエリ配列を表す行も、クエリアリル１１０１と同様に扱う。
【００５７】
次に、Ｓ３０４において、マッピング先探索部１１３は、クエリアリル１１０１を含むクエリ配列であって、「長さ」の列１１０２に記録されている値に１を加えた長さのクエリ配列の先頭の文字をｂ、２文字目から始まる接尾辞をｘとして、文字列ｂｘが存在する新ゲノムインデックス１０９の範囲を計算する。この範囲は、ＬＦ−ｍａｐｐｉｎｇ(Navarro&Makkinen, ACM Computing Surveys 39(1):Article No.2,2007）を用いて、下記の通り計算できる。
beg(bx) ＝C［b］＋rank（BWT，b，beg（x)-1）＋1
end(bx) ＝C［b］＋rank（BWT，b，end（x））
【００５８】
ただし、C［b］は、辞書順でｂより小さな文字の新ゲノム配列での総数の和である。また、beg（x）とend（x）は、それぞれ、新ゲノムインデックス１０９の範囲（列１１０３）に記載されている開始位置と終了位置である。
【００５９】
次のＳ３０５において、マッピング先探索部１１３は、計算結果がbeg（bx）＞end（bx）となったか否か判定する。もし、beg（bx）＞end（bx）であれば、ＬＦ−ｍａｐｐｉｎｇの性質から、文字列ｂｘが新ゲノム配列１１４に存在しないことが分かるので、この場合、マッピング先探索部１１３は、一致領域喪失時の処理を実行する（Ｓ３０６）。
【００６０】
図１４に、Ｓ３０６の詳細動作を示す。この処理において、マッピング先探索部１１３は、一致領域喪失直前まで延長されていた、クエリ配列と新ゲノム配列１１４の一致箇所のうち、必要なものを判別して出力する処理を実行する。まず、Ｓ３０６１において、マッピング先探索部１１３は、｜ｘ｜≧Ｋか否かを判定する。｜ｘ｜＜Ｋであれば、何も出力しない。Ｓ３０６２において、マッピング先探索部１１３は、別のクエリアリル等を処理する際に、既に出力した範囲であるか否かを判定する。既に出力されている場合、マッピング先探索部１１３は、重複して出力はしない。Ｓ３０６３において、マッピング先探索部１１３は、「新ゲノムインデックスの範囲」のうち、ｉ＋１の値に対してまだ出力されていない範囲を、ｉ＋１での一致領域として出力する。
【００６１】
図１２の説明に戻る。Ｓ３０５で、もしbeg(bx)≦end(bx)であった場合、ＬＦ−ｍａｐｐｉｎｇの性質から、文字列ｂｘが新ゲノム配列に存在することが分かるので、この場合、マッピング先探索部１１３は、一致領域延長時の処理を実行する（Ｓ３０７）。
【００６２】
図１５に、Ｓ３０７の詳細動作を示す。この処理において、マッピング先探索部１１３は、おおよそ３つの処理を実行する。第１の処理は、クエリ表情報に記録されている各クエリアリルに対応するクエリ配列ｘを左に１文字延長して得られる文字列ｂｘが、新ゲノム中に出現する範囲を更新する処理である（Ｓ３０７１）。第２の処理は、リード長Ｌに達した一致領域を、出力する処理である（Ｓ３０７２〜Ｓ３０７３）である。第３の処理は、クエリ配列ｂｘを短くすることにより一致箇所を増やす処理であり（Ｓ３０７４〜Ｓ３０７６）、ｂｘの長さＫの接頭辞が一致する、新ゲノム配列１１４上の新たな箇所を計算する。長さＫ未満の一致は出力対象でないから処理不要であり、長さＫ＋１以上の一致は既に探索済みの長さＫ以上の一致を延長することで処理できる。
【００６３】
ここで、Ｓ３０７１において、マッピング先探索部１１３は、処理対象とするクエリアリル１１０１の「新ゲノムインデックスの範囲」を（beg（bx），end（bx））で置き換える。また、マッピング先探索部１１３は、クエリアリル１１０１の「長さ」に１を加える。また、Ｓ３０７２において、マッピング先探索部１１３は、「長さ」がＬ以上となったか否かを判定する。
【００６４】
「長さ」がＬ以上となった場合、マッピング先探索部１１３はＳ３０７３に進み、旧ゲノム配列の位置ｉにマッピングされているリード配列があれば、ｉ及び置き換え後の「新ゲノムインデックスの範囲」の出力のうち、同じｉの値に対してまだ出力されていない範囲を出力するとともに、「長さ」をＬ−１に戻す。「長さ」がＬ未満であった場合又はＳ３０７３が実行された後、マッピング先探索部１１３はＳ３０７４に進み、bxの長さＫの接頭辞ｙが、新ゲノム配列においてbxの接頭辞以外の箇所に存在するか否かを調べる。そのために、マッピング先探索部１１３は、ビットベクトルＢＬを用いて、以下の２つの値beg（y）及びend（y）を計算する。
beg（y）＝select（BL, 0, rank（BL, 0, beg(bx)-1））+1
end（y）＝select（BL, 0, rank（BL, 0, end(bx)-1）+1）
【００６５】
そして、beg(y)≠beg(bx)、又は、end(y)≠end(bx)が成立するか否か判断する。この条件が成立するなら、ｙが新ゲノム配列においてbxの接頭辞以外の箇所に存在すると判断する。なお上記の式で、beg(x)およびend(bx)から１を減算するのは、BWTのbeg(x)番目、end(x)番目の要素がBLのbeg(x)-1番目、end(x)-1番目の要素に対応するためである。
【００６６】
Ｓ３０７５において、マッピング先探索部１１３は、Ｓ３０７４の条件が満たされるか否かを判定し、満たされる場合には、Ｓ３０７６に進み、クエリ表１１０に新しいクエリアリルの組合せを追加する。このクエリアリルは、前記クエリアリルでＫ塩基以内のアリルを全てコピーし、「新ゲノムインデックス上の範囲」は［beg(y),end(y)］、「長さ」をＫとしたものである。なお、Ｋ塩基以内に変異がなければ、図１３の例にあるような、変異がない行をクエリ表に追加する。Ｓ３０７４の条件が満たされない場合、マッピング先探索部１１３は、Ｓ３０７の処理を終了する。
【００６７】
図１２の説明に戻る。以上の処理が終了すると、Ｓ３０８が実行される。Ｓ３０８において、マッピング先探索部１１３は、クエリ表１１０内に未処理のクエリアリル１１０１が残っているか否かを判定し、残っている場合には、前述したＳ３０３〜Ｓ３０８の処理を繰り返す。未処理のクエリアリル１１０１が残っていない場合、マッピング先検出部１１３は、Ｓ３０９として、既存の一致領域の延長ではない、新しい一致領域を探索する処理を実行する。
【００６８】
図１６に、Ｓ３０９の詳細動作を示す。この処理において、マッピング先探索部１１３は、既存のクエリアリル１１０１に無いアリルの組合せを検討し（Ｓ３０９１〜Ｓ３０９３、Ｓ３０９８）、旧ゲノム配列のＫ塩基の領域に反映させ（Ｓ３０９４）、新ゲノム配列１１４にＫ塩基以上一致する箇所を探索する（Ｓ３０９５）。なお、一致する箇所があった場合、マッピング先探索部１１３は、クエリ表１１０に加える(Ｓ３０９６〜Ｓ３０９７)。
【００６９】
ここで、Ｓ３０９１において、マッピング先探索部１１３は、変数ｉが指し示す旧ゲノム配列１０８上の位置からＫ塩基以内にある全ての変異の、アリルの組合せを列挙する。なお、Ｋ塩基以内に変異が無い場合は、旧ゲノム配列と完全に一致するアリルが存在する場合と同様の処理を行う。次のＳ３０９２において、マッピング先探索部１１３は、Ｓ３０９１で列挙したアリルの組合せの中から１つを選択する。次のＳ３０９３において、マッピング先探索部１１３は、Ｓ３０９２で選択したアリルの組合せを含むリード配列があるか否かを判定する。無ければ、マッピング先探索部１１３は、Ｓ３０９８に移動し、アリルの次の組合せに進む。
【００７０】
一方、Ｓ３０９３において肯定結果が得られた場合、マッピング先探索部１１３は、Ｓ３０９４に進み、変数ｉが指し示す旧ゲノム配列１０８上の位置からＫ塩基の旧ゲノム配列１０８に、選択したアリルの組合せを適用した配列を生成する。次のＳ３０９５において、マッピング先探索部１１３は、Ｓ３０９４の配列が、新ゲノム配列１１４に存在するか否かを、新ゲノムインデックス１０９を用いて判定する。
【００７１】
存在しないと判定された場合（Ｓ３０９６で否定結果）、マッピング先探索部１１３は、Ｓ３０９８に移動し、アリルの次の組合せに進む。一方、存在すると判定された場合（Ｓ３０９６で肯定結果）、マッピング先探索部１１３は、Ｓ３０９７に移動し、Ｓ３０９２以降処理してきたアリルの組合せを、クエリ表にまだ無ければ、新たなクエリアリル１１０１としてクエリ表１１０に加える。なお、Ｓ３０９１でＫ塩基以内の変異が存在せず完全一致するアリルがあるものとして処理していた場合には、図１３に例示するような変異がない行をクエリ表１１０に加える。そして、Ｓ３０９８において、マッピング先探索部１１３は、アリルの組合せで、未処理のものがまだあれば、Ｓ３０９２へ戻り、アリルの他の組合せを処理する。
【００７２】
図１２の説明に戻る。前述の処理が終了すると、マッピング先探索部１１３は、旧ゲノム配列１０８の右端から左端へ１塩基ずつ移動する（Ｓ３１０〜Ｓ３１１）。具体的には、Ｓ３１０において、マッピング先探索部１１３は、変数ｉから１を減じる。また、Ｓ３１１において、マッピング先探索部１１３は、変数ｉの値が１以上であれば、Ｓ３０２に戻り、前述の処理を繰り返す。
【００７３】
（３−４）効果
前述した処理の実行により、Ｓ３０７３において、旧ゲノム配列１０８にリード配列１０７に見られる変異を適用した長さＬ以内のあらゆる配列について、新ゲノム配列１１４において出現する位置を、網羅的に出力することができる。従って、本実施例によれば、旧ゲノム配列１０８の同一箇所にマッピングされていたリード配列１０７がマッピングされるべき新ゲノム配列１１４中の位置の候補を、一括して効率よく計算することができる。
【００７４】
（４）実施例２
マッピング結果の正当性を評価するためには、ＤＮＡ解析装置１００で重要な部分を占めるクエリ表１１０の内容を、ユーザが検査できることが望ましい。そこで、本実施例では、ユーザがクエリ表１１０の内容を確認するためのグラフィカルなインタフェースを提供する仕組みについて説明する。
【００７５】
図１７に、インタフェース画面１７００の例を示す。インタフェース画面１７００は、ユーザインタフェース部１０６を構成するディスプレイ画面上に表示される。インタフェース画面１７００は、クエリ表１１０の内容を表示する表示領域１７０１を有する。表示領域１７０１の下段には、クエリ表１１０に対応するクエリ配列の表示領域１７１０が表示される。
【００７６】
表示領域１７１０には、旧ゲノム配列１０８を表す直線（横軸）１７０２に対して平行に、クエリ配列を表す直線１７０３が表示される。直線１７０３上には、クエリ表１１０の各変異の位置１７０４毎に、当該位置におけるクエリ配列のアリル１７０５が表示され、各クエリ配列に合致するリード配列１０７の本数１７０６（例えば「３×」は３本を示す。）が表示される。このインタフェース画面１７００に表示すべき旧ゲノム配列１０８上の範囲は、例えば方向ボタン１７０７のようなインタフェースにより、ユーザが任意に選択できるものとする。クエリ表１１０は、近傍する（Ｌ未満の）領域内で生じた変異のアリルを記録したものである。すなわち、クエリ表１１０は、Ｌ以上離れた領域には無関係であるため、ユーザが観察したい領域のクエリ表を効率よく再構築できる。
【００７７】
（５）他の実施例
以上の実施例は好ましい例を示したものであり、具体的構成に限定する趣旨ではない。以上の説明の要旨を逸脱しない範囲において種々変更可能である。例えば前述した実施例の全ての構成を必ずしも備える必要はない。また、ある実施例の一部を他の実施例の構成に置き換えることができる。また、ある実施例の構成に他の実施例の構成を加えることもできる。また、各実施例の構成の一部について、他の実施例の構成の一部を追加、削除又は置換することもできる。
【００７８】
また、上述した各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現しても良い。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行することにより（すなわちソフトウェア的に）実現しても良い。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリ、ハードディスク、SSD（Solid State Drive）等の記憶装置、又は、ICカード、SDカード、DVD等の記憶媒体に格納することができる。また、制御線や情報線は、説明上必要と考えられるものを示すものであり、製品上必要な全ての制御線や情報線を表すものでない。実際にはほとんど全ての構成が相互に接続されていると考えて良い。
【符号の説明】
【００７９】
１００…ＤＮＡ配列解析装置
１０１…ＣＰＵ
１０２…主記憶装置
１０３…補助記憶装置
１０４…リムーバブルメディア
１０５…ネットワーク
１０６…ユーザインタフェース部
１０７…リード配列及びその旧ゲノム配列へのマッピング結果
１０８…旧ゲノム配列
１０９…新ゲノムインデックス
１１０…クエリ表
１１１…新ゲノムインデックス構築部
１１２…クエリ表更新部
１１３…マッピング先探索部
１１４…新ゲノム配列
１１５…ＤＮＡ配列解析システム
４０１…リード配列の変異
１１０１…クエリ表に格納されているクエリアリル
１１０２…各クエリアリルに対応するクエリ配列の長さ
１１０３…各クエリアリルに対応する新ゲノムインデックスでの範囲
１１０４…各クエリアリルに対応する各変異位置でのアリル
１１０５…各変異位置での、リード配列に見られるアリルの一覧
１７０１…クエリ表の内容を表示する表示領域
１７０２…旧ゲノム配列を表す直線
１７０３…クエリ配列を表す直線
１７０４…クエリ表の各変異の位置
１７０５…当該位置におけるクエリ配列のアリル
１７０６…各クエリ配列に合致するリード配列の本数
１７０７…表示すべき範囲を変更するための方向ボタン
【図１】
0006653628.tif 000002
【図２】
0006653628.tif 000003
【図３】
0006653628.tif 000004
【図４】
0006653628.tif 000005
【図５】
0006653628.tif 000006
【図６】
0006653628.tif 000007
【図７】
0006653628.tif 000008
【図８】
0006653628.tif 000009
【図９】
0006653628.tif 000010
【図１０】
0006653628.tif 000011
【図１１】
0006653628.tif 000012
【図１２】
0006653628.tif 000013
【図１３】
0006653628.tif 000014
【図１４】
0006653628.tif 000015
【図１５】
0006653628.tif 000016
【図１６】
0006653628.tif 000017
【図１７】
0006653628.tif 000018