An improvement of the overlap complexity in the spaced seed searching problem between genomic DNAs

In homology search, finding optimal multiple spaced seeds in genomic DNA sequences is NP-hard but even finding good ones is very difficult. The exponential-time algorithm PatternHunter use optimal spaced seeds to increase both the sensitivity and the speed of homology search. The overlap complexity measure based on the overlaps between hits of a multiple seed are well correlated with sensitivity but is computable in polynomial time. Based on overlap complexity, we have improved polynomial-time algorithms to provide better multiple seeds. Our experimental results shows that these improvements significantly run faster and make better quality of spaced seeds than previous algorithms in almost all test cases.