Efficient Composite Pattern Finding Algorithm Based On Asynchronous Finding

Composite pattern discovery is a new research field of pattern discovery problem in Bioinformatics. And it will be a popular issue and target in composite pattern discovery field in a long future to seek more efficient and more accurate composite pattern discovery algorithm. In this paper, we made an intensive study and discussion.In this paper, we made an intensive study of kinds of composite pattern discovery algorithms in the world, systematically illustrated MITRA-Dyad and RISO, which are the most two representative algorithms. And because the algorithm we realized in this paper had used a monad pattern discovery algorithm, we made a brief introduction to the popular monad pattern discovery algorithms nowadays, analyzed the advantages and disadvantages of each algorithm, and systematically illustrated MITRA-Count, which is a composite pattern discovery algorithm we used in the paper.ECOMP is a asynchronous composite pattern discovery algorithm based on mismatch tree data structure. We researched characteristic of dyad pattern, which is a simple form of composite pattern. By analysis and test of ECOMP, we proved that ECOMP can be used to real composite pattern discovery problem. Meanwhile, because the designed framework of MITRA-Count, which is the first step of ECOMP, it has low efficiency in time and space. We changed the recursive visit mode into non-recursive visit mode by stack-based node stroage, so we accelerated the MITRA-Count and saved space. On the other hand, we optimized the second step of ECOMP, when we combine monad patterns to the composite pattern, reduced the waste of space we realized the algorithm. and we proved the validity of optimization we made by testing the ECOMP to the simulated data and real data.