Patent ID: 8879853

Claim:
A system for enumerating local alignments, comprising a local alignment enumeration module for enumerating local alignments, which are pairs of character strings that are similar between arbitrary two documents, the local alignment enumeration module comprising: a first matrix generation module for generating a first matrix having a character string constituting one of the two documents as a row and a character string constituting another one of the two documents as a column, by registering, in a cell corresponding to a character constituting the character string in the row and a character constituting the character string in the column, a score indicating similarity at the two characters corresponding to the cell; and a second matrix generation module for generating a second matrix by registering, in a cell corresponding to the cell for which the score is calculated by the first matrix generation module, of cells of the second matrix corresponding to cells of the first matrix, an identifier of a local alignment to which the two characters corresponding to the cell belong, the score registered in the cell of the first matrix having a value that becomes larger as the similarity between the two character strings corresponding to the cell becomes higher, the first matrix generation module being configured to: calculate scores of the cell for which the score is to be calculated based on values that are preset to paths from cells for which scores are already calculated, of cells adjacent to the cell to be calculated, to the cell to be calculated; register a maximum score of the calculated scores as the score of the cell to be calculated; and store a cell which is an origin of a path via which the maximum score is calculated as a cell at a transition source, the second matrix generation module being configured to: in a case where a cell of the second matrix corresponding to the cell at the transition source indicates that the cell does not belong to any local alignment and in a case where the maximum score calculated by the first matrix generation module is a predetermined value, register an identifier of a new local alignment in the cell of the second matrix corresponding to the cell to be calculated, and store the cell to be calculated as a start point of the new local alignment; and in a case where the cell of the second matrix corresponding to the cell at the transition source indicates that the cell belongs to a local alignment, and in a case where the maximum score calculated by the first matrix generation module is larger than the predetermined value, register, in the cell of the second matrix corresponding to the cell to be calculated, an identifier of a local alignment registered in the cell of the second matrix corresponding to the cell at the transition source, and further, in a case where the maximum score calculated by the first matrix generation module is larger than the maximum score of the cells belonging to the same local alignment, store the cell to be calculated as an end point of the local alignment.