17160551
Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm
Given an input sequence of data, a motif is a repeating pattern, possibly interspersed with "dont care" characters. The data could be a sequence of characters or sets of characters or even real values. In the first two cases, the number of motifs could potentially be exponential in the size of the input sequence and in the third case there could be infinite number of motifs (assuming two real numbers are equal if they are within some specified 5 > 0 of each other). However, it has been shown in some motif based applications, such as multiple sequence aligz~nent [Par98, PFR99], that a small subset of these motifs capture all the relevant information. Also, from an information-theoretic viewpoint, the special motifs represent the sets with low co-relation, hence of higher informational value. In this paper, we show, for any sequence with n characters, there exists only a linear (or no more than 3n) number of these special motifs and every other motif can be constructed from this set. We term these special motifs as irredundant motifs. We also present an efficient polynomial time algorithm to generate these motifs. This bound on the number of useful motifs ~ves validation to motif-based approaches, since the total number of irredundant motifs does not explode. This result is potentially of significance to most applications that use pattern discovery as the basic engine such as data mining, clustering, matching and others.
18106801
Mining Protein Sequences for Motifs
We use methods from Data Mining and Knowledge Discovery to design an algorithm for detecting motifs in protein sequences. The algorithm assumes that a motif is constituted by the presence of a "good" combination of residues in appropriate locations of the motif. The algorithm attempts to compile such good combinations into a "pattern dictionary" by processing an aligned training set of protein sequences. The dictionary is subsequently used to detect motifs in new protein sequences. Statistical significance of the detection results are ensured by statistically determining the various parameters of the algorithm. Based on this approach, we have implemented a program called GYM. The Helix-Turn-Helix motif was used as a model system on which to test our program. The program was also extended to detect Homeodomain motifs. The detection results for the two motifs compare favorably with existing programs. In addition, the GYM program provides a lot of useful information about a given protein sequence.
11110395
In Vitro Implementation of Finite-State Machines
We explore the information processing capabilities and efficiency of DNA computations by giving two different types of implementations of finite-state machines. A ligation-based approach allows input of arbitrary length and can be readily implemented with current biotechnology, but requires sequential input feed and different molecules for different machines. In a second implementation not based on ligation, transitions are represented by reusable molecules, and the input, coded as a molecule, can be introduced at once. We extend the technique for programmable fault-tolerant implementation of nondeterministic finite-state machines by enforcings the basic conditions in the subset constructions that permit efficient computation. All implementations allow optical extraction of the status of the machine.
16609037
DELPHI: A pattern-based method for detecting sequence similarity
We describe DELPHI, a new computational tool for identifying sequence similarity between a query sequence and a database of proteins. Use is made of a set of patterns obtained from the underlying database through a one-time computation. The patterns are subsequently matched against every query sequence presented to the system. A pattern matched by a region of the query pinpoints a potential local similarity between that region and all of the database sequences also matching that pattern. In a final step, all such local similarities are examined more closely by aligning and scoring the corresponding query and database regions. By prudently choosing a set of patterns, the method can be used to discover weak but biologically important similarities. We provide a number of examples using both classified and unclassified proteins that corroborate this claim.
45061344
Space Complexity of Estimation of Distribution Algorithms
In this paper, we investigate the space complexity of the Estimation of Distribution Algorithms (EDAs), a class of sampling-based variants of the genetic algorithm. By analyzing the nature of EDAs, we identify criteria that characterize the space complexity of two typical implementation schemes of EDAs, the factorized distribution algorithm and Bayesian network-based algorithms. Using random additive functions as the prototype, we prove that the space complexity of the factorized distribution algorithm and Bayesian network-based algorithms is exponential in the problem size even if the optimization problem has a very sparse interaction structure.
181464
An Analysis of Phase Transition in NK Landscapes
In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model. For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.
10779366
An efficient adaptive focused crawler based on ontology learning
The enormous growth of the World Wide Web has made it important to perform resource discovery efficiently. Consequently, several new ideas have been proposed; among them a key technique is focused crawling which is able to crawl particular topical portions of the World Wide Web quickly without having to explore all Web pages. In this paper, we present an intelligent focused crawler algorithm in which we embed ontology to evaluate the page's relevance to the topic. Compared with other algorithms using domain knowledge, our algorithm can evolve the ontology automatically during crawl process. Considering the instinct characteristics of the ontology, propagation has also been imported to accelerate the evolution of the ontology. We applied our approaches in several tasks and provided an empirical evaluation which has shown promising results.
15420304
Incremental gradient descent imputation method for missing data in learning classifier systems
Learning with incomplete or missing data has been a major challenge in learning classifier system. One method for covering missing data is imputing missing values based on the statistic of known values. Another is marking them matching arbitrary case. A new approach using incremental gradient descent imputation model is proposed in this paper, which use the relationship among variables to estimate the missing value. And, some experiments are conducted in order to compare the performance of new approach and other classical covering methods.
28841129
Believability Based Iterated Belief Revision
Classical iterated belief revision methods rarely take into account the impact of the uncertain information. In this paper, an approach of believability based iterated belief revision(BIBR) is presented. BIBR relates the belief revision in the multi-agent system to the believability of information, which plays an important role in the revision process. Based on the Dempster-Shafer theory of evidence and believability function formalism, the believability of information can be obtained. The revised belief set by BIBR is dependent on the history of revision, namely, on the information received prior to the current belief set. It is proved that the BIBR operation meets the AGM postulates for belief revision and the Darwiche and Pearl postulates for iterated belief revision.