Pattern-driven neighborhood search for biclustering of microarray data.

BACKGROUND: Biclustering aims at finding subgroups of genes that show highly correlated behaviors across a subgroup of conditions. Biclustering is a very useful tool for mining microarray data and has various practical applications. From a computational point of view, biclustering is a highly combinatorial search problem and can be solved with optimization methods. RESULTS: We describe a stochastic pattern-driven neighborhood search algorithm for the biclustering problem. Starting from an initial bicluster, the proposed method improves progressively the quality of the bicluster by adjusting some genes and conditions. The adjustments are based on the quality of each gene and condition with respect to the bicluster and the initial data matrix. The performance of the method was evaluated on two well-known microarray datasets (Yeast cell cycle and Saccharomyces cerevisiae), showing that it is able to obtain statistically and biologically significant biclusters. The proposed method was also compared with six reference methods from the literature. CONCLUSIONS: The proposed method is computationally fast and can be applied to discover significant biclusters. It can also used to effectively improve the quality of existing biclusters provided by other biclustering methods.

An evaluation study of biclusters visualization techniques of gene expression data.

Biclustering is a non-supervised data mining technique used to analyze gene expression data, it consists to classify subgroups of genes that have similar behavior under subgroups of conditions. The classified genes can have independent behavior under other subgroups of conditions. Discovering such co-expressed genes, called biclusters, can be helpful to find specific biological features such as gene interactions under different circumstances. Compared to clustering, biclustering has two main characteristics: bi-dimensionality which means grouping both genes and conditions simultaneously and overlapping which means allowing genes to be in more than one bicluster at the same time. Biclustering algorithms, which continue to be developed at a constant pace, give as output a large number of overlapping biclusters. Visualizing groups of biclusters is still a non-trivial task due to their overlapping. In this paper, we present the most interesting techniques to visualize groups of biclusters and evaluate them.

VisBicluster: A Matrix-Based Bicluster Visualization of Expression Data.

One of the main methods to analyze gene expression data is biclustering, a nonsupervised technique, which consists of selection subgroups of genes that co-expressed under subgroups of experimental conditions. A large number of biclustering algorithms have been developed to classify gene expression data. These algorithms can give as output a large number of overlapped biclusters, whose visualization still requires deeper studies. We present VisBicluster, a web-based interactive visualization tool for displaying biclustering results. The developed visualization technique consists of laying out the generated biclusters in a two-dimensional matrix where each bicluster is represented as a column and each overlap between a set of biclusters is represented as a row. A search interface for the user is developed to query the matrix of bicluster intersection and visualize the results matching the queries. Our tool supports many interactive features such as sorting, zooming, and details-on-demand. We proved the usefulness of VisBicluster with biclustering results from real and synthetic datasets. Besides, we performed a user study with 14 participants to illustrate the clarity and simplicity of overlap representation with our tool.

J-binding protein 1 and J-binding protein 2 expression in clinical Leishmania major no response-antimonial isolates.

Cutaneous leishmaniasis (CL) is a major disease in many parts of the world. Since no vaccine has been developed, treatment is the best way to control it. In most areas, antimonial resistance whose mechanisms have not been completely understood has been reported. The main aim of this study is gene expression assessing of J-binging protein 1 and J-binding protein 2 in clinical Leishmania major isolates. The patients with CL from central and north Iran were considered for this study. The samples were transferred in RNAlater solution and stored in - 20 °C. RNA extraction and cDNA synthesis were performed. The gene expression analysis was done with SYBR Green real-time PCR using ∆∆CT. Written informed consent forms were filled out by patients, and then, information forms were filled out based on the Helsinki Declaration. Statistical analysis was done with SPSS (16.0; SPSS Inc, Chicago) using independent t test, Shapiro-Wilk, and Pearson's and Spearman's rank correlation coefficients. P ≤ 0.05 was considered significant. The gene expression of JBP1 and JBP2 had no relation with sex and age. The JBP1 gene expression was high in sensitive isolates obtained from north of the country. The JBP2 gene expression was significant in sensitive and no response-antimonial isolates from the north, but no significant differences were detected in sensitive and resistant isolates from central Iran. Differential gene expression of JBP1 and JBP2 in various clinical resistances isolates in different geographical areas shows multifactorial ways of developing resistance in different isolates.

Gene expression of RNAP II, JBP1 and JBP2 in Leishmania major exposed to antimonials, amphotericin B and paromomycin

Cutaneous leishmaniosis (CL) is treated with pentavalent antimony (SbV) as a first-line drug, while amphotericin B and paromomycin are potential alternatives in antimonial- resistant isolates. However, the mechanisms of drug resistance remain unclear. The present study analyses the gene expression of RNA polymerase II (RNAP II) and J-binding protein 1 (JBP1), and J-binding protein 2 (JBP2) in Leishmania major after exposure to drugs in vitro. L. major (MRHO/IR/75/ER) promastigotes were exposed to various concentrations of glucantime, paromomycin and amphotericin B for 72 hours. The RNA was then extracted and used for cDNA synthesis. The expressions of JBP1, JBP2 and RNAP II were analysed using SYBR Green real-time PCR. No change in JBP2 or RNAP II expression was associated with amphotericin B, but JBP1 expression decreased with increasing drug concentration. Paromomycin had no effect on JBP2 expression, but a 13.5-fold increase in JBP1 was observed at 100 µg/ml, and a decrease in RNAP II expression at 25 and 50 µg/ml. Exposure to glucantime resulted in 1.4-fold lower JBP1 expression at 5 µg/ml, and 333.33- to 500-fold lower RNAP II at concentrations of 5 to 15 µg/ml. As Base J synthesis requires both JBP1 and JBP2, RNAP II (encoding RNA polymerase II) could reduce expression. However, RNAP II was not expressed in all groups, indicating that the genes associated with drug resistance may be regulated in other ways.

A novel biclustering algorithm of binary microarray data: BiBinCons and BiBinAlter.

The biclustering of microarray data has been the subject of a large research. No one of the existing biclustering algorithms is perfect. The construction of biologically significant groups of biclusters for large microarray data is still a problem that requires a continuous work. Biological validation of biclusters of microarray data is one of the most important open issues. So far, there are no general guidelines in the literature on how to validate biologically extracted biclusters. In this paper, we develop two biclustering algorithms of binary microarray data, adopting the Iterative Row and Column Clustering Combination (IRCCC) approach, called BiBinCons and BiBinAlter. However, the BiBinAlter algorithm is an improvement of BiBinCons. On the other hand, BiBinAlter differs from BiBinCons by the use of the EvalStab and IndHomog evaluation functions in addition to the CroBin one (Bioinformatics 20:1993-2003, 2004). BiBinAlter can extracts biclusters of good quality with better p-values.

A fast Boyer-Moore type pattern matching algorithm for highly similar sequences.

In the last decade, biology and medicine have undergone a fundamental change: next generation sequencing (NGS) technologies have enabled to obtain genomic sequences very quickly and at small costs compared to the traditional Sanger method. These NGS technologies have thus permitted to collect genomic sequences (genes, exomes or even full genomes) of individuals of the same species. These latter sequences are identical to more than 99%. There is thus a strong need for efficient algorithms for indexing and performing fast pattern matching in such specific sets of sequences. In this paper we propose a very efficient algorithm that solves the exact pattern matching problem in a set of highly similar DNA sequences where only the pattern can be pre-processed. This new algorithm extends variants of the Boyer-Moore exact string matching algorithm. Experimental results show that it exhibits the best performances in practice.

Extraction of infrequent simple motifs from a finite set of sequences using a lattice structure.

In this paper we present a method for finding infrequent simple motifs in a finite set of sequences. The method uses a lattice structure and minimal forbidden patterns. It is based on a method for solving the Simple Motif Problem and has the potential to discover new patents in biological macromolecules. Indeed, the extracted motifs can help biologists to learn about the biological functions of these macromolecules and, consequently, can help them to understand the mechanisms of the biological processes in which these sequences are involved.

Foreword.

Pattern finding in biomolecular data is at the core of Computational Molecular Biology research. Indeed, it makes a very important contribution in the analysis of these data. It can reveal information about shared biological functions of biological macromolecules, coming from several different organisms, by the identification of patterns that are shared by structures related to these macromolecules. These patterns, which have been conserved during evolution, often play an important structural and/or functional role, and consequently, shed light on the mechanisms and the biological processes in which these macromolecules participate. Pattern finding in biomolecular data is also used in evolutionary studies, in order to analyze relationships that exist between species and establish if two, or several, biological macromolecules are homologous and to reconstruct the phylogenetic tree that links them to their common biological ancestor. On the other hand, with the new sequencing technologies, the number of biological sequences in databases is increasing exponentially. In addition, the lengths of these sequences are large. Hence, the finding of patterns in such databases requires the development of fast, low memory requirement and highperformance techniques and approaches. This issue contains very interesting papers that deal with pattern finding in Computational Molecular Biology.

A biclustering algorithm based on a bicluster enumeration tree: application to DNA microarray data.

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.