[go: up one dir, main page]

JP2012018592A - 配列解析装置、配列解析方法およびコンピュータプログラム - Google Patents

配列解析装置、配列解析方法およびコンピュータプログラム Download PDF

Info

Publication number
JP2012018592A
JP2012018592A JP2010156342A JP2010156342A JP2012018592A JP 2012018592 A JP2012018592 A JP 2012018592A JP 2010156342 A JP2010156342 A JP 2010156342A JP 2010156342 A JP2010156342 A JP 2010156342A JP 2012018592 A JP2012018592 A JP 2012018592A
Authority
JP
Japan
Prior art keywords
block
class
work
candidate
blocks
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2010156342A
Other languages
English (en)
Other versions
JP5516880B2 (ja
Inventor
Kana Shimizu
佳奈 清水
Koji Tsuda
宏治 津田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
National Institute of Advanced Industrial Science and Technology AIST
Original Assignee
National Institute of Advanced Industrial Science and Technology AIST
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by National Institute of Advanced Industrial Science and Technology AIST filed Critical National Institute of Advanced Industrial Science and Technology AIST
Priority to JP2010156342A priority Critical patent/JP5516880B2/ja
Publication of JP2012018592A publication Critical patent/JP2012018592A/ja
Application granted granted Critical
Publication of JP5516880B2 publication Critical patent/JP5516880B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Landscapes

  • Measuring Or Testing Involving Enzymes Or Micro-Organisms (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

【課題】大量のショートリードの中から、高速に、編集距離が所定の範囲内にあるショートリードのペアを探索することができる配列解析装置を提供する。
【解決手段】配列解析装置１０は、複数の塩基配列を入力する配列入力部１１と、編集距離ｄとブロック分割数を決定する数値ｎまたは分割数（ｄ＋ｎ）を入力する条件入力部１２と、複数の塩基配列の各々を（ｄ＋ｎ）個に分割してブロックを生成し、その中から選んだｎ個のすべてのブロックについて、読み出した部分配列、または、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致する条件を満たす塩基配列の集合を等価クラスとする等価クラス生成部１３と、等価クラス生成部から、塩基配列のペアについて、編集距離を計算し、編集距離ｄ以内であると計算されたペアを示すデータを出力する類似判定部１４とを備えた。
【選択図】図５

Description

本発明は、配列解析装置および配列解析方法に関し、特に、大量の塩基配列の中から、距離が所定範囲内にある塩基配列のペアを探索する配列解析装置および配列解析方法に関する。
ＤＮＡ塩基配列の分析技術の発展により、ギガシーケンサと呼ばれるシーケンサを用いることで、大量のリード長の短い塩基配列（以下、「ショートリード」（short read）、または「ＳＲ」という）が得られる。また、昨今では、ショートリードを用いても有効な分析を行うことができる技術が提案されている。ゲノムワイドアライメント（genome-wide alignment）やデノボゲノムアセンブリ（de novo genome assembly）のような塩基配列分析では、まず、大量のショートリードの中から類似のペアを見つけ出すことが重要な作業となる。
大量の（例えば、数千万の）ショートリードの中から類似のペアを見つけ出すために、すべてのショートリードのペアの距離を求めるとすると、膨大な量の計算を行わなければならなくなる。シーケンサからショートリードがｎ個出力された場合には、すべてのショートリードのペアの距離を求めるとすると、｛ｎ×（ｎ−１）｝／２回の距離計算を行わなければならない。
距離が所定の範囲内にあるショートリードのペアを取りこぼすことなく、実際に距離計算をするショートリードのペアの数を削減する方法として、複合ソート法がある。図２１は、複合ソート法を説明するための図である。複合ソート法では、複数のショートリードを対応する部分配列ごとにブロックとして分割し、その中から選んだ所定数のブロックにおいて、すべてのショートリードの部分配列を比較して、配列パターンが一致するショートリードによって等価クラス（equivalence class）を形成し、等価クラスに含まれるショートリードのペアについて距離計算を行う。この方法によれば、実際に距離を計算するショートリードのペアを削減でき、互いに類似するショートリードのペアを高速に探索できる。
本出願に関連する先行技術文献として、以下の文献がある。
特開２００９−１１６５５９号公報
しかしながら、上記の複合ソート法は、ハミング距離（hamming distance）でショートリードの類似性を評価することを前提としている。ここで、ハミング距離とは、等しい長さの２つのショートリードにおいて、対応する位置にある異なった文字の個数であり、換言すれば、一方のショートリードを他方のショートリードに一致させるために必要な文字の置換回数を計測したものである。
ハミング距離によるショットリードの類似性の評価では、配列の一部の塩基が欠損している場合には、配列の全体がずれるため、類似性を適切に判断できない場合がある。遺伝子を構成する一部の塩基が欠損したり、新しい塩基が挿入されたりすることは起こり得ることなので、このような配列どうしは類似すると判断した方が良い場合もある。
配列の一部の欠損や挿入をも考慮して、配列どうしの距離を適切に測る方法として編集距離（edit distance）がある。編集距離は、ハミング距離と同様に、２つのショートリードの類似度を示す数値であるが、文字の挿入、削除、または置換によって、一方のショートリードを他方のショートリードに一致させるために必要な操作の最小回数である。編集距離でショートリードの類似性を評価する場合には、上記の複合ソート法をそのまま採用することはできない。
本発明は、大量のショートリードの中から、高速に、編集距離または最大ギャップ（挿入および欠損の総和の閾値）が所定の範囲内にあるショートリードのペアを探索することができる配列解析装置および配列解析方法を提供することを目的とする。
本発明の配列解析装置は、複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析装置であって、探索対象の複数の塩基配列を入力する配列入力部と、編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力する条件入力部と、前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個のすべてのブロックについて、当該ブロックから読み出した部分配列、または、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致するという条件を満たす塩基配列の集合を、等価クラスとして報告する等価クラス生成部と、前記等価クラス生成部から報告された等価クラス内の塩基配列のペアについて、編集距離を計算して、計算によって編集距離ｄ以内であると計算されたペアを示すデータを出力する類似判定部とを備えた構成を有している。
本発明者らは、膨大な量の塩基配列の中から所定の編集距離ｄ以内のペアを探索する計算コストの低い方法を鋭意研究した結果、塩基配列を（ｄ＋ｎ）個のブロックに分割すると、少なくともｎ個のブロックについては、所定の最大オフセットの範囲内でオフセットさせることにより部分配列が一致することを見出した。この知見に基づいて、最初に、前述のような条件（編集距離がｄ以内であることの必要条件）を満たす塩基配列の集合を等価クラスとして求め、等価クラスに含まれる塩基配列どうしの編集距離を計算する本発明を完成させた。本発明の構成によれば、等価クラス生成部から等価クラスとして報告された塩基配列の集合によってできるすべてのペアの中には、編集距離がｄ以下であるペアがもれなく含まれているので、計算コストを削減した上で、所定の編集距離以内にあるすべてのペアを見つけ出すことができる。
また、本発明の別の態様の配列解析装置は、複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析装置であって、探索対象の複数の塩基配列を入力する配列入力部と、編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）と、前記配列入力部に入力される前記複数の塩基配列の挿入および欠損の総和の閾値である最大ギャップｇ（ｇはｄ以下の自然数）を入力する条件入力部と、前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個のすべてのブロックについて、当該ブロックから読み出した部分配列、または、前記最大ギャップｇによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致するという条件を満たす塩基配列の集合を、等価クラスとして報告する等価クラス生成部と、前記等価クラス生成部から報告された等価クラス内の塩基配列のペアについて、編集距離を計算して、計算によって編集距離ｄ以内かつ、挿入および欠損の総和がｇ以内であると計算されたペアを示すデータを出力する類似判定部とを備えた構成を有している。
また、上記の配列解析装置において、前記等価クラス生成部は、前記ｎ個のブロックのうちの１つのブロックについて前記窓枠を前記最大オフセット内でオフセットを変えて読み出した部分配列または当該ブロック内の部分配列が一致するという絞り込み条件を満たす塩基配列の集合を、前記等価クラスの候補となる候補クラスとして求め、当該候補クラスに含まれる塩基配列に対して、前記ｎ個のブロックのうちの別のブロックについて前記窓枠を前記最大オフセット内でオフセットを変えて読み出した部分配列または当該別のブロック内の部分配列が前記絞り込み条件を満たす候補クラスを求めるという処理を、前記ｎ個のブロックについて順次行い、ｎ個のすべてのブロックを用いて絞り込まれた候補クラスを等価クラスとして生成する。このように候補クラスを順次絞り込んでいくことにより、ｎ個のすべてのブロックについて、所定の最大オフセットの範囲内でオフセットさせることにより部分配列が一致するという条件を満たす塩基配列の集合を適切に求めることができる。
また、上記の配列解析装置において、前記等価クラス生成部は、塩基配列に対して、絞り込みに用いられるブロックから前記最大オフセット内のあらゆるオフセット値で前記窓枠をオフセットさせて部分配列を読み出すオフセット部と、前記窓枠をオフセットさせて読み出された部分配列および前記窓枠をオフセットしないで読み出された部分配列を塩基の並び方に応じてソートして同じ配列パターンの部分配列が続く範囲をグループ化するソート部と、前記ソート部にて生成されたグループに複数の部分配列が含まれ、かつ、当該グループの中の少なくとも１つの部分配列のオフセット値が０であるときに、そのグループを候補クラスとして求める候補クラス生成部とを備える。少なくとも１つの部分配列のオフセット値が０でない場合には、少なくとも１つの部分配列のオフセット値が０である候補クラスが他に存在するので、候補クラスとしないことにより、重複する候補クラスの生成を回避できる。
また、上記の配列解析装置において、前記候補クラス生成部は、候補クラスに含まれる塩基配列に関連付けて、候補クラスを絞り込んだブロックの位置、および、候補クラスに含まれる他の部分配列と一致するために用いたオフセット値をメモリに記憶し、前記ｎ個のブロックのうちのｍ（ｍ＜ｎ）個目のブロックを用いて候補クラスを求める際には、前記１つのグループの中で、オフセット値が０であると判定された塩基配列の中に、前のｍ−１個のブロックを用いた候補クラスの絞り込みにおいて、当該塩基配列の部分配列のオフセット値が連続して０であった塩基配列が存在しない場合には、当該グループを候補クラスとしない。
本発明では、ブロックごとに部分配列のオフセット値が独立しているので、同じ塩基配列の中でも、あるブロックにおいてオフセット値を−１とした部分配列が一致し、別のブロックではオフセット値を＋１とした部分配列が一致するということがあり得る。しかし、このような塩基配列は、全体として見れば、オフセットの与え方が一貫していないため、同じ候補クラス内にある他の塩基配列と所望の編集距離以内にはない可能性が高い。本発明の構成によれば、オフセット値が連続して０である塩基配列が一つも含まれていない場合には候補クラスとしないことにより、所望の編集距離のペアが存在しない等価クラスの生成をあらかじめ防止することができる。
また、上記の配列解析装置において、前記候補クラス生成部は、１つのグループ内に、オフセット値の異なる同じ塩基配列の部分配列が存在する場合において、それらのオフセット値の中に０が含まれるときは０を、含まれないときはそれらのオフセット値の中から任意に選択した値を当該部分配列のオフセット値として記憶する。
また、上記の配列解析装置において、前記類似判定部は、前記メモリから、前記等価クラスに含まれる塩基配列のブロックの位置、および、オフセット値を読み出し、等価クラスに含まれる塩基配列の任意のペアのうち、少なくとも一方の塩基配列のオフセット値がすべてのブロックで０であり、かつ、所定のブロック順位規則に基づく順位において前記ブロックの位置よりも前に、前記最大オフセット内でオフセットさせることにより一致する部分配列がないときに、当該ペアの塩基配列について、その編集距離を計算する。
同じ塩基配列のペアが複数の異なる等価クラスに含まれる場合があるが、本発明の構成によれば、それらの中から代表となる等価クラスを一つ決定することができるため、代表となる等価クラスに含まれるペアについてのみ編集距離の計算を行うことが可能となり、重複した計算処理を回避できる。
また、上記の配列解析装置において、前記等価クラス生成部は、前記候補クラス生成部によって複数の候補クラスが生成された場合には、そのうちの１つの候補クラスについて次のブロックを用いた候補クラスの絞り込みを行なう処理を、等価クラスが求まるか、または候補クラスがなくなるまで繰り返し行い、等価クラスが求まるか、または候補クラスがなくなった時点で１つ前のブロックを用いた処理で求まった他の候補クラスについて絞り込みを行う。
また、上記の配列解析装置において、前記等価クラス生成部は、最初のブロックを用いて求められたすべての候補クラスについての絞り込みを終了したときに、組み合わせの異なるｎ個のブロックを選択し、新たに選択されたｎ個のブロックを用いて等価クラスを生成する。これにより、ｎ個のブロックの組み合わせを順次変えて、編集距離ｄ以内にある塩基配列のペアをもれなく含む複数の等価クラスを求めることができる。
また、上記の配列解析装置において、前記等価クラス生成部は、前記新たに選択されたｎ個のブロックを用いて等価クラスを生成する場合において、前記候補クラス生成部において利用できる候補クラスが生成されているときは、当該既に生成されている候補クラスを利用することで、前記ソート部において同一の候補クラスが複数回整列されるのを回避する。これにより、前記ソート部において、同一の候補クラスが複数回整列されることが回避され、再帰的計算を用いてすでに得られた候補クラスを再利用できる。
また、上記の配列解析装置において、前記等価クラス生成部は、前記候補クラスが生成されるごとに、当該候補クラスを利用するｎ個のブロックの組合せのすべてについて、等価クラスが求まるまで絞込みを行い、当該候補クラスを利用するすべてのｎ個のブロックの組合せについて等価クラスを求めた後に、当該候補クラスをメモリ上から解放する。これにより、前記ソート部において同一の候補クラスが複数回整列されるのを回避しつつ、作成された候補クラスを再利用するために候補クラスを記憶するために必要なメモリ容量を小さく抑えることができる。
また、上記の配列解析装置において、前記配列入力部に入力される前記複数の塩基配列は所定の範囲Ｄ内で長さが異なっており、前記条件入力部に入力される編集距離ｄは、ｄ≧Ｄを満たし、前記最大オフセットは、ｄ／２以上の最小の整数である。
また、上記の配列解析装置において、前記配列入力部に入力される前記複数の塩基配列は所定の範囲Ｄ内で長さが異なっており、前記条件入力部に入力される編集距離ｄは、ｄ≧Ｄを満たし、前記最大オフセット量は、ｇ／２以上の最小の整数である。
また、上記の配列解析装置において、前記配列入力部に入力される前記複数の塩基配列は長さが互いに等しく、前記最大オフセットは、ｄ／２以下の最大の整数である。
また、上記の配列解析装置において、前記配列入力部に入力される前記複数の塩基配列は長さが互いに等しく、前記最大オフセットは、ｇ／２以下の最大の整数である。
また、上記の配列解析装置において、前記数値ｎまたは前記分割数（ｄ＋ｎ）は、前記配列解析装置が所定のアルゴリズムに従って決定して前記条件入力部に入力される。
また、本発明の別の態様は、複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析方法であって、この方法は、探索対象の複数の塩基配列を入力する配列入力ステップと、編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力する条件入力ステップと、前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個のすべてのブロックについて、当該ブロックから読み出した部分配列、または、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致するという条件を満たす塩基配列の集合を、等価クラスとして報告する等価クラス生成ステップと、前記等価クラス生成部から報告された等価クラス内の塩基配列のペアについて、編集距離を計算して、計算によって編集距離ｄ以内であると計算されたペアを示すデータを出力する類似判定ステップとを含む構成を有している。
また、本発明の別の態様の配列解析方法は、複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析方法であって、この方法は、（１）探索対象の複数の塩基配列を入力するステップと、（２）編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力するステップと、（３）前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個のブロックに分割するとともに各ブロックにブロック番号を付与するステップと、（４）前記（ｄ＋ｎ）個のブロックの中からｎ個のブロックをブロックセットとして選択するステップと、（５）作業数を１とし、前記選択されたｎ個のブロック中のブロック番号が最小のブロックを作業ブロックをとし、かつ、ステップ（１）で入力されたすべての塩基配列を候補クラスとするステップと、（６）候補クラス内のすべての塩基配列について、前記作業ブロック内の部分配列と、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該作業ブロックからオフセットさせて読み出した部分配列からなる部分配列の集合を生成するステップと、（７）前記部分配列の集合を塩基の並び方に応じてソートしてグループ集合を生成するステップと、（８）前記グループ集合を順にスキャンしていき、同じ配列パターンの部分配列が続く範囲を１つのグループとして、そのグループに複数の部分配列が含まれ、かつ、少なくとも１つの部分配列のオフセット値が０であるときに、作業数がｎであるかを判断するステップと、（９）ステップ（８）において、作業数がｎでないときに、そのグループを候補クラスとして報告するステップと、（１０）ステップ（９）の後に、作業数をインクリメントし、前記作業ブロックを、ステップ（４）にて選択されたｎ個のブロックのうちの次のブロックに変更して、ステップ（６）に戻るステップと、（１１）ステップ（８）において、作業数がｎであるときに、そのグループを等価クラスとして報告するステップと、（１２）ステップ（１１）の後に、当該等価クラスに含まれる塩基配列の任意のペアのうちの少なくとも一方において、オフセット値の履歴にゼロ以外の値がなく、かつ所定の正準性判断に基づいて正準であると判断されたペアにつき、編集距離を計算するステップと、（１３）ステップ（１２）の後に、編集距離がｄ以内である場合に、当該ペアを示すデータを出力するステップと、（１４）ステップ（１３）の後に、前記グループ集合に未スキャン部分があるかを判断するステップと、（１５）ステップ（１４）において、未スキャン部分がある場合に、ステップ（８）に戻るステップと、（１６）ステップ（１４）において、未スキャン部分がない場合に、作業数をデクリメントして、作業ブロックを１つ前のブロックに戻すステップと、（１７）ステップ（１６）の後に作業数が１以上である場合に、ステップ（１４）に戻るステップと、（１８）ステップ（１６）の後に作業数が０になった場合に、前記グループ集合を消去してまだ選択されていないブロックセットがあるかを判断するステップと、（１９）ステップ（１８）において、まだ選択されていないブロックセットがある場合に、ステップ（４）に戻るステップと、（２０）ステップ（１８）において、まだ選択されていないブロックセットがない場合に、処理を終了するステップとを含む構成を有している。
また、上記の配列解析方法は、さらに、（２１）ステップ（４）の後に、前記ブロックセットに含まれるブロックをブロック番号が小さいものから並べて、ブロック番号が小さい方から１または複数のブロックにより構成されるサブセットの候補クラスが記憶されているか否かを判断するステップと、（２２）ステップ（２１）で、候補クラスが記憶されていると判断された場合に、ステップ（５）に代えて、当該サブセットの候補クラスを読み出して、その候補クラスに対応する作業数および作業ブロックを設定するステップとを含んでいる。
また、本発明のさらに別の態様の配列解析方法は、複数の塩基配列の中から、所定の範囲内にある塩基配列のペアを探索する配列解析方法であって、（５１）探索対象の複数の塩基配列を入力するステップと、（５２）編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力するステップと、（５３）前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個のブロックに分割するとともに、各ブロックにブロック番号を付与するステップと、（５４）作業数Ｗを１とし、作業ブロックｂｋをブロック１とし、作業開始ブロックＳを１とするステップと、（５５）絞込み対象候補クラスＡを入力されたすべてのショートリードとするステップと、（５６）絞込み対象候補クラスＡの作業ブロックｂｋを展開・ソートして、グループ集合Ｇ（ｂｋ）を生成して記憶し、作業数Ｗの作業済み最右のブロックＰ（Ｗ）を作業ブロックｂｋとするステップと、（５７）グループ集合Ｇ（ｂｋ）を上からスキャンして、候補クラスの条件を満たす最初のグループを選択してそのグループを絞り込み対象候補クラスＡとし、かつ、作業数Ｗの絞込み対象候補クラスＱ（Ｗ）をその絞り込み対象候補クラスＡとするステップと、（５８）ステップ（５７）の後に、作業数Ｗがｎであるか否かを判断するステップと、（５９）ステップ（５８）にて作業数Ｗがｎでない場合に、作業数Ｗをインクリメントするステップと、（６０）ステップ（５９）の後に、ｂｋ＋１がｄ＋Ｗ以下であるか否かを判断するステップと、（６１）ステップ（６０）にて、ｂｋ＋１がｄ＋Ｗ以下である場合に、作業ブロックｂｋをインクリメントして、ステップ（５６）に戻るステップと、（６２）ステップ（５８）にて作業数Ｗがｎである場合に、絞込み対象候補クラスＡを等価クラスとするステップと、（６３）ステップ（６２）の後に、等価クラスについて、類似判定をするステップと、（６４）ステップ（６３）の後に、グループ集合Ｇ（ｂｋ）に未スキャン部分があるか否かを判断し、未スキャン部分がある場合に、ステップ（５７）に戻るステップと、（６５）ステップ（６４）にて、未スキャン部分がない場合に、グループ集合Ｇ（ｂｋ）をメモリ上から解放し、作業数Ｗをデクリメントするステップと、（６６）ステップ（６５）の後に、Ｗ＝０であるか否かを判断するステップと、（６７）ステップ（６６）にて、Ｗ＝０でない場合に、絞込み対象候補クラスＡを作業数Ｗの絞込み対象候補クラスとするステップと、（６８）ステップ（６０）にて、ｂｋ＋１がｄ＋Ｗより大きい場合に、作業数Ｗをデクリメントし、作業ブロックｂｋをそのデクリメントされた作業数の作業済み最右のブロックＰ（Ｗ）とするステップと、（６９）ステップ（６６）にて、Ｗ＝０である場合に、作業開始ブロックＳが編集距離ｄ以下であるか否かを判断し、作業開始ブロックＳが編集距離ｄより大きい場合に、処理を終了するステップと、（７０）ステップ（６９）にて、作業開始ブロックＳが編集距離ｄ以下である場合に、作業開始ブロックＳをインクリメントして、作業数Ｗを１にリセットして、ステップ（５５）に戻るステップとを有する。
本発明のさらに別の態様は、コンピュータで実行されることにより、コンピュータに上記の方法を実行させるコンピュータプログラムである。
本発明の配列解析装置によれば、計算コストを削減して、高速に、所定範囲内にあるすべてのショートリードのペアを見つけ出すことができる。
本発明の実施の形態における配列解析装置の入力と出力を説明する図 （ａ）ショートリードのペアを示す図 （ｂ）編集距離を説明する図 （ａ）編集距離の定理を説明する図（挿入と削除の総数の上限が指定されていない場合） （ｂ）編集距離の定理を説明する図（挿入と削除の総数の上限が指定されている場合） （ａ）配列の例を示す図 （ｂ）編集距離の定理を具体例で説明する図 本発明の実施の形態における配列解析装置のブロック図 本発明の実施の形態におけるブロック分割の例を示す図 本発明の実施の形態におけるオフセット部の動作を説明する図 本発明の実施の形態におけるオフセット履歴の情報が付加された部分配列の集合を示す図 本発明の実施の形態におけるソート部によってソートされた部分配列を示す図 本発明の実施の形態における候補クラス記憶部に記憶される情報を示す図 本発明の第１の実施の形態におけるブロックマスクによる距離計算対象の絞込みを説明する図 本発明の第１の実施の形態におけるブロック１、ブロック２、ブロック３がブロックセットとして選択された場合の絞込み手順を説明する図 本発明の第１の実施の形態におけるブロック１、ブロック２、ブロック４がブロックセットとして選択された場合の絞込み手順を説明する図 （ａ）本発明の第１の実施の形態における等価クラスの情報および等価クラスに含まれるショートリードの配列パターンの例を示す図 （ｂ）本発明の第１の実施の形態における正準性判定の条件３の判定例を示す図 （ｃ）本発明の第１の実施の形態におけるＳ22とＳ75のペアの例を示す図 （ｄ）本発明の第１の実施の形態におけるＳ56とＳ75のペアの例を示す図 本発明の第１の実施の形態における配列解析装置の処理フロー図 本発明の第２の実施の形態における絞込み手順を説明する図 本発明の第２の実施の形態における絞込み手順を説明する図 本発明の第２の実施の形態における絞込み手順を説明する図 本発明の第２の実施の形態における絞込み手順を説明する図 本発明の第２の実施の形態における配列解析装置の処理フロー図 従来の複合ソート法を説明する図
以下、本発明の実施の形態について説明する。本発明の実施の形態の配列解析装置は、ほぼ同じ長さの膨大な量のショートリードが与えられたときに、その中から編集距離ｄ以内のペアを類似のペアとして、重複なく、完全に列挙することを目的としている。配列解析装置に入力されるショートリードには、それぞれ固有のＩＤが付与されている。本明細書では、ショートリードに付与されたＩＤを「インデクス」と称し、「Ｓ」に添え字を付す形式で表記する。ショートリードは、塩基配列であるので、「Ａ」、「Ｃ」、「Ｇ」、「Ｔ」という文字の組合せからなる配列である。
図１に示すように、本実施の形態の配列解析装置は、入力として複数のショートリード（Ｓ1，・・・，ＳN）が与えられたときに、編集距離ｄ以内のペア｛Ｓ1， Ｓ2｝、｛Ｓ1， Ｓ100｝、 ｛Ｓ2， Ｓ10｝、・・・を出力する装置である。編集距離としては、例えば、挿入と削除の総和が５以内で、編集距離が１０以内というように、挿入と削除の総和の最大値を指定することもできる。
配列解析装置が扱う複数のショートリードは、完全に長さが等しいものである必要はない。但し、入力される複数のショートリードの中で最も短いショートリードと最も長いショートリードとの長さの差が編集距離ｄ以内であることが条件となる。
以下、編集距離について詳しく説明する。編集距離とは、上述のように、文字の挿入、削除、または置換によって、一方のショートリードを他方のショートリードに一致させるために必要な操作の最小回数である。例えば、図２（ａ）のショートリードのペア（Ｓ1とＳ2）があった場合に、図２（ｂ）に示すように、このＳ1の第２文字目を削除して、第６文字目と第７文字目の間にＧを挿入し、さらに第１１文字目のＴをＡに置換するとＳ2と一致する。よって、この例では、Ｓ1について、１回の削除、１回の挿入、１回の置換という３回の操作によってＳ2と一致することになるので、Ｓ1とＳ2の編集距離は３である。
編集距離については、次の定理が成り立つ。いま、文字列Ｓ1と文字列Ｓ2の編集距離がｄであるとすると、図３（ａ）に示すように、Ｓ1、Ｓ2を中心をそろえて並べ、ｄ＋ｎ個（ｎは任意の自然数）のブロックに分割した場合、ｎ個のブロックが、ずれ幅ｄ／２以内で完全一致する。ここで、ｄ／２が割り切れない時は、切り上げる（ただし、Ｓ1とＳ2の長さが同じ場合は、切り捨てる）。例えば、ｄ=３のときは、一般的には、ずれ幅２以内となる（ただし、Ｓ1、Ｓ2が同じ長さのときはずれ幅１以内となる）。
挿入と削除の総数の上限ｇ（ｇはｇ≦ｄを満たす自然数）が指定されているときは、図３（ｂ）に示すように、Ｓ1、Ｓ2を中心をそろえて並べ、ｄ＋ｎ個（ｎは任意の自然数）のブロックに分割した場合、少なくともｎ個のブロックでは、ずれ幅ｇ／２以内で完全一致する。ここで、ｇ／２が割り切れない時は、切り上げる（ただし、Ｓ1とＳ2の長さが同じ場合は、切り捨てる）。例えば、ｇ=３のときは、一般的には、ずれ幅２以内となる（ただし、Ｓ1、Ｓ2が同じ長さのときはずれ幅１以内となる）。
上記の定理を具体例で説明する。編集距離ｄ＝３、ｎ＝２として、図４（ａ）に示す配列Ｓ1、Ｓ2が与えられたとする。この場合は、配列を（ｄ＋ｎ＝）５ブロックに分割する。この５つのブロックの中からｎ（＝２）個のブロックを選択する組合せは、5Ｃ2＝１０通りある。上記の定理より、Ｓ1、Ｓ2が編集距離ｄ（＝３）以内であるのならば、１０通りある組合せの中で、少なくとも１つの組合せにおいて、２つのブロックがずれ幅１以内で一致することになる。
実際には、図４（ｂ）に示すように、Ｓ1とＳ2は、ブロック１とブロック３、ブロック１とブロック４、ブロック３とブロック４の組合せで、ずれ幅１以内で部分配列が一致する。具体的には、読出し範囲を特定する窓枠をずらして部分配列を読み出し、部分配列の配列パターンを比較したときに、配列パターンが一致すると判断している。即ち、ブロック１については、窓枠のずれ量をゼロとしたときに、窓枠内の配列パターンが「ＡＴ」で一致し、ブロック３については、配列Ｓ1に対してＳ2の窓枠をずれ量−１だけずらしたときに、窓枠内の配列パターンが「ＡＧＣ」で一致し、ブロック４については、窓枠のずれ量をゼロとしたときに、窓枠内の配列パターンが「ＧＡＴ」で一致する。
上記の定理を用いて、本実施の形態の配列解析装置では、複数のショートリードの中から編集距離ｄ以下のショートリードのペアを探索するために、入力された複数のショートリードの各々を（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個（ｎは１以上の自然数）のすべてのブロックにおいて、窓枠を上記のように定義されるずれ幅（以下単に「最大オフセット」という）の範囲内で窓枠内の配列パターンが一致するという条件を満たすショートリードの集合を、等価クラスとして出力する。選択するｎ個のブロックの組合せを変えることで、次々に等価クラスが出力される。
この等価クラス内のショートリードのすべてのペアが編集距離ｄ以内にあるわけではないが、仮に、この等価クラス内のショートリードのすべてのペアについて編集距離ｄ以内にあるかを実際に計算したとしても、シーケンサから与えられた複数のショートリードのすべてのペアに対して計算をする場合と比較すると格段に計算すべきペアの数は減少することになる。本実施の形態では、後述するように、異なる等価クラスに含まれる同一のショートリードのペアについては、重複して編集距離を計算・報告しないようにしている。
以下、図面を参照して本実施の形態の配列解析装置を説明する。図５は、本実施の形態の配列解析装置の構成を示すブロック図である。図５において、配列解析装置１０は、配列入力部１１と、条件入力部１２と、等価クラス生成部１３と、類似計算部１４とを備えている。なお、本実施の形態の配列解析装置１０は、以下に説明する各処理を実行するモジュールを有するプログラムをコンピュータによって実行することによって実現することとしてもよい。このようなプログラムも本発明に含まれる。
配列入力部１１には、シーケンサから出力された複数のショートリードのデータ（以下、単に「ショートリード」ともいう）が入力される。配列入力部１１は、入力されたショートリードを等価クラス生成部１３に出力する。ショートリードの数量は、例えば数千万個である。また、ショートリードの長さは、例えば３５〜５０程度である。なお、本発明は、ショートリードの数量が多いほど計算コスト削減の効果が顕著になる。また、ショートリードの長さは、上記の長さに限られるものではなく、より短くてもよく、より長くてもよい（例えば２００以上であってよい）。
入力されるショートリードは、すべて同一の長さであってもよく、互いに長さが異なっていてもよい。但し、編集距離ｄ以内にあるショートリードのペアを探索する場合には、入力されるショートリードの最長長さと最短長さとの差分Ｄはｄ以下でなければならない。
シーケンサから配列解析装置１０に与えられたショートリードが配列解析装置１０内のハードディスク等の記憶装置に保存されてもよい。この場合は、配列入力部１１は記憶装置からショートリードを読み出して、等価クラス生成部１３に出力する。
条件入力部１２には、探索したいペアの編集距離の最大値である編集距離ｄの値、ショートリードをブロックに分割する際の分割数ｂをｂ＝ｄ＋ｎとして決定するためのｎの値が入力される。ｎは１以上の任意の自然数である。ｎはユーザが任意の値を入力してもよいし、ショートリードの長さや数量等に応じて所定のアルゴリズムで計算された値が入力されてもよい。編集距離ｄおよび最大ギャップｇは、ユーザが所望する任意の値を入力する。配列解析装置１０は、ｎを計算して求める構成を有して、計算により得られた結果を条件入力部１２に入力するようにしてもよい。
等価クラス生成部１３は、配列入力部１１に入力された複数のショートリードに対して、条件入力部１２に入力されたｄおよびｎの値に基づいて、編集距離ｄ以内にあるペアが存在し得る複数のショートリードの集合である等価クラスを出力する。条件入力部１２に編集距離ｄとともに最大ギャップｇが入力された場合には、等価クラス生成部１３は、配列入力部１１に入力された複数のショートリードに対して、条件入力部１２に入力されたｇおよびｎの値に基づいて、最大ギャップｇ以内にあるペアが存在し得る複数のショートリードの集合である等価クラスを出力してもよい。以下の説明では、主に条件入力部１２に編集距離ｄが入力され最大ギャップｇは入力されていない場合について説明する。
等価クラス生成部１３は、ブロック分割部１３１と、ソート対象指定部１３２と、オフセット部１３３と、ソート部１３４と、候補クラス生成部１３５と、候補クラス記憶部１３６とを有している。ブロック分割部１３１は、配列入力部１１より入力されたショートリードの各々を、対応する部分配列ごとに比較する処理で用いる処理単位をブロックとして、当該ブロックごとに分割した状態で記憶している。このときのブロック数は、条件入力部に入力されたｄおよびｎの値を用いて（ｄ＋ｎ）とする。
この結果、各ショートリードは、（ｄ＋ｎ）個の部分配列に分割される。ブロックは左から順に順位が定義されており、最左のブロックをブロック番号１番として、右にいくにつれて番号が増加するように各ブロックにブロック番号が付与される。本明細書では、ブロック番号ｋ番のブロックを「ブロックｋ」と表記する。各ショートリードの同一のブロック番号の部分配列は以下の処理においてブロックが対応する部分配列として扱われる。
上述のように、一般的にはショートリードの長さはすべて等しいわけではないので、ブロック分割部１３１は、各ショートリードの中心をそろえて（ｄ＋ｎ）個のブロックに分割する。ショートリードの長さが奇数の場合と偶数の場合とでは、中心は完全にそろわないが、その場合にも、すべての奇数のショートリードの中心がすべての偶数のショートリードの中心の例えば左側に来るようにして、全体として中心のずれが０．５文字になるようにした上で、同じ列に並ぶ文字が同じブロックに所属するように、すべてのショートリードを分割する。なお、各ブロックの幅、即ち部分配列の長さは必ずしも互いに等しくなくてもよい。
図６は、ブロック分割の例を示す図である。図６の例は、Ｓ1〜Ｓ3のショートリードがあった場合において、Ｓ1〜Ｓ3の長さがそれぞれ１５、１４、１３であったときのブロック分割の例を示している。図６に示すように、奇数長であるＳ1およびＳ3の中心は、それぞれ第８番目および第７番目の文字の中心であり、偶数長であるＳ2の中心は、第７番目の文字と第８番目の文字の間である。この場合に、奇数長のショートリードについては、偶数長のショートリードよりも左に半文字分ずらすことで、奇数長のショートリードおよび偶数長のショートリードを含むすべてのショートリードの中心がそろうことになる。
ソート対象指定部１３２は、処理の過程においてどのショートリードのどのブロックをソート対象とするかを指定する。等価クラス生成部１３は、入力された複数のショートリードをブロックに分割して、ブロックごとに評価することで、入力された複数のショートリードのあらゆる組合せのペアから編集距離がｄ以内にないペアを除外していく絞込みを行う。換言すれば、ソート対象指定部１３２は、この絞り込みに用いられるブロック内に含まれる絞り込み対象のショートリードの部分配列を指定する。絞込みの詳細は後述する。
オフセット部１３３は、ソート対象指定部１３２により指定されたショートリードの集合に含まれる各ショートリードについて、ソート対象指定部１３２により指定されたブロックから窓枠をオフセットして読み出した部分配列を図示しないメモリ上に展開する。このために、オフセット部１３３は、まず、ソート対象指定部１３２により指定されたショートリードの集合に含まれる各ショートリードの、ソート対象指定部１３２により決定されたブロックの部分配列を読み出すとともに、当該ブロックを基準として最大オフセット以下の各オフセット値で窓枠をずらして、部分配列を読み出す。
このとき、ブロック分割部１３１から読み出された各部分配列には、その部分配列が属するショートリードのインデクスの情報とオフセット値の情報が付加されている。以下、オフセット部１３３が上記のようにブロックから窓枠をずらして読み出した部分配列を「オフセット部分配列」ともいう。また、ブロック分割部１３１にて分割されて生成されたブロック内に収まる部分配列を「オフセット部分配列」と特に区別するときは、ブロック分割部１３１にて分割されて生成されたブロック内に収まる部分配列を「原部分配列」ともいう。両者を区別しないときは、単に「部分配列」という。
最大オフセットは、上述のように、ショートリードの長さが均一であるか否か、および編集距離ｄ、または挿入と削除の総数の上限が分かっている場合にはその総数の上限ｇを用いて決定される。例えば、ショートリードの長さが１０文字以内でばらついている場合において、挿入と削除の総数がｇ＝５以内である場合には、ｇ／２＝２．５となるが、ショートリードの長さがばらついているので、２．５を切り上げた３が最大オフセットとなる。この場合、オフセット部１３３は、ソート対象指定部１３２により指定されたショートリードの各々について、ソート対象指定部１３２により指定されたブロックから、窓枠を−３ずらして読み出したオフセット部分配列、窓枠を−２ずらして読み出したオフセット部分配列、窓枠を−１ずらして読み出したオフセット部分配列、窓枠をずらさずに読み出した原部分配列、窓枠を＋１ずらして読み出したオフセット部分配列、窓枠を＋２ずらして読み出したオフセット部分配列、および窓枠を＋３ずらして読み出したオフセット部分配列を生成する。
図７は、オフセット部１３３の動作を説明する図である。図７に示すように、ソート対象指定部１３２がショートリードの集合｛Ｓ1、Ｓ24、Ｓ97、Ｓ257、……｝の「ブロック２」をソート対象として指定すると、オフセット部１３３は、ブロック分割部１３１から該当する部分配列を読み出す。この例では、最大オフセットは１であるので、オフセット部１３３は、ブロック２の原部分配列とともに、ブロック２から−１ずれた位置の部分配列およびブロック２から＋１ずれた位置の部分配列をそれぞれオフセット部分配列として読み出す。
図７において、「ＳＲ」はショートリードのインデクスを表し、「ｐ」はオフセット値を表す。図に示すように、オフセット部１３３によってブロック分割部１３１から読み出される原部分配列およびオフセット部分配列には、それぞれ、当該部分配列が所属するショートリードのインデクスとともに、当該部分配列が指定のブロックから窓枠をどれだけずらして読み出されたかを示すオフセット値が付加されている。なお、ｐ＝０はオフセット値がゼロ、即ちその部分配列が原部分配列であることを示している。
オフセット部１３３は、各部分配列に対して、その部分配列を読み出したときのオフセット値に、その部分配列が所属するショートリードの過去のすべてのオフセット値を加えて、オフセット履歴として付加する。図８は、過去のすべてのオフセット値と当該部分配列を読み出したときのオフセット値とがオフセット履歴として付加された部分配列の集合を示している。図８の例では、過去のブロック１において、Ｓ1、Ｓ24、Ｓ97、Ｓ257は、それぞれオフセット０、１、０、０で候補クラス（後述する）として判断されたため、それらの過去のオフセット値が、各部分配列を読み出した際のオフセット値とともにオフセット履歴として、各部分配列に付加されている。
ソート部１３４は、オフセット部１３３にて生成されたオフセット部分配列および原部分配列のすべてを塩基の並び順に応じてソートし、整列された部分配列の集合を形成する。このとき、ソート部１３４は、基数交換ソートによって部分配列をソートするので、グループ集合では同一の配列パターンを有する部分配列はグループ化されている。以下、ソートされて同一の配列パターンを有する部分配列ごとにグループ化された部分配列の集合を「グループ集合」という。具体的には、部分配列は上述のようにＡ、Ｃ、Ｇ、Ｔの組み合わせからなる配列であるので、ソート部１３４は、これを辞書順に並べ替える。このように、部分配列をソーティング（整列）するのは、原部分配列およびオフセット部分配列の中で一致する部分配列をまとめるためである。図９は、グループ集合の例を示す図である。
候補クラス生成部１３５は、グループ集合を上から順にスキャンして、ソート部にて生成されたグループごとに注目し、注目するグループが候補クラスであるか否かを判断する。候補クラスであると判断する条件は、次の条件１および条件２である。
条件１：そのグループに複数の部分配列が含まれていること
条件２：少なくとも１つの部分配列のオフセット履歴に含まれるオフセット値がすべて０であること
これらの条件１および条件２をいずれも満足する場合には、当該グループは候補クラスと判断される。
図９の例では、条件１および条件２を同時に満足するグループは、文字列「ＧＣＴ」のグループおよび文字列「ＴＧＣ」のグループである。従って、図９の例では、候補クラス生成部１３５は、この「ＧＣＴ」のグループおよび文字列「ＴＧＣ」のグループを候補グループであると判断する。なお、「ＴＴＧ」のグループは、複数の部分配列が含まれてはいるが、オフセット履歴に含まれるオフセット値がすべて０であるという条件を満たす部分配列がないため、候補クラスとは判断されない。これに対して、「ＧＣＴ」のグループでは、Ｓ1のオフセット履歴に含まれるオフセット値がすべて０であり、「ＴＧＣ」のグループは、Ｓ257のオフセット履歴に含まれるオフセット値がすべて０であるので、これらのグループは候補グループであると判断される。
候補クラス生成部１３５は、候補クラスであると判断したグループに含まれる部分配列のインデクスをソート対象指定部１３２に報告する。また、候補クラス生成部１３５は、候補クラスであると判断したグループに含まれる部分配列およびそのオフセット履歴に、その候補クラスが生成されるまでにソート対象となったブロックの履歴と関連付けて候補クラス記憶部１３６に保存する。
なお、このとき、候補クラス生成部１３５は、同一のショートリードに由来する複数の部分配列が１つの候補クラスに重複して含まれないようにする。例えば、オフセット「０」の場合に部分配列が「ＡＡＡ」、オフセット「１」の場合にも部分配列が「ＡＡＡ」となるような塩基配列である。このように、候補クラス生成部１３５は、候補クラスと判断したグループの中に、同一のショートリードに由来する複数の部分配列が含まれている場合において、それらの部分配列の中にオフセットが０である部分配列があるときは、当該オフセットが０を、それらの部分配列の中にオフセットが０である部分配列がないときはそれらの部分配列のオフセット値のうちから任意に選択した値のみを当該同一のショートリードに由来する複数の部分配列のオフセット値として採用する。即ち、オフセット履歴中のオフセット値がすべてゼロのものがあれば、そのオフセット履歴を当該ショートリードのオフセット履歴とし、他のオフセット履歴については、重ねてソート対象指定部１３２に報告したり候補クラス記憶部１３６に保存したりしないようにする。
候補クラス生成部１３５は、作業数（後述）が最大値（条件入力部１２に入力されたｎが作業数の最大値となる）のときに候補クラスである判断したショートリードの集合を等価クラスとして類似判定部１４に出力（報告）する。具体的には、候補クラス生成部１３５は、等価クラスに含まれるショートリードのインデクス、その候補クラスが生成されるまでにソート対象となったブロックの履歴、およびオフセット履歴の情報を類似判定部１４に出力する。
候補クラス記憶部１３６は、ハードディスクで構成され、上述のように、候補クラス生成部１３５から報告を受けた候補クラスを記憶する。候補クラスの情報は、その候補クラスが生成されるまでにソート対象となったブロックの履歴と関連付けられて記憶される。このブロックの履歴は、即ち、その候補クラスに含まれるショートリードが最大オフセット内で一致するブロックを示す情報である。また、候補クラス記憶部１３６に記憶される候補クラスには、当該候補クラスに含まれる各ショートリードのインデクスのそれぞれに対して、当該ショートリードが過去に当該候補クラス内の他のショートリードと一致した各ブロックにおいてどれだけのオフセットで一致したのかを示すオフセット履歴の情報が付加されている。
図１０は、候補クラス記憶部１３６に記憶される情報を示す図である。図１０において、具体的なデータは、図７〜図９の例に対応している。図１０に示すように、一般的には、１つのブロック履歴には複数の候補クラスが対応している。図中、「ｒ」は「ｒｏｏｔ」の略記であり、複数のショートリードの全体を表している。
次に、ソート対象指定部１３２によるソート対象の指定について説明する。編集距離がｄであり、配列の分割数がｂ（ｂ＝ｄ＋ｎ）であるとすると、上記で説明した定理により、編集距離がｄ以内にあるショートリードは、必ず、少なくともｎ個のブロック（ｂ個のブロック中のｎ個のブロックの組合せは複数とおりあるがそのうちの少なくとも１つの組合せ）において、最大オフセット内で部分配列が一致するはずである。従って、少なくともｎ個のブロックにおいて最大オフセット内で部分配列が一致するショートリードのグループの中のペアについてのみ実際の編集距離を計算すればよい。そこで、等価クラス生成部１３は、ｂ個のブロックの中から選択するｎ個のブロック組合せを変更しながら、選択されたｎ個のブロックについて、ショートリードの部分配列が最大オフセット内で一致するか否かを判断するために、ブロックを１つずつ検討して、一致しなかったショートリードを対象から除外していくという、段階的な絞込みを行う。
図１１は、ブロックマスクによる距離計算対象の絞込みを説明する図である。本明細書では、距離計算対象の絞込みについて、２つの実施の形態を説明する。まず、図１１〜図１５を参照して、第１の実施の形態を説明する。図１１は、編集距離がｄ＝２であり、ブロック番号がｂ＝ｄ＋ｎ＝５（ｎ＝３）である例を示している。図中、丸の中の数字は作業を行うブロック（作業ブロック）のブロック番号を示している。ソート対象指定部１３２は、５つのブロックのうちの２つをマスクして３つを選択する。この選択の方法は、5Ｃ3（＝１０）通りある。ソート対象指定部１３２は、図１１に示すようなツリー構造で階層的にブロックを選択していきながら絞込みを行う。
ソート対象指定部１３２は、まず、３つのブロックを選択する（２つのブロックをマスクする）。以下、選択されたブロックの組合せを「ブロックセット」ともいう。ソート対象指定部１３２は、ブロック番号の若いほうから順にブロックを選択してブロックセットを作る。最初は、ブロック１、ブロック２、ブロック３が選択される。そして、ソート対象指定部１３２は、入力されたすべてのショートリードについて、未作業であってかつブロック番号が最も若いブロック１をソート対象として指定する。そして、ソート対象指定部１３２にて指定された対象（すべてのショートリードのブロック１）について、オフセット部１３３でオフセット部分配列を作成し、ソート部１３４にて原部分配列と合わせてソートしてグループ集合を生成し、候補クラス生成部１３５にて候補クラスを生成する。
候補クラス生成部１３５は、候補クラスに含まれる部分配列を含むショートリードのインデクスおよびその各部分配列のオフセット値を候補クラス記憶部１３６に記憶するとともに、ソート対象指定部１３２に報告する。ソート対象指定部１３２は、候補クラス生成部１３５から報告を受けた候補クラスに含まれるショートリードを次の段階の作業のソート対象とする。ソート対象指定部１３２は、既にブロック１、ブロック２、ブロック３というブロックセットを選択しているので、未作業であってかつブロック番号が最も若いブロック２を作業ブロックとして選択する。即ち、ソート対象指定部１３２は、候補クラス生成部１３５から報告を受けた候補クラスに含まれるショートリードのブロック２を次のソート対象として指定する。
オフセット部１３３は、ソート対象指定部１３２にて指定されたソート対象について、原部分配列およびオフセット部分配列を含む部分配列を生成し、ソート部１３４はオフセット部１３４にて生成された部分配列をソートしてグループ集合を生成し、候補クラス１３５は候補クラスを生成する。そして、上記と同様にして、候補クラス生成部１３５は、候補クラスを候補クラス記憶部１３６に記憶するとともに、ソート対象指定部１３２に報告する。
ソート対象指定部１３２は、報告を受けた候補クラスに含まれるショートリードの、既に選択したブロック１、ブロック２、ブロック３のうちの未作業かつ最も若いブロックであるブロック３をソート対象として指定する。そして、上記と同様にして、ソート対象指定部１３２にて指定されたソート対象について、原部分配列およびオフセット部分配列を含む部分配列を生成し、ソート部１３４はオフセット部１３４にて生成された部分配列をソートしてグループ集合を生成し、候補クラス生成部１３５は候補クラスを生成する。
このように、すべてのショートリードのあるブロックをソート対象として候補クラスを生成する作業を作業数１の作業と称し、次のソート対象に対する作業を作業数２の作業と称し、このような作業が進んで、一般的に第ｋ回目にソート対象指定部１３２にてソート対象として決定された対象に対する作業を作業数ｋの作業という。また、各作業数で作業の対象となるブロックを「作業ブロック」という。図１１の例では、ｎ＝３であり、ソート対象指定部１３２は、３つのブロックを選択するので、作業数Ｗが３になった時点で、選択したブロックすべてについて作業が終了したことになる。
候補クラス生成部１３５は、最終作業数での作業を終了したときに生成された候補クラスを等価クラスとして、その等価クラスに含まれるショートリードのインデクスおよびその等価クラスに含まれるショートリードの、過去の作業ブロックでのオフセット履歴の情報を類似判定部１４に出力する。そして、候補クラス生成部１３５は、ソート対象指定部１３２に最終作業数で作業が終了したことを報告する。
ソート対象指定部１３２は、選択したブロックセットについて、必要なすべての作業が終わると、選択するブロックを変更して新たなブロックセットを決定する。本実施の形態では、ソート対象指定部１３２は、ブロック１、ブロック２、ブロック３というブロックセットの次にブロック番号が小さい組合せであるブロック１、ブロック２、ブロック４を選択して新たなブロックセットとする。
以下同様にして、この３つのブロックについて段階的な絞込みの作業を行い、１０通りのすべての組合せのブロックセットについて、上記のような段階的な検索を行うことで、すべての等価クラスが報告される。しかしながら、次のブロック１、ブロック２、ブロック４についてみると、作業数１の作業として、入力されたすべてのショートリードのブロック１をソート対象とした作業を行い、次に、作業数２の作業として、作業数１の作業で生成された候補クラスのブロック２をソート対象とした作業を行って候補クラスを生成するという一連の作業は、ブロック１、ブロック２、ブロック３のブロックセットについて作業をした際に既に行っており、この一連の作業により作成された候補クラスは、候補クラス記憶部１３６に記憶されている。
そこで、ソート対象指定部１３２は、ブロック１、ブロック２、ブロック４をブロックセットとして選択した際には、すでにブロック１からブロック２への絞込みで作成されている候補クラスを利用して作業数３の作業をブロック４に対して行うように、ソート対象を指定する。具体的には、ソート対象指定部１３２は、すでにブロック１からブロック２への絞込みで作成されている候補クラスに含まれるショートリードのブロック４をソート対象として指定する。
一般的には、ソート対象指定部１３２は、既に作成されている候補クラスを利用できるか否かを次のようにして判断する。すなわち、ソート対象指定部１３２は、複数のブロックの組み合わせを新たなブロックセットとして選択したときに、この複数のブロックをブロック番号が小さいものから順に並べて一番最後のブロックを除いたブロックの組合せで既に作業が行われていないかを判断する。この判断のために、ソート対象指定部１３２は、ブロックの組合せのうち、作業済みのブロックの組合せを記憶しておいてもよいし、または、新たに選択したブロックの組合せをブロック番号が若いものから順に並べて一番最後のブロックを除いたブロックの組合せについて、候補クラス記憶部１３６に候補クラスが記憶されているかを直接確認してもよい。
ソート対象指定部１３２は、選択した複数のブロックをブロック番号が若いものから順に並べて一番最後のブロックを除いたブロックの組合せが作業済みでなかった場合には、さらに、残ったブロックの組合せの中で最もブロック番号が大きいブロックを除いて、既に作業が済んでいないかを判断する。このようにして選択した複数のブロックをブロック番号が大きいものから順に除いていって、最後まで作業済みのブロックの組合せがない場合には、上記で説明したブロック１、ブロック２、ブロック３の例のようにして作業を行う。以下、ブロックセットのブロックをブロック番号が小さいものから並べて、ブロック番号が大きいものから順に除いていってできるブロックの組合せをブロックの「サブセット」という。
図１１の例では、ブロック１、ブロック３、ブロック４がブロックセットとして選択されたときは、ブロック４を除いたサブセット（ブロック１、ブロック３）の作業は未だ行われていないので、次にブロック３も除いて、作業数１でブロック１を対象とするという作業が行われていないかを判断する。作業数１でブロック１を対象とするという作業は既に行われているので、この作業を繰り返し行うことはせず、この作業の結果既に作成されている候補クラスを利用して、その候補クラスに含まれるショートリードのブロック３をソート対象とするところから始める。
図１１の例において、ブロック２、ブロック３、ブロック４が選択された際には、作業数１でブロック２を対象とするという作業は未だ行われていないので、上記で説明したブロック１、ブロック２、ブロック３の例と同様にして最初から作業を行う。このようにして、重複した処理を回避して作業数を減らすことで、処理負担を軽減し、かつ高速に等価クラスを報告できる。
以下、ソート対象指定部１３２にてあるブロックセットが選択された場合の、そのブロックセットに対する、距離計算対象の絞込みの手順について、更に詳細に説明する。図１２は、ブロック１、ブロック２、ブロック３がブロックセットとして選択された場合のこのブロックセットに対する絞込み手順を説明するための図である。
ソート対象指定部１３２は、最初に、作業数１（Ｗ＝１）の作業のソート対象として、入力されたすべてのショートリードのブロック１を指定する。そして、この対象について上記のようにして、オフセット部１３３でオフセット部分配列をメモリ上に展開し、ソート部１３４で原部分配列とオフセット部分配列をソートしてグループ集合Ｇ１を生成する。候補クラス生成部１３５は、グループ集合を上からスキャンしていき、候補クラス作成条件を満たすグループが発見されたら、その候補クラス（候補クラスＣＣ(1)１）をソート対象指定部１３２に報告する。本実施の形態では、候補クラスＣＣ(1)１を報告する前に、候補クラスＣＣ(1)１の最下列の位置Ｅ１を記憶しておく。
ソート対象指定部１３２は、報告を受けた候補クラスＣＣ(1)１に含まれるショートリードのブロック２をソート対象として指定する。そして、ソート対象指定部１３２が指定した対象、即ち候補クラスＣＣ(1)１に含まれるショートリードのブロック２について、オフセット部１３２がオフセット部分配列を生成し、ソート部１３３がソートを行いグループ集合Ｇ２を生成する（ステップＳ１１）。以下、候補クラス生成部１３５から報告された候補クラスに含まれるショートリードの、ソート対象指定部１３２が指定した作業ブロックについて、オフセット部１３２がオフセット部分配列をメモリ上に展開し、ソート部１３３がソートを行って配列パターンが同一である部分配列同士をグループ化することを当該候補クラスの当該ブロックを「展開・ソートする」と表現する。
候補クラス生成部１３５は、候補クラスＣＣ(1)１のブロック１を展開・ソートして生成されたグループ集合Ｇ２を上から順にスキャンしていき、候補クラスの生成条件を満たすグループが存在すると、そのグループを候補クラス（候補クラスＣＣ(1-2)１１）としてソート対象指定部１３２に報告する。本実施の形態では、候補クラスＣＣ(1-2)１１を報告する前に、候補クラスＣＣ(1-2)１１の最下列の位置Ｅ２を記憶しておく。そして、ソート対象指定部１３２は、候補クラスＣＣ(1-2)１１のブロック３をソート対象として指定する。この指定に基づいて、オフセット部１３２およびソート部１３３は、候補クラスＣＣ(1-2)１１のブロック３を展開・ソートしてグループ集合Ｇ３を生成する（ステップＳ１２）。
候補クラス生成部１３５は、展開・ソートにより得られたグループ集合Ｇ３を上から順にスキャンしていき、候補クラスの条件を満たすグループを発見すると、そのグループを候補クラスであると判断する。そして、作業数が最終作業数３であるため、この候補クラスＣＣ(1-2-3)１１１を等価クラスとして、そのクラスに含まれるショートリードのインデクスの情報および各ショートリードのオフセット履歴の情報を類似判定部１４に出力する（ステップＳ１３）。なお、本実施の形態では、候補クラスＣＣ(1-2-3)１１１を報告する前に、候補クラスＣＣ(1-2-3)１１１の最下列の位置Ｅ３を記憶しておく。
類似判定部１４は、候補クラス生成部１３５から報告された等価クラス（候補クラスＣＣ(1-2-3)１１１）について、当該等価クラスに含まれるショートリードのペアの編集距離を計算する。類似判定部１４については後述する。等価クラス（候補クラスＣＣ(1-2-3)１１１）について類似判定部１４による計算が終了すると、グループ集合Ｇ３に戻って、再び上から順に候補クラスの条件を満たすグループがないかを探索する。この際、最上の列からスキャンして、すでに候補クラスであると判断されたグループを再び候補クラスと判断しないようにして次の候補クラスを探してもよいが、本実施の形態では、候補クラスＣＣ(1-2-3)１１１を報告する前に、候補クラスＣＣ(1-2-3)１１１の最下列の位置を記憶してあるので、その列から下に向けて次の候補クラスを探索する。
グループ集合Ｇ３のすべての候補クラスが等価クラスとして報告されると、すなわち、グループ集合Ｇ３の最後まで探索が終了すると、候補クラス生成部１３５は、グループ集合Ｇ２に戻る（ステップＳ１４）。このとき、既に展開・ソートされているグループ集合Ｇ３はメモリ上から解放される。候補クラス生成部１３５は、記憶されている前回の探索終了位置Ｅ２から候補クラスの探索を再開し、次の候補クラスＣＣ(1-2)１２を生成してソート対象指定部１３２に報告する。ソート対象指定部１３２は、候補クラスＣＣ(1-2)１２のブロック３をソート対象と指定し、オフセット部１３３およびソート部１３４は、決定された候補クラスＣＣ(1-2)１２のブロック３を展開・ソートする（ステップＳ１５）。
候補クラス生成部１３５は、候補クラスＣＣ(1-2)１２のブロック３を展開・ソートして得られたグループ集合Ｇ４を上から順にスキャンしていって、候補クラスＣＣ(1-2-3)１２１を発見すると、これを等価クラスとして類似判定部１４に報告する（ステップＳ１６）。そして、類似判定部１４にてこの等価クラスについての編集距離の計算が終わると、グループ集合Ｇ４を引き続きスキャンしていって、候補クラスＣＣ(1-2-3)１２２を発見すると、これを等価クラスとして類似判定部１４に報告する（ステップＳ１７）。類似判定部１４にてこの等価クラスについての編集距離の計算が終わると、候補クラス生成部１３５は、グループ集合Ｇ４を引き続きスキャンする。候補クラス生成部１３５は、列の最後までスキャンすると、グループ集合Ｇ４をメモリ上から解放し、グループ集合Ｇ２に戻って（ステップＳ１８）、次の候補クラスを探索する。
候補クラス生成部１３５は、以下同様にして、候補クラスＣＣ(1-2)１２のブロック３を展開・ソートしてグループ集合Ｇ５を生成し（ステップＳ１９）、このグループ集合Ｇ５から候補クラスＣＣ(1-2-3)１２２を等価クラスとして出力し（ステップＳ２０）、その等価クラスについての距離の計算が終わると、グループ集合Ｇ５をメモリ上から解放して、グループ集合Ｇ２に戻る（ステップＳ２１）。そして、候補クラス生成部１３５は、グループ集合Ｇ２に候補クラスがなくなると、グループ集合Ｇ２をメモリ上から解放して、グループ集合Ｇ１に戻って（ステップＳ２２）、前回の探索終了位置Ｅ１から、次の候補クラスを探索する。
候補クラス生成部１３５は、以下同様にして、候補クラスＣＣ(1)２をステップＳ２３、ステップＳ２４、・・・と展開していく。以上は、候補クラス記憶部１３６に既に記憶されている候補クラスを利用しないで、距離計算の対象を絞り込んでいく場合の手順である。
次に、図１３を参照して、候補クラス記憶部１３６に既に記憶されている候補クラスを利用して、距離計算の対象を絞り込んでいく場合の手順を説明する。図１３の例は、ブロック１、ブロック２、ブロック３ののブロックセットについて距離計算が終了した後に、ソート対象指定部１３２がブロック１、ブロック２、ブロック４を新たなブロックセットとして選択した（ブロック３、ブロック５をマスクした）ときの手順を示している。
ソート対象指定部１３２は、ブロック１、ブロック２、ブロック４を選択すると、ブロック１、ブロック２のサブセットについて候補クラス記憶部１３６に候補クラスが記憶されていないかを判断する。この場合は、既に以前のブロックセット（ブロック１、ブロック２、ブロック３）についての絞込みでブロック１、ブロック２のサブセットについての候補クラスが候補クラス記憶部１３６に記憶されているので、ソート対象指定部１３２はこれを読み出して、その候補クラスに含まれるショートリードのブロック４をソート対象として決定する。
オフセット部１３３およびソート部１３４は、最初の候補クラスＣＣ(1-2)１１に含まれるショートリードのブロック４を展開・ソートしてグループ集合Ｇ６を生成する（ステップＳ３１）。候補クラス生成部１３５は、このグループ集合Ｇ６を上から順にスキャンして候補クラスを探索する。候補クラス生成部１３５は、候補クラスＣＣ(1-2-4)１１１を発見すると、これを等価クラスとして類似判定部１４に報告し（ステップＳ３２）、類似判定部１４は、この等価クラスについて編集距離を計算し、編集距離がｄ以内にあるすべてのショートリードのペアを示す情報（当該ペアのインデクス）を出力する。類似判定部１４による類似判定が終了すると、候補クラス生成部１３５は、引き続き候補クラスを探索する。候補クラス生成部１３５は、候補クラスＣＣ(1-2-4)１１２を発見すると、これを等価クラスとして類似判定部１４に報告し（ステップＳ３３）、類似判定部１４は、この等価クラスについて編集距離を計算し、編集距離がｄ以内にあるすべてのショートリードのペアをのインデクスを出力する。
類似判定部１４による類似判定が終了すると、候補クラス生成部１３５は、グループ集合Ｇ６にて引き続き候補クラスを探索する。候補クラス生成部１３５は、グループ集合Ｇ６の最後までスキャンすると、グループ集合Ｇ６をメモリ上から解放して、その旨をソート対象部１３２に報告する。ソート対象部１３２は、この報告を受けて、候補クラス記憶部１３６から読み出した次の候補クラスＣＣ(1-2)１２に含まれるショートリードのブロック４をソート対象として指定する（ステップＳ３４）。
以下同様にして、オフセット部１３３およびソート部１３４が候補クラスＣＣ(1-2)１２に含まれるショートリードのブロック４を展開してグループ集合Ｇ７を生成し（ステップＳ３５）、候補クラス生成部１３５がグループ集合Ｇ７から候補クラスＣＣ(1-2-4)１２１を等価クラスとして類似判定部１４に報告する（ステップＳ３６）。類似判定部１４がこの等価クラスに含まれるショートリードのペアの類似判定を終了すると、候補クラス生成部１３５は、次に候補クラスＣＣ(1-2-4)１２２を等価クラスとして類似判定部１４に報告する（ステップＳ３７）。
類似判定部１４がこの等価クラスに含まれるショートリードのペアの類似判定を終了すると、候補クラス生成部１３５は候補クラスがなくなったことをソート対象指定部１３２に報告し、グループ集合Ｇ７をメモリ上から解放する（ステップＳ３８）。ソート対象指定部１３２は、候補クラス記憶部１３６から読み出した次の候補クラスＣＣ(1-2)１３に含まれるショートリードのブロック４をソート対象として決定し、これを受けて、オフセット部１３３およびソート部１３４が候補クラスＣＣ(1-2)１３に含まれるショートリードのブロック４を展開・ソートしてグループ集合Ｇ８を生成し（ステップＳ３９）、以下同様にしてステップＳ４０、ステップＳ４１、ステップＳ４２、・・・と作業を進めていく。
ソート対象指定部１３２は、候補クラス記憶部１３６から読み出したすべての候補クラスについての展開が終了して、すべての等価クラスが報告されると、新たなブロックセットを選択する。
以上のように、本実施の形態の配列解析装置１０は、候補クラス生成部１３５が候補クラスを生成するたびにそれをソート対象指定部１３２に報告し、ソート対象指定部１３２が報告を受けた候補クラスの次のブロックをソート対象として決定して、オフセット部１３３およびソート部１３４がそのソート対象を展開するという処理を繰り返して、最終作業数まできたときに候補クラス生成部１３５が候補クラスを等価クラスとして類似判定部１４に報告して、類似判定部１４で直ちに等価クラス内のショートリードのペアの編集距離を計算して、編集距離がｄ以内であるショートリードのペアのインデクスを出力する。仮に、これとは異なり、ブロックのすべての組について、すべての候補クラスを展開して、すべての等価クラスを求めた後に、各等価クラスについてそこに含まれるショートリードのペアの編集距離を計算するという手順にすると、求めた等価クラスの情報をすべて記憶装置に記憶しておかなければならなくなる。これに対して、本実施の形態の配列解析装置１０のように、候補クラスを取得するごとに作業数を増やしていき、かつ等価クラスを取得するごとに類似判定を行うようにすると、記憶すべき情報を少なくでき、必要な記憶装置の容量も小さくできる。
必要な記憶装置の容量を小さくするという観点では、候補クラス記憶部１３６に記憶する候補クラスの情報についても、不要となった時点で消去していく構成が望ましい。図１１の例では、例えば、ブロック１、ブロック２、ブロック５を選択して距離計算対象の絞込みおよび距離計算を行った後には、作業数１の作業ブロックとしてブロック１を選択して、作業数２の作業ブロックとしてブロック２を選択して絞込みを行うことで得られた候補クラス（図１３の左列の候補クラス）の情報は、消去することができる。また、ブロック１、ブロック４、ブロック５を選択して距離計算対象の絞込みおよび距離計算を行った後には、作業数１の作業としてブロック１を選択して絞込みを行うことで得られた候補クラス（図１２の最左の列の候補クラス）の情報は、消去することができる。
次に、類似判定部１４について説明する。類似判定部１４は、正準性判定部１４１と、編集距離計算部１４２と、類似ペア出力部１４３とを有している。上述のように、候補クラス生成部１３５からは、等価クラスの情報が類似判定部１４に出力される。この等価クラスの情報には、等価クラスに含まれるショートリードのインデクスのほか、その等価クラスが生成されるまでにソート対象となったブロックの履歴、およびブロック履歴に含まれる各ブロックにおいていくつのオフセット値で他の部分配列と一致したのかを示すオフセット履歴の情報が含まれている。
正準性判定部１４１は、候補クラス生成部１３５から等価クラスが入力されると、その等価クラスに含まれる各ショートリードのブロック履歴およびオフセット履歴に基づいて、正準性を判断する。仮に、等価クラスに含まれる複数のショートリードのすべてのペアについて編集距離を計算すると、すべての等価クラスについて編集距離を計算する過程で、同一のペアについて重複して編集距離を計算することになる。正準性判定部１４１による正準性の判定は、このように同一のペアについての重複した編集処理の計算を避けるために行われる判定である。
正準性判定部１４１は、ショートリードのペアが下記の条件３および条件４を同時に満足するときに、当該ペアを正準（canonical）であると判定する。
条件３：当該ペアの少なくとも一方のショートリードのオフセット履歴に含まれるオフセットがすべてゼロである
条件４：ブロック履歴に含まれる任意のブロックのブロック番号よりも小さいブロック番号のブロックにおいて、一方のショートリードの部分配列または窓枠を最大オフセット内でオフセットさせたオフセット部分配列が、他方のショートリードの当該ブロックの部分配列と一致しない
以下、例を挙げて正準性判定を説明する。図１４（ａ）の左側は等価クラス生成部１３から出力される等価クラスの情報の例である。等価クラスの情報には、当該等価クラスに含まれるショートリードのインデクスの情報、当該等価クラスが生成される際に選択されたブロック（ブロック履歴）の情報、当該等価クラスが生成される過程で生成された候補クラスにおける各ショートリードの部分配列のオフセット値（オフセット履歴）の情報が含まれる。
正準性判定部１４１は、正準性判定のために、この等価クラスに含まれるショートリードのあらゆるペアについて、条件３および条件４を満たすかを判断する。このために、正準判定部１４は、等価クラスの情報中のインデクスが示すショートリードをブロック分割部１３１から読み出す。図１４（ａ）の右側は、実際に読み出したショートリードの配列パターンである。
正準性判定部１４１は、この等価クラスに含まれるショートリードのペアについて、まず条件３を満たすか否かを判断する。Ｓ75とＳ88のみが、オフセット履歴中のオフセット値がすべてゼロであるという条件を満たすので、Ｓ75、Ｓ88のいずれかを含むペアのみが条件３を満たすことになる。これを表にまとめたのが図１４（ｂ）である。図１４（ｂ）に示すように、本来は、５つのショートリードのうちの２つのショートリードの組合せは、5Ｃ2＝１０通りあるが、そのうちの少なくとも一方にＳ75、Ｓ88を含むペアのみが条件３を満たす。
正準性判定部１４１は、例えばＳ22とＳ75については、Ｓ75のオフセット履歴がすべてゼロであるため、条件３を満たすと判断する。図１４（ｃ）、（ｄ）は、条件４の判断例を説明する図である。図１４（ｃ）は、Ｓ22とＳ75のペア、図１４（ｄ）はＳ56とＳ75のペアを示している。なお、いずれのペアも、オフセット履歴中のオフセット値がすべてゼロであるＳ75を含むので、条件３を満たす。以下、このオフセット履歴中のオフセット値がすべてゼロであるショートリードを「基準ショートリード」といい、他方のショートリードを「オフセットショートリード」という。
条件４の判断ではまず、ブロック履歴に含まれる任意のブロックのブロック番号よりも小さいブロック番号のブロックに注目する。図１４（ｃ）、（ｄ）の例では、ブロック１はブロック履歴に含まれるブロック２（およびブロック３、ブロック５）よりもブロック番号が小さいブロックである。よって、正準性判定部１４１は、オフセットショートリードについて、このブロック１の部分配列およびそこから窓枠を最大オフセット内でオフセットさせた複数のオフセット部分配列を生成し、それらの部分配列を、基準ショートリードのブロック１の部分配列と比較する。
図１４（ｃ）の例では、オフセットショートリードであるＳ22においてブロック１から窓枠を最大オフセット１内でオフセットさせても、基準ショートリードであるＳ75のブロック１とは一致しないため、このＳ22とＳ75のペアは条件４を満たす。一方、図１４（ｄ）の例では、オフセットショートリードであるＳ56においてブロック１から窓枠を最大オフセット１内でオフセットさせると、オフセット０で、基準ショートリードであるＳ75のブロック１と一致するため、このＳ56とＳ75のペアは条件４を満たさない。
距離計算部１４２は、条件３および条件４を何れも満たすと判断されたペアについて、その間の編集距離を計算する。なお、２つのショートリードの間の編集距離は、例えば、Daniel Jurafsky and James H.Martin: Speech and Language Processing, pp.74, Prentice Hall, 2009等に記載された公知の方法により計算する。類似ペア出力部１４３は、距離計算部１４２にて計算された編集距離がｄ以下であるときは、当該ショートリードのペアを類似するペアと判定して、当該ショートリードのペアを示すインデクスのペアを出力する（図１参照）。
以上のように、条件３および条件４によって正準性を判断し、正準であると判断したペアのみについて編集距離を計算することで、計算コストの高い編集距離を同一のペアについて重複して行うことによる計算コストの増加を避けることができる。
本実施の形態の配列解析装置１０によれば、等価クラス生成部１３から等価クラスとして出力されたショートリードの集合によってできるすべてのペアの中には、編集距離がｄ以下であるペアがもれなく含まれており、かつ、上述のように同一のペアについての重複した編集距離の計算を回避できるので、計算コストを削減した上で、編集距離がｄ以内にあるすべてのペアを重複なく見つけ出すことができる。
次に、本実施の形態の配列解析装置１０によって実行される配列解析方法を図１５を参照して説明する。図１５は、配列解析装置１０の処理フロー図である。まず、配列解析装置１０は配列入力部１１にて、シーケンサから出力された複数のショートリードを入力し、かつ条件入力部１２にて配列解析の条件、即ち編集距離ｄ、およびブロック分割数を（ｄ＋ｎ）によって決定するための数値ｎを入力する（ステップＳ５１）。
次に、入力されたすべてのショートリードは、等価クラス生成部１３のブロック分割部に記憶される。ブロック分割部１３１は、すべてのショートリードを（ｄ＋ｎ）個のブロックに分割する（ステップＳ５２）。ソート対象指定部１３２は、（ｄ＋ｎ）個のブロックの中からｎ個のブロックを選択する（ステップＳ５３）。
続いて、ソート対象指定部１３２は、選択されたｎ個のブロックのうちのサブセットの候補クラスが候補クラス記憶部１３６に記憶されているかを判断する（ステップＳ５４）。選択されたｎ個のブロックについてサブセットの候補クラスがない場合は（ステップＳ５４でＮＯ）、作業数Ｗを１とし、選択されたブロック中のブロック番号が最小のブロックを作業ブロックｂｋとし、かつ、候補クラスをすべてのショートリードとする（ステップＳ５５）。
続いて、オフセット部１３３およびソート部１３４にて候補クラスを展開して、グループ集合を生成する（ステップＳ５６）。なお、ステップＳ５４でサブセットの候補クラスがある場合には（ステップＳ５４でＹＥＳ）、当該サブセットの候補クラスを候補クラス記憶部１３６から読み出して、読み出した候補クラスに対応する作業数Ｗおよび作業ブロックｂｋを設定して、ステップＳ５６に進む。この場合は、ステップＳ５６では、候補クラス記憶部１３６から読み出した候補クラスを展開して、グループ集合を生成する。
ステップＳ５６の後に、生成したグループ集合を上から順にスキャンして（ステップＳ５７）、同一の配列パターンのグループについて、候補クラスの条件（条件１および条件２）を満たすか否かを判断する（ステップＳ５８）。そのグループが候補クラスの条件を満たす場合は（ステップＳ５８でＹＥＳ）、作業数Ｗがｎであるか否かを判断する（ステップＳ５９）。作業数がｎでない場合には、候補クラス生成部１３５は、発見したグループを候補クラスとしてソート対象指定部１３２に報告し、かつ候補クラス記憶部１３６に保存する（ステップＳ６０）。
候補クラス記憶部１３６は、その候補クラスに含まれるショートリードのインデクスおよびオフセット履歴をブロック履歴に関連付けて記憶する。ソート対象指定部１３２は、候補クラス記憶部１３６から候補クラスの報告を受けると、作業数Ｗをインクリメントし、作業ブロックを、選択されている複数のブロックの次のブロックに変更し（ステップＳ６１）、ステップＳ５６に戻って、候補クラス生成部１３５から報告された候補クラスを展開して部分配列の列を生成する。
このようにして、ステップＳ５６〜Ｓ５９の処理を繰り返して、ステップＳ５９にて作業数Ｗがｎになると、候補クラス生成部１３５は、その直前に生成した候補クラスを等価クラスとして類似判定部１４に報告する（ステップＳ６２）。類似判定部１４は、等価クラスについて類似判定を行い、等価クラスに含まれるペアについて編集距離を計算する（ステップＳ６３）。そして、候補クラス生成部１３５は、グループ集合に未スキャン部分があるか否かを判断する（ステップＳ６４）。また、ステップＳ５７にて、グループ集合をスキャンして同一の配列パターンのグループが候補クラスの条件を満たさなかった場合にも（ステップＳ５８でＮＯ）、ステップＳ６４にて未スキャン部分があるか否かを判断する。候補クラス生成部１３５は、未スキャン部分がある場合には（ステップＳ６４でＮＯ）、ステップＳ５７に戻って当該未スキャン部分をスキャンする。
一方、未スキャン部分がなくなったとき、即ち、グループ集合をすべてスキャンし終わったときは、作業数Ｗをデクリメントして、ブロック番号をブロックセット中の1つ前の番号に変更し（ステップＳ６５）、作業数Ｗがゼロであるかを判断する（ステップＳ６６）。作業数Ｗがまだゼロになっていない場合には（ステップＳ６６でＮＯ）、ステップＳ６４に戻って、ステップＳ６５でデクリメントされた作業数で展開されたグループ集合に未スキャン部分があるか否かを判断する。
ステップＳ６６で作業数Ｗがゼロとなっているときは、そのとき選択されているブロックセットについては既にすべての等価クラスが報告されているということであるため、このブロックセットについて展開されたグループ集合をすべてクリアし（ステップＳ６７）、ソート対象指定部１３２は、未選択のブロックの組合せがまだあるかを判断する（ステップＳ６８）。未選択のブロックセットが未だある場合には（ステップＳ６８でＹＥＳ）、ステップＳ５３に戻って新たなｎ個のブロックを選択する。一方、未選択のブロックセットがなくなった場合は（ステップＳ６８でＮＯ）、処理を終了する。
以下、上記のフローが図１２〜図１３の例で実行されるときに、実際にどのようにフローが進むかを説明する。まず、ステップＳ５１にて複数のショートリードおよび条件（ｄ＝２、ｎ＝３）が入力されて、ステップＳ５２にて複数のショートリードがブロックに分割される。次に、ステップＳ５３にてソート対象指定部１３２は、ｎ個のブロックを選択してブロックセットとするが、このとき、ブロック１、ブロック２、ブロック３が選択される。
次に、ステップＳ５４にて、ブロック１、ブロック２、ブロック３のブロックセットについては、サブセットの候補クラスがまだないので、ステップＳ５５に進み、作業数Ｗが１とされ、ブロック番号ｂｋは、ブロック１、ブロック２、ブロック３のうちの一番小さいブロック１とされ、候補クラスはすべてのショートリードとされる。そして、ステップＳ５６にて、候補クラスであるすべてのショートリードのブロック１が展開されて、グループ集合Ｇ１が生成される。そして、ステップＳ５７にて、このグループ集合Ｇ１が上からスキャンされて、ステップＳ５８では、候補クラスＣＣ(1)１より上のグループについては、候補クラスの要件を満たさないため、ステップＳ６４に進み、この時点ではまだグループ集合Ｇ１をすべてスキャンしていないので、ステップＳ５７に戻る。
このようにして、ステップＳ５７にて、候補クラスＣＣ(1)１が候補クラスの要件を満たすので、ステップＳ５９にて作業数Ｗがｎ（＝３）であるか否かを判断する。作業数Ｗは１であって、Ｗ＝ｎは満たさないため、ステップＳ６０に進み、この候補クラスＣＣ(1)１が報告される。そして、ステップＳ６１にて、作業数Ｗがインクリメントされて、Ｗ＝２となり、作業ブロックが、選択されたブロック１の次のブロック、即ちブロック２とされる。その後、ステップＳ５６に戻って、この候補クラスＣＣ(1)１を展開して（図１２のステップＳ１１に対応する）、グループ集合Ｇ２を生成する。
次に、ステップＳ５７にて、グループ集合Ｇ２を上からスキャンして、ステップＳ５８で候補クラスＣＣ(1-2)１１が見つかると、ステップＳ５９では、Ｗ＝２であって、Ｗ＝ｎ（＝３）ではないので、ステップＳ６０でこの候補クラスＣＣ(1-2)１１が報告される。そして、ステップＳ６１で、作業数Ｗが２から３にインクリメントされ、作業ブロックは次のブロック３となる。
そして、再びステップＳ５６に戻って、候補クラスＣＣ(1-2)１１のブロック３が展開されてグループ集合Ｇ３が生成され（図１２のステップＳ１２に対応する）、ステップＳ５７で、グループ集合Ｇ３がスキャンされて、ステップＳ５８で、候補クラスＣＣ(1-2-3)１１１が生成される。次のステップＳ５９では、作業数がＷ＝３であるので、Ｗ＝ｎ（＝３）となり、ステップＳ６２に移行して、候補クラス生成部１３５は、この候補クラスＣＣ(1-2-3)１１１を等価クラスとして類似判定部１４に報告する（図１２のステップＳ１３に対応する）。ステップＳ６３では、類似判定部１４がこの等価クラス候補クラスＣＣ(1-2-3)１１１について、ショートリードのペアの編集距離を計算し、編集距離がｄ（＝２）以内にあるショートリードのペアのインデクスを出力する。
その後、グループ集合Ｇ３に未スキャン部分があるか判断される。未スキャン部分があるので、ステップＳ５７に戻って、候補クラスＣＣ(1-2-3)１１１より下の部分について、ステップＳ５７、ステップＳ５８、ステップＳ６４を繰り返す。グループ集合Ｇ３の最後まで来ると、ステップＳ６４にて、グループ集合Ｇ３に未スキャン部分がなくなるので、ステップＳ６５で作業数を３から２にデクリメントして（図１２のステップＳ１４に対応する）、かつ作業ブロックをブロック３からブロック２に変更する。ステップＳ６６では、Ｗ＝２であって、Ｗ＝０ではないので、ステップＳ６４に戻って、グループ集合Ｇ２に未スキャン部分があるか否かが判断される。図１２のステップＳ１２の時点では、候補クラスＣＣ(1-2)１１までしかスキャンしていなかったので、ステップＳ６４では、グループ集合Ｇ２に未スキャン部分があるということになり、ステップＳ５７に戻る。
そして、ステップＳ５７で、グループ集合Ｇ２について、候補クラスＣＣ(1-2)１１の下からスキャンを再開する。ステップＳ５８で、候補クラスＣＣ(1-2)１２を生成すると、ステップＳ５９でＷ＝ｎであるかを判断し、Ｗ＝２であってＷ＝ｄ（＝３）ではないので、ステップＳ６０に移行して、この候補クラスＣＣ(1-2)１２を報告し、ステップＳ６１で作業数を２から３にインクリメントして作業ブロックをブロック２から次のブロック３にして、ステップＳ５６で、候補クラスＣＣ(1-2)１２のブロック３を展開して（図１２のステップＳ１５に対応する）、グループ集合Ｇ４を生成する。
次に、ステップＳ５７で、グループ集合Ｇ４がスキャンされて、ステップＳ５８で、候補クラスＣＣ(1-2-3)１２１が生成される。次のステップＳ５９では、作業数がＷ＝３であるので、Ｗ＝ｎ（＝３）となり、ステップＳ６２に移行して、候補クラス生成部１３５は、この候補クラスＣＣ(1-2-3)１２１を等価クラスとして類似判定部１４に報告する（図１２のステップＳ１６に対応する）。ステップＳ６３では、類似判定部１４がこの等価クラスＣＣ(1-2-3)１２１について、ショートリードのペアの編集距離を計算し、編集距離がｄ（＝２）以内にあるショートリードのペアのインデクスを出力する。
その後のステップＳ６２では、グループ集合Ｇ４にまだ未スキャン部分があるので、ステップＳ５７に戻って、その未スキャン部分がスキャンされる。そして、ステップＳ５８で、候補クラスＣＣ(1-2-3)１２２が生成される。次のステップＳ５９では、作業数がＷ＝３であるので、Ｗ＝ｎ（＝３）となり、ステップＳ６２に移行して、候補クラス生成部１３５は、この候補クラスＣＣ(1-2-3)１２２を等価クラスとして類似判定部１４に報告する（図１２のステップＳ１７に対応する）。ステップＳ６３では、類似判定部１４がこの等価クラスＣＣ(1-2-3)１２２について、ショートリードのペアの編集距離を計算し、編集距離がｄ（＝２）以内にあるショートリードのペアのインデクスを出力する。
その後、ステップＳ６４からステップＳ５７に戻って、ステップＳ５７、ステップＳ５８、ステップＳ６４を繰り返し、グループ集合Ｇ４の最後まで来ると、ステップＳ６５にて、作業数が３から２にデクリメントされて、作業ブロックが１つ前のブロック２に変更されて、グループ集合Ｇ２に戻る。作業数はまだゼロではないので、ステップＳ６４に戻って、さらに、グループ集合Ｇ２に未スキャン部分があるのでステップＳ５７に戻って、グループ集合Ｇ２の候補クラスＣＣ(1-2)１２の下からスキャンを開始する（図１２のステップＳ１８に対応する）。
ステップＳ５７、ステップＳ５８、ステップＳ６４を繰り返し、候補クラスＣＣ(1-2)１３まで来ると、ステップＳ５８からステップＳ５９に移行して、作業数２はＷ＝ｄ（＝３）を満たさないので、ステップＳ６０でこの候補クラスＣＣ(1-2)１３を報告して、作業数を２から３にインクリメントし、作業ブロックをブロック３とし、この候補クラスＣＣ(1-2)１３のブロック３を展開して（図１２のステップＳ１９に対応する）、グループ集合Ｇ５を生成する。
ステップＳ５７でグループ集合Ｇ５がスキャンされて、ステップＳ５８で、候補クラスＣＣ(1-2-3)１３１が生成される。次のステップＳ５９では、作業数がＷ＝３であるので、Ｗ＝ｎ（＝３）となり、ステップＳ６２に移行して、候補クラス生成部１３５は、この候補クラスＣＣ(1-2-3)１３１を等価クラスとして類似判定部１４に報告する（図１２のステップＳ２０に対応する）。ステップＳ６３では、類似判定部１４がこの等価クラス候補クラスＣＣ(1-2-3)１３１について、ショートリードのペアの編集距離を計算し、編集距離がｄ（＝２）以内にあるショートリードのペアのインデクスを出力する。
その後、グループ集合Ｇ５に未スキャン部分があるか判断される。未スキャン部分があるので、ステップＳ５７に戻って、候補クラスＣＣ(1-2-3)１３１より下の部分について、ステップＳ５７、ステップＳ５８、ステップＳ６４を繰り返す。グループ集合Ｇ５の最後まで来ると、ステップＳ６４にて、グループ集合Ｇ５に未スキャン部分がなくなるので、ステップＳ６５で作業数を３から２にデクリメントして、かつ作業ブロックをブロック３からブロック２に変更して（図１２のステップＳ２１に対応する）、ステップＳ６６では、Ｗ＝２であって、Ｗ＝０ではないので、ステップＳ６４に戻って、グループ集合Ｇ２に未スキャン部分があるか否かが判断される。図１２のステップＳ２１の時点では、候補クラスＣＣ(1-2)１３までしかスキャンしていなかったので、ステップＳ６４では、未スキャン部分があるということになり、ステップＳ５７に戻る。
その後は、ステップＳ５７、ステップＳ５８、ステップＳ６４を繰り返して、候補クラスが見つからずにグループ集合Ｇ２の最後の行まで来ると、ステップＳ６４でＮＯとなり、ステップＳ６５で、作業数を２から１にデクリメントして、作業ブロックも１つ前のブロック１に変更する。
以下同様にして処理を進め、スキャンの対象がグループ集合Ｇ１の最終行までくると、ステップＳ６４にてＮＯとなり、作業数１がデクリメントされて０になる。そうすると、ステップＳ６７にて、これまでに展開したグループ集合をすべてクリアする。ステップＳ６８では、まだブロック１、ブロック２、ブロック３という最初のブロックセットを処理しただけであるので、ステップＳ５３に移行して、ソート対象指定部１３２は、ブロック１、ブロック２、ブロック４を新たなブロックセットとして選択する。
そして、ステップＳ５４では、サブセットの候補クラスが既にあるか否かが判断されるが、ここでは、いま選択されているブロックセット（ブロック１、ブロック２、ブロック４）のうちのブロック１、ブロック２というサブセットの候補クラスは、前のブロックセット（ブロック１、ブロック２、ブロック３）について処理を行った際に既に生成されているので、ステップＳ６９に移行して、これが読み出される（図１３の左列）。そして、この読み出した候補クラスＣＣ(1-2)１１、ＣＣ(1-2)１２、ＣＣ(1-2)１３、ＣＣ(1-2)２１、ＣＣ(1-2)２２、ＣＣ(1-2)３１、ＣＣ(1-2)３２、・・・に合わせて、作業数は３、作業ブロックはブロック４と設定される。
そして、ステップＳ５６で、読み出された最初の候補クラスＣＣ(1-2)１１に含まれるショートリードのブロック４を展開する（図１３のステップＳ３１に対応する）。以下同様にして、グループ集合Ｇ６から等価クラスＣＣ(1-2-3)１１１、ＣＣ(1-2-3)１１２を順に報告した後、グループ集合Ｇ６の最後までスキャンして、ステップＳ６４でＮＯとなった場合には、作業数を３から２にデクリメントして、ステップＳ６６を経てステップＳ６４に戻る。そして、ステップＳ６４では、グループ集合（ここでは、候補クラス記憶部１３６より読み出した複数の候補クラス）に未スキャン部分（ここでは、まだ展開していない候補クラス）があるか否かを判断する。
そして、候補クラス記憶部１３６より読み出した複数の候補クラスの中に、まだ展開していない候補クラスがあるときは、ステップＳ５７に戻り、候補クラス記憶部１３６より読み出した候補クラスをスキャンする。ステップＳ５８では、候補クラスＣＣ(1-2)１２についてＹＥＳに進み、Ｗはｎまで達していないので、ステップＳ６０で、ソート対象指定部１３２は、この候補クラスＣＣ(1-2)１２を次の候補クラスとして決定する。そして、ステップＳ６１で、作業数が２から３にインクリメントされて、作業ブロックがブロック４とされて、次のステップＳ５６では、候補クラスＣＣ(1-2)１２に含まれるショートリードのブロック４が展開される（図１３のステップＳ３５に対応する）。
以下同様にして、図１３のステップＳ３６、Ｓ３７、・・・、Ｓ４２、・・・と処理が進み、候補クラス記憶部１３６から読み出された複数の候補クラスがすべて展開されて、ステップＳ６３で、このブロックセットについての最後の等価クラスについて類似性が判定され、その後にステップＳ６４でＮＯとなると、作業数が３から２にデクリメントされて、ステップＳ６４に戻って、未展開の候補クラスがあるか否かが判断される。すべての候補クラスについて展開済みであるので、ステップＳ６４ではＮＯとなり、作業数が更に２から１へデクリメントされる。Ｗ＝０ではないのでステップＳ６４に戻るが、このブロックセットについては、作業数１ではもともと作業が行われていないため、Ｓ６４はＮＯになる。そして、ステップＳ６５で作業数がさらに１から０にデクリメントされるので、ステップＳ６６でＹＥＳとなり、ステップＳ６７、Ｓ６８を経て、ステップＳ５３に戻って、次のブロックセットである、ブロック１、ブロック２、ブロック５が選択される。
以上のように、本発明の実施の形態の配列解析装置によれば、大量のショートリードの中から類似のペアを完全に、かつ重複なく抽出することができる。また、上記の第１の実施の形態では、選択された複数のブロックをブロック番号が若い方から順に展開していくに当たって、あるブロックを展開して得られたすべての候補クラスを展開してから次のブロックを展開するのではなく、あるブロックを展開して得られたグループ集合にて候補クラスを発見するごとに当該候補クラスについて次のブロックを展開するという処理を繰り返し、処理の済んだグループ集合を逐次メモリ上から解放することで、展開したグループ集合を記憶するためのメモリの容量を削減することができる。
第１の実施の形態では、まずブロックセットを選択して、当該選択したブロックセットについてのすべての処理が終了した後に新たなブロックセットを選択して処理を行った。このために、あるブロックセットで処理した際の候補クラスを候補クラス記憶部１３６に記憶し、新たに選択されたブロックセットで利用できる候補セットを候補クラス記憶部１３６から読み出す構成を採用した。このような構成は、候補クラス記憶部１３６から既に作成された候補クラスを読み出すのに時間がかかってしまう。一方で、既に作成されて後のブロックセットで再利用する候補クラスをすべてメモリに記憶しておくとすると、きわめて大きなメモリ容量が必要になる。
そこで、以下では、第１の実施の形態と比較して、メモリ容量を増大させることなく、候補クラス記憶部１３６のようなハードディスクへの書き込みおよび読み出しを不要として処理速度を向上できる第２の実施の形態を説明する。第２の実施の形態の配列解析装置は、候補クラス記憶部１３６がないことを除き、図５に示した配列解析装置と同じである。
図１６〜図１９は、本発明の第２の実施の形態における絞込み手順を説明する図である。なお、図１６〜図１９において、グループ集合のうち、候補クラスを形成しない部分配列のグループを省略している。また、図１６〜図１９では、編集距離ｄ＝１、数値ｎ＝３、分割数ｂ（＝ｄ＋ｎ）＝４の例を説明している。
本実施の形態では、第１の実施の形態と同様に、ソート対象指定部１３２は、図１１のツリー構造に従ってブロック番号の若いブロックから順番にブロックを選択する。但し、生成された候補クラスを記憶しておくことを避けるため、生成された候補クラスについて、当該候補クラスを含むグループ集合の他の候補クラスを展開・ソートする処理を行う前に、当該候補クラスを利用する処理をすべて行うという手順を採用する。
具体的には、図１６に示すように、ソート対象指定部１３２は、まず、作業開始ブロックをブロック１として、すべてのショートリードのブロック１を展開・ソートする。このときに、グループ集合Ｇ９には、候補クラス１−１、候補クラス１−２、候補クラス１−３、候補クラス１−４が含まれているとする。候補クラス生成部１３５は、グループ集合Ｇ９を上から順にスキャンしていって、候補クラス１−１を発見すると、ソート対象指定部１３２に報告する。ソート対象指定１３２は、候補クラス１−１に含まれるショートリードについて、ブロック２をソート対象として指定し、オフセット部１３３およびソート部１３４は、指定された対象を展開・ソートしてグループ集合Ｇ１０を生成する。
候補クラス生成部１３５は、このグループ集合Ｇ１０をスキャンしていって候補クラス２−１を発見すると、その旨をソート対象指定部１３２に報告する。ソート対象指定部１３２は、候補クラス２−１に含まれるショートリードのブロック３をソート対象に指定する。オフセット部１３３およびソート部１３４は、指定された対象を展開・ソートしてグループ集合Ｇ１１を生成する。候補クラス生成部１３５は、このグループ集合Ｇ１１をスキャンしていって候補クラス３−１を発見すると、これを等価クラスとして類似判定部１４に出力し、候補クラス３−１をメモリ上から解放する。候補クラス生成部１３５は、続いて、候補クラス３−２を発見すると、これを等価クラスとして類似判定部１４に出力し、候補クラス３−２をメモリ上から解放する。ここまでの処理の手順は、第１の実施の形態と同様である。
ソート対象指定部１３２は、次に、展開済みの候補クラスについて、まだ処理を行っていないブロックの組合せで処理を行う。図１６の例では、ブロック１の候補クラス１−１をブロック２で展開・ソートして得られた候補クラス２−１については、ブロック１、２、４というブロックセットでは処理をしていないため、候補クラス２−１に含まれるショートリードについて、ブロック４を展開・ソートする。こうしてできたグループ集合Ｇ１２について、等価クラス４−１、４−２、４−３を順に出力するとともに、出力し終わった等価クラスを順に消去していく。そうしてグループ集合Ｇ１２について処理が終わると（このときグループ集合Ｇ１２はすべてメモリ上から解放されている）、ソート済み部分配列集合Ｇ１０の候補クラス２−１はすべて処理が終わったので、図１７に示すように、この部分をメモリ上から解放する。
その後、グループ集合Ｇ１０を続けてスキャンし、候補クラス２−２を発見すると、この候補クラス２−２に含まれるショートリードについて、ブロック３を展開・ソートしてグループ集合Ｇ１３を得て、等価クラス３−１、３−２を出力してグループ集合Ｇ１３をメモリ上から解放し、その後に候補クラス２−２に含まれるショートリードについて、ブロック４を展開・ソートしてグループ集合Ｇ１４を得て、等価クラス４−１、４−２、４−３、４−４を出力してグループ集合Ｇ１４をメモリ上から解放する。
ここまで終了すると、グループ集合Ｇ１０の候補クラス２−２はもう使用しないため、メモリ上から解放する。その後、同様にして、候補クラス２−３に含まれるショートリードのブロック３、ブロック４について、順に展開・ソートして、等価クラスを出力する。このようにして、グループ集合Ｇ１０に含まれるすべての候補クラスの処理が終了すると（この時点でグループ集合Ｇ１０はすべてメモリ上から解放されている）、グループ集合Ｇ９の候補クラス１−１に含まれるショートリードのブロック３、ブロック４について、順に展開・ソートして、等価クラスを出力する。この時点で、グループ集合の候補クラス１−１のついてはすべての処理が終了したことになるので、図１８に示すように、グループ集合Ｇ９の候補クラス１−１をメモリ上から解放し、候補クラス１−１の終わりからグループ集合Ｇ９をスキャンする。候補クラス１−２を発見すると、上記と同様にして、展開・ソート、候補クラスの生成を繰り返して、等価クラスを出力する。
以下同様にして処理を進め、候補クラス１−４についてすべての処理が終了し、即ち、グループ集合Ｇ９についてすべての処理が終了すると、この時点でグループ集合Ｇ９はすべてメモリ上から解放されていることになる。このように、作業開始ブロックについてグループ集合がすべて消去されると、ソート対象指定部１３２は、図１９に示すように、作業開始ブロックを次のブロック２として、上記と同様の処理を行う。
このように、第２の実施の形態では、グループ集合を順にスキャンしていき、発見された候補クラスを利用するすべてのパターンのブロックセットについて等価クラスを求め、すべての等価クラスを出力したら当該候補クラスをメモリ上から解放して、そのグループ集合内の次の候補クラスを探すという処理を行う。これにより、第１の実施の形態のように、候補クラスを後のブロックセットで利用するために保存しておく必要がなくなり、候補クラス記憶部のようなハードディスクへの書き込みおよび読み出しを行う必要はなくなると同時に、必要なメモリ容量も第１の実施の形態と同程度に小さく抑えることができる。
図２０は、第２の実施の形態の配列解析装置の処理フロー図である。最初に複数のショートリードおよび条件（編集距離ｄおよび数値ｎ）を入力し（ステップＳ７１）、入力された複数のショートリードの各々をブロックに分割する（ステップＳ７２）処理は、第１の実施の形態のステップＳ５１、ステップＳ５２（図１５参照）と同じである。ブロック分割部１３１にブロックに分割された状態のショートリードが準備されると、次に、作業数Ｗを１とし、作業ブロックｂｋをブロック１とし、作業開始ブロックＳを１とする（ステップＳ７３）。そして、絞込みを行う対象となる候補クラス（以下、「絞込み対象候補クラス」という）Ａを入力されたすべてのショートリードとする（ステップＳ７４）。
次に、絞込み対象候補クラスＡの作業ブロックｂｋを展開・ソートして、グループ集合Ｇ（ｂｋ）を生成して記憶し、作業数Ｗの作業済みブロックであって、図１６〜図１９において最も右にあるブロックＰ（Ｗ）を作業ブロックｂｋとする（ステップＳ７５）。そして、グループ集合Ｇ（ｂｋ）を上からスキャンして、候補クラスの条件を満たす最初のグループを選択してそのグループを絞り込み対象候補クラスＡとし、かつ、作業数Ｗの絞込み対象候補クラスＱ（Ｗ）をその絞り込み対象候補クラスＡとする（ステップＳ７６）。
次に、作業数Ｗがｎになっているかを確認し（ステップＳ７７）、まだｎに達していない場合は（ステップＳ７７でＮＯ）、作業数Ｗをインクリメントして（ステップＳ７８）、作業ブロックｂｋをインクリメントさせた値（ｂｋ＋１）がｄ＋Ｗ以下であるか否かを判断する（ステップＳ７９）。ｂｋ＋１≦ｄ＋Ｗであるときは（ステップＳ７９にてＹＥＳ）、作業ブロックｂｋをインクリメントさせて（ステップＳ８０）、ステップＳ７５に戻る。
ステップＳ７５〜Ｓ８０のループを繰り返して、ステップＳ７７にて作業数Ｗがｎに達すると（ステップＳ７７にてＹＥＳ）、そのときの絞込み対象候補クラスＡを等価クラスとして（ステップＳ８１）、当該等価クラスＡについて、類似判定部１４で類似判定を行う（ステップＳ８２）。そして、グループ集合Ｇ（ｂｋ）に未スキャン部分があるか否かを判断し（ステップＳ８３）、ある場合は（ステップＳ８３にてＹＥＳ）、ステップＳ７６に戻ってスキャンを続ける。ステップＳ７６、ステップＳ７７、ステップＳ８１、ステップＳ８２、ステップＳ８３を繰り返し、グループ集合Ｇ（ｂｋ）をすべてスキャンして、未スキャン部分がなくなった場合には（ステップＳ８３にてＮＯ）、当該グループ集合Ｇ（ｂｋ）をメモリ上から解放し、作業数Ｗをデクリメントする（ステップＳ８４）。
その後、作業数Ｗが０になっていないかを確認し（ステップＳ８５）、Ｗが０になっていない場合は（ステップＳ８５にてＮＯ）、絞込み対象候補クラスＡを作業数Ｗの絞込み対象候補クラスとし（ステップＳ８６）、ステップＳ７８に移行する。ステップＳ７５〜Ｓ８６を繰り返し、ステップＳ７９にて、ｂｋ＋１＞ｄ＋Ｗとなった場合は（ステップＳ７９でＮＯ）、作業数Ｗをデクリメントし、作業ブロックｂｋをそのデクリメントされた作業数の作業済みの最右のブロックとして（ステップＳ８７）、ステップＳ８３に移行する。
上記のようなステップＳ７５〜Ｓ８７を繰り返し、ステップＳ８５にて作業数Ｗが０になった場合には（ステップＳ８５でＹＥＳ）、作業開始ブロックＳが編集距離ｄ以下であるかを判断し（ステップＳ８８）、作業開始ブロックＳが編集距離ｄを越えていない場合には（ステップＳ８８でＹＥＳ）、作業開始ブロックＳをインクリメントして、作業数Ｗを１とし（ステップＳ８９）、ステップＳ７４に戻る。
上記のようにして、ステップＳ７４〜Ｓ８９を繰り返し、ステップＳ８８にて作業開始ブロックＳが編集距離ｄより大きくなった場合には（ステップＳ８８でＮＯ）、処理を終了する。
以下、上記のフローが図１６〜図１９の例で実行されるときに、実際にどのようにフローが進むかを説明する。まず、ステップＳ７３で作業数Ｗを１とし、作業ブロックｂｋを１とし、作業開始ブロックＳが１とされる。そして、ステップＳ７４で、絞込み対象候補クラスＡが入力されたすべてのショートリードとされる。次に、ステップＳ７５で入力されたすべてのショートリードのブロック１が展開・ソートされてグループ集合Ｇ（１）（＝Ｇ９）が生成され、作業数１の作業済み最右のブロックＰ（１）がブロック１とされる。
次に、ステップＳ７６にて、グループ集合Ｇ（１）（＝Ｇ９）がスキャンされ、選択した候補クラス１−１が絞込み対象候補クラスＡとされ、作業数１の絞込み対象候補クラスＱ（１）が候補クラス１−１とされる。ステップＳ７７では、作業数Ｗ（＝１）はｎ（＝３）ではないので、ステップＳ７８に移行して、作業数Ｗが１から２にインクリメントされる。次に、ステップＳ７９では、ｂｋ＋１（＝２）は、ｄ＋Ｗ（＝３）以下であるので、ステップＳ８０に移行して作業ブロックがブロック１からブロック２とされる。
次に、ステップＳ７５にて、いま絞込み対象候補クラスＡとされている候補クラス１−１をブロック２について展開・ソートして、グループＧ（２）（＝Ｇ１０）が生成され、作業数２の作業済み最右のブロックＰ（２）をブロック２とする。続いて、ステップＳ７６では、グループ集合Ｇ（２）（＝Ｇ１０）をスキャンして、候補クラス２−１を選択して、これを絞込み対象候補クラスＡとし、作業数２の絞込み対象候補クラスＱ（２）を候補クラス２−１とする。そして、ステップＳ７７では、作業数Ｗ（＝２）はｎ（＝３）ではないので、ステップＳ７８に移行して、作業数Ｗが２から３にインクリメントされる。次に、ステップＳ７９では、ｂｋ＋１（＝３）は、ｄ＋Ｗ（＝４）以下であるので、ステップＳ８０に移行して作業ブロックがブロック２からブロック３とされる。
以下、同様にして、ステップＳ７５にて、いま絞込み対象候補クラスＡとされている候補クラス２−１をブロック３について展開・ソートして、グループ集合Ｇ（３）（＝Ｇ１１）が生成され、作業数３の作業済み最右のブロックＰ（３）をブロック３とする。続いて、ステップＳ７６では、グループ集合Ｇ（３）（＝Ｇ１１）をスキャンして、候補クラス３−１を選択して、これを絞込み対象候補クラスＡとし、作業数３の絞込み対象候補クラスＱ（３）を候補クラス３−１とする。そして、ステップＳ７７では、Ｗ（＝３）＝ｎ（＝ｎ）なので、ステップＳ８１に移行して、絞込み対象候補クラス３−１を等価クラスとして出力し、ステップＳ８２にて、類似判定部１４にて等価クラス３−１について類似判定を行う。
次に、ステップＳ８３では、グループ集合Ｇ（３）（＝Ｇ１１）にまだ未スキャン部分があるので、ステップＳ７６に戻る。ステップＳ７６では、候補クラス３−２を選択し、それを絞込み対象候補クラスＡとし、作業数３の絞込み対象候補クラスＱ（３）を候補クラス３−２とする。ステップＳ７７では、作業数Ｗ（＝３）＝ｎ（＝３）であるので、ステップＳ８１に移行して、この候補クラス３−２を等価クラスとして出力し、ステップＳ８２で等価クラス３−２について類似判定を行う。
次に、ステップＳ８３に移行すると、グループ集合Ｇ（３）（＝Ｇ１１）には未スキャン部分はないので、ステップＳ８４に移行して、グループ集合Ｇ（３）（＝Ｇ１１）はメモリ上から解放され、作業数Ｗは３から２にデクリメントされる。そして、ステップＳ８５では、作業数Ｗ（＝２）は０ではないので、ステップＳ８６に移行して、絞込み対象候補クラスＡが、絞込み対象候補クラスＱ（２）、即ち候補クラス２−１とされる。続いて、ステップＳ７８にて、作業数Ｗが２から３にインクリメントされ、ステップＳ７９では、ｂｋ＋１（＝４）は、ｄ＋Ｗ（＝４）以下であるので、ステップＳ８０に移行して、作業ブロックｂｋが３から４にインクリメントされる。
ステップＳ７５に戻り、いま絞込み対象候補クラスＡとされている候補クラス２−１がブロック４について展開・ソートされ、グループ集合Ｇ（４）（＝Ｇ１２）が生成され、作業数３の作業済み最右のブロック（３）がブロック４とされる。続いて、ステップＳ７６にて、グループ集合Ｇ（４）（＝Ｇ１２）がスキャンされて、最初の候補クラス４−１が選択され、これが絞込み対象候補クラスＡとされ、作業数３の絞込み対象候補クラスＱ（３）が候補クラス４−１とされる。ステップＳ７７では、Ｗ（＝３）＝ｎ（＝３）であるので、ステップＳ８１に移行して、候補クラス４−１が等価クラスとして出力され、ステップＳ８２で、等価クラス４−１について類似判定が行われる。次に、ステップＳ８３では、グループ集合Ｇ（４）（＝Ｇ１２）にはまだ未スキャン部分が残っているので、ステップＳ７６に戻る。
その後は、ステップＳ７６、Ｓ７７、Ｓ８１、Ｓ８２、Ｓ８３を繰り返すことで、等価クラス４−２、等価クラス４−３を順に出力し、その都度類似判定を行う。等価クラス４−３まで類比判定が終わると、ステップＳ８３では、グループ集合Ｇ（４）（＝Ｇ１２）に未スキャン部分がなくなり、ステップＳ８４に移行して、グループ集合Ｇ（４）（＝Ｇ１２）がメモリ上から解放され、作業数Ｗは、３から２にデクリメントされる。ステップＳ８５では、作業数Ｗ（＝２）は０ではないので、ステップＳ８６に移行して、作業数２の絞込み対象候補クラスＱ（２）である２−１がひとまず絞込み対象候補クラスＡとされ、ステップＳ７８では、作業数Ｗが２から３にインクリメントされる。
そして、ステップＳ７９では、ｂｋ＋１（＝５）はｄ＋Ｗ（＝４）以下ではなくなるので、ステップＳ８７に移行して、作業数Ｗが３から２にデクリメントされ、作業ブロックｂｋは、作業数２の作業済み最右のブロックＰ（２）、即ちブロック２とされ、ステップＳ８３で、グループ集合Ｇ（２）（＝Ｇ１０）に未スキャン部分があるか判断される。グループ集合Ｇ（２）（＝Ｇ１０）には未スキャン部分があるので、ステップＳ７６に戻り、グループ集合Ｇ（２）（＝Ｇ１０）のスキャンを再開して、候補クラス２−２を選択し、これを絞込み対象候補クラスＡとして、作業数２の絞込み対象候補クラスＱ（２）を候補クラス２−２とする。
ステップＳ７７では、作業数Ｗ（＝２）はｎ（＝３）と等しくないないので、ステップＳ７８に移行して、作業数Ｗが２から３にインクリメントされる。ステップＳ７９では、ｂｋ＋１（＝３）は、ｄ＋Ｗ（＝４）以下であるので、ステップＳ８０に移行して、作業ブロックｂｋがブロック２からブロック３に変更されて、ステップＳ７５に戻る。ステップＳ７６では、絞込み対象候補クラスＡである候補クラス２−２が、作業ブロックｂｋ（＝ブロック３）について展開・ソートされて、グループ集合Ｇ（３）（＝Ｇ１３）が生成される。そして、このグループ集合Ｇ１３について、ステップＳ７６、Ｓ７７、Ｓ８１、Ｓ８２、Ｓ８３が繰り返されて、グループ集合Ｇ１３の等価クラス３−１、３−２が出力された後に、ステップＳ８３でグループ集合Ｇ１３に未スキャン部分がないと判断されて、ステップＳ８４に移行して、グループ集合Ｇ１３がメモリ上から解放されて、作業数Ｗが３から２にデクリメントされる。
ステップＳ８５では、Ｗ（＝２）は０ではないので、絞込み対象候補クラスＡは作業数２の絞込み対象候補クラスＱ（２）、即ち候補クラス２−２とされる。その後、ステップＳ７８で、作業数Ｗが２から３にインクリメントされて、ステップＳ７９では、ｂｋ＋１（＝４）は、ｄ＋Ｗ（＝４）以下であるので、ステップＳ８０に移行して作業ブロックｂｋがブロック３からブロック４に変更されて、ステップＳ７５に戻る。ステップＳ７５では、絞込み対象候補クラスＡである候補クラス２−２が作業ブロックｂｋ（＝ブロック４）について展開・ソートされて、グループ集合Ｇ（４）（＝Ｇ１４）が生成され、作業数Ｗ（＝３）の作業済み最右のブロックＰ（３）が作業ブロックｂｋ（＝ブロック４）とされる。
その後、ステップＳ７６、Ｓ７７、Ｓ８１、Ｓ８２、Ｓ８３を繰り返すことで、グループ集合Ｇ１４から等価クラス４−１、４−２、４−３、４−４が出力された後、ステップＳ８３にてグループ集合Ｇ１４に未スキャン部分がなくなったと判断されると、ステップＳ８４で、グループ集合Ｇ１４がメモリ上から解放され、作業数Ｗは３から２にデクリメントされる。次に、ステップＳ８５では、作業数Ｗ（＝２）は０ではないので、ステップＳ８６で絞込み対象候補クラスＡは、一旦、作業数２の絞込み対象候補クラスＱ（２）即ち候補クラス２−２とされる。そして、ステップＳ７８で作業数Ｗが２から３にインクリメントされ、ステップＳ７９では、ｂｋ＋１（＝５）がｄ＋Ｗ（＝４）以下ではなくなるので、ステップＳ８７に移行して、作業数Ｗが３から２にデクリメントされて、作業ブロックは、作業数２の作業済み最右のブロックＰ（２）、即ちブロック２とされる。そして、ステップＳ８３に移行して、グループ集合Ｇ（２）（＝Ｇ１０）に未スキャン部分があるので、ステップＳ７６に移行する。
以下同様にして、候補クラス２−３についてブロック３を展開して得られたすべての等価クラスが出力され、候補クラス２−３についてブロック４を展開して得られたすべての等価クラスが出力されると、ステップＳ８２でブロック４の最後の等価クラスについて類似判定を行った後のステップＳ８３では、グループ集合Ｇ（４）に未スキャン部分がなくなるので、ステップＳ８４でグループ集合Ｇ（４）をメモリ上から解放して、作業数Ｗを３から２にデクリメントする。ステップＳ８５では、Ｗ（＝２）は０ではないので、ステップＳ８６で、絞込み対象候補クラスＡを作業数２の絞込み対象候補クラスＱ（２）即ち、候補クラス２−３とする。そして、ステップＳ７８で、作業数Ｗを２から３にデクリメントする。すると、ｂｋ＋１（＝５）はｄ＋Ｗ（＝４）以下ではなくなるので、ステップＳ８７に移行して、作業数Ｗが３から２にデクリメントされて、作業ブロックｂｋは、作業数２の作業済み最右ブロックＰ（２）、即ちブロック２とされる。
ステップＳ８３では、グループ集合Ｇ（２）（＝Ｇ１０）について未スキャン部分の有無が判断されるが、このときは既に候補クラス２−３までスキャンが終わっているので、ステップＳ８４に移行して、グループ集合Ｇ（２）（＝Ｇ１０）がメモリ上から解放されて、作業数Ｗが２から１にデクリメントされる。そして、ステップＳ８６では、絞込み対象候補クラスＡが作業数１の絞込み対象クラスＱ（１）である候補クラス１−１とされる。そして、ステップＳ７８で、作業数Ｗが１から２へとインクリメントされて、ステップＳ７９では、ｂｋ＋１（＝３）はｄ＋Ｗ（＝３）以下であるので、ステップＳ８０に移行して、作業ブロックｂｋがブロック２からブロック３に変更される。
続くステップＳ７５では、絞込み対象候補クラスＡである候補クラス１−１をブロック数ｂｋ（＝ブロック３）について展開・ソートして、グループ集合Ｇ（３）を生成し、作業数２の作業済み最右のブロックＰ（２）を作業ブロックｂｋ（＝ブロック３）とする。以下、上記と同様にして、ステップＳ７６、Ｓ７７、Ｓ７８、Ｓ７９、Ｓ８０を経てステップＳ７６に戻り、グループ集合Ｇ（４）の最初の候補ブロックが、作業数３の絞込み対象候補クラスＱ（３）とされると、そのグループ集合Ｇ（４）について、ステップＳ７６、Ｓ７７、Ｓ８１、Ｓ８２、Ｓ８３が繰り返されて、グループ集合Ｇ（４）に含まれる等価クラスの出力および出力された等価クラスについての類似判定が行われる。
グループ集合Ｇ（４）の最後の等価クラスについての類比判定がステップＳ８２で行われると、続くステップＳ８３では、グループ集合Ｇ（４）に未スキャン部分がないと判断されて、ステップＳ８４で、グループ集合Ｇ（４）がメモリ上から解放されて、作業数Ｗが３から２にデクリメントされる。続くステップＳ８５では、作業数Ｗ（＝２）は０ではないので、絞込み対象候補クラスＡは作業数２の絞込み対象候補クラスＱ（２）、即ちグループ集合Ｇ（３）の最初の候補クラスとされて、ステップＳ７８で作業数Ｗが２から３にインクリメントされる。ステップＳ７９では、ｂｋ＋１（＝５）はｄ＋Ｗ（４）以下ではないので、ステップＳ８７に移行して、作業数Ｗが３から２にデクリメントされて、作業ブロックｂｋが作業数２の作業済み最右のブロックＰ（２）、即ちブロック３とされる。
そして、ステップＳ８３で、グループ集合Ｇ（３）に未スキャン部分があるか判断される。グループ集合Ｇ（３）に未スキャン部分がある場合には、ステップＳ７６に戻って、グループ集合Ｇ（３）の次の候補クラスを選択して、ブロック４について展開・ソートし、等価クラスを出力するという上述の処理を繰り返す。このようにして、グループ集合Ｇ（３）の最後の等価クラスについて展開したグループ集合Ｇ（４）の最後の等価クラスについて、ステップＳ８２で類比判定を行うと、続くステップＳ８３では、グループ集合Ｇ（４）に未スキャン部分がないことになり、ステップＳ８４にてグループ集合Ｇ（４）をメモリ上から解放した後に、作業数Ｗが３から２にデクリメントされる。
ステップＳ８５では、作業数（＝２）が０でないので、ステップＳ８６に移行し、絞込み対象候補クラスＡが作業数２の絞込み対象候補クラスＱ（２）、即ちグループ集合Ｇ（３）の最後の候補ブロックとされる。そして、ステップＳ７８で作業数Ｗが２から３にインクリメントされると、ステップＳ７９では、ｂｋ＋１（＝５）がｄ＋Ｗ（＝４）以下ではないので、ステップＳ８７に移行して、作業数Ｗが３から２にデクリメントされて、作業ブロックｂｋは、作業数２の作業済み最右ブロックＰ（２）、即ちブロック３とされて、ステップＳ８３でグループ集合Ｇ（３）に未スキャン部分があるかが判断される。グループ集合Ｇ（３）にはすでに未スキャン部分はないので、ステップＳ８４で、このグループ集合Ｇ（３）は、メモリ上から解放され、作業数Ｗは２から１にデクリメントされる。
続いて、ステップＳ８５では、作業数Ｗ（＝１）は０ではないので、ステップＳ８６に移行して、絞込み対象候補クラスＡは、作業数１の絞込み対象候補クラスＱ（１）、即ちグループ集合Ｇ（１）の最初の候補ブロックとされる。次に、ステップＳ７８で、作業数Ｗが１から２にインクリメントされて、ステップＳ７９では、ｂｋ＋１（＝４）がｄ＋Ｗ（＝２）以下ではないので、ステップＳ８７に移行して、作業数Ｗが２から１にデクリメントされ、作業ブロックは、作業数１の作業済み最右のブロックＰ（１）、即ちブロック１とされる。そして、ステップＳ８３では、グループ集合Ｇ（１）（＝Ｇ９）については、まだ候補クラス１−１の処理が終わっただけで、まだ未スキャン部分があるので、ステップＳ７６に戻る。
グループ集合Ｇ９の候補クラス１−１についてした上述の処理を、候補クラス１−２、１−３、１−４についても行い、最後に候補クラス１−４をブロック３について展開してできたグループ集合Ｇ（３）の最後の候補クラスをブロック４について展開してできたグループ集合Ｇ（４）の最後の等価クラスについて、ステップＳ８２で類比の判定を行うと、その後の処理は以下の通りである。ステップＳ８３では、グループ集合Ｇ（４）に未スキャン部分がないので、ステップＳ８４で、グループ集合Ｇ（４）がメモリから解放され、作業数Ｗが３から２にデクリメントされる。ステップＳ８５では、作業数Ｗ（＝２）は０ではないので、ステップＳ８６で、絞込み対象候補クラスＡが作業数２の絞込み対象候補クラスＱ（２）、即ちグループ集合Ｇ（３）の最後の候補クラスとされる。
ステップＳ７８では、作業数Ｗが２から３にインクリメントされるが、ステップＳ７９では、ｂｋ＋１（＝５）はｄ＋Ｗ（＝４）以下ではないので、ステップＳ８７にて、作業数Ｗが３から２にデクリメントされて、作業ブロックｂｋは、作業数２の作業済み最右のブロックＰ（２）、即ち、ブロック３とされる。そして、ステップＳ８３では、グループ集合Ｇ（３）について未スキャン部分がないので、ステップＳ８４に移行して、グループ集合Ｇ（３）がメモリ上から解放され、作業数Ｗが２から１にデクリメントされる。
ステップＳ８５では、作業数Ｗ（＝１）はまだ０ではないので、ステップＳ８６に移行して、絞込み対象候補クラスＡが作業数１の絞込み対象候補クラスＱ（１）、即ちグループ集合Ｇ（１）の最後の候補クラスとされる。そして、ステップＳ７８で、作業数Ｗが１から２にインクリメントされるが、ステップＳ７９では、ｂｋ＋１（＝４）がｄ＋Ｗ（＝２）以下ではないので、ステップＳ８７に移行して、作業数が２から１にデクリメントされて、作業ブロックｂｋは、作業数１の作業済み最右ブロックＰ（１）、即ちブロック１とされる。
続くステップＳ８３では、グループ集合Ｇ（１）（＝Ｇ９）に既に未スキャン部分がないため、ステップＳ８４に移行して、グループ集合Ｇ（１）がメモリ上から解放され、作業数Ｗは１から０にデクリメントされる。そして、ステップＳ８５に移行すると、作業数Ｗは０であることから、ステップＳ８８に移行する。ステップＳ８８では、ステップＳ７３で設定した作業開始ブロックＳが１であるため、Ｓ（＝１）≦ｄ（＝１）を満たし、ステップＳ８９に進んで、作業開始ブロックＳがブロック１からブロック２に変更され、作業数Ｗは１にリセットされる。この状態で、ステップＳ７４に戻って、絞込み対象候補クラスＡがすべてのショートリードとされて、ステップＳ７５に移行し、その後は、上記で説明したのと同様にして、処理が行われる。
そして、作業開始ブロックＳをブロック２とした処理がすべて終了して、ステップＳ８５でＷ＝０となってステップＳ８８に移行すると、ステップＳ８８では、Ｓ（＝２）がｄ（＝１）以下ではないので、処理が終了する。
以上のように、第２の実施の形態の配列解析装置によれば、生成された候補クラスについて、当該候補クラスを含むグループ集合の他の候補クラスを展開・ソートする処理を行う前に、当該候補クラスを利用するすべての処理を行うので、第１の実施の形態のように、候補クラスを後のブロックセットで再利用するためにハードディスクに記憶しておく必要がない。また、そのようにハードディスクを不要としても、必要なメモリ容量は第１の実施の形態とほぼ変わらない。
以上のように、本発明にかかる配列解析装置は、計算コストを削減して、高速に、所定の編集距離以内にあるすべてのショートリードのペアを見つけ出すことができるという効果を有し、大量の塩基配列の中から、距離が所定範囲内にある塩基配列のペアを探索する配列解析装置等に適用できる。
１０ 配列解析装置
１１ 配列入力部
１２ 条件入力部
１３ 等価クラス生成部
１３１ ブロック分割部
１３２ ソート対象指定部
１３３ オフセット部
１３４ ソート部
１３５ 候補クラス生成部
１３６ 候補クラス記憶部
１４ 類似判定部
１４１ 正準性判定部
１４２ 距離計算部
１４３ 類似ペア出力部
Ｇ１〜Ｇ１４ グループ集合

Claims (23)

  1. 複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析装置であって、
    探索対象の複数の塩基配列を入力する配列入力部と、
    編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力する条件入力部と、
    前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個のすべてのブロックについて、当該ブロックから読み出した部分配列、または、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致するという条件を満たす塩基配列の集合を、等価クラスとして報告する等価クラス生成部と、
    前記等価クラス生成部から報告された等価クラス内の塩基配列のペアについて、編集距離を計算して、計算によって編集距離ｄ以内であると計算されたペアを示すデータを出力する類似判定部と、
    を備えたことを特徴とする配列解析装置。
  2. 複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析装置であって、
    探索対象の複数の塩基配列を入力する配列入力部と、
    編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）と、前記配列入力部に入力される前記複数の塩基配列の挿入および欠損の総和の閾値である最大ギャップｇ（ｇはｄ以下の自然数）を入力する条件入力部と、
    前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個のすべてのブロックについて、当該ブロックから読み出した部分配列、または、前記最大ギャップｇによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致するという条件を満たす塩基配列の集合を、等価クラスとして報告する等価クラス生成部と、
    前記等価クラス生成部から報告された等価クラス内の塩基配列のペアについて、編集距離を計算して、計算によって編集距離ｄ以内かつ、挿入および欠損の総和がｇ以内であると計算されたペアを示すデータを出力する類似判定部と、
    を備えたことを特徴とする配列解析装置。
  3. 前記等価クラス生成部は、前記ｎ個のブロックのうちの１つのブロックについて前記窓枠を前記最大オフセット内でオフセットを変えて読み出した部分配列または当該ブロック内の部分配列が一致するという絞り込み条件を満たす塩基配列の集合を、前記等価クラスの候補となる候補クラスとして求め、当該候補クラスに含まれる塩基配列に対して、前記ｎ個のブロックのうちの別のブロックについて前記窓枠を前記最大オフセット内でオフセットを変えて読み出した部分配列または当該別のブロック内の部分配列が前記絞り込み条件を満たす候補クラスを求めるという処理を、前記ｎ個のブロックについて順次行い、ｎ個のすべてのブロックを用いて絞り込まれた候補クラスを等価クラスとして生成することを特徴とする請求項１または２に記載の配列解析装置。
  4. 前記等価クラス生成部は、
    塩基配列に対して、絞り込みに用いられるブロックから前記最大オフセット内のあらゆるオフセット値で前記窓枠をオフセットさせて部分配列を読み出すオフセット部と、
    前記窓枠をオフセットさせて読み出された部分配列および前記窓枠をオフセットしないで読み出された部分配列を塩基の並び方に応じてソートして同じ配列パターンの部分配列が続く範囲をグループ化するソート部と、
    前記ソート部にて生成されたグループに複数の部分配列が含まれ、かつ、当該グループの中の少なくとも１つの部分配列のオフセット値が０であるときに、そのグループを候補クラスとして求める候補クラス生成部と、
    を備えることを特徴とする請求項３に記載の配列解析装置。
  5. 前記候補クラス生成部は、
    候補クラスに含まれる塩基配列に関連付けて、候補クラスを絞り込んだブロックの位置、および、候補クラスに含まれる他の部分配列と一致するために用いたオフセット値をメモリに記憶し、
    前記ｎ個のブロックのうちのｍ（ｍ＜ｎ）個目のブロックを用いて候補クラスを求める際には、前記１つのグループの中で、オフセット値が０であると判定された塩基配列の中に、前のｍ−１個のブロックを用いた候補クラスの絞り込みにおいて、当該塩基配列の部分配列のオフセット値が連続して０であった塩基配列が存在しない場合には、当該グループを候補クラスとしない請求項４に記載の配列解析装置。
  6. 前記候補クラス生成部は、
    １つのグループ内に、オフセット値の異なる同じ塩基配列の部分配列が存在する場合において、それらのオフセット値の中に０が含まれるときは０を、含まれないときはそれらのオフセット値の中から任意に選択した値を当該部分配列のオフセット値として記憶する請求項５に記載の配列解析装置。
  7. 前記類似判定部は、
    前記メモリから、前記等価クラスに含まれる塩基配列のブロックの位置、および、オフセット値を読み出し、
    等価クラスに含まれる塩基配列の任意のペアのうち、少なくとも一方の塩基配列のオフセット値がすべてのブロックで０であり、かつ、所定のブロック順位規則に基づく順位において前記ブロックの位置よりも前に、前記最大オフセット内でオフセットさせることにより一致する部分配列がないときに、当該ペアの塩基配列について、その編集距離を計算することを特徴とする請求項５または６に記載の配列解析装置。
  8. 前記等価クラス生成部は、
    前記候補クラス生成部によって複数の候補クラスが生成された場合には、そのうちの１つの候補クラスについて次のブロックを用いた候補クラスの絞り込みを行なう処理を、等価クラスが求まるか、または候補クラスがなくなるまで繰り返し行い、等価クラスが求まるか、または候補クラスがなくなった時点で１つ前のブロックを用いた処理で求まった他の候補クラスについて絞り込みを行うことを特徴とする請求項４ないし請求項７のいずれかに記載の配列解析装置。
  9. 前記等価クラス生成部は、最初のブロックを用いて求められたすべての候補クラスについての絞り込みを終了したときに、組み合わせの異なるｎ個のブロックを選択し、新たに選択されたｎ個のブロックを用いて等価クラスを生成することを特徴とする請求項８に記載の配列解析装置。
  10. 前記等価クラス生成部は、前記新たに選択されたｎ個のブロックを用いて等価クラスを生成する場合において、前記候補クラス生成部において利用できる候補クラスが生成されているときは、当該既に生成されている候補クラスを利用することで、前記ソート部において同一の候補クラスが複数回整列されるのを回避することを特徴とする請求項９に記載の配列解析装置。
  11. 前記等価クラス生成部は、前記候補クラスが生成されるごとに、当該候補クラスを利用するｎ個のブロックの組合せのすべてについて、等価クラスが求まるまで絞込みを行い、当該候補クラスを利用するすべてのｎ個のブロックの組合せについて等価クラスを求めた後に、当該候補クラスをメモリ上から解放することを特徴とする請求項８に記載の配列解析装置。
  12. 前記配列入力部に入力される前記複数の塩基配列は所定の範囲Ｄ内で長さが異なっており、
    前記条件入力部に入力される編集距離ｄは、ｄ≧Ｄを満たし、
    前記最大オフセットは、ｄ／２以上の最小の整数である
    ことを特徴とする請求項１ないし請求項８のいずれかに記載の配列解析装置。
  13. 前記配列入力部に入力される前記複数の塩基配列は所定の範囲Ｄ内で長さが異なっており、
    前記条件入力部に入力される編集距離ｄは、ｄ≧Ｄを満たし、
    前記最大オフセット量は、ｇ／２以上の最小の整数である
    ことを特徴とする請求項２に記載の配列解析装置。
  14. 前記配列入力部に入力される前記複数の塩基配列は長さが互いに等しく、
    前記最大オフセットは、ｄ／２以下の最大の整数である
    ことを特徴とする請求項１ないし請求項８のいずれかに記載の配列解析装置。
  15. 前記配列入力部に入力される前記複数の塩基配列は長さが互いに等しく、
    前記最大オフセットは、ｇ／２以下の最大の整数である
    ことを特徴とする請求項２に記載の配列解析装置。
  16. 前記数値ｎまたは前記分割数（ｄ＋ｎ）は、前記配列解析装置が所定のアルゴリズムに従って決定して前記条件入力部に入力されることを特徴とする請求項１ないし請求項１５のいずれかに記載の配列解析装置。
  17. 複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析方法であって、
    探索対象の複数の塩基配列を入力する配列入力ステップと、
    編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力する条件入力ステップと、
    前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個のすべてのブロックについて、当該ブロックから読み出した部分配列、または、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致するという条件を満たす塩基配列の集合を、等価クラスとして報告する等価クラス生成ステップと、
    前記等価クラス生成部から報告された等価クラス内の塩基配列のペアについて、編集距離を計算して、計算によって編集距離ｄ以内であると計算されたペアを示すデータを出力する類似判定ステップと、
    を含むことを特徴とする配列解析方法。
  18. 複数の塩基配列の中から、所定の範囲内にある塩基配列のペアを探索する配列解析方法であって、
    （１）探索対象の複数の塩基配列を入力するステップと、
    （２）編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力するステップと、
    （３）前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個のブロックに分割するとともに、各ブロックにブロック番号を付与するステップと、
    （４）前記（ｄ＋ｎ）個のブロックの中からｎ個のブロックをブロックセットとして選択するステップと、
    （５）作業数を１とし、前記選択されたｎ個のブロック中のブロック番号が最小のブロックを作業ブロックとし、かつ、ステップ（１）で入力されたすべての塩基配列を候補クラスとするステップと、
    （６）候補クラス内のすべての塩基配列について、前記作業ブロック内の部分配列と、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該作業ブロックからオフセットさせて読み出した部分配列からなる部分配列の集合を生成するステップと、
    （７）前記部分配列の集合を塩基の並び方に応じてソートしてグループ集合を生成するステップと、
    （８）前記グループ集合を順にスキャンしていき、同じ配列パターンの部分配列が続く範囲を１つのグループとして、そのグループに複数の部分配列が含まれ、かつ、少なくとも１つの部分配列のオフセット値が０であるときに、作業数がｎであるかを判断するステップと、
    （９）ステップ（８）において、作業数がｎでないときに、そのグループを候補クラスとして報告するステップと、
    （１０）ステップ（９）の後に、作業数をインクリメントし、前記作業ブロックを、ステップ（４）にて選択されたｎ個のブロックのうちの次のブロックに変更して、ステップ（６）に戻るステップと、
    （１１）ステップ（８）において、作業数がｎであるときに、そのグループを等価クラスとして報告するステップと、
    （１２）ステップ（１１）の後に、当該等価クラスに含まれる塩基配列の任意のペアのうちの少なくとも一方において、オフセット値の履歴にゼロ以外の値がなく、かつ所定の正準性判断に基づいて正準であると判断されたペアにつき、編集距離を計算するステップと、
    （１３）ステップ（１２）の後に、編集距離がｄ以内である場合に、当該ペアを示すデータを出力するステップと、
    （１４）ステップ（１３）の後に、前記グループ集合に未スキャン部分があるかを判断するステップと、
    （１５）ステップ（１４）において、未スキャン部分がある場合に、ステップ（８）に戻るステップと、
    （１６）ステップ（１４）において、未スキャン部分がない場合に、作業数をデクリメントして、作業ブロックを１つ前のブロックに戻すステップと、
    （１７）ステップ（１６）の後に作業数が１以上である場合に、ステップ（１４）に戻るステップと、
    （１８）ステップ（１６）の後に作業数が０になった場合に、前記グループ集合を消去してまだ選択されていないブロックセットがあるかを判断するステップと、
    （１９）ステップ（１８）において、まだ選択されていないブロックセットがある場合に、ステップ（４）に戻るステップと、
    （２０）ステップ（１８）において、まだ選択されていないブロックセットがない場合に、処理を終了するステップと、
    を有することを特徴とする配列解析方法。
  19. さらに、
    （２１）ステップ（４）の後に、前記ブロックセットに含まれるブロックをブロック番号が小さいものから並べて、ブロック番号が小さい方から１または複数のブロックにより構成されるサブセットの候補クラスが記憶されているか否かを判断するステップと、
    （２２）ステップ（２１）で、候補クラスが記憶されていると判断された場合に、ステップ（５）に代えて、当該サブセットの候補クラスを読み出して、その候補クラスに対応する作業数および作業ブロックを設定するステップと、
    を有することを特徴とする請求項１７に記載の配列解析方法。
  20. 複数の塩基配列の中から、所定の範囲内にある塩基配列のペアを探索する配列解析方法であって、
    （５１）探索対象の複数の塩基配列を入力するステップと、
    （５２）編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力するステップと、
    （５３）前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個のブロックに分割するとともに、各ブロックにブロック番号を付与するステップと、
    （５４）作業数Ｗを１とし、作業ブロックｂｋをブロック１とし、作業開始ブロックＳを１とするステップと、
    （５５）絞込み対象候補クラスＡを入力されたすべてのショートリードとするステップと、
    （５６）絞込み対象候補クラスＡの作業ブロックｂｋを展開・ソートして、グループ集合Ｇ（ｂｋ）を生成して記憶し、作業数Ｗの作業済み最右のブロックＰ（Ｗ）を作業ブロックｂｋとするステップと、
    （５７）グループ集合Ｇ（ｂｋ）を上からスキャンして、候補クラスの条件を満たす最初のグループを選択してそのグループを絞り込み対象候補クラスＡとし、かつ、作業数Ｗの絞込み対象候補クラスＱ（Ｗ）をその絞り込み対象候補クラスＡとするステップと、
    （５８）ステップ（５７）の後に、作業数Ｗがｎであるか否かを判断するステップと、
    （５９）ステップ（５８）にて作業数Ｗがｎでない場合に、作業数Ｗをインクリメントするステップと、
    （６０）ステップ（５９）の後に、ｂｋ＋１がｄ＋Ｗ以下であるか否かを判断するステップと、
    （６１）ステップ（６０）にて、ｂｋ＋１がｄ＋Ｗ以下である場合に、作業ブロックｂｋをインクリメントして、ステップ（５６）に戻るステップと、
    （６２）ステップ（５８）にて作業数Ｗがｎである場合に、絞込み対象候補クラスＡを等価クラスとするステップと、
    （６３）ステップ（６２）の後に、等価クラスについて、類似判定をするステップと、
    （６４）ステップ（６３）の後に、グループ集合Ｇ（ｂｋ）に未スキャン部分があるか否かを判断し、未スキャン部分がある場合に、ステップ（５７）に戻るステップと、
    （６５）ステップ（６４）にて、未スキャン部分がない場合に、グループ集合Ｇ（ｂｋ）をメモリ上から解放し、作業数Ｗをデクリメントするステップと、
    （６６）ステップ（６５）の後に、Ｗ＝０であるか否かを判断するステップと、
    （６７）ステップ（６６）にて、Ｗ＝０でない場合に、絞込み対象候補クラスＡを作業数Ｗの絞込み対象候補クラスとするステップと、
    （６８）ステップ（６０）にて、ｂｋ＋１がｄ＋Ｗより大きい場合に、作業数Ｗをデクリメントし、作業ブロックｂｋをそのデクリメントされた作業数の作業済み最右のブロックＰ（Ｗ）とするステップと、
    （６９）ステップ（６６）にて、Ｗ＝０である場合に、作業開始ブロックＳが編集距離ｄ以下であるか否かを判断し、作業開始ブロックＳが編集距離ｄより大きい場合に、処理を終了するステップと、
    （７０）ステップ（６９）にて、作業開始ブロックＳが編集距離ｄ以下である場合に、作業開始ブロックＳをインクリメントして、作業数Ｗを１にリセットして、ステップ（５５）に戻るステップと、
    を有することを特徴とする配列解析方法。
  21. コンピュータを、複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析装置として機能させるコンピュータプログラムであって、該コンピュータプログラムは、コンピュータに、
    探索対象の複数の塩基配列を入力する配列入力ステップと、
    編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力する条件入力ステップと、
    前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個に分割して（ｄ＋ｎ）個のブロックを生成し、その中から選んだｎ個のすべてのブロックについて、当該ブロックから読み出した部分配列、または、前記編集距離ｄによって定まる最大オフセットの範囲内で、読出し範囲を特定する窓枠を当該ブロックからオフセットさせて読み出した部分配列が一致するという条件を満たす塩基配列の集合を、等価クラスとして報告する等価クラス生成ステップと、
    前記等価クラス生成部から報告された等価クラス内の塩基配列のペアについて、編集距離を計算して、計算によって編集距離ｄ以内であると計算されたペアを示すデータを出力する類似判定ステップと、
    を実行させることを特徴とするコンピュータプログラム。
  22. コンピュータを、複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析装置として機能させるコンピュータプログラムであって、該コンピュータプログラムは、コンピュータに、
    （１）探索対象の複数の塩基配列を入力するステップと、
    （２）編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力するステップと、
    （３）前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個のブロックに分割するステップと、
    （４）前記（ｄ＋ｎ）個のブロックの中からｎ個のブロックをブロックセットとして選択するステップと、
    （５）作業数を１とし、作業ブロックを前記選択されたｎ個のブロック中のブロック番号が最小のブロックとし、かつ、候補クラスをすべてのショートリードとするステップと、
    （６）候補クラス内のすべての塩基配列について、前記作業ブロックに対して部分配列を読み出す窓枠を前記編集距離ｄによって定まる最大オフセット内のあらゆるオフセット値でオフセットさせて読み出した部分配列および前記作業ブロック内の部分配列からなる部分配列の集合を生成するステップと、
    （７）前記部分配列の集合を塩基の並び方に応じてソートしてグループ集合を生成するステップと、
    （８）前記グループ集合を順にスキャンしていき、同じ配列パターンの部分配列が続く範囲を１つのグループとして、そのグループに複数の部分配列が含まれ、かつ、少なくとも１つの部分配列のオフセット値が０であるときに、作業数がｎであるかを判断するステップと、
    （９）ステップ（８）において、作業数がｎであるときに、そのグループを候補クラスとして報告するステップと、
    （１０）ステップ（９）の後に、作業数をインクリメントし、前記作業ブロックを、ステップ（４）にて選択されたｎ個のブロックの次のブロックに変更して、ステップ（６）に戻るステップと、
    （１１）ステップ（８）において、作業数がｎであるときに、そのグループを等価クラスとして報告するステップと、
    （１２）ステップ（１１）の後に、当該等価クラスに含まれる塩基配列の任意のペアのうちの少なくとも一方において、オフセット値の履歴にゼロ以外の値がなく、かつ所定の正準性判断に基づいて正準であると判断されたペアにつき、編集距離を計算するステップと、
    （１３）ステップ（１２）の後に、編集距離がｄ以内である場合に、当該ペアを示すデータを出力するステップと、
    （１４）ステップ（１３）の後に、前記グループ集合に未スキャン部分があるかを判断するステップと、
    （１５）ステップ（１４）において、未スキャン部分がある場合に、ステップ（８）に戻るステップと、
    （１６）ステップ（１４）において、未スキャン部分がない場合に、作業数をデクリメンと、して、作業ブロックを１つ前のブロックに戻すステップと、
    （１７）ステップ（１６）の後に作業数が１以上である場合に、ステップ（１４）に戻るステップと、
    （１８）ステップ（１６）の後に作業数が０になった場合に、前記グループ集合を消去してまだ選択されていないブロックセットがあるかを判断するステップと、
    （１９）ステップ（１８）において、まだ選択されていないブロックセットがある場合に、ステップ（４）に戻るステップと、
    （２０）ステップ（１８）において、まだ選択されていないブロックセットがない場合に、処理を終了するステップと、
    を実行させることを特徴とするコンピュータプログラム。
  23. コンピュータを、複数の塩基配列の中から、所定範囲内にある塩基配列のペアを探索する配列解析装置として機能させるコンピュータプログラムであって、該コンピュータプログラムは、コンピュータに、
    （５１）探索対象の複数の塩基配列を入力するステップと、
    （５２）編集距離ｄと、複数の塩基配列を対応する部分配列ごとに比較する処理で用いる処理単位をブロックとし、塩基配列を何ブロックに分割するかを示す分割数を決定する数値ｎまたは前記分割数（ｄ＋ｎ）を入力するステップと、
    （５３）前記複数の塩基配列の各々を前記分割数（ｄ＋ｎ）個のブロックに分割するとともに、各ブロックにブロック番号を付与するステップと、
    （５４）作業数Ｗを１とし、作業ブロックｂｋをブロック１とし、作業開始ブロックＳを１とするステップと、
    （５５）絞込み対象候補クラスＡを入力されたすべてのショートリードとするステップと、
    （５６）絞込み対象候補クラスＡの作業ブロックｂｋを展開・ソートして、グループ集合Ｇ（ｂｋ）を生成して記憶し、作業数Ｗの作業済み最右のブロックＰ（Ｗ）を作業ブロックｂｋとするステップと、
    （５７）グループ集合Ｇ（ｂｋ）を上からスキャンして、候補クラスの条件を満たす最初のグループを選択してそのグループを絞り込み対象候補クラスＡとし、かつ、作業数Ｗの絞込み対象候補クラスＱ（Ｗ）をその絞り込み対象候補クラスＡとするステップと、
    （５８）ステップ（５７）の後に、作業数Ｗがｎであるか否かを判断するステップと、
    （５９）ステップ（５８）にて作業数Ｗがｎでない場合に、作業数Ｗをインクリメントするステップと、
    （６０）ステップ（５９）の後に、ｂｋ＋１がｄ＋Ｗ以下であるか否かを判断するステップと、
    （６１）ステップ（６０）にて、ｂｋ＋１がｄ＋Ｗ以下である場合に、作業ブロックｂｋをインクリメントして、ステップ（５６）に戻るステップと、
    （６２）ステップ（５８）にて作業数Ｗがｎである場合に、絞込み対象候補クラスＡを等価クラスとするステップと、
    （６３）ステップ（６２）の後に、等価クラスについて、類似判定をするステップと、
    （６４）ステップ（６３）の後に、グループ集合Ｇ（ｂｋ）に未スキャン部分があるか否かを判断し、未スキャン部分がある場合に、ステップ（５７）に戻るステップと、
    （６５）ステップ（６４）にて、未スキャン部分がない場合に、グループ集合Ｇ（ｂｋ）をメモリ上から解放し、作業数Ｗをデクリメントするステップと、
    （６６）ステップ（６５）の後に、Ｗ＝０であるか否かを判断するステップと、
    （６７）ステップ（６６）にて、Ｗ＝０でない場合に、絞込み対象候補クラスＡを作業数Ｗの絞込み対象候補クラスとするステップと、
    （６８）ステップ（６０）にて、ｂｋ＋１がｄ＋Ｗより大きい場合に、作業数Ｗをデクリメントし、作業ブロックｂｋをそのデクリメントされた作業数の作業済み最右のブロックＰ（Ｗ）とするステップと、
    （６９）ステップ（６６）にて、Ｗ＝０である場合に、作業開始ブロックＳが編集距離ｄ以下であるか否かを判断し、作業開始ブロックＳが編集距離ｄより大きい場合に、処理を終了するステップと、
    （７０）ステップ（６９）にて、作業開始ブロックＳが編集距離ｄ以下である場合に、作業開始ブロックＳをインクリメントして、作業数Ｗを１にリセットして、ステップ（５５）に戻るステップと、
    を実行させることを特徴とするコンピュータプログラム。
JP2010156342A 2010-07-09 2010-07-09 配列解析装置、配列解析方法およびコンピュータプログラム Active JP5516880B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2010156342A JP5516880B2 (ja) 2010-07-09 2010-07-09 配列解析装置、配列解析方法およびコンピュータプログラム

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP2010156342A JP5516880B2 (ja) 2010-07-09 2010-07-09 配列解析装置、配列解析方法およびコンピュータプログラム

Publications (2)

Publication Number Publication Date
JP2012018592A true JP2012018592A (ja) 2012-01-26
JP5516880B2 JP5516880B2 (ja) 2014-06-11

Family

ID=45603790

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2010156342A Active JP5516880B2 (ja) 2010-07-09 2010-07-09 配列解析装置、配列解析方法およびコンピュータプログラム

Country Status (1)

Country Link
JP (1) JP5516880B2 (ja)

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110889468A (zh) * 2019-12-23 2020-03-17 长沙理工大学 一种可排除错误信息的多模型不确定再现结果分析方法
JP2022088566A (ja) * 2017-01-18 2022-06-14 イルミナ インコーポレイテッド 不均一分子長を有するユニーク分子インデックスセットの生成およびエラー補正のための方法およびシステム
CN115602278A (zh) * 2022-10-31 2023-01-13 武汉理工大学（Cn） 基于块状编辑距离的相似患者诊断记录的查询方法、装置及系统
CN118522347A (zh) * 2024-07-23 2024-08-20 江西师范大学 基于同源性分析和区域加权的线粒体基因组重排量化方法

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2022088566A (ja) * 2017-01-18 2022-06-14 イルミナ インコーポレイテッド 不均一分子長を有するユニーク分子インデックスセットの生成およびエラー補正のための方法およびシステム
CN110889468A (zh) * 2019-12-23 2020-03-17 长沙理工大学 一种可排除错误信息的多模型不确定再现结果分析方法
CN115602278A (zh) * 2022-10-31 2023-01-13 武汉理工大学（Cn） 基于块状编辑距离的相似患者诊断记录的查询方法、装置及系统
CN118522347A (zh) * 2024-07-23 2024-08-20 江西师范大学 基于同源性分析和区域加权的线粒体基因组重排量化方法

Also Published As

Publication number Publication date
JP5516880B2 (ja) 2014-06-11

Similar Documents

Publication Publication Date Title
US11886786B2 (en) Two-step x-architecture steiner minimum tree construction method
Dutt et al. VLSI circuit partitioning by cluster-removal using iterative improvement techniques
US20050149471A1 (en) Computer representation of a data tree structure and the associated encoding/decoding methods
US10521441B2 (en) System and method for approximate searching very large data
JPH11212980A (ja) インデクス作成方法および検索方法
JP5516880B2 (ja) 配列解析装置、配列解析方法およびコンピュータプログラム
CN107239549A (zh) 数据库术语检索的方法、装置及终端
CN114564306B (zh) 一种基于GPU并行计算的第三代测序RNA-seq比对方法
KR100440949B1 (ko) 특징 벡터 공간내에서의 적응적 검색 방법
Huang et al. Fast algorithms for finding the common subsequence of multiple sequences
CN101430709B (zh) 富媒体信息的近邻查找方法和装置
Wei et al. A branch elimination-based efficient algorithm for large-scale multiple longest common subsequence problem
CN115206434A (zh) 一种基于De Bruijn图的多序列比对方法
CN107463676A (zh) 文本数据存储方法及装置
Li et al. Seeding with minimized subsequence
JP2012128672A (ja) 相同性検索装置及びプログラム
JP2007011784A (ja) データソート処理プログラム、データソート処理方法およびデータソート処理装置
CN111814009B (zh) 一种基于搜索引擎检索信息的模式匹配方法
CN112802556B (zh) 一种针对测序数据的多标记序列并行识别的加速器装置
CN110866088B (zh) 一种语料库之间的快速全文检索方法及系统
JP3534471B2 (ja) マージソート方法及びマージソート装置
CN110704579B (zh) 一种基于分支界定的全文检索方法及系统
CN118503312B (zh) 一种基于强化学习的电路结构模糊搜索方法和装置
Ehrenfeucht et al. String searching
CN119626330A (zh) 一种基于片段拓补序的有向无环泛基因组图构建方法

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20130305

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20140311

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20140318

R150 Certificate of patent or registration of utility model

Ref document number: 5516880

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150

S533 Written request for registration of change of name

Free format text: JAPANESE INTERMEDIATE CODE: R313533

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250