The U-curve optimization problem is characterized by a decomposable in U-shaped curves cost function over the chains of a Boolean lattice. This problem can be applied to model the classical feature selection problem in Machine Learning. In this paper, we point out that the firstly proposed algorithm to tackle the U-curve problem, the RBM algorithm, is in fact suboptimal. We also present two new algorithms: UCS, which is actually optimal to tackle this problem; and UCSR, a variation of UCS that solves a special case of the U-curve problem and relies on a reduced, ordered binary decision diagram to control the search space. We provide results of two computational assays with these new algorithms: first, W-operator design for filtering of binary images; second, linear SVM design for classification of data sets from the UCI Machine Learning Repository. We show that, in these assays, UCS and UCSR outperformed an exhaustive search and also three widely used heuristics: the SFFS sequential selection, the BFS graph-based search, and the CHCGA genetic algorithm. Finally, we analyze the obtained results and point out improvements that might enhance the performance of these two novel algorithms.

We consider the problem of deciding the existence of matrimonial circuits, and finding implexa in kinship networks. These networks can be modeled by acyclic digraphs. A matrimonial circuit can be seen as vertex-disjoint directed paths from special starting to special ending vertices of these acyclic digraphs. An implex is the set of all matrimonial circuits of a given pair of special vertices. We present methods based on Eppstein's reduction and algorithms for finding junctions to decide the existence of matrimonial circuits. The efficiency of these methods is shown in our empirical results on seven Amerindian kinship networks. To enumerate all implexa, we present an algorithm, given that the kinship network is limited. We present some descriptive statistics which help us to justify the good performance of the methods. We incorporate to our software tool, the Kinship Machine, a feature to enumerate matrimonial circuits. This tool is being used by Anthropologists to analyze Amerindian kinship networks of northern Brazil.

Several gene regulatory network models containing concepts of directionality at the edges have been proposed. However, only a few reports have an interpretable definition of directionality. Here, differently from the standard causality concept defined by Pearl, we introduce the concept of contagion in order to infer directionality at the edges, i.e., asymmetries in gene expression dependences of regulatory networks. Moreover, we present a bootstrap algorithm in order to test the contagion concept. This technique was applied in simulated data and, also, in an actual large sample of biological data. Literature review has confirmed some genes identified by contagion as actually belonging to the TP53 pathway.

Graph matching plays a central role in different problems for structural pattern recognition. Examples of applications include matching 3D CAD models, shape matching and medical imaging, to name but a few. In this paper, we present a new integer linear formulation for the problem and employ a combinatorial optimization technique, called “column generation”, in order to solve instances of the problem. We also present computational experiments with generated instances.

MOTIVATION: A variety of biological cellular processes are achieved through a variety of extracellular regulators, signal transduction, protein-protein interactions and differential gene expression. Understanding of the mechanisms underlying these processes requires detailed molecular description of the protein and gene networks involved. To better understand these molecular networks, we propose a statistical method to estimate time-varying gene regulatory networks from time series microarray data. One well known problem when inferring connectivity in gene regulatory networks is the fact that the relationships found constitute correlations that do not allow inferring causation, for which, a priori biological knowledge is required. Moreover, it is also necessary to know the time period at which this causation occurs. Here, we present the Dynamic Vector Autoregressive model as a solution to these problems. RESULTS: We have applied the Dynamic Vector Autoregressive model to estimate time-varying gene regulatory networks based on gene expression profiles obtained from microarray experiments. The network is determined entirely based on gene expression profiles data, without any prior biological knowledge. Through construction of three gene regulatory networks (of p53, NF-kappaB and c-myc) for HeLa cells, we were able to predict the connectivity, Granger-causality and dynamics of the information flow in these networks. SUPPLEMENTARY INFORMATION: Additional figures may be found at http://mariwork.iq.usp.br/dvar/.

BACKGROUND: Several mathematical and statistical methods have been proposed in the last few years to analyze microarray data. Most of those methods involve complicated formulas, and software implementations that require advanced computer programming skills. Researchers from other areas may experience difficulties when they attempting to use those methods in their research. Here we present an user-friendly toolbox which allows large-scale gene expression analysis to be carried out by biomedical researchers with limited programming skills. RESULTS: Here, we introduce an user-friendly toolbox called GEDI (Gene Expression Data Interpreter), an extensible, open-source, and freely-available tool that we believe will be useful to a wide range of laboratories, and to researchers with no background in Mathematics and Computer Science, allowing them to analyze their own data by applying both classical and advanced approaches developed and recently published by Fujita et al. CONCLUSION: GEDI is an integrated user-friendly viewer that combines the state of the art SVR, DVAR and SVAR algorithms, previously developed by us. It facilitates the application of SVR, DVAR and SVAR, further than the mathematical formulas present in the corresponding publications, and allows one to better understand the results by means of available visualizations. Both running the statistical methods and visualizing the results are carried out within the graphical user interface, rendering these algorithms accessible to the broad community of researchers in Molecular Biology.

BACKGROUND: With the development of DNA hybridization microarray technologies, nowadays it is possible to simultaneously assess the expression levels of thousands to tens of thousands of genes. Quantitative comparison of microarrays uncovers distinct patterns of gene expression, which define different cellular phenotypes or cellular responses to drugs. Due to technical biases, normalization of the intensity levels is a pre-requisite to performing further statistical analyses. Therefore, choosing a suitable approach for normalization can be critical, deserving judicious consideration. RESULTS: Here, we considered three commonly used normalization approaches, namely: Loess, Splines and Wavelets, and two non-parametric regression methods, which have yet to be used for normalization, namely, the Kernel smoothing and Support Vector Regression. The results obtained were compared using artificial microarray data and benchmark studies. The results indicate that the Support Vector Regression is the most robust to outliers and that Kernel is the worst normalization technique, while no practical differences were observed between Loess, Splines and Wavelets. CONCLUSION: In face of our results, the Support Vector Regression is favored for microarray normalization due to its superiority when compared to the other methods for its robustness in estimating the normalization curve.