1,721,031 research outputs found
Fast Protein Folding in the Hydrophobic-hydrophilic Model within Three-eighths of Optimal (Extended Abstract)
No full text) William E. Hart y Sorin Istrail z Dedicated to Professor Solomon Marcus on the occasion of his 70th birthday Abstract We present performance-guaranteed approximation algorithms for the protein folding problem in the hydrophobichydrophilic model, Dill (1985). To our knowledge, our algorithms are the first approximation algorithms in the literature with guaranteed performance for this model, Dill (1994). The hydrophobic-hydrophilic model abstracts the dominant force of protein folding: the hydrophobic interaction. The protein is modeled as a chain of amino acids of length n which are of two types: H (hydrophobic, i.e., nonpolar) and P (hydrophilic, i.e., polar). Although this model is a simplification of more complex protein folding models, the protein folding structure prediction problem is notoriously difficult for this model. Our algorithms have linear (3n) time and achieve a three-dimensional protein conformation that has a guaranteed free energy within 3=8 of optimal. By ac..
Lattice and Off-Lattice Side Chain Models of Protein Folding: Linear Time Structure Prediction Better Than 86% of Optimal (Extended Abstract)
No full text) William E. Hart Sorin Istrail y Abstract This paper considers the protein structure prediction problem for lattice and off-lattice protein folding models that explicitly represent side chains. Lattice models of proteins have proven extremely useful tools for reasoning about protein folding in unrestricted continuous space through analogy. This paper provides the first illustration of how rigorous algorithmic analyses of lattice models can lead to rigorous algorithmic analyses of off-lattice models. We consider two side chain models: a lattice model that generalizes the HP model (Dill 85) to explicitly represent side chains on the cubic lattice, and a new off-lattice model, the HP Tangent Spheres Side Chain model (HP-TSSC), that generalizes this model further by representing the backbone and side chains of proteins with tangent spheres. We describe algorithms with mathematically guaranteed error bounds for both of these models. In particular, we describe a linear time performanc..
Practical Algorithms and Fixed-Parameter Tractability for the Single Individual SNP Haplotyping Problem
No full textSingle nucleotide polymorphisms (SNPs) are the most frequent form of human genetic variation, of foremost importance for a variety of applications including medical diagnostic, phylogenies and drug design.
The complete SNPs sequence information from each of the two copies of a given chromosome in a diploid genome is called a haplotype. The Haplotyping Problem for a single individual is as follows: Given a set of fragments from one individual’s DNA, find a maximally consistent pair of SNPs haplotypes (one per chromosome copy) by removing data “errors” related to sequencing errors, repeats, and paralogous recruitment. Two versions of the problem, i.e. the Minimum Fragment Removal (MFR) and the Minimum SNP Removal (MSR), are considered.
The Haplotyping Problem was introduced in [8], where it was proved that both MSR and MFR are polynomially solvable when each fragment covers a set of consecutive SNPs (i.e., it is a gapless fragment), and NP-hard in general. The original algorithms of [8] are of theoretical interest, but by no means practical. In fact, one relies on finding the maximum stable set in a perfect graph, and the other is a reduction to a network flow problem. Furthermore, the reduction does not work when there are fragments completely included in others, and neither algorithm can be generalized to deal with a bounded total number of holes in the data. In this paper, we give the first practical algorithms for the Haplotyping Problem, based on Dynamic Programming. Our algorithms do not require the fragments to not include each other, and are polynomial for each constant k bounding the total number of holes in the data. For m SNPs and n fragments, we give an O(mn^{2k+2}) algorithm for the MSR problem, and an O(2^{2k} m^2 n+2^{3k} m^3) algorithm for the MFR problem, when each fragment has at most k holes. In particular, we obtain an O(mn^2) algorithm for MSR and an O(m^2 n+m^3) algorithm for MFR on gapless fragments.
Finally, we prove that both MFR and MSR are APX-hard in general
Research in Computational Molecular Biology, 10th Annual International Conference, RECOMB 2006, Venice, Italy, April 2-5, 2006, Proceedings Springer 2006
No full text
Polynomial and APX-hard cases of the individual haplotyping problem
No full textAbstractSNP haplotyping problems have been the subject of extensive research in the last few years, and are one of the hottest areas of Computational Biology today. In this paper we report on our work of the last two years, whose preliminary results were presented at the European Symposium on Algorithms (Proceedings of the Annual European Symposium on Algorithms (ESA), Vol. 2161. Lecture Notes in Computer Science, Springer, 2001, pp. 182–193.) and Workshop on Algorithms in Bioinformatics (Proceedings of the Annual Workshop on Algorithms in Bioinformatics (WABI), Vol. 2452. Lecture Notes in Computer Science, Springer, 2002, pp. 29–43.). We address the problem of reconstructing two haplotypes for an individual from fragment assembly data. This problem will be called the Single Individual Haplotyping Problem. On the positive side, we prove that the problem can be solved effectively for gapless data, and give practical, dynamic programming algorithms for its solution. On the negative side, we show that it is unlikely that polynomial algorithms exist, even to approximate the solution arbitrarily well, when the data contain gaps. We remark that both the gapless and gapped data arise in different real-life applications
A bayesian network model of proteins' association with promyelocytic leukemia (PML) nuclear bodies
No full textThe modularity that nuclear organization brings has the potential to explain the function of aggregates of proteins and RNA. Promyelocytic leukemia nuclear bodies are implicated in important regulatory processes. To understand the complement of proteins associated with these intra-nuclear bodies, we construct a Bayesian network model that integrates sequence and protein-protein interaction data. The model predicts association with promyelocytic leukemia nuclear bodies accurately when interaction data is available. At a false positive rate of 10%, the true positive rate is almost 50%, indicated by an independent nuclear proteome reference set. The model provides strong support for further expanding the protein complement with several important regulators and a richer functional repertoire. Using special support vector machine (SVM)-nodes (equipped with string kernels), the Bayesian network is also able to produce predictions on the basis of sequence only, with an accuracy superior to that of baseline models. Supplementary Material is available online at www.liebertonline.com
- …
