Résumé

The behavior of many diseases is still not well understood by researchers. Genome-Wide Association (GWA) analyzes have recently become a popular approach to discovering the genetic causes of many complex diseases. These analyzes could lead to the discovery of genetic factors potentially involved in certain disease susceptibility. These studies typically use the most common genetic variation between individuals, the Single Nucleotide Polymorphism (SNP). Indeed, many complex diseases have been revealed to be associated with combinations of SNP interactions. However, the identification of such interactions is considered difficult. Therefore, various unsupervised data mining methods are often developed in the literature to identify such variation involved in disease. In this work, a biclustering method is adopted to detect possible associations between SNP markers and disease susceptibility. It is an unsupervised classification technique, which plays an increasingly important role in the study of modern biology. We propose an evolutionary algorithm based on a bi-objective approach for the biclustering of the Genome-Wide Association. An experimental study is achieved on synthetic data to evaluate the performance of the proposed algorithm. Promising results are obtained.

Résumé

Biclustering is an unsupervised classification technique that plays an increasingly important role in the study of modern biology. This data mining technique has provided answers to several challenges raised by the analysis of biological data and more particularly the analysis of gene expression data. It aims to cluster simultaneously genes and conditions. These unsupervised techniques are based essentially on the assumption that the extraction of the co-expressed genes allows to have co-regulated genes. In addition, the integration of biological information in the search process may induce to the extraction of relevant and non-trivial biclusters. Therefore, this work proposes an evolutionary algorithm based on local search method that relies on biological knowledge. An experimental study is achieved on real microarray datasets to evaluate the performance of the proposed algorithm. The assessment and the comparison are based on statistical and biological criteria. A cross-validation experiment is also used to estimate its accuracy. Promising results are obtained. They demonstrate the importance of the integration of the biological knowledge in the biclustering process to foster the efficiency and to promote the discovery of non-trivial and biologically relevant biclusters.

Résumé

The extraction of knowledge from large biological data is among the main challenges of bioinformatics. Several data mining techniques have been proposed to extract data; in this work, we focus on biclustering which has grown considerably in recent years. Biclustering aims to extract a set of genes with similar behavior under a condition set. In this paper, we propose an evolutionary biclustering algorithm and we analyze its performance by varying its genetic components. Hence, several versions of the evolutionary biclustering algorithm are introduced. Further, an experimental study is achieved on two real microarray datasets and the results are compared to other state-of-the-art biclustering algorithms. This thorough study allows to retain the best combination of operators among the various experienced choices.

Résumé

Biclustering has been very relevant within the field of gene expression data analysis. In fact, its main thrust stands in its ability to identify groups of genes that behave in the same way under a subset of samples (conditions). However, the pioneering algorithms of the literature has shown some limits in terms of the quality of unveiled biclusters. In this paper, we introduce a new algorithm, called BiFCA+, for biclustering microarray data. BiFCA+ heavily relies on the mathematical background of the formal concept analysis, in order to extract the set of biclusters. In addition, the Bond correlation measure is of use to filter out the overlapping biclusters. The extensive experiments, carried out on real-life datasets, shed light on BiFCA+’s ability to identify statistically and biologically significant biclusters.

Résumé

Biclustering is a popular technique to study gene expression data, especially to identify functionally related groups of genes under subsets of conditions. Nevertheless, most of the existing biclustering algorithms only focus on the positive correlations of genes. However, recent research shows that groups of biologically significant genes may exhibit negative correlations. Thus, we need a novel way to efficiently unveil such a type of correlations. We introduce, in this paper, a new algorithm, called the Negative Bicluster Finder (NBF). The sighting features of the NBF stands in its ability to discover the biclusters of negative correlations using the theoretical results provided by the Formal Concept Analysis. Exhaust experiments are carried out on three real-life datasets to assess the performance of the NBF. Our results prove the NBF's ability to statistically and biologically identify significant biclusters.

Résumé

Multiple Sequence Alignment (MSA) generally refers to cluster conserved subsequences. However, the choice of the clustering method can easily impact the quality of the alignment. In this context, we use the biclustering technique to generate a local multiple alignment which is independent of the types of biological sequences (DNA, RNA and proteins). Until now, the use of biclustering to solve the MSA problem is not well explored. In this paper, we present the Biclustering-based local MSA algorithm, called BiLMSA, that uses the bicluster enumeration approach to solve the problem of multiple sequence alignment. BiLMSA looks for aligning the maximum of blocks having the maximum relations with a set of sequences. BiLMSA was tested on proteins, RNA and DNA families. Our algorithm provides the best alignments compared to some of the best known algorithms and comparable to some others.

Résumé

A majority of existing biclustering algorithms for microarrays data focus only on extracting biclusters with positive correlations of genes. Nevertheless, biological studies show that a group of biologically significant genes may exhibit negative correlations. In this paper, we propose a new biclustering algorithm, called NBic-ARM (Negative Biclusters using Association Rule Mining). Based on Generic Association Rules, our algorithm identifies negatively-correlated genes. To assess NBic-ARM’s performance, we carried out exhaustive experiments on three real-life datasets. Our results prove NBic-ARM’s ability to identify statistically and biologically significant biclusters.

Résumé

Résumé

Most biclustering algorithms for microarrays data analysis focus on positive correlations of genes. However, recent studies demonstrate that groups of biologically significant genes can show negative correlations as well. So, discovering negatively correlated patterns from microarrays data represents a real need. In this paper, we propose a Memetic Biclustering Algorithm (MBA) which is able to detect negatively correlated biclusters. The performance of the method is evaluated based on two well-known microarray datasets (Yeast cell cycle and Saccharomyces cerevisiae), showing that MBA is able to obtain statistically and biologically significant biclusters

Résumé

Résumé

Microarrays allow measuring the expression level of a large number of genes under different experimental samples or environmental conditions. The data generated from them are called gene expression data. Gene expression data are usually represented by a matrix M, where the ith row represents the ith gene, the jth column represents the jth condition, and the cell m_ij represents the expression level of the th gene under the jth condition. In this chapter, the authors make a survey on biclustering of gene expression data. First, the chapter presents the different types of biclusters and groups of biclusters. Then, it discusses the evaluation functions and systematic and stochastic biclustering algorithms. Finally, the chapter focuses on bicluster validation that can qualitatively evaluate the capacity of an algorithm to extract meaningful biclusters from a biological point of view.

Résumé

Résumé

In the context of microarray data analysis, biclustering allows the simultaneous identification of a maximum group of genes that show highly correlated expression patterns through a maximum group of experimental conditions (samples). This paper introduces a heuristic algorithm called BicFinder (The BicFinder software is available at: http://www.info.univ-angers.fr/pub/hao/BicFinder.html) for extracting biclusters from microarray data. BicFinder relies on a new evaluation function called Average Correspondence Similarity Index (ACSI) to assess the coherence of a given bicluster and utilizes a directed acyclic graph to construct its biclusters. The performance of BicFinder is evaluated on synthetic and three DNA microarray datasets. We test the biological significance using a gene annotation web-tool to show that our proposed algorithm is able to produce biologically relevant biclusters. Experimental results show that BicFinder is able to identify coherent and overlapping biclusters.

Résumé

Biclustering is a very useful tool for analyzing microarray data. It aims to identify maximal groups of genes which are coherent with maximal groups of conditions. In this paper, we propose a biclustering algorithm, called BiMine+, which is able to detect significant biclusters from gene expression data. The proposed algorithm is based on two original features. First, BiMine+ is based on the use of a new tree structure, called Modified Bicluster Enumeration Tree (MBET), on which biclusters are represented by the profile shapes of genes. Second, BiMine+ uses a pruning rule to avoid both trivial biclusters and combinatorial explosion of the search tree. The performance of BiMine+ is assessed on both synthetic and real DNA microarray datasets. Experimental results show that BiMine+ competes favorably with several state-of-the-art biclustering algorithms and is able to extract functionally enriched and biologically relevant biclusters.

Résumé

Microarrays represent a new technology for measuring expression levels of several genes under various biological conditions generating multiple data. These data can be analyzed by using biclustering method which aims to extract a maximum number of genes and conditions presenting a similar behavior. This paper proposes a new evolutionary approach to obtain maximal high-quality biclusters of highly-correlated genes. The performance of the proposed algorithm is assessed on synthetic gene expression data. Experimental results show that our algorithm competes favorably with several state-of-the-art biclustering algorithms.

Résumé

Biclustering of microarray data

Résumé

In the context of microarray data analysis, biclustering aims to identify simultaneously a group of genes that are highly correlated across a group of experimental conditions. This paper presents a Biclustering Iterative Local Search (BILS) algorithm to the problem of biclustering of microarray data. The proposed algorithm is highlighted by the use of some original features including a new evaluation function, a dedicated neighborhood relation and a tailored perturbation strategy. The BILS algorithm is assessed on the well-known yeast cell-cycle dataset and compared with two most popular algorithms.

Résumé

Background

In a number of domains, like in DNA microarray data analysis, we need to cluster simultaneously rows (genes) and columns (conditions) of a data matrix to identify groups of rows coherent with groups of columns. This kind of clustering is called biclustering. Biclustering algorithms are extensively used in DNA microarray data analysis. More effective biclustering algorithms are highly desirable and needed.

Methods

We introduce BiMine, a new enumeration algorithm for biclustering of DNA microarray data. The proposed algorithm is based on three original features. First, BiMine relies on a new evaluation function called Average Spearman's rho (ASR). Second, BiMine uses a new tree structure, called Bicluster Enumeration Tree (BET), to represent the different biclusters discovered during the enumeration process. Third, to avoid the combinatorial explosion of the search tree, BiMine introduces a parametric rule that allows the enumeration process to cut tree branches that cannot lead to good biclusters.

Results

The performance of the proposed algorithm is assessed using both synthetic and real DNA microarray data. The experimental results show that BiMine competes well with several other biclustering methods. Moreover, we test the biological significance using a gene annotation web-tool to show that our proposed method is able to produce biologically relevant biclusters. The software is available upon request from the authors to academic users.

Résumé

Discovering association rules that identify relationships among sets of items is an important problem in data mining. Finding frequent itemsets is computationally the most expensive step in association rule discovery and therefore it has grasped significant research focus [1]. Discovery of frequently occurring subsets of items, called itemsets, is the core of many data mining methods. Most of the previous studies adopt Apriori- like algorithms, whom iteratively generate candidate itemsets and check their occurrence frequencies in the database. These approaches suffer from serious costs of repeated passes over the analyzed database. In this paper, we propose a new BDD-based (Binary Decision Diagram) data structure called TreeSupBDD. The TREESUPBDD extends the idea claimed by the authors of FP-TREE [9] and ITL-Tree [5] structures, aiming to improve storage compression and to allow frequent pattern mining without an "explicit" candidate itemset generation step. To address this problem, we propose a novel method, called TreeSupBDD- MlNE, for reducing database activity of frequent itemset discovery algorithms. The idea of TREESUPBDD-MlNE consists in using a Binary Decision Diagram and a tree for representing both database and frequent itemsets. The proposed method requires one scan over the source database : to create the associated tree and BDD and check discovered itemset supports. The originality of our work stands on the fact that the proposed algorithm extracts the frequent itemsets directly from the TreeSupBDD. Carried out experiments showed very encouraged results. Its performance improvements have been shown in a series of our experiments. We extend the binary decision diagram structure to store transaction groups and propose a new method to discover frequents itemsets. To study the trade-offs in the new representation of transactions in binary decision diagram, we compare the performance of our algorithm with the fastest Apriori [2] implementation algorithm and the latest extension of FP-Growth [15]. We have tested all the algorithms using different benchmark datasets. The performance study shows that the new algorithm significantly reduces the processing time for mining frequent itemsets from dense datasets that contain relatively long patterns and for low threshold. We discuss the performance results in detail and also the strengths and limitations of our algorithm.

Résumé

ships among sets of items is an important problem in data mining. Finding frequent itemsets is computationally the most expensive step in a association rules discovery algorithms. Therefore, it has grasped significant research focus. Most of the previous studies adopt Apriori-like algorithms, whom iteratively generate candidate itemsets and check their frequencies in the database. These approaches suffer from serious costs of repeated passes over the database. To address this problem, we propose a new parallel method, called PARALLELTREESUPBDD-MINE, for reducing cost time to find frequent itemset discovery algorithms. The idea of PRALLELTREESUPBDD-MINE consists in using a Binary De- cision Diagram (BDD) and a prefix tree for representing both database and frequent itemsets. The proposed method requires only one scan over the source database to create the associated tree and BDD and to check discovered itemset supports. The originality of our work stands on the fact that the proposed algorithm extracts in a parallel manner the frequent itemsets directly from the TREESUPBDD. We have tested our algorithm using different benchmark datasets and we have obtained good results. Keywords: Data mining, Association rules, Frequent itemsets, Binary decision diagram, Parallel data mining.