SEQUENCE SEARCH SYSTEM AND SEARCH PROGRAM

摘要

The time computational complexity and the space computational complexity required when a similar part of a sequence are searched for is improved. A sequence search system comprises a first table storing the appearance positions of subsequences extending from the elements of a first sequence out of the subsequences constituting the sequence, appearance position acquiring means for acquiring the appearance positions associated with the subsequences of the first sequence stored in the first table and corresponding to the subsequences extending from the elements of a second sequence, heap forming means for putting a structural body based on the appearance positions associated with the subsequences of the first and second sequences into a heap according to the differences among the appearance positions, taking out the structural body when a structural body of the same difference appears a predetermined times in the root of the formed heap, and storing the information in a storage unit, and a similar position identifying means for identifying the position where the first sequence agrees with the second one for a predetermined length on the basis of the appearance positions associated with the subsequences of the first and second sequences of the taken-out structural bodies of the same difference.