Natural Computing Methods in Bioinformatics: A Survey
---
paper_title: Genetic Algorithms + Data Structures = Evolution Programs

paper_content:

Like a good politician, Michalewicz begins by reducing expectations (he quotes Anthony de Mello: "[The Master] only points the way - he teaches nothing") and follows with a book that is a hodgepodge of introductory material and original work. The subject of the book, as the title suggests, is the study of evolution programs, which are genetic algorithms augmented by novel genetic operators and domain dependent data structures. Indeed, a better title for the book would be: Genetic Algorithms * (Genetic Operators + Data Structures) = Evolution Programs.
---
paper_title: Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms

paper_content:

Introduction PART I: A COMPARISON OF EVOLUTIONARY ALGORITHMS 1. Organic Evolution and Problem Solving 2. Specific Evolutionary Algorithms 3. Artificial Landscapes 4. An Empirical Comparison PART II: EXTENDING GENETIC ALGORITHMS 5. Selection 6. Mutation 7. An Experiment in Meta-Evolution Summary and Outlook Appendix A: Data for the Fletcher-Powell Function Appendix B: Data from Selection Experiments Appendix D: The Multiprocessor Environment Appendix E: Mathematical Symbols Bibliography Index
---
paper_title: The human genome project: past, present, and future

paper_content:

This article presents a short discussion of the development of the human genome program in the United States, a summary of the current status of the organization and administration of the National Institutes of Health component of the program, and some prospects for the future directions of the program and the applications of genome information.
---
paper_title: Introduction to Machine Learning and Bioinformatics

paper_content:

Introduction The Biology of a Living Organism Cells DNA and Genes Proteins Metabolism Biological Regulation Systems: When They Go Awry Measurement Technologies Probabilistic and Model-Based Learning Introduction: Probabilistic Learning Basics of Probability Random Variables and Probability Distributions Basics of Information Theory Basics of Stochastic Processes Hidden Markov Models Frequentist Statistical Inference Some Computational Issues Bayesian Inference Exercises Classification Techniques Introduction and Problem Formulation The Framework Classification Methods Applications of Classification Techniques to Bioinformatics Problems Exercises Unsupervised Learning Techniques Introduction Principal Components Analysis Multidimensional Scaling Other Dimension Reduction Techniques Cluster Analysis Techniques Exercises Computational Intelligence in Bioinformatics Introduction Fuzzy Sets Artificial Neural Networks Evolutionary Computing Rough Sets Hybridization Application to Bioinformatics Conclusion Exercises Connections Sequence Analysis Analysis of High-Throughput Gene Expression Data Network Inference Exercises Machine Learning in Structural Biology Introduction Background arp/warp resolve textal acmi Conclusion Soft Computing in Biclustering Introduction Biclustering Multiobjective Biclustering Fuzzy Possibilistic Biclustering Experimental Results Conclusions and Discussion Bayesian Methods for Tumor Classification Introduction Classification Based on Reproducing Kernel Hilbert Spaces Hierarchical Classification Model Likelihoods of RKHS Models The Bayesian Analysis Prediction and Model Choice Some Examples Concluding Remarks Modeling and Analysis of iTRAQ Data Introduction Statistical Modeling of iTRAQ Data Data Illustration Discussion and Concluding Remarks Mass Spectrometry Classification Introduction Background on Proteomics Classification Methods Data and Implementation Results and Discussion Conclusions Acknowledgment Index References appear at the end of each chapter.
---
paper_title: Optimization by simulated annealing

paper_content:

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.
---
paper_title: Neural fuzzy systems: a neuro-fuzzy synergism to intelligent systems

paper_content:

Neural Fuzzy Systems provides a comprehensive, up-to-date introduction to the basic theories of fuzzy systems and neural networks, as well as an exploration of how these two fields can be integrated to create Neural-Fuzzy Systems. It includes Matlab software, with a Neural Network Toolkit, and a Fuzzy System Toolkit.
---
paper_title: Self-organizing maps in mining gene expression data

paper_content:

Abstract Modern DNA microarray technology provides means of measuring gene expression patterns of the whole genome of simple organisms at once. Exploratory analysis of these large-scale expression datasets is becoming vital to extracting functional information from the measurements. We demonstrate how self-organizing maps (SOM) can be applied to exploratory analysis of gene expression data from a yeast DNA microarray database in order to very rapidly find gene families with similar expression patterns. SOM not only enabled quickly selecting the gene families identified in previous work, but it facilitated identifying additional genes with similar expression patterns. Identifying new families of genes also appears to be possible as demonstrated by additional clusters of genes discovered from the data. Moreover, further insight into the primary pattern variations that discriminate between the families became explicit.
---
paper_title: Applying a Fuzzy Sets-based Heuristic to the Protein Structure Prediction Problem

paper_content:

We show the application of this fuzzy sets-based heuristic to the protein structure prediction problem in two aspects: first, to analyze how the codification of the solutions affects the results, and second, to confirm that FANSis able to obtain as good results as a genetic algorithm. Both results shed some light on the application of heuristics to the protein structure prediction problem and show the benefits and power of combining basic fuzzy sets ideas with heuristic techniques. © 2002 Wiley Periodicals, Inc.
---
paper_title: Prediction of protein secondary structures by a neural network

paper_content:

We have studied the prediction of globular protein secondary structures by neural network. Protein secondary structures are allocated to amino acid residues using Kabsch and Sander's dictionary of protein secondary structures and the neural network is taught the protein secondary structures. The input layer of the neural network allows sequences of residues including 20 amino acids, chain break, B, X and Z. We consider classifying secondary structures into groups of 3, 4 and 8. In each case, we calculate the percentage of correct predictions. We discuss the effect of overlearning on the protein secondary structure prediction. In addition, we include the application of a neural network with a modular architecture to prediction of protein secondary structures
---
paper_title: Exploring the conditional coregulation of yeast gene expression through fuzzy k-means clustering

paper_content:

Organisms simplify the orchestration of gene expression by coregulating genes whose products function together in the cell. Many proteins serve different roles depending on the demands of the organism, and therefore the corresponding genes are often coexpressed with different groups of genes under different situations. This poses a challenge in analyzing whole-genome expression data, because many genes will be similarly expressed to multiple, distinct groups of genes. Because most commonly used analytical methods cannot appropriately represent these relationships, the connections between conditionally coregulated genes are often missed. We used a heuristically modified version of fuzzy k-means clustering to identify overlapping clusters of yeast genes based on published gene-expression data following the response of yeast cells to environmental changes. We have validated the method by identifying groups of functionally related and coregulated genes, and in the process we have uncovered new correlations between yeast genes and between the experimental conditions based on similarities in gene-expression patterns. To investigate the regulation of gene expression, we correlated the clusters with known transcription factor binding sites present in the genes' promoters. These results give insights into the mechanism of the regulation of gene expression in yeast cells responding to environmental changes. Fuzzy k-means clustering is a useful analytical tool for extracting biological insights from gene-expression data. Our analysis presented here suggests that a prevalent theme in the regulation of yeast gene expression is the condition-specific coregulation of overlapping sets of genes.
---
paper_title: A Fuzzy Sets based Generalization of Contact Maps for the Overlap of Protein Structures

paper_content:

The comparison of protein structures is an important problem in bioinformatics. As a protein biological role is derived from its three-dimensional native state, the comparison of a new protein structure (with unknown function) with other protein structures (with known biological activity) can shed light into the biological role of the former. Consequently, advances in the comparison (and clustering) of proteins according to their three-dimensional configurations might also have an impact on drug discovery and other biomedical research that relies on understanding the inter-relations between structure and function in proteins. The contributions described in this paper are: Firstly, we propose a generalization of the maximum contact map overlap problem (MAX-CMO) by means of fuzzy sets and systems. The MAX-CMO is a model for protein structure comparison. In our new model, namedgeneralized maximum fuzzy contact map overlap (GMAX-FCMO), a contact map is defined by means of one (or more) fuzzy thresholds and one (or more) membership functions. The advantages and limitations of our new model are discussed. Secondly, we show how a fuzzy sets based metaheuristic can be used to compute protein similarities based on the new model. Finally, we compute the protein structure similarity of real-world proteins and show how our new model correctly measures their (di)similarity.
---
paper_title: Predicting secondary structures of membrane proteins with neural networks

paper_content:

Back-propagation, feed-forward neural networks are used to predict the secondary structures of membrane proteins whose structures are known to atomic resolution. These networks are trained on globular proteins and can predict globular protein structures having no homology to those of the training set with correlation coefficients (Ci) of 0.45, 0.32 and 0.43 for alpha-helix, beta-strand and random coil structures, respectively. When tested on membrane proteins, neural networks trained on globular proteins do, on average, correctly predict (Qi) 62%, 38% and 69% of the residues in the alpha-helix, beta-strand and random coil structures. These scores rank higher than those obtained with the currently used statistical methods and are comparable to those obtained with the joint approaches tested so far on membrane proteins. The lower success score for beta-strand as compared to the other structures suggests that the sample of beta-strand patterns contained in the training set is less representative than those of alpha-helix and random coil. Our analysis, which includes the effects of the network parameters and of the structural composition of the training set on the prediction, shows that regular patterns of secondary structures can be successfully extrapolated from globular to membrane proteins.
---
paper_title: BIOINFORMATICS A Machine Learning Information Retrieval Approach to Protein Fold Recognition

paper_content:

Motivation: Recognizing proteins that have similar tertiary structure is the key step of template-based protein structure prediction methods. Traditionally, a variety of alignment methods are used to identify similar folds, based on sequence similarity and sequence-structure compatibility. Although these methods are complementary, their integration has not been thoroughly exploited. Statistical machine learning methods provide tools for integrating multiple features, but so far these methods have been used primarily for protein and fold classification, rather than addressing the retrieval problem of fold recognition-finding a proper template for a given query protein. ::: ::: Results: Here we present a two-stage machine learning, information retrieval, approach to fold recognition. First, we use alignment methods to derive pairwise similarity features for query-template protein pairs. We also use global profile--profile alignments in combination with predicted secondary structure, relative solvent accessibility, contact map and beta-strand pairing to extract pairwise structural compatibility features. Second, we apply support vector machines to these features to predict the structural relevance (i.e. in the same fold or not) of the query-template pairs. For each query, the continuous relevance scores are used to rank the templates. The FOLDpro approach is modular, scalable and effective. Compared with 11 other fold recognition methods, FOLDpro yields the best results in almost all standard categories on a comprehensive benchmark dataset. Using predictions of the top-ranked template, the sensitivity is ∼85, 56, and 27% at the family, superfamily and fold levels respectively. Using the 5 top-ranked templates, the sensitivity increases to 90, 70, and 48%. ::: ::: Availability: The FOLDpro server is available with the SCRATCH suite through http://www.igb.uci.edu/servers/psss.html. ::: ::: Contact: pfbaldi@ics.uci.edu ::: ::: Supplementary information: Supplementary data are available at http://mine5.ics.uci.edu:1026/gain.html
---
paper_title: Protein secondary structure prediction with a neural network

paper_content:

A method is presented for protein secondary structure prediction based on a neural network. A training phase was used to teach the network to recognize the relation between secondary structure and amino acid sequences on a sample set of 48 proteins of known structure. On a separate test set of 14 proteins of known structure, the method achieved a maximum overall predictive accuracy of 63% for three states: helix, sheet, and coil. A numerical measure of helix and sheet tendency for each residue was obtained from the calculations. When predictions were filtered to include only the strongest 31% of predictions, the predictive accuracy rose to 79%.
---
paper_title: Predicting the secondary structure of globular proteins using neural networks models

paper_content:

We present a new method for predicting the secondary structure of globular proteins based on non-linear neural network models. Network models learn from existing protein structures how to predict the secondary structure of local sequences of amino acids. The average success rate of our method on a testing set of proteins non-homologous with the corresponding training set was 64.3% on three types of secondary structure (alpha-helix, beta-sheet, and coil), with correlation coefficients of C alpha = 0.41, C beta = 0.31 and Ccoil = 0.41. These quality indices are all higher than those of previous methods. The prediction accuracy for the first 25 residues of the N-terminal sequence was significantly better. We conclude from computational experiments on real and artificial structures that no method based solely on local information in the protein sequence is likely to produce significantly better results for non-homologous proteins. The performance of our method of homologous proteins is much better than for non-homologous proteins, but is not as good as simply assuming that homologous sequences have identical structures.
---
paper_title: Protein secondary structure and homology by neural networks The α-helices in rhodopsin

paper_content:

Abstract Neural networks provide a basis for semiempirical studies of pattern matching between the primary and secondary structures of proteins. Networks of the perceptron class have been trained to classify the amino-acid residues into two categories for each of three types of secondary feature: α-helix or not, β-sheet or not, and random coil or not. The explicit prediction for the helices in rhodopsin is compared with both electron microscopy results and those of the Chou-Fasman method. A new measure of homology between proteins is provided by the network approach, which thereby leads to quantification of the differences between the primary structures of proteins.
---
paper_title: A multi-objective evolutionary approach to the protein structure prediction problem

paper_content:

The protein structure prediction (PSP) problem is concerned with the prediction of the folded, native, tertiary structure of a protein given its sequence of amino acids. It is a challenging and computationally open problem, as proven by the numerous methodological attempts and the research effort applied to it in the last few years. The potential energy functions used in the literature to evaluate the conformation of a protein are based on the calculations of two different interaction energies: local (bond atoms) and non-local (non-bond atoms). In this paper, we show experimentally that those types of interactions are in conflict, and do so by using the potential energy function Chemistry at HARvard Macromolecular Mechanics. A multi-objective formulation of the PSP problem is introduced and its applicability studied. We use a multi-objective evolutionary algorithm as a search procedure for exploring the conformational space of the PSP problem.
---
paper_title: Hidden Markov models for detecting remote protein homologies

paper_content:

MOTIVATION: A new hidden Markov model method (SAM-T98) for finding remote homologs of protein sequences is described and evaluated. The method begins with a single target sequence and iteratively builds a hidden Markov model (HMM) from the sequence and homologs found using the HMM for database search. SAM-T98 is also used to construct model libraries automatically from sequences in structural databases. ::: ::: METHODS: We evaluate the SAM-T98 method with four datasets. Three of the test sets are fold-recognition tests, where the correct answers are determined by structural similarity. The fourth uses a curated database. The method is compared against WU-BLASTP and against DOUBLE-BLAST, a two-step method similar to ISS, but using BLAST instead of FASTA. ::: ::: RESULTS: SAM-T98 had the fewest errors in all tests-dramatically so for the fold-recognition tests. At the minimum-error point on the SCOP (Structural Classification of Proteins)-domains test, SAM-T98 got 880 true positives and 68 false positives, DOUBLE-BLAST got 533 true positives with 71 false positives, and WU-BLASTP got 353 true positives with 24 false positives. The method is optimized to recognize superfamilies, and would require parameter adjustment to be used to find family or fold relationships. One key to the performance of the HMM method is a new score-normalization technique that compares the score to the score with a reversed model rather than to a uniform null model. ::: ::: AVAILABILITY: A World Wide Web server, as well as information on obtaining the Sequence Alignment and Modeling (SAM) software suite, can be found at http://www.cse.ucsc.edu/research/compbi o/ CONTACT: karplus@cse.ucsc.edu; http://www.cse.ucsc.edu/karplus.
---
paper_title: Improving the Prediction of Protein Secondary Structure in Three and Eight Classes Using Recurrent Neural Networks and Profiles

paper_content:

Secondary structure predictions are increasingly becoming the workhorse for several methods aiming at predicting protein structure and function. Here we use ensembles of bidirectional recurrent neural network architectures, PSI-BLAST-derived profiles, and a large nonredundant training set to derive two new predictors: (a) the second version of the SSpro program for secondary structure classification into three categories and (b) the first version of the SSpro8 program for secondary structure classification into the eight classes produced by the DSSP program. We describe the results of three different test sets on which SSpro achieved a sustained performance of about 78% correct prediction. We report confusion matrices, compare PSI-BLAST to BLAST-derived profiles, and assess the corresponding performance improvements. SSpro and SSpro8 are implemented as web servers, available together with other structural feature predictors at: http://promoter.ics.uci.edu/BRNN-PRED/. Proteins 2002;47:228–235. © 2002 Wiley-Liss, Inc.
---
paper_title: Coupled prediction of protein secondary and tertiary structure

paper_content:

The strong coupling between secondary and tertiary structure formation in protein folding is neglected in most structure prediction methods. In this work we investigate the extent to which nonlocal interactions in predicted tertiary structures can be used to improve secondary structure prediction. The architecture of a neural network for secondary structure prediction that utilizes multiple sequence alignments was extended to accept low-resolution nonlocal tertiary structure information as an additional input. By using this modified network, together with tertiary structure information from native structures, the Q3-prediction accuracy is increased by 7–10% on average and by up to 35% in individual cases for independent test data. By using tertiary structure information from models generated with the rosetta de novo tertiary structure prediction method, the Q3-prediction accuracy is improved by 4–5% on average for small and medium-sized single-domain proteins. Analysis of proteins with particularly large improvements in secondary structure prediction using tertiary structure information provides insight into the feedback from tertiary to secondary structure.
---
paper_title: Fuzzy C-means method for clustering microarray data

paper_content:

Motivation: Clustering analysis of data from DNA microarra yh ybridization studies is essential for identifying biologically relevant groups of genes. Partitional clustering methods such as K-means or self-organizing maps assign each gene to a single cluster. However, these methods do not provide information about the influence of a given gene for the overall shape of clusters. Here we apply a fuzzy partitioning method, Fuzzy C-means (FCM), to attribute cluster membership values to genes. Results: Am ajor problem in applying the FCM method for clustering microarray data is the choice of the fuzziness parameter m .W eshow that the commonly used value m = 2 is not appropriate for some data sets, and that optimal values for m vary widely from one data set to another. We propose an empirical method, based on the distribution of distances between genes in a given data set, to determine an adequate value for m .B ysetting threshold levels for the membership values, genes which are tigthly associated to a given cluster can be selected. Using a yeast cell cycle data set as an example, we show that this selection increases the overall biological significance of the genes within the cluster. Availability: Supplementary text and Matlab functions are available at http://www-igbmc.u-strasbg.fr/fcm/
---
paper_title: Predicting Protein Secondary Structure Using Neural Net and Statistical Methods

paper_content:

A comparison of neural network methods, and Bayesian statistical methods, is presented for prediction of the secondary structure of proteins given their primary sequence. The Bayesian method makes the unphysical assumption that the probability of an amino acid occurring in each position in the protein is independent of the amino acids occurring elsewhere. However, we find the predictive accuracy of the Bayesian method to be only minimally less than the accuracy of the most sophisticated methods used to date. We present the relationship of neural network methods to Bayesian statistical methods and show that in principle neural methods offer considerable power, although apparently it is not particularly useful for this problem. In the process, we derive a neural formalism in which the output neurons directly represent the conditional probabilities of structure class. The probabilistic formalism allows introduction of a new objective function, the mutual information, which translates the notion of correlation as a measure of predictive accuracy into a useful training measure. Although a similar accuracy to other approaches (utilising a Mean Square Error) is achieved using this new measure, the accuracy on the training set is significantly, and tantalisingly, higher, even though the number of adjustable parameters remains the same. The mutual information measure predicts a greater fraction of helix and sheet structures correctly than the mean square error measure, at the expense of coil accuracy -- precisely as it was designed to do. By combining the two objective functions, we obtain a marginally improved accuracy of 64.4%, with Mathews coefficients $C_\alpha$, $C_\beta$ and $C_{coil}$ of 0.40, 0.32 and 0.42 respectively. However, since all methods to date perform only slightly better than the Bayes algorithm which entails the drastic assumption of independence of amino acids, one is forced to conclude that little progress has been made on this problem despite the application of a variety of sophisticated algorithms such as neural networks, and that further advances will require a better understanding of the relevant biophysics.
---
paper_title: Validating clustering for gene expression data

paper_content:

Motivation: Many clustering algorithms have been proposed for the analysis of gene expression data, but little guidance is available to help choose among them. We provide a systematic framework for assessing the results of clustering algorithms. Clustering algorithms attempt to partition the genes into groups exhibiting similar patterns of variation in expression level. Our methodology is to apply a clustering algorithm to the data from all but one experimental condition. The remaining condition is used to assess the predictive power of the resulting clusters—meaningful clusters should exhibit less variation in the remaining condition than clusters formed by chance. Results: We successfully applied our methodology to compare six clustering algorithms on four gene expression data sets. We found our quantitative measures of cluster quality to be positively correlated with external standards of cluster quality. Availability: The software is under development.
---
paper_title: Evolving connectionist systems for knowledge discovery from gene expression data of cancer tissue

paper_content:

Microarray techniques have made it possible to observe the expression of thousands of genes simultaneously. They have recently been applied to study gene expression patterns in tissue samples. This may lead to highly desirable improvements in the diagnosis and treatment of human diseases. Statistical and machine learning methods have recently been used to classify cancer tissue based on gene expression data. Although some of these methods have achieved a high degree of accuracy, they generally lack transparency in their classification process. This, however, is crucial for the application in the medical field. In order to overcome this obstacle, we used knowledge-based neurocomputing (KBN), since KBN seeks to gain knowledge that is comprehensible to humans. In particular, we applied evolving fuzzy neural networks (EFuNNs) to classify cancer tissue, which is illustrated on the case studies of leukaemia and colon cancer. EFuNNs belong to the evolving connectionist system paradigm (ECOS) that has been recently introduced. They are well suited for adaptive learning and knowledge discovery. Fuzzy logic rules can be extracted from the trained networks and offer knowledge about the classification process in an easily accessible form. These rules point to genes that are strongly associated with specific types of cancer and may be used for the development of new tests and treatment discoveries.
---
paper_title: Analysis of expression profile using fuzzy adaptive resonance theory

paper_content:

Motivation: It is well understood that the successful clustering of expression profiles give beneficial ideas to understand the functions of uncharacterized genes. In order to realize such a successful clustering, we investigate a clustering method based on adaptive resonance theory (ART) in this report. Result: We apply Fuzzy ART as a clustering method for analyzing the time series expression data during sporulation of Saccharomyces cerevisiae. The clustering result by Fuzzy ART was compared with those by other clustering methods such as hierarchical clustering, k-means algorithm and self-organizing maps (SOMs). In terms of the mathematical validations, Fuzzy ART achieved the most reasonable clustering. We also verified the robustness of Fuzzy ART using noised data. Furthermore, we defined the correctness ratio of clustering, which is based on genes whose temporal expressions are characterized biologically. Using this definition, it was proved that the clustering ability of Fuzzy ART was superior to other clustering methods such as hierarchical clustering, k-means algorithm and SOMs. Finally, we validate the clustering results by Fuzzy ART in terms of biological functions and evidence.
---
paper_title: Critical assessment of methods of protein structure prediction—Round VII

paper_content:

This paper is an introduction to the supplemental issue of the journal PROTEINS, dedicated to the seventh CASP experiment to assess the state of the art in protein structure prediction. The paper describes the conduct of the experiment, the categories of prediction included, and outlines the evaluation and assessment procedures. Highlights are improvements in model accuracy relative to that obtainable from knowledge of a single best template structure; convergence of the accuracy of models produced by automatic servers toward that produced by human modeling teams; the emergence of methods for predicting the quality of models; and rapidly increasing practical applications of the methods.
---
paper_title: Classifying Gene Expression Data of Cancer Using Classifier Ensemble With Mutually Exclusive Features

paper_content:

The explosion of DNA and protein sequence data in public and private databases has been encouraging interdisciplinary research on biology and information technology. Gene expression profiles are just sequences of numbers, and the necessity of tools analyzing them to get useful information has risen significantly. In order to predict the cancer class of patients from the gene expression profile, this paper presents a classification framework that combines a pair of classifiers trained with mutually exclusive features. The idea behind feature selection with nonoverlapping correlation is to encourage classifier ensemble, which consists of multiple classifiers, to learn different aspects of training data, so that classifiers can search in a wide solution space. Experimental results show that the classifier ensemble produces higher recognition accuracy than conventional classifiers.
---
paper_title: Improvements in protein secondary structure prediction by an enhanced neural network.

paper_content:

Computational neural networks have recently been used to predict the mapping between protein sequence and secondary structure. They have proven adequate for determining the first-order dependence between these two sets, but have, until now, been unable to garner higher-order information that helps determine secondary structure. By adding neural network units that detect periodicities in the input sequence, we have modestly increased the secondary structure prediction accuracy. The use of tertiary structural class causes a marked increase in accuracy. The best case prediction was 79% for the class of all-alpha proteins. A scheme for employing neural networks to validate and refine structural hypotheses is proposed. The operational difficulties of applying a learning algorithm to a dataset where sequence heterogeneity is under-represented and where local and global effects are inadequately partitioned are discussed.
---
paper_title: A Hierarchical Unsupervised Growing Neural Network for Clustering Gene Expression Patterns

paper_content:

Motivation: We describe a new approach to the analysis of gene expression data coming from DNA array experiments, using an unsupervised neural network. DNA array technologies allow monitoring thousands of genes rapidly and efficiently. One of the interests of these studies is the search for correlated gene expression patterns, and this is usually achieved by clustering them. The Self-Organising Tree Algorithm, (SOTA) (Dopazo,J. and Carazo,J.M. (1997) J. Mol. Evol., 44, 226‐233), is a neural network that grows adopting the topology of a binary tree. The result of the algorithm is a hierarchical cluster obtained with the accuracy and robustness of a neural network. Results: SOTA clustering confers several advantages over classical hierarchical clustering methods. SOTA is a divisive method: the clustering process is performed from top to bottom, i.e. the highest hierarchical levels are resolved before going to the details of the lowest levels. The growing can be stopped at the desired hierarchical level. Moreover, a criterion to stop the growing of the tree, based on the approximate distribution of probability obtained by randomisation of the original data set, is provided. By means of this criterion, a statistical support for the definition of clusters is proposed. In addition, obtaining average gene expression patterns is a built-in feature of the algorithm. Different neurons defining the different hierarchical levels represent the averages of the gene expression patterns contained in the clusters. Since SOTA runtimes are approximately linear with the number of items to be classified, it is especially suitable for dealing with huge amounts of data. The method proposed is very general and applies to any data providing that they can be coded as a series of numbers and that a computable measure of similarity between data items can be used. Availability: A server running the program can be found at: http://bioinfo.cnio.es/sotarray
---
paper_title: Analysis of gene expression data using self-organizing maps

paper_content:

DNA microarray technologies together with rapidly increasing genomic sequence information is leading to an explosion in available gene expression data. Currently there is a great need for efficient methods to analyze and visualize these massive data sets. A self-organizing map (SOM) is an unsupervised neural network learning algorithm which has been successfully used for the analysis and organization of large data files. We have here applied the SOM algorithm to analyze published data of yeast gene expression and show that SOM is an excellent tool for the analysis and visualization of gene expression profiles.
---
paper_title: Interpreting patterns of gene expression with self-organizing maps: methods and application to hematopoietic differentiation.

paper_content:

Array technologies have made it straightforward to monitor simultaneously the expression pattern of thousands of genes. The challenge now is to interpret such massive data sets. The first step is to extract the fundamental patterns of gene expression inherent in the data. This paper describes the application of self-organizing maps, a type of mathematical cluster analysis that is particularly well suited for recognizing and classifying features in complex, multidimensional data. The method has been implemented in a publicly available computer package, GENECLUSTER, that performs the analytical calculations and provides easy data visualization. To illustrate the value of such analysis, the approach is applied to hematopoietic differentiation in four well studied models (HL-60, U937, Jurkat, and NB4 cells). Expression patterns of some 6,000 human genes were assayed, and an online database was created. GENECLUSTER was used to organize the genes into biologically relevant clusters that suggest novel hypotheses about hematopoietic differentiation-for example, highlighting certain genes and pathways involved in "differentiation therapy" used in the treatment of acute promyelocytic leukemia.
---
paper_title: The Protein Data Bank

paper_content:

The Protein Data Bank (PDB; http://www.rcsb.org/pdb/ ) is the single worldwide archive of structural data of biological macromolecules. This paper describes the goals of the PDB, the systems in place for data deposition and access, how to obtain further information, and near-term plans for the future development of the resource.
---
paper_title: Improved prediction of protein secondary structure by use of sequence profiles and neural networks.

paper_content:

The explosive accumulation of protein sequences in the wake of large-scale sequencing projects is in stark contrast to the much slower experimental determination of protein structures. Improved methods of structure prediction from the gene sequence alone are therefore needed. Here, we report a substantial increase in both the accuracy and quality of secondary-structure predictions, using a neural-network algorithm. The main improvements come from the use of multiple sequence alignments (better overall accuracy), from "balanced training" (better prediction of beta-strands), and from "structure context training" (better prediction of helix and strand lengths). This method, cross-validated on seven different test sets purged of sequence similarity to learning sets, achieves a three-state prediction accuracy of 69.7%, significantly better than previous methods. In addition, the predicted structures have a more realistic distribution of helix and strand segments. The predictions may be suitable for use in practice as a first estimate of the structural type of newly sequenced proteins.
---
paper_title: Protein folding simulations with genetic algorithms and a detailed molecular description

paper_content:

Abstract We have explored the application of genetic algorithms (GA) to the determination of protein structure from sequence, using a full atom representation. A free energy function with point charge electrostatics and an area based solvation model is used. The method is found to be superior to previously investigated Monte Carlo algorithms. For selected fragments, up to 14 residues long, the lowest free energy structures produced by the GA are similar in conformation to the corresponding experimental structures in most cases. There are three main conclusions from these results. First, the genetic algorithm is an effective method for searching amongst the compact conformations of a polypeptide chain. Second, the free energy function is generally able to select native-like conformations. However, some deficiencies are identified, and further development is proposed. Third, the selection of native-like conformations for some protein fragments establishes that in these cases the conformation observed in the full protein structure is largely context independent. The implications for the nature of protein folding pathways are discussed.
---
paper_title: Assembly of protein tertiary structures from fragments with similar local sequences using simulated annealing and Bayesian scoring functions

paper_content:

We explore the ability of a simple simulated annealing procedure to assemble native-like structures from fragments of unrelated protein structures with similar local sequences using Bayesian scoring functions. Environment and residue pair specific contributions to the scoring functions appear as the first two terms in a series expansion for the residue probability distributions in the protein database; the decoupling of the distance and environment dependencies of the distributions resolves the major problems with current database-derived scoring functions noted by Thomas and Dill. The simulated annealing procedure rapidly and frequently generates native-like structures for small helical proteins and better than random structures for small beta sheet containing proteins. Most of the simulated structures have native-like solvent accessibility and secondary structure patterns, and thus ensembles of these structures provide a particularly challenging set of decoys for evaluating scoring functions. We investigate the effects of multiple sequence information and different types of conformational constraints on the overall performance of the method, and the ability of a variety of recently developed scoring functions to recognize the native-like conformations in the ensembles of simulated structures.
---
paper_title: Gene selection and cancer classification using a fuzzy neural network

paper_content:

Cancer classification based on microarray gene expressions is an important problem. In this work, we use a t- test-based feature selection method to choose some important genes from thousands of genes. After that, we classify the microarray data sets with a fuzzy neural network (FNN) that we proposed earlier. This FNN combines important features of initial fuzzy model self-generation, parameter optimization, and rule-base simplification. We applied this FNN to three well-known gene expression data sets, i.e., the lymphoma data set (with 3 sub-types), small round blue cell tumor (SRBCT) data set (with 4 sub-types), and the liver cancer data set (with 2 classes, i.e., non-tumor and hepatocellular carcinoma (HCC)). Our results in all the three data sets show that the FNN can obtain 100% accuracy with a much smaller number of genes in comparison with previously published methods. In view of the smaller number of genes required by the FNN and its high accuracy, we conclude that the FNN classifier not only helps biological researchers differentiate cancers that are difficult to be classified using traditional clinical methods, but also helps biological researchers focus on a small number of important genes to find the relationships between those important genes and the development of cancers.
---
paper_title: Exploiting the Past and the Future in Protein Secondary Structure Prediction

paper_content:

Motivation: Predicting the secondary structure of a protein (alpha-helix, beta-sheet, coil) is an important step towards elucidating its three-dimensional structure, as well as its function. Presently, the best predictors are based on machine learning approaches, in particular neural network architectures with a fixed, and relatively short, input window of amino acids, centered at the prediction site. Although a fixed small window avoids overfitting problems, it does not permit capturing variable long-rang information. Results: We introduce a family of novel architectures which can learn to make predictions based on variable ranges of dependencies. These architectures extend recurrent neural networks, introducing non-causal bidirectional dynamics to capture both upstream and downstream information. The prediction algorithm is completed by the use of mixtures of estimators that leverage evolutionary information, expressed in terms of multiple alignments, both at the input and output levels. While our system currently achieves an overall performance close to 76% correct prediction ‐ at least comparable to the best existing systems ‐ the main emphasis here is on the development of new algorithmic
---
paper_title: Improving prediction of protein secondary structure using structured neural networks and multiple sequence alignments

paper_content:

The prediction of protein secondary structure by use of carefully structured neural networks and multiple sequence alignments has been investigated. Separate networks are used for predicting the three secondary structures alpha-helix, beta-strand, and coil. The networks are designed using a priori knowledge of amino acid properties with respect to the secondary structure and the characteristic periodicity in alpha-helices. Since these single-structure networks all have less than 600 adjustable weights, overfitting is avoided. To obtain a three-state prediction of alpha-helix, beta-strand, or coil, ensembles of single-structure networks are combined with another neural network. This method gives an overall prediction accuracy of 66.3% when using 7-fold cross-validation on a database of 126 nonhomologous globular proteins. Applying the method to multiple sequence alignments of homologous proteins increases the prediction accuracy significantly to 71.3% with corresponding Matthew's correlation coefficients C alpha = 0.59, C beta = 0.52, and Cc = 0.50. More than 72% of the residues in the database are predicted with an accuracy of 80%. It is shown that the network outputs can be interpreted as estimated probabilities of correct prediction, and, therefore, these numbers indicate which residues are predicted with high confidence.
---
paper_title: Neural network system for the evaluation of side-chain packing in protein structures

paper_content:

An artificial neural network system is used for pattern recognition in protein side-chain-side-chain contact maps. A back-propagation network was trained on a set of patterns which are popular in side-chain contact maps of protein structures. Several neural network architectures and different training parameters were tested to decide on the best combination for the neural network. The resulting network can distinguish between original (from protein structures) and randomized patterns with an accuracy of 84.5% and a Matthews' coefficient of 0.72 for the testing set. Applications of this system for protein structure evaluation and refinement are also proposed. Examples include structures obtained after the application of molecular dynamics to crystal structures, structures obtained from X-ray crystallography at various stages of refinement, structures obtained from a de novo folding algorithm and deliberately misfolded structures.
---
paper_title: An EA framework for biclustering of gene expression data

paper_content:

In recent years, several biclustering methods have been suggested to identify local patterns in gene expression data. Most of these algorithms represent greedy strategies that are heuristic in nature: an approximate solutions is found within reasonable time bounds. The quality of biclustering, though, is often considered more important than the computation time required to generate it. Therefore, this paper addresses the question whether additional run-time resources can be exploited in order to improve the outcome of the aforementioned greedy algorithms. To this end, we propose a general framework that embed such biclustering methods as local search procedures in an evolutionary algorithm. We demonstrate on one prominent example that this approach achieves significant improvements in the quality of the biclusters when compared to the application of the greedy strategy alone.
---
paper_title: Neural fuzzy systems: a neuro-fuzzy synergism to intelligent systems

paper_content:

Neural Fuzzy Systems provides a comprehensive, up-to-date introduction to the basic theories of fuzzy systems and neural networks, as well as an exploration of how these two fields can be integrated to create Neural-Fuzzy Systems. It includes Matlab software, with a Neural Network Toolkit, and a Fuzzy System Toolkit.
---
paper_title: KEGG: Kyoto Encyclopedia of Genes and Genomes

paper_content:

Kyoto Encyclopedia of Genes and Genomes (KEGG) is a knowledge base for systematic analysis of gene functions in terms of the networks of genes and molecules. The major component of KEGG is the PATHWAY database that consists of graphical diagrams of biochemical pathways including most of the known metabolic pathways and some of the known regulatory pathways. The pathway information is also represented by the ortholog group tables summarizing orthologous and paralogous gene groups among different organisms. KEGG maintains the GENES database for the gene catalogs of all organisms with complete genomes and selected organisms with partial genomes, which are continuously re-annotated, as well as the LIGAND database for chemical compounds and enzymes. Each gene catalog is associated with the graphical genome map for chromosomal locations that is represented by Java applet. In addition to the data collection efforts, KEGG develops and provides various computational tools, such as for reconstructing biochemical pathways from the complete genome sequence and for predicting gene regulatory networks from the gene expression profiles. The KEGG databases are daily updated and made freely available (http://www.genome.ad.jp/kegg/).
---
paper_title: Gene interaction - An evolutionary biclustering approach

paper_content:

DNA Microarray experiments form a powerful tool for studying gene expression patterns, in large scale. Sharing of the regulatory mechanism among genes, in an organism, is predominantly responsible for their co-expression. Biclustering aims at finding a subset of similarly expressed genes under a subset of experimental conditions. A small number of genes participate in a cellular process of interest. Again, a gene may be simultaneously involved in a number of cellular processes. In cellular environment, genes interact among themselves to produce enzymes, metabolites, proteins, etc. responsible for a particular function(s). In this study, a simple and novel correlation-based approach is proposed to extract gene interaction networks from biclusters in microarray data. Local search strategy is employed to add (remove) relevant (irrelevant) genes for finer tuning, in multi-objective biclustering framework. Preprocessing is done to preserve strongly correlated gene interaction pairs. Experimental results on time-series gene expression data from Yeast are biologically validated using benchmark databases and literature.
---
paper_title: Inference of a gene regulatory network by means of interactive evolutionary computing

paper_content:

Inferring a gene regulatory network is one of the challenging topics in, the field of Bioinformatics. In order to infer a network structure effectively, the new approach that allows human intervention and strategic data acquisition in the inference process seems to be necessary. In this paper, we will propose an effective approach for interactively inferring gene regulatory networks using gene expression data from DNA microarrays. We will also establish the system that realizes our approach by GA-based interactive algorithm. Experimental results show that our method can infer the network structure accurately with a relatively small amount of expression data.
---
paper_title: Genetic Algorithms + Data Structures = Evolution Programs

paper_content:

Like a good politician, Michalewicz begins by reducing expectations (he quotes Anthony de Mello: "[The Master] only points the way - he teaches nothing") and follows with a book that is a hodgepodge of introductory material and original work. The subject of the book, as the title suggests, is the study of evolution programs, which are genetic algorithms augmented by novel genetic operators and domain dependent data structures. Indeed, a better title for the book would be: Genetic Algorithms * (Genetic Operators + Data Structures) = Evolution Programs.
---
paper_title: Modeling Regulatory Networks with Weight Matrices

paper_content:

Systematic gene expression analyses provide comprehensive information about the transcriptional response to different environmental and developmental conditions. With enough gene expression data points, computational biologists may eventually generate predictive computer models of transcription regulation. Such models will require computational methodologies consistent with the behavior of known biological systems that remain tractable. We represent regulatory relationships between genes as linear coefficients or weights, with the "net" regulation influence on a gene's expression being the mathematical summation of the independent regulatory inputs. Test regulatory networks generated with this approach display stable and cyclically stable gene expression levels, consistent with known biological systems. We include variables to model the effect of environmental conditions on transcription regulation and observed various alterations in gene expression patterns in response to environmental input. Finally, we use a derivation of this model system to predict the regulatory network from simulated input/output data sets and find that it accurately predicts all components of the model, even with noisy expression data.
---
paper_title: Discovering gene networks with a neural-genetic hybrid

paper_content:

Recent advances in biology (namely, DNA arrays) allow an unprecedented view of the biochemical mechanisms contained within a cell. However, this technology raises new challenges for computer scientists and biologists alike, as the data created by these arrays is often highly complex. One of the challenges is the elucidation of the regulatory connections and interactions between genes, proteins and other gene products. In this paper, a novel method is described for determining gene interactions in temporal gene expression data using genetic algorithms combined with a neural network component. Experiments conducted on real-world temporal gene expression data sets confirm that the approach is capable of finding gene networks that fit the data. A further repeated approach shows that those genes significantly involved in interaction with other genes can be highlighted and hypothetical gene networks and circuits proposed for further laboratory testing.
---
paper_title: From specific gene regulation to genomic networks : a global analysis of transcriptional regulation in Escherichia coli

paper_content:

Summary Because a large number of molecular mechanisms involved in gene regulation have been described during the last decades, it is now becoming possible to address questions about the global structure of gene regulatory networks, at least in the case of some of the best-characterized organisms.This paper presents a global characterization of the transcriptional regulation in Escherichia coli on the basis of the current data. The connectivity of the corresponding network was evaluated by analyzing the distribution of the number of genes regulated by a given regulatory protein, and the distribution of the number of regulatory genes regulating a given regulated gene. The mean connectivity found (between 2 and 3) shows a rather loosely interconnected structure. Special emphasis is given to circular sequences of interactions (‘‘circuits’’) because of their critical dynamical properties. Only one-element circuits were found, in which negative autoregulation is the dominant architecture. These global properties are discussed in light of several pertinent theoretical approaches, as well as in terms of physiological and evolutionary considerations. BioEssays 20:433‐440, 1998. r 1998 John Wiley & Sons, Inc.
---
paper_title: Genetic network inference: from co-expression clustering to reverse engineering

paper_content:

motivation: Advances in molecular biological, analytical and computational technologies are enabling us to systematically investigate the complex molecular processes underlying biological systems. In particular, using highthroughput gene expression assays, we are able to measure the output of the gene regulatory network. We aim here to review datamining and modeling approaches for conceptualizing and unraveling the functional relationships implicit in these datasets. Clustering of co-expression profiles allows us to infer shared regulatory inputs and functional pathways. We discuss various aspects of clustering, ranging from distance measures to clustering algorithms and multiple-cluster memberships. More advanced analysis aims to infer causal connections between genes directly, i.e. who is regulating whom and how. We discuss several approaches to the problem of reverse engineering of genetic networks, from discrete Boolean networks, to continuous linear and non-linear models. We conclude that the combination of predictive modeling with systematic experimental verification will be required to gain a deeper insight into living organisms, therapeutic targeting and bioengineering.
---
paper_title: Increasing the efficiency of fuzzy logic-based gene expression data analysis

paper_content:

DNA microarray technology can accommodate a multifaceted analysis of the expression of genes in an organism. The wealth of spatiotemporal data generated by this technology allows researchers to potentially reverse engineer a particular genetic network. “Fuzzy logic” has been proposed as a method to analyze the relationships between genes and help decipher a genetic network. This method can identify interacting genes that fit a known “fuzzy” model of gene interaction by testing all combinations of gene expression profiles. This paper introduces improvements made over previous fuzzy gene regulatory models in terms of computation time and robustness to noise. Improvement in computation time is achieved by using a cluster analysis as a preprocessing method to reduce the total number of gene combinations analyzed. This approach speeds up the algorithm by a factor of 50% with minimal effect on the results. The model’s sensitivity to noise is reduced by implementing appropriate methods of “fuzzy rule aggregation...
---
paper_title: Multi-objective evolutionary biclustering of gene expression data

paper_content:

Biclustering or simultaneous clustering of both genes and conditions have generated considerable interest over the past few decades, particularly related to the analysis of high-dimensional gene expression data in information retrieval, knowledge discovery, and data mining. The objective is to find sub-matrices, i.e., maximal subgroups of genes and subgroups of conditions where the genes exhibit highly correlated activities over a range of conditions. Since these two objectives are mutually conflicting, they become suitable candidates for multi-objective modeling. In this study, a novel multi-objective evolutionary biclustering framework is introduced by incorporating local search strategies. A new quantitative measure to evaluate the goodness of the biclusters is developed. The experimental results on benchmark datasets demonstrate better performance as compared to existing algorithms available in literature.
---
paper_title: A Fuzzy Logic Approach to Analyzing Gene Expression Data

paper_content:

We have developed a novel algorithm for analyzing gene expression data. This algorithm uses fuzzy logic to transform expression values into qualitative descriptors that can be evaluated by using a set of heuristic rules. In our tests we designed a model to find triplets of activators, repressors, and targets in a yeast gene expression data set. For the conditions tested, the predictions made by the algorithm agree well with experimental data in the literature. The algorithm can also assist in determining the function of uncharacterized proteins and is able to detect a substantially larger number of transcription factors than could be found at random. This technology extends current techniques such as clustering in that it allows the user to generate a connected network of genes using only expression data.
---
paper_title: Linear fuzzy gene network models obtained from microarray data by exhaustive search

paper_content:

BackgroundRecent technological advances in high-throughput data collection allow for experimental study of increasingly complex systems on the scale of the whole cellular genome and proteome. Gene network models are needed to interpret the resulting large and complex data sets. Rationally designed perturbations (e.g., gene knock-outs) can be used to iteratively refine hypothetical models, suggesting an approach for high-throughput biological system analysis. We introduce an approach to gene network modeling based on a scalable linear variant of fuzzy logic: a framework with greater resolution than Boolean logic models, but which, while still semi-quantitative, does not require the precise parameter measurement needed for chemical kinetics-based modeling.ResultsWe demonstrated our approach with exhaustive search for fuzzy gene interaction models that best fit transcription measurements by microarray of twelve selected genes regulating the yeast cell cycle. Applying an efficient, universally applicable data normalization and fuzzification scheme, the search converged to a small number of models that individually predict experimental data within an error tolerance. Because only gene transcription levels are used to develop the models, they include both direct and indirect regulation of genes.ConclusionBiological relationships in the best-fitting fuzzy gene network models successfully recover direct and indirect interactions predicted from previous knowledge to result in transcriptional correlation. Fuzzy models fit on one yeast cell cycle data set robustly predict another experimental data set for the same system. Linear fuzzy gene networks and exhaustive rule search are the first steps towards a framework for an integrated modeling and experiment approach to high-throughput "reverse engineering" of complex biological systems.
---

Title: Natural Computing Methods in Bioinformatics: A Survey

Section 1: Introduction
Description 1: Introduce the significant developments in bioinformatics and the necessity for advanced mathematical and algorithmic methods to process and extract information from biological data.

Section 2: Protein Structure Prediction
Description 2: Discuss methodologies used for predicting protein structures, including historical approaches and contemporary techniques employing neural networks, evolutionary algorithms, and other natural computing methods.

Section 3: Microarray Data Analysis
Description 3: Present various natural computing tools and techniques used for the analysis of microarray data, focusing on clustering, classification, and feature selection methods.

Section 4: Biological Networks Modeling
Description 4: Provide an overview of methodologies used for modeling biological networks, including genetic regulatory networks, transcriptional networks, and techniques like fuzzy logic and neural networks.

Section 5: Conclusions
Description 5: Summarize the main points of the survey, highlighting the success and critical importance of Natural Computing models in bioinformatics, and suggest future directions for research.