STUDY ON EFFICIENT SEARCH ALGORITHMS

点击翻译按钮获取中文摘要

Technologies for discoverring knowledge from nucleic acid and amino acid sequences are most expected in Genome Informatics/Molecular Bioinformatics. Various search techniques have traditionally playd a very important role in knowledge discovery from sequence. Our goal of this research are to establish the fundamental search strategies and to analyze its computational complexity. The following are the selection of the result for our study on efficient seach algorithms :We define a new framework for rewriting graphs, called a formal graph system (FGS) , which is a logic program having hypergraphs instead of terms in first-order logic. We show that the refutation tree problem for three subclasses of FGSs are computed efficiently in parallel.A partial walk in an undirected edge-colored graph G is a path in G.If a partial walk in G contains all edges of G,it is called a walk in G.The graph inference from walk is, given a string x, to find the smallest graph which can realize x as a walk in G.We prove that the graph inference from a walk for tree of bounded degree 3 is NP-complete.The knowledge on sequences is often expressed as a motif which is a pattern common to a family of sequences. We presents a greedy strategy for finding such motifs wich ambiguity just from positive and negative examples by exploiting the probabilistic argument.We have developed a parallel machine discovery system BONSAI Garden by employing these results. This system has succeeded in discovering resonable knowledge on a hodgepodge of amino acid sequences.