Research On The Improved Algorithm For Composite Pattern Discovery Based On Fractional Steps

Composite pattern discovery is a new research field of pattern discovery problemin Bioinformatics, and it will be a popular issue and target in this field in future to seekmore efficient and more accurate composite pattern discovery algorithms. Compositepattern discovery is the generalization of the pattern discovery problem. A difficulty ofdiscovering composite patterns is that one or more of the component monad patterns inthe groups may be “too weak”, which is poor statistical performance. So it is difficult touse some traditional monad-based approaches for the composite pattern discovery.In this paper, we propose a new algorithm called IACF (the Improved Algorithmfor Composite Pattern Discovery based on Fractional Steps, IACF) for compositepattern discovery based on fractional steps composite pattern discovery algorithm,which combines three algorithms: random projection algorithm, genetic algorithm andmultiple sequence alignment algorithm. At first, we find instances of strong monad inthe composite pattern by using a random projection algorithm and geneticalgorithm.And then, after locating other weak candidate instances of the week monad ofthe composite pattern in the downstream or upstream within a certain distance of thestrong monad, we find the weak monad instance of each sequence through multiplesequence alignment, record the distance between the two monad instances, and combinethe two parts to obtain composite patter instance. Finally, the composite pattern isderived through the representation of the common sequence without considering thebase relevance and space.IACF algorithm only needs to find the strong monad of the composite pattern, andthere is only one search process in this algorithm. The experient result demonstrates thatIACF consumses less memory than other three algorithms, RISO algorithm,MITRA-Dyad algorithm and ECOMP algorithm.We proved the practicality of IACFalgorithm using in the simulated data and real data. IACF need shorter time to findinstance than other three algorithms, when there is a strong monad in composite pattern.