A pair character string retrieval system, comprising:
- a storing device storing a reference character string;
- an input device inputting paired first and second character strings, and an upper limit value of a distance between the first and second character strings;
- a suffix array construction processor constructing a suffix array of the reference character string;
- an index range retrieval processor computing an index range in the suffix array for each of the first and second character strings in an independent manner;
- an LSA construction processor that designates the suffix array as an initial block, divides the suffix array into two blocks corresponding to subregions that are first and second halves of the reference character string according to most significant bits thereof being zero or one, designates arrangement of the most significant bits, having been referred to, as a first column of LSA, further dichotomizes the acquired two blocks according to whether second significant bits are zero or one, thus dividing these two blocks into four blocks corresponding to subregions dividing the entire reference character string such as the entire reference genome sequence into four, designates arrangement of the second significant bits, having been referred to, as a second column of LSA, repeats analogous processing until the length of the subregion becomes one, computes each column of LSA in the processing, and thereby constructs localizable index information LSA;
- an index range localization processor that designates the respective index ranges in the suffix array that correspond to the first and second character strings as index ranges in the initial block, divides the index range in the initial block into the index ranges in the blocks using information of the first column of the LSA according to division into the two blocks corresponding to the subregions that are the first and second halves of the reference character string, divides the index ranges in the two blocks into index ranges in the four blocks using information of the second column of the LSA according to division into the four blocks corresponding to the subregions dividing the entire reference character string into four, repeats analogous processing thereafter, and performs computation of localizing the index range in the initial block into the index range in the subregion in the reference character string;
- an evaluation processor of the distance between index ranges that evaluates an upper limit of a distance between the first and second character strings localized into the subregions in the reference character string such that positional coordinates of the index ranges localized into the subregions on the reference character string have a remaining undetermined range corresponding to the subregions;
- and
- an output device outputting positions on the reference character string of the first and second character strings paired in a distance not exceeding the upper limit value,
- wherein the index range localization processor removes information of the index range incapable of creating a pair in a distance not exceeding the upper limit value, as a result of information of the index range which becomes null in the computation process and evaluation by the evaluation processor of the distance between index ranges.