NetworkTrail--a web service for identifying and visualizing deregulated subnetworks.

UNLABELLED: The deregulation of biochemical pathways plays a central role in many diseases like cancer or Parkinsons's disease. In silico tools for calculating these deregulated pathways may help to gain new insights into pathogenic mechanisms and may open novel avenues for therapy stratification in the sense of personalized medicine. Here, we present NetworkTrail, a web service for the detection of deregulated pathways and subgraphs in biological networks. NetworkTrail uses a state-of-the-art integer linear programming-based approach for this task and offers interfaces to the Biological Network Analyzer (BiNA) and Cytoscape Web for visualizing the resulting subnetworks. By providing an accessible interface to otherwise hard-to-use command line tools, the new web service enables non-experts to quickly and reliably carry out this type of network analyses. AVAILABILITY AND IMPLEMENTATION: NetworkTrail is a JavaServer Pages-based web service. The algorithm for finding deregulated subnetworks has been implemented in C++. NetworkTrail is available at http://networktrail.bioinf.uni-sb.de/.

An integer linear programming approach for finding deregulated subgraphs in regulatory networks.

Deregulation of cell signaling pathways plays a crucial role in the development of tumors. The identification of such pathways requires effective analysis tools that facilitate the interpretation of expression differences. Here, we present a novel and highly efficient method for identifying deregulated subnetworks in a regulatory network. Given a score for each node that measures the degree of deregulation of the corresponding gene or protein, the algorithm computes the heaviest connected subnetwork of a specified size reachable from a designated root node. This root node can be interpreted as a molecular key player responsible for the observed deregulation. To demonstrate the potential of our approach, we analyzed three gene expression data sets. In one scenario, we compared expression profiles of non-malignant primary mammary epithelial cells derived from BRCA1 mutation carriers and of epithelial cells without BRCA1 mutation. Our results suggest that oxidative stress plays an important role in epithelial cells of BRCA1 mutation carriers and that the activation of stress proteins may result in avoidance of apoptosis leading to an increased overall survival of cells with genetic alterations. In summary, our approach opens new avenues for the elucidation of pathogenic mechanisms and for the detection of molecular key players.

Automated bond order assignment as an optimization problem.

MOTIVATION: Numerous applications in Computational Biology process molecular structures and hence strongly rely not only on correct atomic coordinates but also on correct bond order information. For proteins and nucleic acids, bond orders can be easily deduced but this does not hold for other types of molecules like ligands. For ligands, bond order information is not always provided in molecular databases and thus a variety of approaches tackling this problem have been developed. In this work, we extend an ansatz proposed by Wang et al. that assigns connectivity-based penalty scores and tries to heuristically approximate its optimum. In this work, we present three efficient and exact solvers for the problem replacing the heuristic approximation scheme of the original approach: an A*, an ILP and an fixed-parameter approach (FPT) approach. RESULTS: We implemented and evaluated the original implementation, our A*, ILP and FPT formulation on the MMFF94 validation suite and the KEGG Drug database. We show the benefit of computing exact solutions of the penalty minimization problem and the additional gain when computing all optimal (or even suboptimal) solutions. We close with a detailed comparison of our methods. AVAILABILITY: The A* and ILP solution are integrated into the open-source C++ LGPL library BALL and the molecular visualization and modelling tool BALLView and can be downloaded from our homepage www.ball-project.org. The FPT implementation can be downloaded from http://bio.informatik.uni-jena.de/software/.

BALL--biochemical algorithms library 1.3.

BACKGROUND: The Biochemical Algorithms Library (BALL) is a comprehensive rapid application development framework for structural bioinformatics. It provides an extensive C++ class library of data structures and algorithms for molecular modeling and structural bioinformatics. Using BALL as a programming toolbox does not only allow to greatly reduce application development times but also helps in ensuring stability and correctness by avoiding the error-prone reimplementation of complex algorithms and replacing them with calls into the library that has been well-tested by a large number of developers. In the ten years since its original publication, BALL has seen a substantial increase in functionality and numerous other improvements. RESULTS: Here, we discuss BALL's current functionality and highlight the key additions and improvements: support for additional file formats, molecular edit-functionality, new molecular mechanics force fields, novel energy minimization techniques, docking algorithms, and support for cheminformatics. CONCLUSIONS: BALL is available for all major operating systems, including Linux, Windows, and MacOS X. It is available free of charge under the Lesser GNU Public License (LPGL). Parts of the code are distributed under the GNU Public License (GPL). BALL is available as source code and binary packages from the project web site at http://www.ball-project.org. Recently, it has been accepted into the debian project; integration into further distributions is currently pursued.

A new Lamarckian genetic algorithm for flexible ligand-receptor docking.

We present a Lamarckian genetic algorithm (LGA) variant for flexible ligand-receptor docking which allows to handle a large number of degrees of freedom. Our hybrid method combines a multi-deme LGA with a recently published gradient-based method for local optimization of molecular complexes. We compared the performance of our new hybrid method to two non gradient-based search heuristics on the Astex diverse set for flexible ligand-receptor docking. Our results show that the novel approach is clearly superior to other LGAs employing a stochastic optimization method. The new algorithm features a shorter run time and gives substantially better results, especially with increasing complexity of the ligands. Thus, it may be used to dock ligands with many rotatable bonds with high efficiency.

A consensus line search algorithm for molecular potential energy functions.

Force field based energy minimization of molecular structures is a central task in computational chemistry and biology. Solving this problem usually requires efficient local minimization techniques, i.e., iterative two-step methods that search first for a descent direction and then try to estimate the step width. The second step, the so called line search, typically uses polynomial interpolation schemes to estimate the next trial step. However, dependent on local properties of the objective function alternative schemes may be more appropriate especially if the objective function shows singularities or exponential behavior. As the choice of the best interpolation scheme cannot be made a priori, we propose a new consensus line search approach that performs several different interpolation schemes at each step and then decides which one is the most reliable at the current position. Although a naive consensus approach would lead to severe performance impacts, our method does not require additional evaluations of the energy function, imposing only negligible computational overhead. Additionally, our method can be easily adapted to the local behavior of other objective functions by incorporating suitable interpolation schemes or omitting non-fitting schemes. The performance of our consensus line search approach has been evaluated and compared to established standard line search algorithms by minimizing the structures of a large set of molecules using different force fields. The proposed algorithm shows better performance in almost all test cases, i.e., it reduces the number of iterations and function and gradient evaluations, leading to significantly reduced run times.

A new method for the gradient-based optimization of molecular complexes.

We present a novel method for the local optimization of molecular complexes. This new approach is especially suited for usage in molecular docking. In molecular modeling, molecules are often described employing a compact representation to reduce the number of degrees of freedom. This compact representation is realized by fixing bond lengths and angles while permitting changes in translation, orientation, and selected dihedral angles. Gradient-based energy minimization of molecular complexes using this representation suffers from well-known singularities arising during the optimization process. We suggest an approach new in the field of structure optimization that allows to employ gradient-based optimization algorithms for such a compact representation. We propose to use exponential mapping to define the molecular orientation which facilitates calculating the orientational gradient. To avoid singularities of this parametrization, the local minimization algorithm is modified to change efficiently the orientational parameters while preserving the molecular orientation, i.e. we perform well-defined jumps on the objective function. Our approach is applicable to continuous, but not necessarily differentiable objective functions. We evaluated our new method by optimizing several ligands with an increasing number of internal degrees of freedom in the presence of large receptors. In comparison to the method of Solis and Wets in the challenging case of a non-differentiable scoring function, our proposed method leads to substantially improved results in all test cases, i.e. we obtain better scores in fewer steps for all complexes.

Proteomic and Lipidomic Analysis of Nanoparticle Corona upon Contact with Lung Surfactant Reveals Differences in Protein, but Not Lipid Composition.

Pulmonary surfactant (PS) constitutes the first line of host defense in the deep lung. Because of its high content of phospholipids and surfactant specific proteins, the interaction of inhaled nanoparticles (NPs) with the pulmonary surfactant layer is likely to form a corona that is different to the one formed in plasma. Here we present a detailed lipidomic and proteomic analysis of NP corona formation using native porcine surfactant as a model. We analyzed the adsorbed biomolecules in the corona of three NP with different surface properties (PEG-, PLGA-, and Lipid-NP) after incubation with native porcine surfactant. Using label-free shotgun analysis for protein and LC-MS for lipid analysis, we quantitatively determined the corona composition. Our results show a conserved lipid composition in the coronas of all investigated NPs regardless of their surface properties, with only hydrophilic PEG-NPs adsorbing fewer lipids in total. In contrast, the analyzed NP displayed a marked difference in the protein corona, consisting of up to 417 different proteins. Among the proteins showing significant differences between the NP coronas, there was a striking prevalence of molecules with a notoriously high lipid and surface binding, such as, e.g., SP-A, SP-D, DMBT1. Our data indicate that the selective adsorption of proteins mediates the relatively similar lipid pattern in the coronas of different NPs. On the basis of our lipidomic and proteomic analysis, we provide a detailed set of quantitative data on the composition of the surfactant corona formed upon NP inhalation, which is unique and markedly different to the plasma corona.