bluuebunny/crossref_metadata_2025_split huggingface dataset:
Discovering statistically significant biclusters in gene expression data
Authors: Tanay Amos , Sharan Roded , Shamir Ron 
Published: May 2011

Abstract
In gene expression data, a bicluster is a subset of the genes exhibiting consistent patterns over a subset of the conditions. We propose a new method to detect significant biclusters in large expression datasets. Our approach is graph theoretic coupled with statistical modelling of the data. Under plausible assumptions, our algorithm is polynomial and is guaranteed to find the most significant biclusters. We tested our method on a collection of yeast expression profiles and on a human cancer dataset. Cross validation results show high specificity in assigning function to genes based on their biclusters, and we are able to annotate in this way 196 uncharacterized yeast genes. We also demonstrate how the biclusters lead to detecting new concrete biological associations. In cancer data we are able to detect and relate finer tissue types than was previously possible. We also show that the method outperforms the biclustering algorithm of Cheng and Church (2000).
Contact: amos@tau.ac.il; roded@tau.ac.il; rshamir@tau.ac.il
Availability:
*These authors contributed equally to this work.
Co-clustering of biological networks and gene expression data
Authors: Hanisch Daniel , Zien Alexander , Zimmer Ralf , Lengauer Thomas 
Published: May 2011

Abstract
Motivation: Large scale gene expression data are often analysed by clustering genes based on gene expression data alone, though a priori knowledge in the form of biological networks is available. The use of this additional information promises to improve exploratory analysis considerably.
Results: We propose constructing a distance function which combines information from expression data and biological networks. Based on this function, we compute a joint clustering of genes and vertices of the network. This general approach is elaborated for metabolic networks. We define a graph distance function on such networks and combine it with a correlation-based distance function for gene expression measurements. A hierarchical clustering and an associated statistical measure is computed to arrive at a reasonable number of clusters. Our method is validated using expression data of the yeast diauxic shift. The resulting clusters are easily interpretable in terms of the biochemical network and the gene expression data and suggest that our method is able to automatically identify processes that are relevant under the measured conditions.
Contact: Daniel.Hanisch@scai.fhg.de
Keywords: gene expression; biological networks; metabolic networks; co-clustering; clustering.
The degenerate primer design problem
Authors: Linhart Chaim , Shamir Ron 
Published: May 2011

Abstract
A PCR primer sequence is called degenerate if some of its positions have several possible bases. The degeneracy of the primer is the number of unique sequence combinations it contains. We study the problem of designing a pair of primers with prescribed degeneracy that match a maximum number of given input sequences. Such problems occur when studying a family of genes that is known only in part, or is known in a related species. We prove that various simplified versions of the problem are hard, show the polynomiality of some restricted cases, and develop approximation algorithms for one variant. Based on these algorithms, we implemented a program called hyden for designing highly-degenerate primers for a set of genomic sequences. We report on the success of the program in an experimental scheme for identifying all human olfactory receptor (OR) genes. In that project, hyden was used to design primers with degeneracies up to 1010 that amplified with high specificity many novel genes of that family, tripling the number of OR genes known at the time.
Availability: Available on request from the authors.
Contact: chaiml@tau.ac.il; rshamir@tau.ac.il
Keywords: PCR primer design; degenerate primers; optimization; human olfactory subgenome; protein families.
Splicing graphs and EST assembly problem
Authors: Heber Steffen , Alekseyev Max , Sze Sing-Hoi , Tang Haixu , Pevzner Pavel A. 
Published: May 2011

Abstract
Motivation: The traditional approach to annotate alternative splicing is to investigate every splicing variant of the gene in a case-by-case fashion. This approach, while useful, has some serious shortcomings. Recent studies indicate that alternative splicing is more frequent than previously thought and some genes may produce tens of thousands of different transcripts. A list of alternatively spliced variants for such genes would be difficult to build and hard to analyse. Moreover, such a list does not show the relationships between different transcripts and does not show the overall structure of all transcripts. A better approach would be to represent all splicing variants for a given gene in a way that captures the relationships between different splicing variants.
Results: We introduce the notion of the splicing graph that is a natural and convenient representation of all splicing variants. The key difference with the existing approaches is that we abandon the linear (sequence) representation of each transcript and replace it with a graph representation where each transcript corresponds to a path in the graph. We further design an algorithm to assemble EST reads into the splicing graph rather than assembling them into each splicing variant in a case-by-case fashion.
Availability: http://www-cse.ucsd.edu/groups/bioinformatics/software.html
Contact: sheber@ucsd.edu
Keywords: EST assembly; splicing graph; alternative splicing
Discovering regulatory and signalling circuits in molecular
interaction networks
Authors: Ideker Trey , Ozier Owen , Schwikowski Benno , Siegel Andrew F. 
Published: May 2011

Abstract
Motivation: In model organisms such as yeast, large databases of protein–protein and protein-DNA interactions have become an extremely important resource for the study of protein function, evolution, and gene regulatory dynamics. In this paper we demonstrate that by integrating these interactions with widely-available mRNA expression data, it is possible to generate concrete hypotheses for the underlying mechanisms governing the observed changes in gene expression. To perform this integration systematically and at large scale, we introduce an approach for screening a molecular interaction network to identify active subnetworks, i.e., connected regions of the network that show significant changes in expression over particular subsets of conditions. The method we present here combines a rigorous statistical measure for scoring subnetworks with a search algorithm for identifying subnetworks with high score.
Results: We evaluated our procedure on a small network of 332 genes and 362 interactions and a large network of 4160 genes containing all 7462 protein–protein and protein-DNA interactions in the yeast public databases. In the case of the small network, we identified five significant subnetworks that covered 41 out of 77 (53%) of all significant changes in expression. Both network analyses returned several top-scoring subnetworks with good correspondence to known regulatory mechanisms in the literature. These results demonstrate how large-scale genomic approaches may be used to uncover signalling and regulatory pathways in a systematic, integrative fashion.
Availability: The methods presented in this paper are implemented in the Cytoscape software package which is available to the academic community at http://www.cytoscape.org.
Contact: trey@wi.mit.edu
Keywords: molecular interactions; gene expression; data integration; simulated annealing; Monte carlo methods.
*To whom correspondence should be addressed.
Minreg: Inferring an active regulator set
Authors: Pe'er Dana , Regev Aviv , Tanay Amos 
Published: May 2011

Abstract
Regulatory relations between genes are an important component of molecular pathways. Here, we devise a novel global method that uses a set of gene expression profiles to find a small set of relevant active regulators, identify the genes that they regulate, and automatically annotate them. We show that our algorithm is capable of handling a large number of genes in a short time and is robust to a wide range of parameters. We apply our method to a combined dataset of S. cerevisiae expression profiles, and validate the resulting model of regulation by cross-validation and extensive biological analysis of the selected regulators and their derived annotations.
Keywords: gene expression; gene regulation; gene networks; machine learning.
Marginalized kernels for biological sequences
Authors: Tsuda Koji , Kin Taishin , Asai Kiyoshi 
Published: May 2011

Abstract
Motivation: Kernel methods such as support vector machines require a kernel function between objects to be defined a priori. Several works have been done to derive kernels from probability distributions, e.g., the Fisher kernel. However, a general methodology to design a kernel is not fully developed.
Results: We propose a reasonable way of designing a kernel when objects are generated from latent variable models (e.g., HMM). First of all, a joint kernel is designed for complete data which include both visible and hidden variables. Then a marginalized kernel for visible data is obtained by taking the expectation with respect to hidden variables. We will show that the Fisher kernel is a special case of marginalized kernels, which gives another viewpoint to the Fisher kernel theory. Although our approach can be applied to any object, we particularly derive several marginalized kernels useful for biological sequences (e.g., DNA and proteins). The effectiveness of marginalized kernels is illustrated in the task of classifying bacterial gyrase subunit B (gyrB) amino acid sequences.
Contact: koji.tsuda@aist.go.jp
Keywords: kernel design; marginalized kernels; the Fisher kernel; biological sequence classification; string kernels.
Efficient multiple genome alignment
Authors: Höhl Michael , Kurtz Stefan , Ohlebusch Enno 
Published: May 2011

Abstract
Motivation: To allow a direct comparison of the genomic DNA sequences of sufficiently similar organisms, there is an urgent need for software tools that can align more than two genomic sequences.
Results: We developed new algorithms and a software tool ‘Multiple Genome Aligner’ (MGA for short) that efficiently computes multiple genome alignments of large, closely related DNA sequences. For example, it can align 85% percent of the complete genomes of six human adenoviruses (average length 35305 bp.) in 159 seconds. An alignment of 74% of the complete genomes of three of strains of E. coli (lengths: 5528445; 5498450; 4639221~bp.) is produced in 30 minutes.
Availability: The software MGA is available free of charge for non-commercial research institutions. For details see http://bibiserv.techfak.uni-bielefeld.de/mga/
Contact: kurtz@techfak.uni-bielefeld.deenno@techfak.uni-bielefeld.de
Keywords: genome comparison; multiple alignment; efficient algorithms; graph algorithms; suffix trees.
PseudoViewer: automatic visualization of RNA pseudoknots
Authors: Han Kyungsook , Lee Yujin , Kim Wootaek 
Published: May 2011

Abstract
Motivation: Several algorithms have been developed for drawing RNA secondary structures, however none of these can be used to draw RNA pseudoknot structures. In the sense of graph theory, a drawing of RNA secondary structures is a tree, whereas a drawing of RNA pseudoknots is a graph with inner cycles within a pseudoknot as well as possible outer cycles formed between a pseudoknot and other structural elements. Thus, RNA pseudoknots are more difficult to visualize than RNA secondary structures. Since no automatic method for drawing RNA pseudoknots exists, visualizing RNA pseudoknots relies on significant amount of manual work and does not yield satisfactory results. The task of visualizing RNA pseudoknots by hand becomes more challenging as the size and complexity of the RNA pseudoknots increase.
Results: We have developed a new representation and an algorithm for drawing H-type pseudoknots with RNA secondary structures. Compared to existing representations of H-type pseudoknots, the new representation ensures uniform and clear drawings with no edge crossing for any H-type pseudoknots. To the best of our knowledge, this is the first algorithm for automatically drawing RNA pseudoknots with RNA secondary structures. The algorithm has been implemented in a Java program, which can be executed on any computing system. Experimental results demonstrate that the algorithm generates an aesthetically pleasing drawing of all H-type pseudoknots. The results have also shown that the drawing has high readability, enabling the user to quickly and easily recognize the whole RNA structure as well as the pseudoknots themselves.
Availability: All algorithms are available on request from the corresponding author.
Contact: khan@inha.ac.kr
Keywords: RNA structure; H-type pseudoknot; visualization, graph drawing.
*To whom correspondence should be addressed.
A powerful non-homology method for the prediction of
operons in prokaryotes
Authors: Moreno-Hagelsieb Gabriel , Collado-Vides Julio 
Published: May 2011

Abstract
Motivation: The prediction of the transcription unit organization of genomes is an important clue in the inference of functional relationships of genes, the interpretation and evaluation of transcriptome experiments, and the overall inference of the regulatory networks governing the expression of genes in response to the environment. Though several methods have been devised to predict operons, most need a high characterization of the genome analysed. Log-likelihoods derived from inter-genic distance distributions work surprisingly well to predict operons in Escherichia coli and are available for any genome as soon as the gene sets are predicted.
Results: Here we provide evidence that the very same method is applicable to any prokaryotic genome. First, the method has the same efficiency when evaluated using a collection of experimentally known operons of Bacillus subtilis. Second, operons among most if not all prokaryotes seem to have the same tendencies to keep short distances between their genes, the most frequent distances being the overlaps of four and one base pairs. The universality of this structural feature allows us to predict the organization of transcription units in all prokaryotes. Third, predicted operons contain a higher proportion of genes with related phylogenetic profiles and conservation of adjacency than predicted borders of transcription units.
Supplementary information: Additional materials and graphs, are available at: http://www.cifn.unam.mx/moreno/pub/TUpredictions/
Contact: moreno@cifn.unam.mx
Keywords: functional genomics; comparative genomics; operon prediction; operon structure.
*To whom correspondence should be addressed.
Identifying operons and untranslated regions of transcripts
using Escherichia coli RNA expression analysis
Authors: Tjaden Brian , Haynor David R. , Stolyar Sergey , Rosenow Carsten , Kolker Eugene 
Published: May 2011

Abstract
Microarrays traditionally have been used to assay the transcript expression of coding regions of genes. Here, we use Escherichia coli oligonucleotide microarrays to assay transcript expression of both open reading frames (ORFs) and intergenic regions. We then use hidden Markov models to analyse this expression data and estimate transcription boundaries of genes. This approach allows us to identify 5′ untranslated regions (5′ UTRs) of transcripts as well as genes that are likely to be operon members. The operon elements we identify correspond to documented operons with 99% specificity and 63% sensitivity. Similarly we find that our 5′ UTR results accurately coincide with experimentally verified promoter regions for most genes.
Contact: tjaden@cs.washington.edu
Keywords: untranslated regions; operons; intergenic; microarrays; Escherichia coli.
*To whom correspondence should be addressed.
Detecting recombination with MCMC
Authors: Husmeier Dirk , McGuire Gráinne 
Published: May 2011

Abstract
Motivation: We present a statistical method for detecting recombination, whose objective is to accurately locate the recombinant breakpoints in DNA sequence alignments of small numbers of taxa (4 or 5). Our approach explicitly models the sequence of phylogenetic tree topologies along a multiple sequence alignment. Inference under this model is done in a Bayesian way, using Markov chain Monte Carlo (MCMC). The algorithm returns the site-dependent posterior probability of each tree topology, which is used for detecting recombinant regions and locating their breakpoints.
Results: The method was tested on a synthetic and three real DNA sequence alignments, where it was found to outperform the established detection methods PLATO, RECPARS, and TOPAL.
Availability: The algorithm has been implemented in the C++ program package BARCE, which is freely available from http://www.bioss.sari.ac.uk/~dirk/my_software
Contact: dirk@bioss.ac.uk
Keywords: phylogenetic trees; DNA sequence alignments; recombination; hidden Markov models; Gibbs sampling; Markov chain Monte Carlo.
Finding composite regulatory patterns in DNA sequences
Authors: Eskin Eleazar , Pevzner Pavel A. 
Published: May 2011

Abstract
Pattern discovery in unaligned DNA sequences is a fundamental problem in computational biology with important applications in finding regulatory signals. Current approaches to pattern discovery focus on monad patterns that correspond to relatively short contiguous strings. However, many of the actual regulatory signals are composite patterns that are groups of monad patterns that occur near each other. A difficulty in discovering composite patterns is that one or both of the component monad patterns in the group may be ‘too weak’. Since the traditional monad-based motif finding algorithms usually output one (or a few) high scoring patterns, they often fail to find composite regulatory signals consisting of weak monad parts. In this paper, we present a MITRA (MIsmatch TRee Algorithm) approach for discovering composite signals. We demonstrate that MITRA performs well for both monad and composite patterns by presenting experiments over biological and synthetic data.
Availability: MITRA is available at http://www.cs.columbia.edu/compbio/mitra/
Contact: eeskin@cs.columbia.edu
Keywords: regulatory motif finding; pattern finding; dyad motifs.
The POPPs: clustering and searching using peptide probability
profiles
Authors: Wise Michael J. 
Published: May 2011

Abstract
The POPPs is a suite of inter-related software tools which allow the user to discover what is statistically ‘unusual’ in the composition of an unknown protein, or to automatically cluster proteins into families based on peptide composition. Finally, the user can search for related proteins based on peptide composition. Statistically based peptide composition provides a view of proteins that is, to some extent, orthogonal to that provided by sequence. In a test study, the POPP suite is able to regroup into their families sets of approximately 100 randomised Pfam protein domains. The POPPs suite is used to explore the diverse set of late embryogenesis abundant (LEA) proteins.
Availability: Contact the author.
Contact: mw263@cam.ac.uk
Keywords: protein clustering; clustering algorithms; protein search; peptide composition; Pfam; late embryogenesis abundant proteins.
A sequence-profile-based HMM for predicting and
discriminating β barrel membrane proteins
Authors: Martelli Pier Luigi , Fariselli Piero , Krogh Anders , Casadio Rita 
Published: May 2011

Abstract
Motivation: Membrane proteins are an abundant and functionally relevant subset of proteins that putatively include from about 15 up to 30% of the proteome of organisms fully sequenced. These estimates are mainly computed on the basis of sequence comparison and membrane protein prediction. It is therefore urgent to develop methods capable of selecting membrane proteins especially in the case of outer membrane proteins, barely taken into consideration when proteome wide analysis is performed. This will also help protein annotation when no homologous sequence is found in the database. Outer membrane proteins solved so far at atomic resolution interact with the external membrane of bacteria with a characteristic β barrel structure comprising different even numbers of β strands (β barrel membrane proteins). In this they differ from the membrane proteins of the cytoplasmic membrane endowed with alpha helix bundles (all alpha membrane proteins) and need specialised predictors.
Results: We develop a HMM model, which can predict the topology of β barrel membrane proteins using, as input, evolutionary information. The model is cyclic with 6 types of states: two for the β strand transmembrane core, one for the β strand cap on either side of the membrane, one for the inner loop, one for the outer loop and one for the globular domain state in the middle of each loop. The development of a specific input for HMM based on multiple sequence alignment is novel. The accuracy per residue of the model is 83% when a jack knife procedure is adopted. With a model optimisation method using a dynamic programming algorithm seven topological models out of the twelve proteins included in the testing set are also correctly predicted. When used as a discriminator, the model is rather selective. At a fixed probability value, it retains 84% of a non-redundant set comprising 145 sequences of well-annotated outer membrane proteins. Concomitantly, it correctly rejects 90% of a set of globular proteins including about 1200 chains with low sequence identity (&lt;30%) and 90% of a set of all alpha membrane proteins, including 188 chains.
Availability:The program will be available on request from the authors.
Contact: gigi@lipid.biocomp.unibo.ithttp://www.biocomp.unibo.it
Keywords: β barrel membrane proteins; HMM; genome analysis; protein structure prediction; outer membrane protein topology.
3Present address: Bioinformatics Centre, University of Copenhagen, DK-2100 Copenhagen, Denmark
*To whom correspondence should be addressed.
Variance stabilization applied to microarray data calibration
and to the quantification of differential expression
Authors: Huber Wolfgang , von Heydebreck Anja , Sültmann Holger , Poustka Annemarie , Vingron Martin 
Published: May 2011

Abstract
We introduce a statistical model for microarray gene expression data that comprises data calibration, the quantification of differential expression, and the quantification of measurement error. In particular, we derive a transformation h for intensity measurements, and a difference statistic Δh whose variance is approximately constant along the whole intensity range. This forms a basis for statistical inference from microarray data, and provides a rational data pre-processing strategy for multivariate analyses. For the transformation h, the parametric form h(x)=arsinh(a+bx) is derived from a model of the variance-versus-mean dependence for microarray intensity data, using the method of variance stabilizing transformations. For large intensities, h coincides with the logarithmic transformation, and Δh with the log-ratio. The parameters of h together with those of the calibration between experiments are estimated with a robust variant of maximum-likelihood estimation. We demonstrate our approach on data sets from different experimental platforms, including two-colour cDNA arrays and a series of Affymetrix oligonucleotide arrays.
Availability: Software is freely available for academic use as an R package at http://www.dkfz.de/abt0840/whuber
Contact: w.huber@dkfz.de