DISCOVERY of LONGEST INCREASING SUBSEQUENCES and its VARIANTS using DNA OPERATIONS

摘要

The Longest Increasing Subsequence (LIS) and Common Longest Increasing Subsequence (CLIS) have their importance in many data mining applications. We propose algorithms to discover LIS and CLIS from varied databases. This work finds all increasing subsequences from the given database, find increasing subsequences in n sliding window, longest increasing sequences in one and more sequences, decreasing subsequences and common increasing sequences of varied window sizes. The proposed work can be applied to finding diverging patterns, constraint LIS, sequence alignment, find motifs in genetic data bases, pattern recognition, mine emerging patterns, and contrast patterns in both, scientific and commercial databases. The algorithms are implemented and tested for accuracy in both real and simulated databases. Finally, the validity of the algorithms are checked and their time complexity are analyzed.