| 1. |
- Dubrova, Elena, et al.
(författare)
-
A SAT-Based Algorithm for Finding Attractors in Synchronous Boolean Networks
- 2011
-
Ingår i: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - 1545-5963 .- 1557-9964. ; 8:5, s. 1393-1399
-
Tidskriftsartikel (refereegranskat)abstract
- This paper addresses the problem of finding attractors in synchronous Boolean networks. The existing Boolean decision diagram-based algorithms have limited capacity due to the excessive memory requirements of decision diagrams. The simulation-based algorithms can be applied to larger networks, however, they are incomplete. We present an algorithm, which uses a SAT-based bounded model checking to find all attractors in a Boolean network. The efficiency of the presented algorithm is evaluated by analyzing seven networks models of real biological processes, as well as 150,000 randomly generated Boolean networks of sizes between 100 and 7,000. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.
|
|
| 2. |
- Flores, Samuel Coulbourn, et al.
(författare)
-
Fast Flexible Modeling of RNA Structure Using Internal Coordinates
- 2011
-
Ingår i: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - 1545-5963 .- 1557-9964. ; 8:5, s. 1247-1257
-
Tidskriftsartikel (refereegranskat)abstract
- Modeling the structure and dynamics of large macromolecules remains a critical challenge. Molecular dynamics (MD) simulations are expensive because they model every atom independently, and are difficult to combine with experimentally derived knowledge. Assembly of molecules using fragments from libraries relies on the database of known structures and thus may not work for novel motifs. Coarse-grained modeling methods have yielded good results on large molecules but can suffer from difficulties in creating more detailed full atomic realizations. There is therefore a need for molecular modeling algorithms that remain chemically accurate and economical for large molecules, do not rely on fragment libraries, and can incorporate experimental information. RNABuilder works in the internal coordinate space of dihedral angles and thus has time requirements proportional to the number of moving parts rather than the number of atoms. It provides accurate physics-based response to applied forces, but also allows user-specified forces for incorporating experimental information. A particular strength of RNABuilder is that all Leontis-Westhof basepairs can be specified as primitives by the user to be satisfied during model construction. We apply RNABuilder to predict the structure of an RNA molecule with 160 bases from its secondary structure, as well as experimental information. Our model matches the known structure to 10.2 Angstroms RMSD and has low computational expense.
|
|
| 3. |
- Rübel, Oliver, et al.
(författare)
-
Integrating data clustering and visualization for the analysis of 3D gene expression data
- 2010
-
Ingår i: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - 1545-5963 .- 1557-9964. ; 7:1, s. 64-79
-
Tidskriftsartikel (refereegranskat)abstract
- The recent development of methods for extracting precise measurements of spatial gene expression patterns from three-dimensional (3D) image data opens the way for new analyses of the complex gene regulatory networks controlling animal development. We present an integrated visualization and analysis framework that supports user-guided data clustering to aid exploration of these new complex data sets. The interplay of data visualization and clustering-based data classification leads to improved visualization and enables a more detailed analysis than previously possible. We discuss 1) the integration of data clustering and visualization into one framework, 2) the application of data clustering to 3D gene expression data, 3) the evaluation of the number of clusters k in the context of 3D gene expression clustering, and 4) the improvement of overall analysis quality via dedicated postprocessing of clustering results based on visualization. We discuss the use of this framework to objectively define spatial pattern boundaries and temporal profiles of genes and to analyze how mRNA patterns are controlled by their regulatory transcription factors.
|
|
| 4. |
- Tofigh, Ali, et al.
(författare)
-
Simultaneous Identification of Duplications and Lateral Gene Transfers
- 2011
-
Ingår i: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - 1545-5963 .- 1557-9964. ; 8:2, s. 517-535
-
Tidskriftsartikel (refereegranskat)abstract
- The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where a so-called DTL-scenario is used to explain the differences between a gene tree anda corresponding species tree taking into account gene duplications, gene losses, and lateral genetransfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateralgene transfer may only occur between contemporary species leads to the notion of acyclic DTLscenarios.Parsimony methods are introduced by defining appropriate optimization problems. Weshow that finding most parsimonious acyclic DTL-scenarios is NP-complete. However, by droppingthe condition of acyclicity, the problem becomes tractable, and we provide a dynamic programmingalgorithm as well as a fixed-parameter-tractable algorithm for finding most parsimonious DTLscenarios.
|
|
| 5. |
- Hafemeister, Christoph, et al.
(författare)
-
Selecting oligonucleotide probes for whole-genome tiling arrays with a cross-hybridization potential.
- 2011
-
Ingår i: IEEE/ACM transactions on computational biology and bioinformatics. - 1557-9964. ; 8:6, s. 1642-52
-
Tidskriftsartikel (refereegranskat)abstract
- For designing oligonucleotide tiling arrays popular, current methods still rely on simple criteria like Hamming distance or longest common factors, neglecting base stacking effects which strongly contribute to binding energies. Consequently, probes are often prone to cross-hybridization which reduces the signal-to-noise ratio and complicates downstream analysis. We propose the first computationally efficient method using hybridization energy to identify specific oligonucleotide probes. Our Cross-Hybridization Potential (CHP) is computed with a Nearest Neighbor Alignment, which efficiently estimates a lower bound for the Gibbs free energy of the duplex formed by two DNA sequences of bounded length. It is derived from our simplified reformulation of t-gap insertion-deletion-like metrics. The computations are accelerated by a filter using weighted ungapped q-grams to arrive at seeds. The computation of the CHP is implemented in our software OSProbes, available under the GPL, which computes sets of viable probe candidates. The user can choose a trade-off between running time and quality of probes selected. We obtain very favorable results in comparison with prior approaches with respect to specificity and sensitivity for cross-hybridization and genome coverage with high-specificity probes. The combination of OSProbes and our Tileomatic method, which computes optimal tiling paths from candidate sets, yields globally optimal tiling arrays, balancing probe distance, hybridization conditions, and uniqueness of hybridization.
|
|
| 6. |
- You, Liwen, et al.
(författare)
-
Using gaussian process with test rejection to detect T-cell epitopes in pathogen genomes.
- 2010
-
Ingår i: IEEE/ACM Transactions on Computational Biology & Bioinformatics. - 1557-9964. ; 7:4, s. 741-751
-
Tidskriftsartikel (refereegranskat)abstract
- A major challenge in the development of peptide-based vaccines is finding the right immunogenic element, with efficient and long-lasting immunization effects, from large potential targets encoded by pathogen genomes. Computer models are convenient tools for scanning pathogen genomes to preselect candidate immunogenic peptides for experimental validation. Current methods predict many false positives resulting from a low prevalence of true positives. We develop a test reject method based on the prediction uncertainty estimates determined by Gaussian process regression. This method filters false positives among predicted epitopes from a pathogen genome. The performance of stand-alone Gaussian process regression is compared to other state-of-the-art methods using cross validation on 11 benchmark data sets. The results show that the Gaussian process method has the same accuracy as the top performing algorithms. The combination of Gaussian process regression with the proposed test reject method is used to detect true epitopes from the Vaccinia virus genome. The test rejection increases the prediction accuracy by reducing the number of false positives without sacrificing the method's sensitivity. We show that the Gaussian process in combination with test rejection is an effective method for prediction of T-cell epitopes in large and diverse pathogen genomes, where false positives are of concern.
|
|
