Journal of Bioinformatics and Computational Biology

It is already known that power in multimarker transmission/disequilibrium tests may improve with the number of markers as some associations may require several markers to be captured. However, a mechanism such as haplotype grouping must be used to avoid incremental complexity with the number of markers. 2G, a state-of-the-art transmission/disequilibrium test, implements this mechanism to its maximum extent by grouping haplotypes into only two groups, high and low-risk haplotypes, so that the test has only one degree of freedom regardless of the number of markers. The test checks whether those haplotypes more often transmitted from parents to offspring are truly high-risk haplotypes. In this paper we use haplotype similarity as prior knowledge to classify haplotypes as high or low risk ones and start with those haplotypes in which the prior will have lower impact i.e. those with the largest differences between transmission and non-transmission counts. If their counts are very different, the prior knowledge has little effect and haplotypes are classified as low or high risk as 2G does. We show a substantial gain in power achieved by this approach, in both simulation and real data sets.

Very often biologists are interested to know the biological function of a particular gene. Its true biological function may depend on other genes. Finding other genes in the same biological pathway of that gene may enhance further understanding of its biological function. Therefore, we are interested in finding other candidate genes whose expression values are highly correlated with that of a "seed" gene. The "seed" gene, which is known and associated with a disease, is used as a reference to extract candidate genes from microarray experiments and enriched pathways. We propose a nonparametric procedure for selecting the candidate genes. The expression levels for these candidate genes are correlated with that of a "seed" gene in microarray experiments. The proposed test statistic compares two Area Under Receiver Operating Characteristic Curves (AUC) for gene pairs, taking implicit correlation between two AUCs into account. The performance of our method is compared to the other well-known methods through the use of simulation and real data analysis.

DNA markers are frequently used to analyze crop varieties, with the coded marker data summarized in a computer-generated table. Such summary tables often provide extraneous data about individual crop genotypes, needlessly complicating and prolonging DNA-based differentiation between crop varieties. At present, it is difficult to identify minimal marker sets — the smallest sets that can distinguish between all crop varieties listed in a marker-summary table — due to the absence of algorithms capable of such characterization. Here, we describe the development of just such an algorithm and MinimalMarker, its accompanying Perl-based computer program. MinimalMarker has been validated in variety identification of fruit trees using published datasets and is available for use with both dominant and co-dominant markers, regardless of the number of alleles, including SSR markers with numeric notation. We expect that this program will prove useful not only to genomics researchers but also to government agencies that use DNA markers to support a variety of food-inspection and -labeling regulations.

This is a study on the precision of four known protein disorder predictors, ranked among the best-performing ones: DISOPRED2, PONDR VSL2B, IUPred and ESpritz. We address here the problem of a systematic overestimation of the number of disordered proteins recognized through the use of these predictors, considered as a standard. Some of these predictors, used with their default setting, have a low precision, implying a tendency to overestimate the occurrence of disordered proteins in genome-wide surveys. Moreover, different predictors often disagree on the evaluation of individual proteins. To cope with this problem and in order to propose a simple procedure that enhances precision based on precision-recall curves, we re-tuned the discriminative thresholds of the predictors by training and cross-validating their performance on a cured dataset. After re-tuning, both the disagreement among predictors and the tendency to overestimate the occurrence of disordered proteins are reduced. This is shown in a dedicated study over the human proteome and a set of cancer-related human proteins, with no a priori disorder annotation. Simple quantitative estimates suggest that the occurrence of disorder among cancer-related proteins and other similar large-scale surveys has been overestimated in the past.

The extraction of fluorescence intensity profiles of single cells from image data is a common challenge in cell biology. The manual segmentation of cells, the extraction of cell orientation and finally the extraction of intensity profiles are time-consuming tasks. This article proposes a routine for the segmentation of single rod-shaped cells (i.e. without neighboring cells in a distance of the cell length) from image data combined with an extraction of intensity distributions along the longitudinal cell axis under the aggravated conditions of (i) a low spatial resolution and (ii) lacking information on the imaging system i.e. the point spread function and signal-to-noise ratio. The algorithm named cipsa transfers a new approach from particle streak velocimetry to cell classification interpreting the rod-shaped as streak-like structures. An automatic reduction of systematic errors such as photobleaching and defocusing is included to guarantee robustness of the proposed approach under the described conditions and to the convenience of end-users unfamiliar with image processing. Performance of the algorithm has been tested on image sequences with high noise level produced by an overlay of different error sources. The developed algorithm provides a user-friendly, stand-alone procedure.

Comparative genomic studies are often conducted by reconciliation analyses comparing gene and species trees. One of the issues with reconciliation approaches is that an exponential number of optimal scenarios is possible. The resulting complexity is masked by the fact that a majority of reconciliation software pick up a random optimal solution that is returned to the end-user. However, the alternative solutions should not be ignored since they tell different stories that parsimony considers as viable as the output solution. In this paper, we describe a polynomial space and time algorithm to build a minimum reconciliation graph — a graph that summarizes the set of all most parsimonious reconciliations. Amongst numerous applications, it is shown how this graph allows counting the number of non-equivalent most parsimonious reconciliations.

Synthetic biology is a rapidly emerging discipline with long-term ramifications that range from single-molecule detection within cells to the creation of synthetic genomes and novel life forms. Truly phenomenal results have been obtained by pioneering groups — for instance, the combinatorial synthesis of genetic networks, genome synthesis using BioBricks, and hybridization chain reaction (HCR), in which stable DNA monomers assemble only upon exposure to a target DNA fragment, biomolecular self-assembly pathways, etc. Such work strongly suggests that nanotechnology and synthetic biology together seem poised to constitute the most transformative development of the 21st century. In this paper, we present a Constraint Programming (CP) approach to solve the RNA inverse folding problem. Given a target RNA secondary structure, we determine an RNA sequence which folds into the target structure; i.e. whose minimum free energy structure is the target structure. Our approach represents a step forward in RNA design — we produce the first complete RNA inverse folding approach which allows for the specification of a wide range of design constraints. We also introduce a Large Neighborhood Search approach which allows us to tackle larger instances at the cost of losing completeness, while retaining the advantages of meeting design constraints (motif, GC-content, etc.). Results demonstrate that our software, RNAiFold, performs as well or better than all state-of-the-art approaches; nevertheless, our approach is unique in terms of completeness, flexibility, and the support of various design constraints. The algorithms presented in this paper are publicly available via the interactive webserver http://bioinformatics.bc.edu/clotelab/RNAiFold; additionally, the source code can be downloaded from that site.

High-throughput single nucleotide polymorphism genotyping assays conveniently produce genotype data for genome-wide genetic linkage and association studies. For pedigree datasets, the unphased genotype data is used to infer the haplotypes for individuals, according to Mendelian inheritance rules. Linkage studies can then locate putative chromosomal regions based on the haplotype allele sharing among the pedigree members and their disease status. Most existing haplotyping programs require rather strict pedigree structures and return a single inferred solution for downstream analysis. In this research, we relax the pedigree structure to contain ungenotyped founders and present a cubic time whole genome haplotyping algorithm to minimize the number of zero-recombination haplotype blocks. With or without explicitly enumerating all the haplotyping solutions, the algorithm determines all distinct haplotype allele identity-by-descent (IBD) sharings among the pedigree members, in linear time in the total number of haplotyping solutions. Our algorithm is implemented as a computer program iBDD. Extensive simulation experiments using 2 sets of 16 pedigree structures from previous studies showed that, in general, there are trillions of haplotyping solutions, but only up to a few thousand distinct haplotype allele IBD sharings. iBDD is able to return all these sharings for downstream genome-wide linkage and association studies.

Host–pathogen interactions are important for understanding infection mechanism and developing better treatment and prevention of infectious diseases. Many computational studies on host–pathogen interactions have been published. Here, we review recent progress and results in this field and provide a systematic summary, comparison and discussion of computational studies on host–pathogen interactions, including prediction and analysis of host–pathogen protein–protein interactions; basic principles revealed from host–pathogen interactions; and database and software tools for host–pathogen interaction data collection, integration and analysis.

Complexes of physically interacting proteins are one of the fundamental functional units responsible for driving key biological mechanisms within the cell. Their identification is therefore necessary to understand not only complex formation but also the higher level organization of the cell. With the advent of "high-throughput" techniques in molecular biology, significant amount of physical interaction data has been cataloged from organisms such as yeast, which has in turn fueled computational approaches to systematically mine complexes from the network of physical interactions among proteins (PPI network). In this survey, we review, classify and evaluate some of the key computational methods developed till date for the identification of protein complexes from PPI networks. We present two insightful taxonomies that reflect how these methods have evolved over the years toward improving automated complex prediction. We also discuss some open challenges facing accurate reconstruction of complexes, the crucial ones being the presence of high proportion of errors and noise in current high-throughput datasets and some key aspects overlooked by current complex detection methods. We hope this review will not only help to condense the history of computational complex detection for easy reference but also provide valuable insights to drive further research in this area.

We review the proposed mathematical models of the response to osmotic stress in yeast. These models mainly differ in the choice of mathematical representation (e.g. Bayesian networks, ordinary differential equations, or rule-based models), the extent to which the modeling is data-driven, and predictability. The overview exemplifies how one biological system can be modeled with various modeling techniques and at different levels of resolution, and how the choice typically is based on the amount and quality of available data, prior information of the system, and the research question in focus. As a natural part of the overview, we discuss requirements, advantages, and limitations of the different modeling approaches.