{"title":"Constraint Based Frequent Pattern Mining Technique for Solving GCS Problem","authors":"First G.M. Karthik, Second Ramachandra.V.Pujeri, Dr.","country":null,"institution":"","volume":18,"journal":"International Journal of Computer and Information Engineering","pagesStart":1989,"pagesEnd":1997,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/11090","abstract":"Generalized Center String (GCS) problem are\r\ngeneralized from Common Approximate Substring problem\r\nand Common substring problems. GCS are known to be\r\nNP-hard allowing the problems lies in the explosion of\r\npotential candidates. Finding longest center string without\r\nconcerning the sequence that may not contain any motifs is\r\nnot known in advance in any particular biological gene\r\nprocess. GCS solved by frequent pattern-mining techniques\r\nand known to be fixed parameter tractable based on the\r\nfixed input sequence length and symbol set size. Efficient\r\nmethod known as Bpriori algorithms can solve GCS with\r\nreasonable time\/space complexities. Bpriori 2 and Bpriori\r\n3-2 algorithm are been proposed of any length and any\r\npositions of all their instances in input sequences. In this\r\npaper, we reduced the time\/space complexity of Bpriori\r\nalgorithm by Constrained Based Frequent Pattern mining\r\n(CBFP) technique which integrates the idea of Constraint\r\nBased Mining and FP-tree mining. CBFP mining technique\r\nsolves the GCS problem works for all center string of any\r\nlength, but also for the positions of all their mutated copies\r\nof input sequence. CBFP mining technique construct TRIE\r\nlike with FP tree to represent the mutated copies of center\r\nstring of any length, along with constraints to restraint\r\ngrowth of the consensus tree. The complexity analysis for\r\nConstrained Based FP mining technique and Bpriori\r\nalgorithm is done based on the worst case and average case\r\napproach. Algorithm's correctness compared with the\r\nBpriori algorithm using artificial data is shown.","references":null,"publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 18, 2008"}