【手続補正書】
【提出日】令和1年7月25日(2019.7.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
検索配列を基準データに適合させるための方法であって、
演算装置により、
ａ）基準データをメモリ内に保存することと、
ｂ）前記基準データに基づいて階層的索引表を作成することであって、前記作成することが、前記階層的索引表内の複数のレベルで複数のエントリを作成することを含み、
前記複数のレベルは第１のレベルを含み、第１のレベルのエントリは、第１の長さを有する前記基準データの複数の副配列のそれぞれのために作成され、
それぞれのレベルｎのエントリに対して、ｎは少なくとも１つがゼロでない正の整数であり、前記作成は、閾値より大きい前記それぞれのレベルｎのエントリの適合基準に応答して、前記階層的索引表内の前記それぞれのレベルｎのエントリに対するｎ＋１レベルのエントリを作成することを含み、
前記階層的索引表内にｎ＋１レベルのエントリを作成することは、前記ｎ＋１レベルに対応する長さを有する前記基準データの複数の副配列のそれぞれに対するｎ＋１レベルのエントリを作成することを含み、
ｃ）検索配列を特定する入力を受信することと、
ｄ）前記基準データへの前記検索配列の１つまたは複数の適合について前記階層的索引表を検索することとを含み、
前記階層的索引表の前記検索は、前記階層的索引表のその後のレベルで前記検索配列の小区分の適合を反復的に検索することを含む、
方法。
【請求項２】
前記第１の長さを有する前記基準データの前記複数の副配列、および前記ｎ＋１レベルに対応する長さを有する前記基準データの前記複数の副配列は、それぞれの長さの副配列の網羅的なセットをそれぞれ含む、請求項１に記載の方法。
【請求項３】
前記階層的索引表の任意のそれぞれのレベルでそれぞれのエントリを前記作成することが、
前記基準データ内の前記それぞれのエントリに対応する前記それぞれの長さの前記副配列の適合について検索することと、
前記階層的索引表のそれぞれのレベル内の前記それぞれのエントリに情報を保存することであって、前記情報が、前記基準データ内での前記基準データ内のそれぞれの長さの前記副配列の適合の数を特定し、前記情報が、前記基準データ内での前記適合の各々の場所をさらに特定し、保存することと、
により実行される、請求項２に記載の方法。
【請求項４】
ｎ＋１レベルに対して、前記ｎ＋１レベルの前記それぞれの副配列の適合について前記検索することが、前記ｎレベルにおける前記対応するエントリに関連付けられた場所で実行される、請求項３に記載の方法。
【請求項５】
各エントリに関連付けられた前記適合の数を示す前記データが、第１のデータ構造内に保存され、各エントリに関連付けられた前記適合の各々の前記データ場所が、第２のデータ構造内に保存され、前記第１及び第２のデータ構造が、前記階層的索引表内に各々含まれる、請求項３に記載の方法。
【請求項６】
各それぞれのｎレベルのエントリに対して、前記それぞれのｎレベルのエントリに対応するｎ＋１レベルのエントリを参照するメモリ内にポインタを保存することをさらに含む、請求項１に記載の方法。
【請求項７】
前記基準データが、基準ゲノムを含み、前記基準データを検索することが、短い読み出し（ＳＲ）を前記基準ゲノムと整列させることを含む、請求項１に記載の方法。
【請求項８】
短い読み出しを基準ゲノムと整列させるためのプログラム命令を含むコンピュータ読み取り可能な記憶媒体であって、前記プログラム命令が、
ａ）前記基準ゲノムをメモリ内に保存することと、
ｂ）前記基準ゲノムに基づいて階層的検索表を作成することであって、前記作成することが、前記階層的索引表において複数のレベルのそれぞれで複数のエントリを作成することを含み、前記複数のレベルは第１のレベルを含み、第１のレベルのエントリは、第１の長さを有する前記基準データの複数の副配列のそれぞれのために作成され、各それぞれのエントリが、前記それぞれのエントリに関連付けられた塩基対の配列の前記基準ゲノム内の場所に関連する情報を含み、各それぞれのレベルｎのエントリについて、少なくとも１つのゼロでない正の整数ｎに対して、前記作成することは、閾値より大きい前記それぞれのレベルｎのエントリの適合基準に応答して、前記階層的索引表内のそれぞれのレベルｎのエントリに対する前記ｎ＋１レベルのエントリを作成することを含む、作成することと、
前記階層的索引表内にｎ＋１レベルのエントリを作成することは、前記ｎ＋１レベルに対応する長さを有する前記基準データの複数の副配列のそれぞれのためにｎ＋１レベルのエントリを作成することを含み、
ｃ）短い読み出しを特定する入力を受信することと、
ｄ）前記基準ゲノムへの前記短い読み出しの１つまたは複数の適合に対して前記階層的索引表を検索することであって、前記階層的索引表の前記検索は、前記階層的索引表のその後のレベルで前記短い読み出しの小区分の適合を反復的に検索することを含む、検索することと、
を行うように実行可能である、コンピュータ読み取り可能な記憶媒体。
【請求項９】
前記第１の長さを有する前記基準データの前記複数の副配列、および前記ｎ＋１レベルに対応する長さを有する前記基準データの前記複数の副配列は、それぞれの長さの副配列の網羅的なセットをそれぞれ含む、請求項８に記載の記憶媒体。
【請求項１０】
前記階層的索引表の任意のそれぞれのレベル内のそれぞれのエントリを前記作成することが、
前記基準データ内の前記それぞれのエントリに対応する前記それぞれの長さの前記それぞれの副配列の適合について検索することと、
前記階層的索引表のそれぞれのレベルの前記それぞれのエントリ内の情報を保存することであって、前記情報が、前記基準ゲノム内のそれぞれの長さの前記それぞれの副配列の適合の数を特定し、前記情報が、前記基準ゲノムでの前記適合の各々の前記場所をさらに特定する、保存することと、により実行される、請求項８に記載の記憶媒体。
【請求項１１】
ｎ＋１レベルに対して、前記ｎ＋１レベルの前記それぞれの副配列の適合について前記検索することが、前記ｎレベル内の前記対応するエントリに関連付けられた場所で実行される、請求項１０に記載の方法。
【請求項１２】
各エントリに関連付けられた前記適合の数を示す前記データが、第１のデータ構造内に保存され、各エントリに関連付けられた前記適合の各々の前記データ場所が、第２のデータ構造内に保存され、前記第１及び第２のデータ構造が、前記階層的索引表内に各々含まれる、請求項１０に記載の方法。
【請求項１３】
それぞれのｎレベルのエントリに対して、前記それぞれのｎレベルのエントリに対応するｎ＋１レベルのエントリを参照するメモリ内にポインタを保存することをさらに含む、請求項８に記載の方法。
【請求項１４】
検索配列を基準データに適合させるための方法であって、
演算装置により、
ａ）基準データをメモリ内に保存することと、
ｂ）前記基準データに基づいて階層的索引表を作成することであって、
第１の長さを有する前記基準データのそれぞれの副配列の各網羅的なセットに対して、
ｉ）前記基準データ内の前記第１の長さの前記それぞれの副配列の適合について検索すること、ならびに
前記階層的索引表の第１のレベルにおける前記それぞれのエントリ内の情報を保存することであって、前記情報が、前記基準データ内の前記第１の長さの前記それぞれの副配列の適合の数を特定し、前記情報が、前記基準データ内での前記適合の各々の前記場所をさらに特定する、保存すること、により、前記階層的索引表の第１のレベル内のそれぞれのエントリを作成すること、
ｉｉ）前記それぞれの第１のエントリ内の前記適合の数を第１の閾値と比較すること、ならびに
ｉｉｉ）前記第１の閾値より大きい適合の数を有する前記第１のレベル内の各それぞれのエントリに対して、第２の長さを有する副配列の第２のセットに対する前記階層的索引表の第２のレベル内のそれぞれのエントリを前記作成することを実行することであって、前記第１のレベル内の各それぞれのエントリが、前記第２のレベル内のその対応するエントリに関連付けられ、副配列の前記第２のセットが、前記第２の長さを有する前記基準データの副配列の各網羅的なセットを含み、前記第２の長さを有する前記それぞれの副配列の適合について前記検索することが、前記第１のレベル内の前記対応するエントリに関連付けられた場所で実行される、実行すること、を含む、作成することと、
ｃ）検索配列を特定する入力を受信することと、
ｄ）前記基準データへの前記検索配列の小区分の１つまたは複数の適合について前記階層的索引表を検索することであって、前記階層的索引表の前記検索は、前記階層的索引表のその後のレベルで前記検索配列の小区分の適合を反復的に検索することを含む、検索することと、を実行することを含む、検索配列を基準データに適合させるための方法。
【請求項１５】
前記基準データ及び各副配列が、数字的にコード化される、請求項１４に記載の方法。
【請求項１６】
前記階層的索引表の第２のレベル内のそれぞれのエントリを前記比較すること及び前記作成することが、第２の反復を含み、前記方法が、
前記階層的索引表の１つ以上のそれぞれの追加の閾値、長さ、副配列のセット、及びレベルを使用して、１つ以上の追加の反復を実行することをさらに含む、請求項１４に記載の方法。
【請求項１７】
前記基準データが、基準ゲノムを含み、前記基準データを検索することが、短い読み出し（ＳＲ）を前記基準ゲノムと整列させることを含む、請求項１４に記載の方法。
【請求項１８】
各エントリに関連付けられた前記場所の数を示す前記データが、第１のデータ構造内に保存され、各エントリに関連付けられた前記基準データ内の前記場所を示す前記データが、第２のデータ構造内に保存され、前記第１及び第２のデータ構造が、前記階層的索引表内に各々含まれる、請求項１４に記載の方法。
【請求項１９】
前記第２のレベル内の前記対応するエントリの前記第１のレベル内の前記それぞれのエントリとの前記関連付けが、前記第１のレベル内の前記それぞれのエントリ内に含まれる情報を含み、前記情報が、
前記第２のレベル内の前記対応するエントリを指摘するリンク情報と、前記第２の長さとを含む、請求項１４に記載の方法。
【請求項２０】
前記第２のその後の反復の各々が、
前記それぞれの閾値より大きくない適合の数を有すると発見された各それぞれの副配列に対して、
前記それぞれの副配列に関連付けられた前記エントリ内のストップ命令を保存することであって、前記ストップ命令が、前記ストップ命令に関連付けられた前記副配列に基づいてさらなるエントリの前記作成を防止するために、前記方法により使用可能である、保存すること、をさらに含む、請求項１６に記載の方法。
【請求項２１】
前記検索配列に関連付けられた前記索引表内の第１のエントリが、前記索引表の端末エントリではないとの判定に基づいて、前記検索配列の前記小区部の前記長さを増加することと、
前記第１のエントリが、前記索引表の端末エントリではないとの判定に基づいて、増加された長さの前記検索配列の前記小区分に適合する前記索引表内の第２のエントリを調べることと、をさらに含む、請求項１４に記載の方法。
【請求項２２】
前記基準データを検索する間に発見された各適合を評価することであって、
各適合に対して、前記検索配列と前記基準データとの間の塩基誤差の特定に基づいて、検索配列と前記基準データとの間の不適合を判定すること、を含む、評価すること、をさらに含む、請求項１４に記載の方法。
【請求項２３】
前記評価することが、
前記検索配列内の少なくとも１つのインデルを判定することであって、
前記検索配列のＬｏ端及びＨｉ端不適合の数に基づいて、前記検索配列内のアンカ位置を判定することと、
前記アンカ位置を使用して、前記少なくとも１つのインデルの長さ及び種類を判定することと、
前記少なくとも１つのインデルの開始位置を判定することであって、
前記適合場所で前記検索配列と前記基準データとの間の第１の移動誤差合計を演算すること、
前記適合場所からのオフセットで前記検索配列と前記基準データとの間の第２の移動誤差合計を演算することであって、前記オフセットが、前記少なくとも１つのインデルの前記種類及び長さに基づいている、演算すること、ならびに
前記第１及び第２の移動誤差合計の最小値に基づいて、前記少なくとも１つのインデルの開始場所を判定すること、を含む、判定することと、をさらに含む、請求項２２に記載の方法。