THE DISCOVERY OF TOP-K DNA FREQUENT PATTERNS WITH APPROXIMATE METHOD
Nittaya Kerdprasop and Kittisak Kerdprasop
Data Engineering and Knowledge Engineering Research Units,
School of Computer Engineering, Suranaree University of Technology,
Nakhon Ratchasima, Thailand
Top-k frequent pattern discovery is indeed an association analysis concerning automatic extraction of the k most correlated and interesting patterns from large databases. Current studies in association mining concentrate on how to effectively find all objects that are frequently co-occurring. Given a set of objects with m features, there are almost 2m frequent patterns to consider. For DNA data that are normally very high in dimensionality, frequent pattern discovery from genetic data is obviously a computationally expensive problem. We therefore devise an approximate approach to tackle this problem. We propose an approximate method based on the window sliding concept to estimate data density and obtain data characteristics from a small set of samples. Then we draw a set of representatives with reservoir sampling technique. These representatives are subsequently used in the main process of frequent pattern mining. Our designed algorithm had been implemented with the Erlang language, which is the functional programming paradigm with inherent support for pattern matching. The experimental results confirm the efficiency and reliability of our approximate method.
Keywords: Top-k frequent patterns, Approximate method, DNA patterns, Window sliding, Reservoir sampling, Erlang language