Search

In this paper, we study the adaptive version of the point placement problem on a line, which is motivated by a DNA mapping problem. To identify the relative positions of n distinct points on a straight line, we are allowed to ask queries of pairwise distances of the points in rounds. The problem is to find the number of queries required to determine a unique solution for the positions of the points up to translation and reflection. We improved the bounds for several cases. We show that $4n/3 + O(\sqrt{n})$ queries are sufficient for the case of two rounds while the best known result was 3n/2 queries. For unlimited number of rounds, the best result was 4n/3 queries. We obtain a much better result of using $5n/4 + O(\sqrt{n})$ queries with three rounds only. We also improved the lower bound of 30n/29 to 17n/16 for the case of two rounds. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new method of combined synthesis and inference of biological signal transduction networks. A main idea of our method lies in representing observed causal relationships as network paths and using techniques from combinatorial optimization to find the sparsest graph consistent with all experimental observations. Our contributions are twofold: on the theoretical and algorithmic side, we formalize our approach, study its computational complexity and prove new results for exact and approximate solutions of the computationally hard transitive reduction substep of the approach. On the application side, we validate the biological usability of our approach by successfully applying it to a previously published signal transduction network by Li et al. [20] and show that our algorithm for the transitive reduction substep performs well on graphs with a structure similar to those observed in transcriptional regulatory and signal transduction networks. [ABSTRACT FROM AUTHOR]

Genomic tiling arrays are a type of DNA microarrays which can investigate the complete genome of arbitrary species for which the sequence is known. The design or selection of suitable oligonucleotide probes for such arrays is however computationally difficult if features such as oligonucleotide quality and repetitive regions are to be considered. We formulate the minimal cost tiling path problem for the selection of oligonucleotides from a set of candidates, which is equivalent to a shortest path problem. An efficient implementation of Dijkstra's shortest path algorithm allows us to compute globally optimal tiling paths from millions of candidate oligonucleotides on a standard desktop computer. The solution to this multi-criterion optimization is spatially adaptive to the problem instance. Our formulation incorporates experimental constraints with respect to specific regions of interest and tradeoffs between hybridization parameters, probe quality and tiling density easily. Solutions for the basic formulation can be obtained more efficiently from Monge theory. [ABSTRACT FROM AUTHOR]

The comprehensive annotation of non-coding RNAs in newly sequenced genomes is still a largely unsolved problem because many functional RNAs exhibit not only poorly conserved sequences but also large variability in structure. In many cases, such as Y RNAs, vault RNAs, or telomerase RNAs, sequences differ by large insertions or deletions and have only a few small sequence patterns in common. Here we present fragrep2, a purely sequence-based approach to detect such patterns in complete genomes. A fragrep2 pattern consists of an ordered list of position-specific weight matrices (PWMs) describing short, approximately conserved sequence elements, that are separated by intervals of non-conserved regions of bounded length. The program uses a fractional programming approach to align the PWMs to genomic DNA in order to allow for a bounded number of insertions and deletions in the patterns. These patterns are then combined to significant combinations of PWMs. At this step, a subset of PWMs may be deleted, i.e., have no match in the current region of the genome. The program furthermore estimates p- and E-values for the matches. We apply fragrep2 to homology searches for RNase MRP, unveiling two previously unidentified matches as well as reproducing the results of two previous surveys. Furthermore, we complement the picture of vertebrate vault RNAs, a class of ncRNAs that has not received much attention so far. [ABSTRACT FROM AUTHOR]

Parameter estimation of large bio-pathway models is an important and difficult problem. To reduce the prohibitive computational cost, one approach is to decompose a large model into components and estimate their parameters separately. However, the decomposed components often share common parts that may have conflicting parameter estimates, as they are computed independently within each component. In this paper, we propose to use a probabilistic inference technique called belief propagation to reconcile these independent estimates in a principled manner and compute new estimates that are globally consistent and fit well with data. An important advantage of our approach in practice is that it naturally handles incomplete or noisy data. Preliminary results based on synthetic data show promising performance in terms of both accuracy and efficiency. [ABSTRACT FROM AUTHOR]

We introduce a novel algorithm to cluster and order markers on a genetic linkage map, which is based on several theoretical observations. In most cases, the true order of the markers in a linkage group can be efficiently computed from the minimum spanning tree of a graph. Our empirical studies confirm our theoretical observations, and show that our algorithm consistently outperforms the best available tool in the literature, in particular when the genotyping data is noisy or in case of missing observations. [ABSTRACT FROM AUTHOR]

Improving the accuracy and efficiency of computational RNA secondary structure prediction is an important challenge, particularly for pseudoknotted secondary structures. We propose a new approach for prediction of pseudoknotted structures, motivated by the hypothesis that RNA structures fold hierarchically, with pseudoknot free pairs forming initially, and pseudoknots forming later so as to minimize energy relative to the initial pseudoknot free structure. Our HFold (Hierarchical Fold) algorithm has O(n3) running time, and can handle a wide range of biological structures, including nested kissing hairpins, which have previously required Θ(n6) time using traditional minimum free energy approaches. We also report on an experimental evaluation of HFold. [ABSTRACT FROM AUTHOR]

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 appropriate for biological sequences is inverse parametric sequence alignment. Given a collection of examples of biologically correct alignments, this is the problem of finding parameter values that make the example alignments score close to optimal. We extend prior work on inverse alignment to partial examples and to an improved model based on minimizing the average error of the examples. Experiments on benchmark biological alignments show we can find parameters that generalize across protein families and that boost the recovery rate for multiple sequence alignment by up to 25%. [ABSTRACT FROM AUTHOR]

In comparing genomic maps, we try to distinguish mapping errors and incorrectly resolved paralogies from genuine rearrangements of the genomes. This can be formulated as a Maximum Weight Independent Set (MWIS) search, where vertices are potential strips of markers syntenic on both genomes, and edges join conflicting strips, in order to extract the subset of compatible strips that accounts for the largest proportion of the data. This technique is computationally hard. We introduce biologically meaningful constraints on the strips, reducing the number of vertices for the MWIS analysis and provoking a decomposition of the graph into more tractable components. New improvements to existing MWIS algorithms greatly improve running time, especially when the strip conflicts define an interval graph structure. A validation of solutions through genome rearrangement analysis enables us to identify the most realistic solution. We apply this to the comparison of the rice and sorghum genomes. [ABSTRACT FROM AUTHOR]

The Specific Selection Problem arises from the need to design short interfering RNA (siRNA) that aims at gene silencing. These short sequences target specific messenger RNA (mRNA) and cause the degradation of such mRNA, inhibiting the synthesis of the protein generated by it. In [11] this problem was solved in a reasonable amount of time when restricted to the design of siRNA for a particular mRNA, but their approach becomes too time consuming when trying to design siRNA for each mRNA in a given organism. We devise simple algorithms based on sorting and hashing techniques that allow us to solve this problem for the entire mRNA of the Human in less than 4 hours, obtaining a speedup of almost two orders of magnitude over previous approaches. [ABSTRACT FROM AUTHOR]

Homology search finds similar segments between two biological sequences, such as DNA or protein sequences. A significant fraction of computing power in the world is dedicated to performing such tasks. The introduction of optimal spaced seeds by Ma et al. has increased both the sensitivity and the speed of homology search and it has been adopted by many alignment programs such as BLAST. With the further improvement provided by multiple spaced seeds in PatternHunterII, the sensitivity of dynamic programming is approached at BLASTn speed. Whereas computing optimal multiple spaced seeds was proved to be NP-hard, we show that, from practical point of view, computing good ones can be very efficient. We give a simple heuristic algorithm which computes good multiple seeds in polynomial time. Computing sensitivity is not required. When allowing the computation of the sensitivity for few seeds, we obtain better multiple seeds than previous ones in much shorter time. [ABSTRACT FROM AUTHOR]

Predicting the secondary structure of an RNA sequence is an important problem in structural bioinformatics. The general RNA folding problem, where the sequence to be folded may contain pseudoknots, is computationally intractable when no prior knowledge on the pseudoknot structures the sequence contains is available. In this paper, we consider stable stems in an RNA sequence and provide a new characterization for its stem graph, a graph theoretic model that has been used to describe the overlapping relationships for stable stems. Based on this characterization, we identify a new structure parameter for a stem graph. We call this structure parameter crossing width. We show that given a sequence with crossing width c for its stem graph, the general RNA folding problem can be solved in time O(2ck3n2), where n is the length of the sequence, k is the maximum length of stable stems. Moreover, this characterization leads to an $O(2^{(1+2k^2)n}n^{2}k^{3})$ time algorithm for the general RNA folding problem where the lengths of stems in the sequence are at most k, this result improves the upper bound of the problem to 2O(n)n2 when the maximum stem length is bounded by a constant. [ABSTRACT FROM AUTHOR]

Graph-theoretic models have come to the forefront as some of the most powerful and practical methods for sequence assembly. Simultaneously, the computational hardness of the underlying graph algorithms has remained open. Here we present two theoretical results about the complexity of these models for sequence assembly. In the first part, we show sequence assembly to be NP-hard under two different models: string graphs and de Bruijn graphs. Together with an earlier result on the NP-hardness of overlap graphs, this demonstrates that all of the popular graph-theoretic sequence assembly paradigms are NP-hard. In our second result, we give the first, to our knowledge, optimal polynomial time algorithm for genome assembly that explicitly models the double-strandedness of DNA. We solve the Chinese Postman Problem on bidirected graphs using bidirected flow techniques and show to how to use it to find the shortest double-stranded DNA sequence which contains a given set of k-long words. This algorithm has applications to sequencing by hybridization and short read assembly. [ABSTRACT FROM AUTHOR]

In this work we study string kernel methods for sequence analysis and focus on the problem of species-level identification based on short DNA fragments known as barcodes. We introduce efficient sorting-based algorithms for exact string k-mer kernels and then describe a divide-and-conquer technique for kernels with mismatches. Our algorithms for mismatch kernel matrix computations improve currently known time bounds for these computations. We then consider the mismatch kernel problem with feature selection, and present efficient algorithms for it. Our experimental results show that, for string kernels with mismatches, kernel matrices can be computed 100-200 times faster than traditional approaches. Kernel vector evaluations on new sequences show similar computational improvements. On several DNA barcode datasets, k-mer string kernels considerably improve identification accuracy compared to prior results. String kernels with feature selection demonstrate competitive performance with substantially fewer computations. [ABSTRACT FROM AUTHOR]

Genomes have both deterministic and random aspects, with the underlying DNA sequences exhibiting features at numerous scales, from codons to regions of conserved or divergent gene order. This work examines the unique manner in which oligonucleotides fit together to comprise a genome, within a graph-theoretic setting. A de Bruijn chain (DBC) is a generalization of a finite Markov chain. A DNA word graph (DWG) is a generalization of a de Bruijn graph that records the occurrence counts of node and edges in a genomic sequence generated by a DBC. We combine the properties of DWGs and DBCs to obtain a powerful genomic signature demonstrated as information-rich, efficient, and sufficiently representative of the sequence from which it is derived. We illustrate its practical value in distinguishing genomic sequences and predicting the origin of short DNA sequences of unknown origin, while highlighting its superior performance compared to existing genomic signatures including the dinucleotides odds ratio. [ABSTRACT FROM AUTHOR]

Two efficient and complementary sampling algorithms are presented to explore the space of closed clash-free conformations of a flexible protein loop. The "seed sampling" algorithm samples conformations broadly distributed over this space, while the "deformation sampling" algorithm uses these conformations as starting points to explore more finely selected regions of the space. Computational results are shown for loops ranging from 5 to 25 residues. The algorithms are implemented in a toolkit, LoopTK, available at https://simtk.org/home/looptk. [ABSTRACT FROM AUTHOR]

Proteins are the most important molecular entities of a living organism and understanding their functions is an important task to treat diseases and synthesize new drugs. It is largely known that the function of a protein is strictly related to its spatial conformation: to tackle this problem, we have proposed a new approach based on a class of pattern search algorithms that is largely used in optimization of real world applications. The obtained results are interesting in terms of the quality of the structures (RMSD-Cα) and energy values found. [ABSTRACT FROM AUTHOR]

Hidden Markov models (HMMs) are routinely used for analysis of long genomic sequences to identify various features such as genes, CpG islands, and conserved elements. A commonly used Viterbi algorithm requires O(mn) memory to annotate a sequence of length n with an m-state HMM, which is impractical for analyzing whole chromosomes. In this paper, we introduce the on-line Viterbi algorithm for decoding HMMs in much smaller space. Our analysis shows that our algorithm has the expected maximum memory Θ(mlogn) on two-state HMMs. We also experimentally demonstrate that our algorithm significantly reduces memory of decoding a simple HMM for gene finding on both simulated and real DNA sequences, without a significant slow-down compared to the classical Viterbi algorithm. [ABSTRACT FROM AUTHOR]

We present a novel approach for predicting protein folding kinetics using techniques from the field of model checking. This represents the first time model checking has been applied to a problem in the field of structural biology. The protein's energy landscape is encoded symbolically using Binary Decision Diagrams and related data structures. Questions regarding the kinetics of folding are encoded as formulas in the temporal logic CTL. Model checking algorithms are then used to make quantitative predictions about the kinetics of folding. We show that our approach scales to state spaces as large as 1023 when using exact algorithms for model checking. This is at least 14 orders of magnitude larger than the number of configurations considered by comparable techniques. Furthermore, our approach scales to state spaces at least as large as 1032 unique configurations when using approximation algorithms for model checking. We tested our method on 19 test proteins. The quantitative predictions regarding folding rates for these test proteins are in good agreement with experimentally measured values, achieving a correlation coefficient of 0.87. [ABSTRACT FROM AUTHOR]

Background: Protein domains are the common functional elements used by nature to generate tremendous diversity among proteins, and they are used repeatedly in different combinations across all major domains of life. In this paper we address the problem of using similarity to known protein domains in helping with the identification of genes in a DNA sequence. We have adapted the generalized hidden Markov model (GHMM) architecture of the ab intio gene finder GlimmerHMM such that a higher probability is assigned to exons that contain homologues to protein domains. To our knowledge, this domain homology based approach has not been used previously in the context of ab initio gene prediction. Results: GlimmerHMM was augmented with a protein domain module that recognizes gene structures that are similar to Pfam models. The augmented system, GlimmerHMM+, shows 2% improvement in sensitivity and a 1% increase in specificity in predicting exact gene structures compared to GlimmerHMM without this option. These results were obtained on two very different model organisms: Arabidopsis thaliana (mustard wee) and Danio rerio (zebrafish), and together these preliminary results demonstrate the value of using protein domain homology in gene prediction. The results obtained are encouraging, and we believe that a more comprehensive approach including a model that reflects the statistical characteristics of specific sets of protein domain families would result in a greater increase of the accuracy of gene prediction. GlimmerHMM and GlimmerHMM+ are freely available as open source software at http://cbcb.umd.edu/software. [ABSTRACT FROM AUTHOR]

Pairwise structure alignment commonly uses root mean square deviation (RMSD) to measure the structural similarity, and methods for optimizing RMSD are well established. However, multiple structure alignment with gaps cannot use these methods directly. We extend RMSD to weighted RMSD for multiple structures, which includes gapped alignment as a special case. By using multiplicative weights, we show that weighted RMSD for all pairs is the same as weighted RMSD to an ave-rage of the structures. Although we show that the two tasks of finding the optimal translations and rotations for minimizing weighted RMSD cannot be separated for multiple structures like they can for pairs, an inherent difficulty and a fact ignored by previous work, we develop an iterative algorithm, in which each iteration takes linear time and the number of iterations is small, to converge weighted RMSD to a local minimum. 10,000 experiments done on each of 23 protein families from HOMSTRAD (where each structure starts with a random translation and rotation) converge rapidly to the same minimum. Finally we propose a heuristic method to iteratively remove the effect of outliers and find well-aligned positions that determine the structural conserved region by modeling B-factors and deviations from the average positions as weights and iteratively assigning higher weights to better aligned atoms. [ABSTRACT FROM AUTHOR]

The aim of the motif recognition problem is to detect a set of mutually similar subsequences in a collection of biological sequences. Weak motif recognition is where the sequences are highly degenerate. Our new approach to this problem uses a weighted graph model and a heuristic that determines high weight subgraphs in polynomial time. Our experimental tests show impressive accuracy and efficiency. We give results that demonstrate a theoretical dichotomy between cliques in our graph that represent actual motifs and those that do not. [ABSTRACT FROM AUTHOR]

Compact bases formed by motifs called "irredundant" and capable of generating all other motifs in a sequence have been proposed in [8,10] and successfully tested in tasks of biosequence analysis and classification. Given a sequence s of n characters drawn from an alphabet Σ, the problem of extracting such a base from s had been previously solved in time O(Σn2 logn) and O(Σn2 logn), respectively in [9] and [7], through resort to the FFT-based string searching by Fischer and Paterson [5]. More recently, a solution taking time O(Σn2) without resort to the FFT was also devised [4]. [ABSTRACT FROM AUTHOR]

Protein structural alignment is an indispensable tool used for many different studies in bioinformatics. Most structural alignment algorithms assume that the structural units of two similar proteins will align sequentially. This assumption may not be true for all similar proteins and as a result, proteins with similar structure but with permuted sequence arrangement are often missed. We present a solution to the problem based on an approximation algorithm that finds a sequence-order independent structural alignment that is close to optimal. We first exhaustively fragment two proteins and calculate a novel similarity score between all possible aligned fragment pairs. We treat each aligned fragment pair as a vertex on a graph. Vertices are connected by an edge if there are intra residue sequence conflicts. We regard the realignment of the fragment pairs as a special case of the maximum-weight independent set problem and solve this computationally intensive problem approximately by iteratively solving relaxations of an appropriate integer programming formulation. The resulting structural alignment is sequence order independent. Our method is insensitive to gaps, insertions/deletions, and circular permutations. [ABSTRACT FROM AUTHOR]

Consensus and sequence pattern analysis on family alignments are extensively used to identify new family members and to determine functionally and structurally important identities. Since these common approaches emphasize dominant characteristics of the family and assume residue identities are independent at each position, there is no way to describe residue preferences outside of the family consensus. In this study, we propose a novel approach to detect motifs outside the consensus of a protein family alignment via an information theoretic approach. We implemented an algorithm that discovers frequent residue motifs that are high in information content and outside of the family consensus, called informative motifs, inspired by the classic Apriori algorithm. We observed that these informative motifs are mostly spatially localized and present distinctive features of various members of the family. Availability: The source code is available upon request from the authors. [ABSTRACT FROM AUTHOR]

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. We introduce a constrained form of this problem in which a partial mapping of a set of nodes in one tree to a corresponding set of nodes in the other tree is given, and present efficient algorithms for both ordered and unordered trees. Whereas ordered tree matching based on seeded nodes has applications in pattern matching of RNA structures, unordered tree matching based on seeded nodes has applications in co-speciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which we give a polynomial-time algorithm. [ABSTRACT FROM AUTHOR]

The presence of genotyping errors can invalidate statistical tests for linkage and disease association, particularly for methods based on haplotype analysis. Becker et al. have recently proposed a simple likelihood ratio approach for detecting errors in trio genotype data. Under this approach, a SNP genotype is flagged as a potential error if the likelihood associated with the original trio genotype data increases by a multiplicative factor exceeding a user selected threshold when the SNP genotype under test is deleted. In this paper we give improved error detection methods using the likelihood ratio test approach in conjunction with likelihood functions that can be efficiently computed based on a Hidden Markov Model of haplotype diversity in the population under study. Experimental results on both simulated and real datasets show that proposed methods achieve significantly improved detection accuracy compared to previous methods with highly scalable running time. [ABSTRACT FROM AUTHOR]

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 stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. We improve on the time complexity of the local search problem by a factor of n2/logn, where n is the size of the resulting species supertree. Typically, several thousand instances of the local search problem are solved throughout a stepwise heuristic search. Hence, our improvement makes the gene-duplication problem much more tractable for large-scale phylogenetic analyses. [ABSTRACT FROM AUTHOR]

The evolution of viruses is very rapid and in addition to local point mutations (insertion, deletion, substitution) it also includes frequent recombinations, genome rearrangements, and horizontal transfer of genetic material. Evolutionary analysis of viral sequences is therefore a complicated matter for two main reasons: First, due to HGTs and recombinations, the right model of evolution is a network and not a tree. Second, due to genome rearrangements, an alignment of the input sequences is not guaranteed. Since contemporary methods for inferring phylogenetic networks require aligned sequences as input, they cannot deal with viral evolution. In this work we present the first computational approach which deals with both genome rearrangements and horizontal gene transfers and does not require a multiple alignment as input. We formalize a new set of computational problems which involve analyzing such complex models of evolution, investigate their computational complexity, and devise algorithms for solving them. Moreover, we demonstrate the viability of our methods on several synthetic datasets as well as biological datasets. [ABSTRACT FROM AUTHOR]

Selecting an informative subset of SNPs, generally referred to as tag SNPs, to genotype and analyze is considered to be an essential step toward effective disease association studies. However, while the selected informative tag SNPs may characterize the allele information of a target genomic region, they are not necessarily the ones directly associated with disease or with functional impairment. To address this limitation, we present a first integrative SNP selection system that simultaneously identifies SNPs that are both informative and carry a deleterious functional effect - which in turn means that they are likely to be directly associated with disease. We formulate the problem of selecting functionally informative tag SNPs as a multi-objective optimization problem and present a heuristic algorithm for addressing it. We also present the system we developed for assessing the functional significance of SNPs. To evaluate our system, we compare it to other state-of-the-art SNP selection systems, which conduct both information-based tag SNP selection and function-based SNP selection, but do so in two separate consecutive steps. Using 14 datasets, based on disease-related genes curated by the OMIM database, we show that our system consistently improves upon current systems. [ABSTRACT FROM AUTHOR]

Single nucleotide polymorphism (SNP) is the most frequent form of DNA variation. The set of SNPs present in a chromosome (called the haplotype) is of interest in a wide area of applications in molecular biology and biomedicine, including diagnostic and medical therapy. In this paper we propose a new heuristic method for the problem of haplotype reconstruction for (portions of ) a pair of homologous human chromosomes from a single individual (SIH). The problem is well known in literature and exact algorithms have been proposed for the case when no (or few) gaps are allowed in the input fragments. These algorithms, though exact and of polynomial complexity, are slow in practice. Therefore fast heuristics have been proposed. In this paper we describe a new heuristic method that is able to tackle the case of many gapped fragments and retains its effectiveness even when the input fragments have high rate of reading errors (up to 20%) and low coverage (as low as 3). We test our method on real data from the HapMap Project. [ABSTRACT FROM AUTHOR]

The within-species genetic variation due to recombinations leads to a mosaic-like structure of DNA. This structure can be modeled, e.g. by parsing sample sequences of current DNA with respect to a small number of founders. The founders represent the ancestral sequence material from which the sample was created in a sequence of recombination steps. This scenario has recently been successfully applied on developing probabilistic Hidden Markov Methods for haplotyping genotypic data. In this paper we introduce a combinatorial method for haplotyping that is based on a similar parsing idea. We formulate a polynomial-time parsing algorithm that finds minimum cross-over parse in a simplified ‘flat' parsing model that ignores the historical hierarchy of recombinations. The problem of constructing optimal founders that would give minimum possible parse for given genotypic sequences is shown NP-hard. A heuristic locally-optimal algorithm is given for founder construction. Combined with flat parsing this already gives quite good haplotyping results. Improved haplotyping is obtained by using a hierarchical parsing that properly models the natural recombination process. For finding short hierarchical parses a greedy polynomial-time algorithm is given. Empirical haplotyping results on HapMap data are reported. [ABSTRACT FROM AUTHOR]

In this paper we describe FT-COMAR an algorithm that improves fault tolerance of our heuristic algorithm (COMAR) previously described for protein reconstruction [10]. The algorithm [COMAR-Contact Map Reconstruction] can reconstruct the three-dimensional (3D) structure of the real protein from its contact map with 100% efficiency when tested on 1760 proteins from different structural classes. Here we test the performances of COMAR on native contact maps when a perturbation with random errors is introduced. This is done in order to simulate possible scenarios of reconstruction from predicted (and therefore highly noised) contact maps. From our analysis we obtain that our algorithm performs better reconstructions on blurred contact maps when contacts are under predicted than over predicted. Moreover we modify the algorithm into FT-COMAR [Fault Tolerant-COMAR] in order to use it with incomplete contact maps. FT-COMAR can ignore up to 75% of the contact map and still recover from the remaining 25% entries a 3D structure whose root mean square deviation (RMSD) from the native one is less then 4 Å. Our results indicate that the quality more than the quantity of predicted contacts is relevant to the protein 3D reconstruction and that some hints about "unsafe" areas in the predicted contact maps can be useful to improve reconstruction quality. For this, we implement a very simple filtering procedure to detect unsafe areas in contact maps and we show that by this and in the presences of errors the performance of the algorithm can be significantly improved. Furthermore, we show that both COMAR and FT-COMAR overcome a previous state-of-the-art algorithm for the same task [13]. [ABSTRACT FROM AUTHOR]

We propose kernels that take advantage of local correlations in sequential data and present their application to the protein classification problem. Our locality kernels measure protein sequence similarities within a small window constructed around matching amino acids. The kernels incorporate positional information of the amino acids inside the window and allow a range of position dependent similarity evaluations. We use these kernels with regularized least-squares algorithm (RLS) for protein classification on the SCOP database. Our experiments demonstrate that the locality kernels perform significantly better than the spectrum and the mismatch kernels. When used together with RLS, performance of the locality kernels is comparable with some state-of-the-art methods of protein classification and remote homology detection. [ABSTRACT FROM AUTHOR]

The topology of β-sheets is defined by the pattern of hydrogen-bonded strand pairing. Therefore, predicting hydrogen bonded strand partners is a fundamental step towards predicting β-sheet topology. In this work we report a new strand pairing algorithm. Our algorithm attempts to mimic elements of the folding process. Namely, in addition to ensuring that the predicted hydrogen bonded strand pairs satisfy basic global consistency constraints, it takes into account hypothetical folding pathways. Consistently with this view, introducing hydrogen bonds between a pair of strands changes the probabilities of forming other strand pairs. We demonstrate that this approach provides an improvement over previously proposed algorithms. [ABSTRACT FROM AUTHOR]

Sequence-derived structural and physicochemical features have been used to develop models for predicting protein families. Here, we test the hypothesis that high-level functional groups of proteins may be classified by a very small set of global features directly extracted from sequence alone. To test this, we represent each protein using a small number of normalized global sequence features and classify them into functional groups, using support vector machines (SVM). Furthermore, the contribution of specific subsets of features to the classification quality is thoroughly investigated. The representation of proteins using global features provides effective information for protein family classification, with comparable results to those obtained by representation using local sequence alignment scores. Furthermore, a combination of global and local sequence features significantly improves classification performance. [ABSTRACT FROM AUTHOR]

Transcriptional regulation critically depends on proper interactions between transcription factors (TF) and their cognate DNA binding sites or cis elements. A better understanding and modelling of the TF-DNA interaction is an important area of research. The Positional Weight Matrix (PWM) is the most common model of TF-DNA binding and it presumes that the nucleotide preferences at individual positions within the binding site are independent. However, studies have shown that this independence assumption does not always hold. If the nucleotide preference at one position depends on the nucleotide at another position, a chance mutation at one position should exert selection pressures at the other position. By comparing the patterns of evolutionary conservation at individual positions within cis elements, here we show that positional dependence within binding sites is highly prevalent. We also show that dependent positions are more likely to be functional, as evidenced by a higher information content and higher conservation. We discuss two examples—Elk-1 and SAP-1 where the inferred compensatory mutation is consistent with known TF-DNA crystal structure. [ABSTRACT FROM AUTHOR]

Transcriptional regulation is accomplished by several transcription factor proteins that bind to specific DNA elements in the relative vicinity of the gene, and interact with each other and with Polymerase enzyme. Thus the determination of transcription factor-DNA binding is an important step toward understanding transcriptional regulation. An effective way to experimentally determine the genomic regions bound by a transcription factor is by a ChIP-on-chip assay. Then, given the putative genomic regions, computational motif finding algorithms are applied to estimate the DNA binding motif or positional weight matrix for the TF. The a priori expectation is that the presence or absence of the estimated motif in a promoter should be a good indicator of the binding of the TF to that promoter. This association between the presence of the transcription factor motif and its binding is however weak in a majority of cases where the whole genome ChIP experiments have been performed. One possible reason for this is that the DNA binding of a particular transcription factor depends not only on its own motif, but also on synergistic or antagonistic action of neighboring motifs for other transcription factors. We believe that modeling this interaction-dependent binding with linear regression can better explain the observed binding data. We assess this hypothesis based on the whole genome ChIP-on-chip data for Yeast. The derived interactions are largely consistent with previous results that combine ChIP-on-chip data with expression data. We additionally apply our method to determine interacting partners for CREB and validate our findings based on published experimental results. [ABSTRACT FROM AUTHOR]

In the era of structural genomics, comparing a large number of protein structures can be a dauntingly time-consuming task. Traditional structural alignment methods, although offer accurate comparison, are not fast enough. Therefore, a number of databases storing pre-computed structural similarities are created to handle structural comparison queries efficiently. However, these databases cannot be updated in a timely fashion due to the sheer burden of computational requirements, thus offering only a rigid classification by some predefined parameters. Therefore, there is an increasingly urgent need for algorithms that can rapidly compare a large set of structures. Recently proposed projection methods, e.g., [1,2,3,4,5], show good promise for the development of fast structural database search solutions. Projection methods map a structure into a point in a high dimensional space and compare two structures by measuring distance between their projected points. These methods offer a tremendous increase in speed over residue-level structural alignment methods. However, current projection methods are not practical, partly because they are unable to identify local similarities. We propose a new projection-based approach that can rapidly detect global as well as local structural similarities. Local structural search is enabled by a topology-based writhe decomposition protocol (inspired by [4]) that produces a small number of fragments while ensuring that similar structures are cut in a similar manner. In a benchmark test for local structural similarity detection, we show that our method, Writher, dramatically improves accuracy over current leading projection methods [4,5] in terms of recognizing SCOP domains out of multidomain proteins. [ABSTRACT FROM AUTHOR]

A central challenge in biomedical research remains identification of genetic factors influencing human behavior and susceptibility to common disease. Recent advances in genotyping technologies, coupled with the fundamental information provided by the Human Genome and International HapMap Projects, permit characterization and analysis of high-density SNP genotype data for thousands of individuals. Using genotype data obtained on the Illumina HumanHap550 SNP platform, for 1000 individuals (in 170 autism multiplex families from Autism Genetic Resource Exchange, 120 HapMap samples and 320 neurologically normal children from Children's Hospital of Philadelphia) we performed a pilot study to identify genetics risk factors for autism susceptibility. Using these data we illustrate that novel statistical and computational biology approaches provide additional insights than can not be observed when using simple association tests. These novel approaches include: a) phylogenetic analysis of population structure; b) pathway-based analysis of genome-wide association data c) selection of variants based on a priori potential to affect phenotypes and d) analysis of copy number variation (CNVs) in autistic and healthy (control) children. In addition, our results demonstrate that high-density SNP genotyping array can be used to detect copy number variants (CNV) at an unprecedentedly high resolution and that regions with a high density of CNVs in many cases correspond to syntenic breakpoints, providing further support for the importance of evolutionary analysis of structural variation to disease and disease susceptibility. This is a joint work with Junhyong Kim (Penn), Mingyao Li (Penn) and Hakon Hakonarson (CHOP). [ABSTRACT FROM AUTHOR]

Despite significant advances in the identification of known proteins, the analysis of unknown proteins by tandem mass spectrometry (MS/MS) still remains a challenging open problem. Although Klaus Biemann recognized the potential of mass spectrometry for sequencing of unknown proteins in the 1980s, low-throughput Edman degradation followed by cloning still remains the main method to sequence unknown proteins. The automated spectral interpretation has been limited by a focus on individual spectra and has not capitalized on the information contained in spectra of overlapping peptides. Indeed, the powerful Shotgun DNA Sequencing strategies have not been extended to protein sequencing yet.We demonstrate, for the first time, the feasibility of Shotgun Protein Sequencing of protein mixtures and validate this approach by generating highly accurate de novo reconstructions of various proteins in western diamondback rattlesnake venom. We further argue that Shotgun Protein Sequencing has the potential to overcome the limitations of current protein sequencing approaches and thus catalyze the otherwise impractical applications of proteomics methodologies in studies of unknown proteins. We further describe applications of this technique to analyzing proteins that are not directly inscribed in DNA sequences (like antibodies and fusion proteins in cancer). This is a joint work with Nuno Bandeira (UCSD) and Karl Clauser (Broad). [ABSTRACT FROM AUTHOR]