International Journal on Artificial Intelligence Tools

Hard or large-scale constraint satisfaction and optimization problems, occur widely in artificial intelligence and operations research. These problems are often difficult to solve with global search methods, but many of them can be efficiently solved by local search methods. Evolutionary algorithms are local search methods which have considerable success in tackling difficult, or ill-defined optimization problems. In contrast they have not been so successful in tackling constraint satisfaction problems. Other local search methods, in particular GENET and EGENET are designed specifically for constraint satisfaction problems, and have demonstrated remarkable success in solving hard examples of these problems. In this paper we examine how we can transfer the mechanisms that were so successful in (E)GENET to evolutionary algorithms, in order to tackle constraint satisfaction algorithms efficiently. An empirical comparison of our evolutionary algorithm improved by mechanisms from EGENET and shows how it can markedly improve on the efficiency of EGENET in solving certain hard instances of constraint satisfaction problems.

This paper proposes a DNA algorithm for solving an NP-complete problem (The Shortest Common Superstring Problem) by manipulation of biomolecules, and presents partial results of the experiment that implements our algorithm. We also discuss practical constraints that have to be taken into account when implementing the algorithm, propose a coding system as a solution to these practical restrictions, and discuss the control experiments performed for establishing the parameters controlling the specificity of the assay.

This paper presents a new method of comparison of protein structures from the viewpoint of the secondary structural elements. The structural similarity can be evaluated through the structure transformation from one protein to the other, which is composed of a set of predefined primitive operations that are applied to each of the secondary structural elements. The cost that is required for each of the primitive operations is defined in advance, and the similarity between the proteins is calculated as the total cost of transformation that is the sum of costs for applied primitive operations. In addition, a feature extraction method that is also based on the structural transformation is presented. In this method, the feature to be extracted is defined as a pair including a representative structure and a cluster region. The representative structure is generated by estimating the center of structural balance among proteins in one cluster using the transformation costs. The cluster region shows how far the cluster has spread. The effectiveness of these methods are empirically demonstrated through the experiments using the data in the Brookhaven Protein Data Bank.

With the exponential accumulation of sequence data, continued progress in the Human Genome Project will depend increasingly on advanced computational tools to manage and analyze the data. Utilizing information embedded within families of homologous sequences, a gene family identification approach may facilitate the understanding of gene functions. We have developed a GeneFIND (Gene Family Identification Network Design) system for database searching against gene families. It provides rapid and accurate protein family identification by combining global and motif sequence similarities and incorporating ProClass family information. Multi-level filters are used, starting with the MOTIFIND neural networks and BLAST search, followed by SSEARCH alignment, motif pattern match, hidden Markov modeling of motifs and ClustalW motif alignment. GeneFIND has been implemented as a full-scale system for the classification of more than 1200 ProSite and 6000 PIR families. It has been used to identify thousands of new family members and is well suited for genomic sequence analysis. The system is available for on-line family identification from our WWW server ().

Biological data mining is the activity of finding significant information in biomolecular data. The significant information may refer to motifs, clusters, genes, and protein signatures. This paper presents an example of biological data mining: the recognition of promoters in DNA. We propose a two-level ensemble of classifiers to recognize E. Coli promoter sequences. The first-level classifiers include three Bayesian neural networks that learn from three different feature sets. The outputs of the first-level classifiers are combined in the second-level to give the final result. Empirical study shows that a precision rate of 92.2% is achieved, indicating an excellent performance of the proposed approach.