Improving Strand Pairing Prediction through Exploring Folding Cooperativity
The topology of $\beta$-sheets is defined by the pattern of hydrogen-bonded strand pairing. Therefore, predicting hydrogen bonded strand partners is a fundamental step towards predicting $\beta$-sheet topology. At the same time, finding the correct ...
SpeedHap: An Accurate Heuristic for the Single Individual SNP Haplotyping Problem with Many Gaps, High Reading Error Rate and Low Coverage
Single nucleotide polymorphism (SNP) is the most frequent form of DNA variation. The set of SNP's present in a chromosome (called the em haplotype) is of interest in a wide area of applications in molecular biology and biomedicine, including diagnostic ...
Seeded Tree Alignment
The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in ...
An Ω(n^2/ log n) Speed-Up of TBR Heuristics for the Gene-Duplication Problem
The gene-duplication problem is to infer a species supertree from gene trees that are confounded by complex histories of gene duplications. This problem is NP-hard and thus requires efficient and effective heuristics. Existing heuristics perform a ...
Defining and Computing Optimum RMSD for Gapped and Weighted Multiple-Structure Alignment
Pairwise structure alignment commonly uses root mean square deviation (RMSD) to measure the structural similarity, and methods for optimizing RMSD are well established. We extend RMSD to weighted RMSD for multiple structures. By using multiplicative ...
Efficient Algorithms to Explore Conformation Spaces of Flexible Protein Loops
- Peggy Yao,
- Ankur Dhanik,
- Nathan Marz,
- Ryan Propper,
- Charles Kou,
- Guanfeng Liu,
- Henry van den Bedem,
- Jean-Claude Latombe,
- Inbal Halperin-Landsberg,
- Russ B. Altman
Several applications in biology - e.g., incorporation of protein flexibility in ligand docking algorithms, interpretation of fuzzy X-ray crystallographic data, and homology modeling - require computing the internal parameters of a flexible fragment (...
Learning Scoring Schemes for Sequence Alignment from Partial Examples
When aligning biological sequences, the choice of parameter values for the alignment scoring function is critical. Small changes in gap penalties, for example, can yield radically different alignments. A rigorous way to compute parameter values that are ...
Efficient Algorithms for the Computational Design of Optimal Tiling Arrays
The representation of a genome by oligonucleotide probes is a prerequisite for the analysis of many of its basic properties, such as transcription factor binding sites, chromosomal breakpoints, gene expression of known genes and detection of novel genes,...
Computational Approaches for Automatic Structural Analysis of Large Biomolecular Complexes
We present computational solutions to two problemsof macromolecular structure interpretation from reconstructedthree-dimensional electron microscopy (3D-EM) maps of largebio-molecular complexes at intermediate resolution (5A-15A). Thetwo problems ...
Gene Expression Data Analysis Using a Novel Approach to Biclustering Combining Discrete and Continuous Data
Many different methods exist for pattern detection in gene expression data. In contrast to classical methods, biclustering has the ability to cluster a group of genes together with a group of conditions (replicates, set of patients or drug compounds). ...
An Introduction to Metabolic Networks and Their Structural Analysis
There has been a renewed interest for metabolism in the computational biology community, leading to an avalanche of papers coming from methodological network analysis as well as experimental and theoretical biology. This paper is meant to serve as an ...
The Undirected Incomplete Perfect Phylogeny Problem
The incomplete perfect phylogeny (IPP) problem and the incomplete perfect phylogeny haplotyping (IPPH) problem deal with constructing a phylogeny for a given set of haplotypes or genotypes with missing entries. The earlier approaches for both of these ...
Optimization of cDNA Microarray Experimental Designs Using an Evolutionary Algorithm
The cDNA microarray is an important tool for generating large datasets of gene expression measurements.An efficient design is critical to ensure that the experiment will be able to address relevant biologicalquestions. Microarray experimental design can ...