A safety framework for flow decomposition problems via integer linear programming.

MOTIVATION: Many important problems in Bioinformatics (e.g. assembly or multiassembly) admit multiple solutions, while the final objective is to report only one. A common approach to deal with this uncertainty is finding "safe" partial solutions (e.g. contigs) which are common to all solutions. Previous research on safety has focused on polynomially time solvable problems, whereas many successful and natural models are NP-hard to solve, leaving a lack of "safety tools" for such problems. We propose the first method for computing all safe solutions for an NP-hard problem, "minimum flow decomposition" (MFD). We obtain our results by developing a "safety test" for paths based on a general integer linear programming (ILP) formulation. Moreover, we provide implementations with practical optimizations aimed to reduce the total ILP time, the most efficient of these being based on a recursive group-testing procedure. RESULTS: Experimental results on transcriptome datasets show that all safe paths for MFDs correctly recover up to 90% of the full RNA transcripts, which is at least 25% more than previously known safe paths. Moreover, despite the NP-hardness of the problem, we can report all safe paths for 99.8% of the over 27 000 non-trivial graphs of this dataset in only 1.5 h. Our results suggest that, on perfect data, there is less ambiguity than thought in the notoriously hard RNA assembly problem. AVAILABILITY AND IMPLEMENTATION: https://github.com/algbio/mfd-safety.

Search for a Shared Genetic or Biochemical Basis for Biofilm Tolerance to Antibiotics across Bacterial Species.

Is there a universal genetically programmed defense providing tolerance to antibiotics when bacteria grow as biofilms? A comparison between biofilms of three different bacterial species by transcriptomic and metabolomic approaches uncovered no evidence of one. Single-species biofilms of three bacterial species (Pseudomonas aeruginosa, Staphylococcus aureus, and Acinetobacter baumannii) were grown in vitro for 3 days and then challenged with respective antibiotics (ciprofloxacin, daptomycin, and tigecycline) for an additional 24 h. All three microorganisms displayed reduced susceptibility in biofilms compared to planktonic cultures. Global transcriptomic profiling of gene expression comparing biofilm to planktonic and antibiotic-treated biofilm to untreated biofilm was performed. Extracellular metabolites were measured to characterize the utilization of carbon sources between biofilms, treated biofilms, and planktonic cells. While all three bacteria exhibited a species-specific signature of stationary phase, no conserved gene, gene set, or common functional pathway could be identified that changed consistently across the three microorganisms. Across the three species, glucose consumption was increased in biofilms compared to planktonic cells, and alanine and aspartic acid utilization were decreased in biofilms compared to planktonic cells. The reasons for these changes were not readily apparent in the transcriptomes. No common shift in the utilization pattern of carbon sources was discerned when comparing untreated to antibiotic-exposed biofilms. Overall, our measurements do not support the existence of a common genetic or biochemical basis for biofilm tolerance against antibiotics. Rather, there are likely myriad genes, proteins, and metabolic pathways that influence the physiological state of individual microorganisms in biofilms and contribute to antibiotic tolerance.

Hijacking a rapid and scalable metagenomic method reveals subgenome dynamics and evolution in polyploid plants.

Premise: The genomes of polyploid plants archive the evolutionary events leading to their present forms. However, plant polyploid genomes present numerous hurdles to the genome comparison algorithms for classification of polyploid types and exploring genome dynamics. Methods: Here, the problem of intra- and inter-genome comparison for examining polyploid genomes is reframed as a metagenomic problem, enabling the use of the rapid and scalable MinHashing approach. To determine how types of polyploidy are described by this metagenomic approach, plant genomes were examined from across the polyploid spectrum for both k-mer composition and frequency with a range of k-mer sizes. In this approach, no subgenome-specific k-mers are identified; rather, whole-chromosome k-mer subspaces were utilized. Results: Given chromosome-scale genome assemblies with sufficient subgenome-specific repetitive element content, literature-verified subgenomic and genomic evolutionary relationships were revealed, including distinguishing auto- from allopolyploidy and putative progenitor genome assignment. The sequences responsible were the rapidly evolving landscape of transposable elements. An investigation into the MinHashing parameters revealed that the downsampled k-mer space (genomic signatures) produced excellent approximations of sequence similarity. Furthermore, the clustering approach used for comparison of the genomic signatures is scrutinized to ensure applicability of the metagenomics-based method. Discussion: The easily implementable and highly computationally efficient MinHashing-based sequence comparison strategy enables comparative subgenomics and genomics for large and complex polyploid plant genomes. Such comparisons provide evidence for polyploidy-type subgenomic assignments. In cases where subgenome-specific repeat signal may not be adequate given a chromosomes' global k-mer profile, alternative methods that are more specific but more computationally complex outperform this approach.

Antigen-antibody interface properties: composition, residue interactions, and features of 53 non-redundant structures.

The structures of protein antigen-antibody (Ag-Ab) interfaces contain information about how Ab recognize Ag as well as how Ag are folded to present surfaces for Ag recognition. As such, the Ab surface holds information about Ag folding that resides with the Ab-Ag interface residues and how they interact. In order to gain insight into the nature of such interactions, a data set comprised of 53 non-redundant 3D structures of Ag-Ab complexes was analyzed. We assessed the physical and biochemical features of the Ag-Ab interfaces and the degree to which favored interactions exist between amino acid residues on the corresponding interface surfaces. Amino acid compositional analysis of the interfaces confirmed the dominance of TYR in the Ab paratope-containing surface (PCS), with almost two fold greater abundance than any other residue. Additionally TYR had a much higher than expected presence in the PCS compared to the surface of the whole antibody (defined as the occurrence propensity), along with aromatics PHE, TRP, and to a lesser degree HIS and ILE. In the Ag epitope-containing surface (ECS), there were slightly increased occurrence propensities of TRP and TYR relative to the whole Ag surface, implying an increased significance over the compositionally most abundant LYS>ASN>GLU>ASP>ARG. This examination encompasses a large, diverse set of unique Ag-Ab crystal structures that help explain the biological range and specificity of Ag-Ab interactions. This analysis may also provide a measure of the significance of individual amino acid residues in phage display analysis of Ag binding.

Flow Decomposition With Subpath Constraints.

Flow network decomposition is a natural model for problems where we are given a flow network arising from superimposing a set of weighted paths and would like to recover the underlying data, i.e., decompose the flow into the original paths and their weights. Thus, variations on flow decomposition are often used as subroutines in multiassembly problems such as RNA transcript assembly. In practice, we frequently have access to information beyond flow values in the form of subpaths, and many tools incorporate these heuristically. But despite acknowledging their utility in practice, previous work has not formally addressed the effect of subpath constraints on the accuracy of flow network decomposition approaches. We formalize the flow decomposition with subpath constraints problem, give the first algorithms for it, and study its usefulness for recovering ground truth decompositions. For finding a minimum decomposition, we propose both a heuristic and an FPT algorithm. Experiments on RNA transcript datasets show that for instances with larger solution path sets, the addition of subpath constraints finds 13% more ground truth solutions when minimal decompositions are found exactly, and 30% more ground truth solutions when minimal decompositions are found heuristically.

Efficient Minimum Flow Decomposition via Integer Linear Programming.

Minimum flow decomposition (MFD) is an NP-hard problem asking to decompose a network flow into a minimum set of paths (together with associated weights). Variants of it are powerful models in multiassembly problems in Bioinformatics, such as RNA assembly. Owing to its hardness, practical multiassembly tools either use heuristics or solve simpler, polynomial time-solvable versions of the problem, which may yield solutions that are not minimal or do not perfectly decompose the flow. Here, we provide the first fast and exact solver for MFD on acyclic flow networks, based on Integer Linear Programming (ILP). Key to our approach is an encoding of all the exponentially many solution paths using only a quadratic number of variables. We also extend our ILP formulation to many practical variants, such as incorporating longer or paired-end reads, or minimizing flow errors. On both simulated and real-flow splicing graphs, our approach solves any instance in <13 seconds. We hope that our formulations can lie at the core of future practical RNA assembly tools. Our implementations are freely available on Github.

Safety in Multi-Assembly via Paths Appearing in All Path Covers of a DAG.

A multi-assembly problem asks to reconstruct multiple genomic sequences from mixed reads sequenced from all of them. Standard formulations of such problems model a solution as a path cover in a directed acyclic graph, namely a set of paths that together cover all vertices of the graph. Since multi-assembly problems admit multiple solutions in practice, we consider an approach commonly used in standard genome assembly: output only partial solutions (contigs, or safe paths), that appear in all path cover solutions. We study constrained path covers, a restriction on the path cover solution that incorporate practical constraints arising in multi-assembly problems. We give efficient algorithms finding all maximal safe paths for constrained path covers. We compute the safe paths of splicing graphs constructed from transcript annotations of different species. Our algorithms run in less than 15 seconds per species and report RNA contigs that are over 99% precise and are up to 8 times longer than unitigs. Moreover, RNA contigs cover over 70% of the transcripts and their coding sequences in most cases. With their increased length to unitigs, high precision, and fast construction time, maximal safe paths can provide a better base set of sequences for transcript assembly programs.

Genetic dissection of natural variation in oilseed traits of camelina by whole-genome resequencing and QTL mapping.

Camelina [Camelina sativa (L.) Crantz] is an oilseed crop in the Brassicaceae family that is currently being developed as a source of bioenergy and healthy fatty acids. To facilitate modern breeding efforts through marker-assisted selection and biotechnology, we evaluated genetic variation among a worldwide collection of 222 camelina accessions. We performed whole-genome resequencing to obtain single nucleotide polymorphism (SNP) markers and to analyze genomic diversity. We also conducted phenotypic field evaluations in two consecutive seasons for variations in key agronomic traits related to oilseed production such as seed size, oil content (OC), fatty acid composition, and flowering time. We determined the population structure of the camelina accessions using 161,301 SNPs. Further, we identified quantitative trait loci (QTL) and candidate genes controlling the above field-evaluated traits by genome-wide association studies (GWAS) complemented with linkage mapping using a recombinant inbred line (RIL) population. Characterization of the natural variation at the genome and phenotypic levels provides valuable resources to camelina genetic studies and crop improvement. The QTL and candidate genes should assist in breeding of advanced camelina varieties that can be integrated into the cropping systems for the production of high yield of oils of desired fatty acid composition.

Maximal Perfect Haplotype Blocks with Wildcards.

Recent work provides the first method to measure the relative fitness of genomic variants within a population that scales to large numbers of genomes. A key component of the computation involves finding maximal perfect haplotype blocks from a set of genomic samples for which SNPs (single-nucleotide polymorphisms) have been called. Often, owing to low read coverage and imperfect assemblies, some of the SNP calls can be missing from some of the samples. In this work, we consider the problem of finding maximal perfect haplotype blocks where some missing values may be present. Missing values are treated as wildcards, and the definition of maximal perfect haplotype blocks is extended in a natural way. We provide an output-linear time algorithm to identify all such blocks and demonstrate the algorithm on a large population SNP dataset. Our software is publicly available.

Exploring Frequented Regions in Pan-Genomic Graphs.

We consider the problem of identifying regions within a pan-genome De Bruijn graph that are traversed by many sequence paths. We define such regions and the subpaths that traverse them as frequented regions (FRs). In this work, we formalize the FR problem and describe an efficient algorithm for finding FRs. Subsequently, we propose some applications of FRs based on machine-learning and pan-genome graph simplification. We demonstrate the effectiveness of these applications using data sets for the organisms Staphylococcus aureus (bacterium) and Saccharomyces cerevisiae (yeast). We corroborate the biological relevance of FRs such as identifying introgressions in yeast that aid in alcohol tolerance, and show that FRs are useful for classification of yeast strains by industrial use and visualizing pan-genomic space.

Physiological dynamic compression regulates central energy metabolism in primary human chondrocytes.

Chondrocytes use the pathways of central metabolism to synthesize molecular building blocks and energy for cartilage homeostasis. An interesting feature of the in vivo chondrocyte environment is the cyclical loading generated in various activities (e.g., walking). However, it is unknown whether central metabolism is altered by mechanical loading. We hypothesized that physiological dynamic compression alters central metabolism in chondrocytes to promote production of amino acid precursors for matrix synthesis. We measured the expression of central metabolites (e.g., glucose, its derivatives, and relevant co-factors) for primary human osteoarthritic chondrocytes in response to 0-30 minutes of compression. To analyze the data, we used principal components analysis and ANOVA-simultaneous components analysis, as well as metabolic flux analysis. Compression-induced metabolic responses consistent with our hypothesis. Additionally, these data show that chondrocyte samples from different patient donors exhibit different sensitivity to compression. Most importantly, we find that grade IV osteoarthritic chondrocytes are capable of synthesizing non-essential amino acids and precursors in response to mechanical loading. These results suggest that further advances in metabolic engineering of chondrocyte mechanotransduction may yield novel translational strategies for cartilage repair.

Combining Targeted Metabolomic Data with a Model of Glucose Metabolism: Toward Progress in Chondrocyte Mechanotransduction.

Osteoarthritis is a debilitating disease likely involving altered metabolism of the chondrocytes in articular cartilage. Chondrocytes can respond metabolically to mechanical loads via cellular mechanotransduction, and metabolic changes are significant because they produce the precursors to the tissue matrix necessary for cartilage health. However, a comprehensive understanding of how energy metabolism changes with loading remains elusive. To improve our understanding of chondrocyte mechanotransduction, we developed a computational model to calculate the rate of reactions (i.e. flux) across multiple components of central energy metabolism based on experimental data. We calculated average reaction flux profiles of central metabolism for SW1353 human chondrocytes subjected to dynamic compression for 30 minutes. The profiles were obtained solving a bounded variable linear least squares problem, representing the stoichiometry of human central energy metabolism. Compression synchronized chondrocyte energy metabolism. These data are consistent with dynamic compression inducing early time changes in central energy metabolism geared towards more active protein synthesis. Furthermore, this analysis demonstrates the utility of combining targeted metabolomic data with a computational model to enable rapid analysis of cellular energy utilization.

Constraints on the conformation of the cytoplasmic face of dark-adapted and light-excited rhodopsin inferred from antirhodopsin antibody imprints.

Rhodopsin is the best-understood member of the large G protein-coupled receptor (GPCR) superfamily. The G-protein amplification cascade is triggered by poorly understood light-induced conformational changes in rhodopsin that are homologous to changes caused by agonists in other GPCRs. We have applied the "antibody imprint" method to light-activated rhodopsin in native membranes by using nine monoclonal antibodies (mAbs) against aqueous faces of rhodopsin. Epitopes recognized by these mAbs were found by selection from random peptide libraries displayed on phage. A new computer algorithm, FINDMAP, was used to map the epitopes to discontinuous segments of rhodopsin that are distant in the primary sequence but are in close spatial proximity in the structure. The proximity of a segment of the N-terminal and the loop between helices VI and VIII found by FINDMAP is consistent with the X-ray structure of the dark-adapted rhodopsin. Epitopes to the cytoplasmic face segregated into two classes with different predicted spatial proximities of protein segments that correlate with different preferences of the antibodies for stabilizing the metarhodopsin I or metarhodopsin II conformations of light-excited rhodopsin. Epitopes of antibodies that stabilize metarhodopsin II indicate conformational changes from dark-adapted rhodopsin, including rearrangements of the C-terminal tail and altered exposure of the cytoplasmic end of helix VI, a portion of the C-3 loop, and helix VIII. As additional antibodies are subjected to antibody imprinting, this approach should provide increasingly detailed information on the conformation of light-excited rhodopsin and be applicable to structural studies of other challenging protein targets.

A new method for mapping discontinuous antibody epitopes to reveal structural features of proteins.

Antibodies that bind to protein surfaces of interest can be used to report the three-dimensional structure of the protein as follows: Proteins are composed of linear polypeptide chains that fold together in complex spatial patterns to create the native protein structure. These folded structures form binding sites for antibodies. Antibody binding sites are typically "assembled" on the protein surface from segments that are far apart in the primary amino acid sequence of the target proteins. Short amino acid probe sequences that bind to the active region of each antibody can be used as witnesses to the antibody epitope surface and these probes can be efficiently selected from random sequence peptide libraries. This paper presents a new method to align these antibody epitopes to discontinuous regions of the one-dimensional amino acid sequence of a target protein. Such alignments of the epitopes indicate how segments of the protein sequence must be folded together in space and thus provide long-range constraints for solving the 3-D protein structure. This new antibody-based approach is applicable to the large fraction of proteins that are refractory to current approaches for structure determination and has the additional advantage of requiring very small amounts of the target protein. The binding site of an antibody is a surface, not just a continuous linear sequence, so the epitope mapping alignment problem is outside the scope of classical string alignment algorithms, such as Smith-Waterman. We formalize the alignment problem that is at the heart of this new approach, prove that the epitope mapping alignment problem is NP-complete, and give some initial results using a branch-and-bound algorithm to map two real-life cases. Initial results for two validation cases are presented for a graph-based protein surface neighbor mapping procedure that promises to provide additional spatial proximity information for the amino acid residues on the protein surface.

C-terminal tail phosphorylation of N-formyl peptide receptor: differential recognition of two neutrophil chemoattractant receptors by monoclonal antibodies NFPR1 and NFPR2.

The N-formyl peptide receptor (FPR), a G protein-coupled receptor that binds proinflammatory chemoattractant peptides, serves as a model receptor for leukocyte chemotaxis. Recombinant histidine-tagged FPR (rHis-FPR) was purified in lysophosphatidyl glycerol (LPG) by Ni(2+)-NTA agarose chromatography to >95% purity with high yield. MALDI-TOF mass analysis (>36% sequence coverage) and immunoblotting confirmed the identity as FPR. The rHis-FPR served as an immunogen for the production of 2 mAbs, NFPR1 and NFPR2, that epitope map to the FPR C-terminal tail sequences, 305-GQDFRERLI-313 and 337-NSTLPSAEVE-346, respectively. Both mAbs specifically immunoblotted rHis-FPR and recombinant FPR (rFPR) expressed in Chinese hamster ovary cells. NFPR1 also recognized recombinant FPRL1, specifically expressed in mouse L fibroblasts. In human neutrophil membranes, both Abs labeled a 45-75 kDa species (peak M(r) approximately 60 kDa) localized primarily in the plasma membrane with a minor component in the lactoferrin-enriched intracellular fractions, consistent with FPR size and localization. NFPR1 also recognized a band of M(r) approximately 40 kDa localized, in equal proportions to the plasma membrane and lactoferrin-enriched fractions, consistent with FPRL1 size and localization. Only NFPR2 was capable of immunoprecipitation of rFPR in detergent extracts. The recognition of rFPR by NFPR2 is lost after exposure of cellular rFPR to f-Met-Leu-Phe (fMLF) and regained after alkaline phosphatase treatment of rFPR-bearing membranes. In neutrophils, NFPR2 immunofluorescence was lost upon fMLF stimulation. Immunoblotting approximately 60 kDa species, after phosphatase treatment of fMLF-stimulated neutrophil membranes, was also enhanced. We conclude that the region 337-346 of FPR becomes phosphorylated after fMLF activation of rFPR-expressing Chinese hamster ovary cells and neutrophils.

Towards a consensus on datasets and evaluation metrics for developing B-cell epitope prediction tools.

A B-cell epitope is the three-dimensional structure within an antigen that can be bound to the variable region of an antibody. The prediction of B-cell epitopes is highly desirable for various immunological applications, but has presented a set of unique challenges to the bioinformatics and immunology communities. Improving the accuracy of B-cell epitope prediction methods depends on a community consensus on the data and metrics utilized to develop and evaluate such tools. A workshop, sponsored by the National Institute of Allergy and Infectious Disease (NIAID), was recently held in Washington, DC to discuss the current state of the B-cell epitope prediction field. Many of the currently available tools were surveyed and a set of recommendations was devised to facilitate improvements in the currently existing tools and to expedite future tool development. An underlying theme of the recommendations put forth by the panel is increased collaboration among research groups. By developing common datasets, standardized data formats, and the means with which to consolidate information, we hope to greatly enhance the development of B-cell epitope prediction tools.