Search

We develop, analyze, and experiment with a new tool, called madmx, which extracts frequent motifs from biological sequences. We introduce the notion of density to single out the 'significant' motifs. The density is a simple and flexible measure for bounding the number of don't cares in a motif, defined as the fraction of solid (i.e., different from don't care) characters in the motif. A maximal dense motif has density above a certain threshold, and any further specialization of a don't care symbol in it or any extension of its boundaries decreases its number of occurrences in the input sequence. By extracting only maximal dense motifs, madmx reduces the output size and improves performance, while enhancing the quality of the discoveries. The efficiency of our approach relies on a newly defined combining operation, dubbed fusion, which allows for the construction of maximal dense motifs in a bottom-up fashion, while avoiding the generation of nonmaximal ones. We provide experimental evidence of the efficiency and the quality of the motifs returned by madmx. [ABSTRACT FROM AUTHOR]

Phylogeny inference is an importance issue in computational biology. Some early approaches based on characteristics such as the maximum parsimony algorithm and the maximum likelihood algorithm will become intractable when the number of taxonomic units is large. Recent algorithms based on distance data which adopt an agglomerative scheme are widely used for phylogeny inference. However, they have to recursively merge the nearest pair of taxa and estimate a distance matrix; this may enlarge the error gradually, and lead to an inaccurate tree topology. In this study, a splitting algorithm is proposed for phylogeny inference by using the spectral graph clustering (SGC) technique. The SGC algorithm splits graphs by using the maximum cut criterion and circumvents optimization problems through solving a generalized eigenvalue system. The promising features of the proposed algorithm are the following: (i) using a heuristic strategy for constructing phylogenies from certain distance functions, which are not even additive; (ii) distance matrices do not have to be estimated recursively; (iii) inferring a more accurate tree topology than that of the Neighbor-joining (NJ) algorithm on simulated datasets; and (iv) strongly supporting hypotheses induced by other methods for Baculovirus genomes. Our numerical experiments confirm that the SGC algorithm is efficient for phylogeny inference. [ABSTRACT FROM AUTHOR]

Background: It is commonly believed that including domain knowledge in a prediction model is desirable. However, representing and incorporating domain information in the learning process is, in general, a challenging problem. In this research, we consider domain information encoded by discrete or categorical attributes. A discrete or categorical attribute provides a natural partition of the problem domain, and hence divides the original problem into several non-overlapping sub-problems. In this sense, the domain information is useful if the partition simplifies the learning task. The goal of this research is to develop an algorithm to identify discrete or categorical attributes that maximally simplify the learning task. Results: We consider restructuring a supervised learning problem via a partition of the problem space using a discrete or categorical attribute. A naive approach exhaustively searches all the possible restructured problems. It is computationally prohibitive when the number of discrete or categorical attributes is large. We propose a metric to rank attributes according to their potential to reduce the uncertainty of a classification task. It is quantified as a conditional entropy achieved using a set of optimal classifiers, each of which is built for a sub-problem defined by the attribute under consideration. To avoid high computational cost, we approximate the solution by the expected minimum conditional entropy with respect to random projections. This approach is tested on three artificial data sets, three cheminformatics data sets, and two leukemia gene expression data sets. Empirical results demonstrate that our method is capable of selecting a proper discrete or categorical attribute to simplify the problem, i.e., the performance of the classifier built for the restructured problem always beats that of the original problem. Conclusions: The proposed conditional entropy based metric is effective in identifying good partitions of a classification problem, hence enhancing the prediction performance. [ABSTRACT FROM AUTHOR]

The author comments on the evolution of phylogenetic inference over the past decade that greatly increased the scope of the evolutionary trees that can be inferred. He says that phylogenetic inference has been revolutionized by the combination of molecular sequence data and bioinformatics. The limiting factor has always been the amount of data available to scientists in the attempts to derive the Tree of Life.

Background: The center string (or closest string) problem is a classic computer science problem with important applications in computational biology. Given k input strings and a distance threshold d, we search for a string within Hamming distance at most d to each input string. This problem is NP complete. Results: In this paper, we focus on exact methods for the problem that are also swift in application. We first introduce data reduction techniques that allow us to infer that certain instances have no solution, or that a center string must satisfy certain conditions. We describe how to use this information to speed up two previously published search tree algorithms. Then, we describe a novel iterative search strategy that is effecient in practice, where some of our reduction techniques can also be applied. Finally, we present results of an evaluation study for two different data sets from a biological application. Conclusions: We find that the running time for computing the optimal center string is dominated by the subroutine calls for d = dopt -1 and d = dopt. Our data reduction is very effective for both, either rejecting unsolvable instances or solving trivial positions. We find that this speeds up computations considerably. [ABSTRACT FROM AUTHOR]

Background: A fraction of the Neanderthal mitochondrial genome sequence has a similarity with a 5,839-bp nuclear DNA sequence of mitochondrial origin (numt) on the human chromosome 1. This fact has never been interpreted. Although this phenomenon may be attributed to contamination and mosaic assembly of Neanderthal mtDNA from short sequencing reads, we explain the mysterious similarity by integration of this numt (mtAncestor-1) into the nuclear genome of the common ancestor of Neanderthals and modern humans not long before their reproductive split. Principal Findings: Exploiting bioinformatics, we uncovered an additional numt (mtAncestor-2) with a high similarity to the Neanderthal mtDNA and indicated that both numts represent almost identical replicas of the mtDNA sequences ancestral to the mitochondrial genomes of Neanderthals and modern humans. In the proteins, encoded by mtDNA, the majority of amino acids distinguishing chimpanzees from humans and Neanderthals were acquired by the ancestral hominins. The overall rate of nonsynonymous evolution in Neanderthal mitochondrial protein-coding genes is not higher than in other lineages. The model incorporating the ancestral hominin mtDNA sequences estimates the average divergence age of the mtDNAs of Neanderthals and modern humans to be 450,000-485,000 years. The mtAncestor-1 and mtAncestor-2 sequences were incorporated into the nuclear genome approximately 620,000 years and 2,885,000 years ago, respectively. Conclusions: This study provides the first insight into the evolution of the mitochondrial DNA in hominins ancestral to Neanderthals and humans. We hypothesize that mtAncestor-1 and mtAncestor-2 are likely to be molecular fossils of the mtDNAs of Homo heidelbergensis and a stem Homo lineage. The dN/dS dynamics suggests that the effective population size of extinct hominins was low. However, the hominin lineage ancestral to humans, Neanderthals and H. heidelbergensis, had a larger effective population size and possessed genetic diversity comparable with those of chimpanzee and gorilla. [ABSTRACT FROM AUTHOR]

The field of glycobiology is concerned with the study of the structure, properties, and biological functions of the family of biomolecules called carbohydrates. Bioinformatics for glycobiology is a particularly challenging field, because carbohydrates exhibit a high structural diversity and their chains are often branched. Significant improvements in experimental analytical methods over recent years have led to a tremendous increase in the amount of carbohydrate structure data generated. Consequently, the availability of databases and tools to store, retrieve and analyze these data in an efficient way is of fundamental importance to progress in glycobiology. In this review, the various graphical representations and sequence formats of carbohydrates are introduced, and an overview of newly developed databases, the latest developments in sequence alignment and data mining, and tools to support experimental glycan analysis are presented. Finally, the field of structural glycoinformatics and molecular modeling of carbohydrates, glycoproteins, and protein–carbohydrate interaction are reviewed. [ABSTRACT FROM AUTHOR]

Motivation: Multiple sequence alignment is of central importance to bioinformatics and computational biology. Although a large number of algorithms for computing a multiple sequence alignment have been designed, the efficient computation of highly accurate multiple alignments is still a challenge. [ABSTRACT FROM PUBLISHER]

Motivation: Molecular chaperones prevent the aggregation of their substrate proteins and thereby ensure that they reach their functional native state. The bacterial GroEL/ES chaperonin system is understood in great detail on a structural, mechanistic and functional level; its interactors in Escherichia coli have been identified and characterized. However, a long-standing question in the field is: What makes a protein a chaperone substrate? [ABSTRACT FROM PUBLISHER]

Motivation: The inference of regulatory networks from large-scale expression data holds great promise because of the potentially causal interpretation of these networks. However, due to the difficulty to establish reliable methods based on observational data there is so far only incomplete knowledge about possibilities and limitations of such inference methods in this context. [ABSTRACT FROM PUBLISHER]

In this article the authors discuss the theoretical ideas originally specified by the epigenetics concepts of revolutionary interdisciplinary thinker Conrad Hal Waddington. They argue that in the age of post-genomic bioinformatics and laboratory tools, Waddington's epigenetics is more instructive and informative that it has been before. They note that his epigenetics is essential to the changing theoretical understanding of evolutionary developmental biology.

The recent and astonishing accomplishments in the field of Genomics would not have been possible without the techniques, algorithms, and tools developed in Bioinformatics. Biological sequence comparison is an important operation in Bioinformatics because it is used to determine how similar two sequences are. As a result of this operation, one or more alignments are produced. DIALIGN is an exact algorithm that uses dynamic programming to obtain optimal biological sequence alignments in quadratic space and time. One effective way to accelerate DIALIGN is to design FPGA-based architectures to execute it. Nevertheless, the complete retrieval of an alignment in hardware requires modifications on the original algorithm because it executes in quadratic space. In this paper, we propose and evaluate two FPGA-based accelerators executing DIALIGN in linear space: one to obtain the optimal DIALIGN score (DIALIGN-Score) and one to retrieve the DIALIGN alignment (DIALIGN-Alignment). Because it appears to be no documented variant of the DIALIGN algorithm that produces alignments in linear space, we here propose a linear space variant of the DIALIGN algorithm and have designed the DIALIGN-Alignment accelerator to implement it. The experimental results show that impressive speedups can be obtained with both accelerators when comparing long biological sequences: the DIALIGN-Score accelerator achieved a speedup of 383.4 and the DIALIGN-Alignment accelerator reached a speedup of 141.38. [ABSTRACT FROM AUTHOR]

Motivation: A major challenge in utilizing microarray technologies to measure nucleic acid abundances is ‘normalization’, the goal of which is to separate biologically meaningful signal from other confounding sources of signal, often due to unavoidable technical factors. It is intuitively clear that true biological signal and confounding factors need to be simultaneously considered when performing normalization. However, the most popular normalization approaches do not utilize what is known about the study, both in terms of the biological variables of interest and the known technical factors in the study, such as batch or array processing date. [ABSTRACT FROM PUBLISHER]

We propose a formal language that allows for transposing biological information precisely and rigorously into machine-readable information. This language, which we call Zsyntax (where Z stands for the Greek word ζωή, life), is grounded on a particular type of non-classical logic, and it can be used to write algorithms and computer programs. We present it as a first step towards a comprehensive formal language for molecular biology in which any biological process can be written and analyzed as a sort of logical ''deduction''. Moreover, we illustrate the potential value of this language, both in the field of text mining and in that of biological prediction. [ABSTRACT FROM AUTHOR]

Motivation: Many biological phenomena involve extensive interactions between many of the biological pathways present in cells. However, extraction of all the inherent biological pathways remains a major challenge in systems biology. With the advent of high-throughput functional genomic techniques, it is now possible to infer biological pathways and pathway organization in a systematic way by integrating disparate biological information. [ABSTRACT FROM PUBLISHER]

Background: Functional genomics technologies that measure genome expression at a global scale are accelerating biological knowledge discovery. Generating these high throughput datasets is relatively easy compared to the downstream functional modelling necessary for elucidating the molecular mechanisms that govern the biology under investigation. A number of publicly available 'discovery-based' computational tools use the computationally amenable Gene Ontology (GO) for hypothesis generation. However, there are few tools that support hypothesis-based testing using the GO and none that support testing with user defined hypothesis terms. Here, we present GOModeler, a tool that enables researchers to conduct hypothesis-based testing of high throughput datasets using the GO. GOModeler summarizes the overall effect of a user defined gene/protein differential expression dataset on specific GO hypothesis terms selected by the user to describe a biological experiment. The design of the tool allows the user to complement the functional information in the GO with his/her domain specific expertise for comprehensive hypothesis testing. Results: GOModeler tests the relevance of the hypothesis terms chosen by the user for the input gene dataset by providing the individual effects of the genes on the hypothesis terms and the overall effect of the entire dataset on each of the hypothesis terms. It matches the GO identifiers (ids) of the genes with the GO ids of the hypothesis terms and parses the names of those ids that match to assign effects. We demonstrate the capabilities of GOModeler with a dataset of nine differentially expressed cytokine genes and compare the results to those obtained through manual analysis of the dataset by an immunologist. The direction of overall effects on all hypothesis terms except one was consistent with the results obtained by manual analysis. The tool's editing capability enables the user to augment the information extracted. GOModeler is available as a part of the AgBase tool suite (http://www.agbase.msstate.edu). Conclusions: GOModeler allows hypothesis driven analysis of high throughput datasets using the GO. Using this tool, researchers can quickly evaluate the overall effect of quantitative expression changes of gene set on specific biological processes of interest. The results are provided in both tabular and graphical formats. [ABSTRACT FROM AUTHOR]

Background: Protein structure comparison is a fundamental task in structural biology. While the number of known protein structures has grown rapidly over the last decade, searching a large database of protein structures is still relatively slow using existing methods. There is a need for new techniques which can rapidly compare protein structures, whilst maintaining high matching accuracy. Results: We have developed IR Tableau, a fast protein comparison algorithm, which leverages the tableau representation to compare protein tertiary structures. IR tableau compares tableaux using information retrieval style feature indexing techniques. Experimental analysis on the ASTRAL SCOP protein structural domain database demonstrates that IR Tableau achieves two orders of magnitude speedup over the search times of existing methods, while producing search results of comparable accuracy. Conclusion: We show that it is possible to obtain very significant speedups for the protein structure comparison problem, by employing an information retrieval style approach for indexing proteins. The comparison accuracy achieved is also strong, thus opening the way for large scale processing of very large protein structure databases. [ABSTRACT FROM AUTHOR]

Background: Glycobiology pertains to the study of carbohydrate sugar chains, or glycans, in a particular cell or organism. Many computational approaches have been proposed for analyzing these complex glycan structures, which are chains of monosaccharides. The monosaccharides are linked to one another by glycosidic bonds, which can take on a variety of comformations, thus forming branches and resulting in complex tree structures. The q-gram method is one of these recent methods used to understand glycan function based on the classification of their tree structures. This q-gram method assumes that for a certain q, different q-grams share no similarity among themselves. That is, that if two structures have completely different components, then they are completely different. However, from a biological standpoint, this is not the case. In this paper, we propose a weighted q-gram method to measure the similarity among glycans by incorporating the similarity of the geometric structures, monosaccharides and glycosidic bonds among q-grams. In contrast to the traditional q-gram method, our weighted q-gram method admits similarity among q-grams for a certain q. Thus our new kernels for glycan structure were developed and then applied in SVMs to classify glycans. Results: Two glycan datasets were used to compare the weighted q-gram method and the original q-gram method. The results show that the incorporation of q-gram similarity improves the classification performance for all of the important glycan classes tested. Conclusion: The results in this paper indicate that similarity among q-grams obtained from geometric structure, monosaccharides and glycosidic linkage contributes to the glycan function classification. This is a big step towards the understanding of glycan function based on their complex structures. [ABSTRACT FROM AUTHOR]

Background: Most software packages for whole genome association studies are non-graphical, purely text based programs originally designed to run with UNIX-like operating systems. Graphical output is often not intended or supposed to be performed with other command line tools, e.g. gnuplot. Results: Using the Microsoft .NET 2.0 platform and Visual Studio 2005, we have created a graphical software package to analyze data from microarray whole genome association studies, both for a DNA-pooling based approach as well as regular single sample data. Part of this package was made to integrate with GenePool 0.8.2, a previously existing software suite for GNU/Linux systems, which we have modified to run in a Microsoft Windows environment. Further modifications cause it to generate some additional data. This enables GenePool to interact with the .NET parts created by us. The programs we developed are GPFrontend, a graphical user interface and frontend to use GenePool and create metadata files for it, and GPGraphics, a program to further analyze and graphically evaluate output of different WGA analysis programs, among them also GenePool. Conclusions: Our programs enable regular MS Windows users without much experience in bioinformatics to easily visualize whole genome data from a variety of sources. [ABSTRACT FROM AUTHOR]

Background: Large phylogenies are crucial for many areas of biological research. One method of creating such large phylogenies is the supertree method, but creating supertrees containing thousands of taxa, and hence providing a comprehensive phylogeny, requires hundred or even thousands of source input trees. Managing and processing these data in a systematic and error-free manner is challenging and will become even more so as supertrees contain ever increasing numbers of taxa. Protocols for processing input source phylogenies have been proposed to ensure data quality, but no robust software implementations of these protocols as yet exist. Findings: The aim of the Supertree Tool Kit (STK) is to aid in the collection, storage and processing of input source trees for use in supertree analysis. It is therefore invaluable when creating supertrees containing thousands of taxa and hundreds of source trees. The STK is a Perl module with executable scripts to carry out various steps in the processing protocols. In order to aid processing we have added meta-data, via XML, to each tree which contains information such as the bibliographic source information for the tree and how the data were derived, for instance the character data used to carry out the original analysis. These data are essential parts of previously proposed protocols. Conclusions: The STK is a bioinformatics tool designed to make it easier to process source phylogenies for inclusion in supertree analysis from hundreds or thousands of input source trees, whilst reducing potential errors and enabling easy sharing of such datasets. It has been successfully used to create the largest known supertree to date containing over 5000 taxa from over 700 source phylogenies. [ABSTRACT FROM AUTHOR]

In the last decade, some significant changes occurred in the bio-medical area with the introduction of systemic view. In neurology and pharmacokinetics, the systemic paradigm was already well accepted, whereas other areas of bio-medicine were more or less accepting the reductionism paradigm where systems were studied through the analysis of its isolated sub-systems. The genome project showed that it is not possible to explain the diversity of life only with combinations of genes, which resulted in a new science called systems biology. Mathematical modelling, as one of the principal tools of control engineering, is now becoming a necessary tool in the analysis of biological systems. Interdisciplinary research has the already showed significant advantages over single-disciplinary research; however, the communication barrier between scientists of different backgrounds is still a major problem. Therefore, mathematical modelling is not as widely used in life sciences as would be expected with the potential benefits to the area. [ABSTRACT FROM AUTHOR]

Two databases, “Ephemeroptera of the World” and “Phylogeny of Ephemeroptera”, are now available from the website http://www.insecta.bio.pu.ru. They are linked by a common front-page, common alphabetic index, common list of references and numerous links, however, both are basically different and each database can be used separately. While the web database “Phylogeny of Ephemeroptera” represents a usual scientific work, the web database “Ephemeroptera of the World” is unusual in a way that it can objectively reflect all scientific literature on the Ephemeroptera. This is the first attempt to build such a database in all biology. Cataloguing of biological information of a group of animals as a web database is necessary, but existing sites do not fulfill the requirements needed in such catalogues. In existing web catalogues, objective information is mixed with subjective opinions by the compilers in such a manner that further development of these databases for scientific needs is impossible. Principles elaborated for the database “Ephemeroptera of the World” can be used to create such comprehensive global databases, which could be used and filled up for an unlimitedly long time without reconstruction. The most important principles include correct selection of objective nomenclatural information from subjective scientific information, using primary binomina as universal markers for nomenclatural species, uniting typified supra-species nomenclatural taxa according to their type genera, and using the universal form of typified names. [ABSTRACT FROM AUTHOR]

The article presents a study that investigates the computational biology in Colombia. It mentions the use of bioinformatics as a tool in solving particular research problems and the establishment of a strong network for a long term perspective. It states that several public and private research centers and development participated in the development of genomics and bioinformatics in present times especially in the agricultural sector.

Motivation: CellML is an implementation-independent model description language for specifying and exchanging biological processes. The focus of CellML is the representation of mathematical formulations of biological processes. The language captures the mathematical and model building constructs well, but does not lend itself to capturing the biology these models represent. [ABSTRACT FROM PUBLISHER]

Abstract: Objective: This paper presents an algorithm for the solution of the motif discovery problem (MDP). Methods and materials: Motif discovery problem can be considered in two cases: motifs with insertions/deletions, and motifs without insertions/deletions. The first group motifs can be found by stochastic and approximated methods. The second group can be found by using stochastic and approximated methods, but also deterministic method. We proved that the second group motifs can be found with a deterministic algorithm, and so, it can be said that the second motifs finding is a P-type problem as proved in this paper. Results and conclusions: An algorithm was proposed in this paper for motif discovery problem. The proposed algorithm finds all motifs which are occurred in the sequence at least two times, and it also finds motifs of various sizes. Due to this case, this algorithm is regarded as Automatic Exact Motif Discovery Algorithm. All motifs of different sizes can be found with this algorithm, and this case was proven in this paper. It shown that automatic exact motif discovery is a P-type problem in this paper. The application of the proposed algorithm has been shown that this algorithm is superior to MEME, MEME3, Motif Sampler, WEEDER, CONSENSUS, AlignACE. [Copyright &y& Elsevier]

We recently identified a group of proteins which are dysregulated in renal cell carcinoma (RCC). In this study, we performed bioinformatics and pathway analysis of these proteins. Proteins were mapped to gene ontology biological processes. The upregulated proteins tend to cluster in processes, such as cancer initiation and progression. In addition, we identified a number of pathways that are significantly enriched in RCC. Some of these are ‘common’ pathways which are dysregulated in many cancers, but we also identified a number of pathways which were not previously linked to RCC. In addition to their potential prognostic values, many of these pathways have a potential as therapeutic targets for RCC. To verify our findings, we compared our proteins to a pool of datasets from published reports. Although there were only a minimal number of common proteins, there was a significant overlap between the identified pathways in the two groups. Moreover, out of 16 individually discovered genes identified by a literature search, 10 were found to be related to our dysregulated pathways. We also verified the upregulation of the mammalian target of rapamycin signaling pathway in RCC by immunohistochemistry. Finally, we highlight the potential clinical applications of pathway analysis in kidney cancer. [ABSTRACT FROM AUTHOR]

Background: The analysis of information in the biological domain is usually focused on the analysis of data from single on-line data sources. Unfortunately, studying a biological process requires having access to disperse, heterogeneous, autonomous data sources. In this context, an analysis of the information is not possible without the integration of such data. Methods: KA-SB is a querying and analysis system for final users based on combining a data integration solution with a reasoner. Thus, the tool has been created with a process divided into two steps: 1) KOMF, the Khaos Ontology-based Mediator Framework, is used to retrieve information from heterogeneous and distributed databases; 2) the integrated information is crystallized in a (persistent and high performance) reasoner (DBOWL). This information could be further analyzed later (by means of querying and reasoning). Results: In this paper we present a novel system that combines the use of a mediation system with the reasoning capabilities of a large scale reasoner to provide a way of finding new knowledge and of analyzing the integrated information from different databases, which is retrieved as a set of ontology instances. This tool uses a graphical query interface to build user queries easily, which shows a graphical representation of the ontology and allows users o build queries by clicking on the ontology concepts. Conclusion: These kinds of systems (based on KOMF) will provide users with very large amounts of information (interpreted as ontology instances once retrieved), which cannot be managed using traditional main memory-based reasoners. We propose a process for creating persistent and scalable knowledgebases from sets of OWL instances obtained by integrating heterogeneous data sources with KOMF. This process has been applied to develop a demo tool http://khaos.uma.es/ KA-SB, which uses the BioPax Level 3 ontology as the integration schema, and integrates UNIPROT, KEGG, CHEBI, BRENDA and SABIORK databases. [ABSTRACT FROM AUTHOR]

Motivation: Time-course microarray experiments study the progress of gene expression along time across one or several experimental conditions. Most developed analysis methods focus on the clustering or the differential expression analysis of genes and do not integrate functional information. The assessment of the functional aspects of time-course transcriptomics data requires the use of approaches that exploit the activation dynamics of the functional categories to where genes are annotated. Methods: We present three novel methodologies for the functional assessment of time-course microarray data. i) maSigFun derives from the maSigPro method, a regression-based strategy to model time-dependent expression patterns and identify genes with differences across series. maSigFun fits a regression model for groups of genes labeled by a functional class and selects those categories which have a significant model. ii) PCA-maSigFun fits a PCA model of each functional class-defined expression matrix to extract orthogonal patterns of expression change, which are then assessed for their fit to a time-dependent regression model. iii) ASCA-functional uses the ASCA model to rank genes according to their correlation to principal time expression patterns and assess functional enrichment on a GSA fashion. We used simulated and experimental datasets to study these novel approaches. Results were compared to alternative methodologies. Results: Synthetic and experimental data showed that the different methods are able to capture different aspects of the relationship between genes, functions and co-expression that are biologically meaningful. The methods should not be considered as competitive but they provide different insights into the molecular and functional dynamic events taking place within the biological system under study. [ABSTRACT FROM AUTHOR]

Background: Intrinsically disordered proteins (IDPs) and intrinsically disordered regions (IDRs) lack stable tertiary and/or secondary structure yet fulfills key biological functions. The recent recognition of IDPs and IDRs is leading to an entire field aimed at their systematic structural characterization and at determination of their mechanisms of action. Bioinformatics studies showed that IDPs and IDRs are highly abundant in different proteomes and carry out mostly regulatory functions related to molecular recognition and signal transduction. These activities complement the functions of structured proteins. IDPs and IDRs were shown to participate in both one-to-many and many-to-one signaling. Alternative splicing and posttranslational modifications are frequently used to tune the IDP functionality. Several individual IDPs were shown to be associated with human diseases, such as cancer, cardiovascular disease, amyloidoses, diabetes, neurodegenerative diseases, and others. This raises questions regarding the involvement of IDPs and IDRs in various diseases. Results: IDPs and IDRs were shown to be highly abundant in proteins associated with various human maladies. As the number of IDPs related to various diseases was found to be very large, the concepts of the disease-related unfoldome and unfoldomics were introduced. Novel bioinformatics tools were proposed to populate and characterize the disease-associated unfoldome. Structural characterization of the members of the disease-related unfoldome requires specialized experimental approaches. IDPs possess a number of unique structural and functional features that determine their broad involvement into the pathogenesis of various diseases. Conclusion: Proteins associated with various human diseases are enriched in intrinsic disorder. These disease-associated IDPs and IDRs are real, abundant, diversified, vital, and dynamic. These proteins and regions comprise the disease-related unfoldome, which covers a significant part of the human proteome. Profound association between intrinsic disorder and various human diseases is determined by a set of unique structural and functional characteristics of IDPs and IDRs. Unfoldomics of human diseases utilizes unrivaled bioinformatics and experimental techniques, paves the road for better understanding of human diseases, their pathogenesis and molecular mechanisms, and helps develop new strategies for the analysis of disease-related proteins. [ABSTRACT FROM AUTHOR]

Motivation: Genes and proteins are often associated with multiple names. More names are added as new functional or structural information is discovered. Because authors can use any one of the known names for a gene or protein, information retrieval and extraction would benefit from identifying the gene and protein terms that are synonyms of the same substance. Results: We have explored four complementary approaches for extracting gene and protein synonyms from text, namely the unsupervised, partially supervised, and supervised machine-learning techniques, as well as the manual knowledge-based approach. We report results of a large scale evaluation of these alternatives over an archive of biological journal articles. Our evaluation shows that our extraction techniques could be a valuable supplement to resources such as SWISSPROT, as our systems were able to capture gene and protein synonyms not listed in the SWISSPROT database. Data Availability: The extracted gene and protein synonyms are available at http://synonyms.cs.columbia.edu/ Contact: {hongyu,eugene}@cs.columbia.edu [ABSTRACT FROM AUTHOR]

Over the past twenty years there have been great advances in light microscopy with the result that multidimensional imaging has driven a revolution in modern biology. The development of new approaches of data acquisition is reported frequently, and yet the significant data management and analysis challenges presented by these new complex datasets remain largely unsolved. As in the well-developed field of genome bioinformatics, central repositories are and will be key resources, but there is a critical need for informatics tools in individual laboratories to help manage, share, visualize, and analyze image data. In this article we present the recent efforts by the bioimage informatics community to tackle these challenges, and discuss our own vision for future development of bioimage informatics solutions. [ABSTRACT FROM AUTHOR]

Background: Biologists need to perform complex queries, often across a variety of databases. Typically, each data resource provides an advanced query interface, each of which must be learnt by the biologist before they can begin to query them. Frequently, more than one data source is required and for high-throughput analysis, cutting and pasting results between websites is certainly very time consuming. Therefore, many groups rely on local bioinformatics support to process queries by accessing the resource's programmatic interfaces if they exist. This is not an efficient solution in terms of cost and time. Instead, it would be better if the biologist only had to learn one generic interface. BioMart provides such a solution. Results: BioMart enables scientists to perform advanced querying of biological data sources through a single web interface. The power of the system comes from integrated querying of data sources regardless of their geographical locations. Once these queries have been defined, they may be automated with its "scripting at the click of a button" functionality. BioMart's capabilities are extended by integration with several widely used software packages such as BioConductor, DAS, Galaxy, Cytoscape, Taverna. In this paper, we describe all aspects of BioMart from a user's perspective and demonstrate how it can be used to solve real biological use cases such as SNP selection for candidate gene screening or annotation of microarray results. Conclusion: BioMart is an easy to use, generic and scalable system and therefore, has become an integral part of large data resources including Ensembl, UniProt, HapMap, Wormbase, Gramene, Dictybase, PRIDE, MSD and Reactome. BioMart is freely accessible to use at http://www.biomart.org. [ABSTRACT FROM AUTHOR]

Background: Current usability studies of bioinformatics tools suggest that tools for exploratory analysis support some tasks related to finding relationships of interest but not the deep causal insights necessary for formulating plausible and credible hypotheses. To better understand design requirements for gaining these causal insights in systems biology analyses a longitudinal field study of 15 biomedical researchers was conducted. Researchers interacted with the same proteinprotein interaction tools to discover possible disease mechanisms for further experimentation. Results: Findings reveal patterns in scientists' exploratory and explanatory analysis and reveal that tools positively supported a number of well-structured query and analysis tasks. But for several of scientists' more complex, higher order ways of knowing and reasoning the tools did not offer adequate support. Results show that for a better fit with scientists' cognition for exploratory analysis systems biology tools need to better match scientists' processes for validating, for making a transition from classification to model-based reasoning, and for engaging in causal mental modelling. Conclusion: As the next great frontier in bioinformatics usability, tool designs for exploratory systems biology analysis need to move beyond the successes already achieved in supporting formulaic query and analysis tasks and now reduce current mismatches with several of scientists' higher order analytical practices. The implications of results for tool designs are discussed. [ABSTRACT FROM AUTHOR]

Abstract: Draft genome sequences of Acidthiobacillus thiooxidans and A. caldus have been annotated and compared to the previously annotated genome of A. ferrooxidans. This has allowed the prediction of metabolic and regulatory models for each species and has provided a unique opportunity to undertake comparative genomic studies of this group of related bioleaching bacteria. In this paper, the presence or absence of predicted genes for eleven metabolic processes, electron transfer pathways and other phenotypic characteristics are reported for the three acidithiobacilli: CO2 fixation, the TCA cycle, sulfur oxidation, sulfur reduction, iron oxidation, iron assimilation, quorum sensing via the acyl homoserine lactone mechanism, hydrogen oxidation, flagella formation, Che signaling (chemotaxis) and nitrogen fixation. Predicted transcriptional and metabolic interplay between pathways pinpoints possible coordinated responses to environmental signals such as energy source, oxygen and nutrient limitations. The predicted pathway for nitrogen fixation in A. ferrooxidans will be described as an example of such an integrated response. Several responses appear to be especially characteristic of autotrophic microorganisms and may have direct implications for metabolic processes of critical relevance to the understanding of how these microorganisms survive and proliferate in extreme environments, including industrial bioleaching operations. [Copyright &y& Elsevier]

Abstract: This study reports the identification of nematode neuropeptide-like protein (nlp) sequelogs from the GenBank expressed sequence tag (EST) database, using BLAST (Basic Local Alignment Search Tool) search methodology. Search strings derived from peptides encoded by the 45 known Caenorhabditis elegans nlp genes were used to identify more than 1000 ESTs encoding a total of 26 multi-species nlp sequelogs. The remaining 18 nlps (nlp-4, -16, -24 through -36, -39, -41 and -45) were identified only in C. elegans, while the sole EST representative of nlp-23 was from Caenorhabditis remanei. Several ESTs encoding putative antibacterial peptides similar to those encoded by the C. elegans genes nlp-24–33 were observed in several parasite species. A novel gene (nlp-46) was identified, encoding a single, amidated dodecapeptide (NIA[I/T]GR[G/A]DG[F/L]RPG) in eight species. Secretory signal peptides were identified in at least one species representing each nlp sequelog, confirming that all 46 nematode nlp genes encode secretory peptides. A random sub-set of C. elegans NLPs was tested physiologically in Ascaris suum ovijector and body wall muscle bioassays. None of the peptides tested were able to modulate ovijector activity, while only three displayed measurable myoactivity on somatic body wall muscle. AFAAGWNRamide (from nlp-23) and AVNPFLDSIamide (nlp-3) both produced a relaxation of body wall muscle, while AIPFNGGMYamide (nlp-10) induced a transient contraction. Numerical analyses of nlp-encoding ESTs demonstrate that nlp-3, -13, -14, -15 and -18 are amongst the most highly represented transcripts in the dataset. Using available bioinformatics resources, this study delineates the nlp complement of phylum Nematoda, providing a rich source of neuropeptide ligands for deorphanisation of nematode neuropeptide receptors. [Copyright &y& Elsevier]

Motivation: We developed an EM-random forest (EMRF) for Haseman–Elston quantitative trait linkage analysis that accounts for marker ambiguity and weighs each sib-pair according to the posterior identical by descent (IBD) distribution. The usual random forest (RF) variable importance (VI) index used to rank markers for variable selection is not optimal when applied to linkage data because of correlation between markers. We define new VI indices that borrow information from linked markers using the correlation structure inherent in IBD linkage data. [ABSTRACT FROM PUBLISHER]

Biology, chemistry and medicine are faced by tremendous challenges caused by an overwhelming amount of data and the need for rapid interpretation. Computational intelligence (Cl) approaches such as artificial neural networks, fuzzy systems and evolutionary computation are being used with increasing frequency to contend with this problem, in light of noise, non-linearity and temporal dynamics in the data. Such methods can be used to develop robust models of processes either on their own or in combination with standard statistical approaches. This is especially true for database mining, where modeling is a key component of scientific understanding. This review provides an introduction to current Cl methods, their application to biological problems, and concludes with a commentary about the anticipated impact of these approaches in bioinformatics. [ABSTRACT FROM AUTHOR]

We present a de novo assembly of a eukaryote transcriptome using 454 pyrosequencing data. The Glanville fritillary butterfly ( Melitaea cinxia; Lepidoptera: Nymphalidae) is a prominent species in population biology but had no previous genomic data. Sequencing runs using two normalized complementary DNA collections from a genetically diverse pool of larvae, pupae, and adults yielded 608 053 expressed sequence tags (mean length = 110 nucleotides), which assembled into 48 354 contigs (sets of overlapping DNA segments) and 59 943 singletons.blast comparisons confirmed the accuracy of the sequencing and assembly, and indicated the presence of c. 9000 unique genes, along with > 6000 additional microarray-confirmed unannotated contigs. Average depth of coverage was 6.5-fold for the longest 4800 contigs (348–2849 bp in length), sufficient for detecting large numbers of single nucleotide polymorphisms. Oligonucleotide microarray probes designed from the assembled sequences showed highly repeatable hybridization intensity and revealed biological differences among individuals. We conclude that 454 sequencing, when performed to provide sufficient coverage depth, allows de novo transcriptome assembly and a fast, cost-effective, and reliable method for development of functional genomic tools for nonmodel species. This development narrows the gap between approaches based on model organisms with rich genetic resources vs. species that are most tractable for ecological and evolutionary studies. [ABSTRACT FROM AUTHOR]

Although theoretical systems analysis has been available for over half a century, the recent advent of omic high-throughput analytical platforms along with the integration of individual tools and technologies has given rise to the field of modern systems biology. Coupled with information technology, bioinformatics, knowledge management and powerful mathematical models, systems biology has opened up new vistas in our understanding of complex biological systems. Currently there are two distinct approaches that include the inductively driven computational systems biology (bottom-up approach) and the deductive data-driven top-down analysis. Such approaches offer enormous potential in the elucidation of disease as well as defining key pathways and networks involved in optimal human health and nutrition. The tools and technologies now available in systems biology analyses offer exciting opportunities to develop the emerging areas of personalized medicine and individual nutritional profiling. [Copyright &y& Elsevier]

Abstract: Motif patterns consisting of sequences of intermixed solid and don’t-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms. [Copyright &y& Elsevier]

Background: Advanced Text Mining (TM) such as semantic enrichment of papers, event or relation extraction, and intelligent Question Answering have increasingly attracted attention in the bio-medical domain. For such attempts to succeed, text annotation from the biological point of view is indispensable. However, due to the complexity of the task, semantic annotation has never been tried on a large scale, apart from relatively simple term annotation. Results: We have completed a new type of semantic annotation, event annotation, which is an addition to the existing annotations in the GENIA corpus. The corpus has already been annotated with POS (Parts of Speech), syntactic trees, terms, etc. The new annotation was made on half of the GENIA corpus, consisting of 1,000 Medline abstracts. It contains 9,372 sentences in which 36,114 events are identified. The major challenges during event annotation were (1) to design a scheme of annotation which meets specific requirements of text annotation, (2) to achieve biology-oriented annotation which reflect biologists' interpretation of text, and (3) to ensure the homogeneity of annotation quality across annotators. To meet these challenges, we introduced new concepts such as Single-facet Annotation and Semantic Typing, which have collectively contributed to successful completion of a large scale annotation. Conclusion: The resulting event-annotated corpus is the largest and one of the best in quality among similar annotation efforts. We expect it to become a valuable resource for NLP (Natural Language Processing)-based TM in the bio-medical domain. [ABSTRACT FROM AUTHOR]

We study a new data mining problem concerning the discovery of frequent agreement subtrees (FASTs) from a set of phylogenetic trees. A phylogenetic tree, or phylogeny, is an unordered tree in which the order among siblings is unimportant. Furthermore, each leaf in the tree has a label representing a taxon (species or organism) name, whereas internal nodes are unlabeled. The tree may have a root, representing the common ancestor of all species in the tree, or may be unrooted. An unrooted phylogeny arises due to the lack of sufficient evidence to infer a common ancestor of the taxa in the tree. The FAST problem addressed here is a natural extension of the maximum agreement subtree (MAST) problem widely studied in the computational phylogenetics community. The paper establishes a framework for tackling the FAST problem for both rooted and unrooted phylogenetic trees using data mining techniques. We first develop a novel canonical form for rooted trees together with a phylogeny-aware tree expansion scheme for generating candidate subtrees level by level. Then, we present an efficient algorithm to find all FASTs in a given set of rooted trees, through an Apriori-like approach. We show the correctness and completeness of the proposed method. Finally, we discuss the extensions of the techniques to unrooted trees. Experimental results demonstrate that the proposed methods work well, and are capable of finding interesting patterns in both synthetic data and real phylogenetic trees. [ABSTRACT FROM AUTHOR]

Integration of biological data of various types and development of adapted bioinformatics tools represent critical objectives to enable research at the systems level. The European Network of Excellence ENFIN is engaged in developing both an adapted infrastructure to connect databases and platforms to enable the generation of new bioinformatics tools as well as the experimental validation of computational predictions. We will give an overview of the projects tackled within ENFIN and discuss the challenges associated with integration for systems biology. [ABSTRACT FROM AUTHOR]

Modelling and simulation techniques are valuable tools for the understanding of complex biological systems. The design of a computer model necessarily has many diverse inputs, such as information on the model topology, reaction kinetics and experimental data, derived either from the literature, databases or direct experimental investigation. In this review, we describe different data resources, standards and modelling and simulation tools that are relevant to integrative systems biology. [ABSTRACT FROM AUTHOR]

Abstract: Much has been written of the facilities for ontology building and reasoning offered for ontologies expressed in the Web Ontology Language (OWL). Less has been written about how the modelling requirements of different areas of interest are met by OWL-DL''s underlying model of the world. In this paper we use the disciplines of biology and bioinformatics to reveal the requirements of a community that both needs and uses ontologies. We use a case study of building an ontology of protein phosphatases to show how OWL-DL''s model can capture a large proportion of the community''s needs. We demonstrate how Ontology Design Patterns (ODPs) can extend inherent limitations of this model. We give examples of relationships between more than two instances; lists and exceptions, and conclude by illustrating what OWL-DL and its underlying description logic either cannot handle in theory or because of lack of implementation. Finally, we present a research agenda that, if fulfilled, would help ensure OWL''s wider take up in the life science community. [Copyright &y& Elsevier]

The promise of the genome project was that a complete sequence would provide us with information that would transform biology and medicine. But the 'parts list' that has emerged from the genome project is far from the 'wiring diagram' and 'circuit logic' we need to understand the link between genotype, environment and phenotype. While genomic technologies such as DNA microarrays, proteomics and metabolomics have given us new tools and new sources of data to address these problems, a number of crucial elements remain to be addressed before we can begin to close the loop and develop a predictive quantitative biology that is the stated goal of so much of current biological research, including systems biology. Our approach to this problem has largely been one of integration, bringing together a vast wealth of information to better interpret the experimental data we are generating in genomic assays and creating publicly available databases and software tools to facilitate the work of others. Recently, we have used a similar approach to trying to understand the biological networks that underlie the phenotypic responses we observe and starting us on the road to developing a predictive biology. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies the problem of building a machine learning method for biological data. Various feature selection methods and classifier design strategies have been generally used and compared. However, most published articles have applied a certain technique to a certain dataset, and recently several researchers compared these techniques based on several public datasets. We propose an ensemble of classifiers that combine a linear classifier, linear support vector machine, a non-linear classifier, radial basis-support vector machines and a Subspace Classifier. We validate our new method on several recent publicly available datasets both with predictive accuracy of testing samples and through cross validation. Compared with the best performance of other current methods, remarkably improved results can be obtained using our new strategy on a wide range of different datasets. On a wide range of recently published datasets, our method performs better, or is at least comparable to, the current best methods of our knowledge. [Copyright &y& Elsevier]

Motivation: Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar.Results: We introduce a new systematic measure of a network''s local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes ‘touching’ k edges, into distributions measuring the number of nodes ‘touching’ k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions of graphlets with 2–5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network ‘agreement’ measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erdös–Rény, random scale-free, or Barabási–Albert scale-free networks.Availability: Software executables are available upon request.Contact:natasha@ics.uci.edu [ABSTRACT FROM AUTHOR]

Background: Innovative extensions of (M) ANOVA gain common ground for the analysis of designed metabolomics experiments. ASCA is such a multivariate analysis method; it has successfully estimated effects in megavariate metabolomics data from biological experiments. However, rigorous statistical validation of megavariate effects is still problematic because megavariate extensions of the classical F-test do not exist. Methods: A permutation approach is used to validate megavariate effects observed with ASCA. By permuting the class labels of the underlying experimental design, a distribution of no-effect is calculated. If the observed effect is clearly different from this distribution the effect is deemed significant Results: The permutation approach is studied using simulated data which gave successful results. It was then used on real-life metabolomics data set dealing with bromobenzene-dosed rats. In this metabolomics experiment the dosage and time-interaction effect were validated, both effects are significant. Histological screening of the treated rats' liver agrees with this finding. Conclusion: The suggested procedure gives approximate p-values for testing effects underlying metabolomics data sets. Therefore, performing model validation is possible using the proposed procedure. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, a novel center-based nearest neighbor (CNN) classifier is proposed to deal with the pattern classification problems. Unlike nearest feature line (NFL) method, CNN considers the line passing through a sample point with known label and the center of the sample class. This line is called the center-based line (CL). These lines seem to have more capacity of representation for sample classes than the original samples and thus can capture more information. Similar to NFL, CNN is based on the nearest distance from an unknown sample point to a certain CL for classification. As a result, the computation time of CNN can be shortened dramatically with less accuracy decrease when compared with NFL. The performance of CNN is demonstrated in one simulation experiment from computational biology and high classification accuracy has been achieved in the leave-one-out test. The comparisons with nearest neighbor (NN) classifier and NFL classifier indicate that this novel classifier achieves competitive performance. [Copyright &y& Elsevier]