Biology subjects

Kingsford, C.

Publications and source records attributed to Kingsford, C..

At least 37 records · Page 2Linked to original sources

bioRxiv2020

HARVESTMAN: A framework for hierarchical featurelearning and selection from whole genome sequencingdata

We present HO_SCPLOWARVESTMANC_SCPLOW, a method that takes advantage of hierarchical relationships among the possible biological interpretations and representations of genomic variants to perform automatic feature learning, feature selection, and model building. We demonstrate that HO_SCPLOWARVESTMANC_SCPLOW scales to thousands of genomes comprising more than 84 million variants by processing phase 3 data from the 1000 Genomes Project, the largest publicly available collection of whole genome sequences. Next, using breast cancer data from The Cancer Genome Atlas, we show that HO_SCPLOWARVESTMANC_SCPLOW selects a rich combination of representations that are adapted to the learning task, and performs better than a binary representation of SNPs alone. Finally, we compare HO_SCPLOWARVESTMANC_SCPLOW to existing feature selection methods and demonstrate that our method selects smaller and less redundant feature subsets, while maintaining accuracy of the resulting classifier. The data used is available through either the 1000 Genomes Project or The Cancer Genome Atlas. Access to TCGA data requires the completion of a Data Access Request through the Database of Genotypes and Phenotypes (dbGaP). Binary releases of HO_SCPLOWARVESTMANC_SCPLOW compatible with Linux, Windows, and Mac are available for download at https://github.com/cmlh-gp/Harvestman-public/releases

bioinformatics↗

bioRxiv2020

Improved design and analysis of practical minimizers

MotivationMinimizers are methods to sample k-mers from a sequence, with the guarantee that similar set of k-mers will be chosen on similar sequences. It is parameterized by the k-mer length k, a window length w and an order on the k-mers. Minimizers are used in a large number of softwares and pipelines to improve computation efficiency and decrease memory usage. Despite the methods popularity, many theoretical questions regarding its performance remain open. The core metric for measuring performance of a minimizer is the density, which measures the sparsity of sampled k-mers. The theoretical optimal density for a minimizer is 1/w, provably not achievable in general. For given k and w, little is known about asymptotically optimal minimizers, that is minimizers with density O(1/w). ResultsWe derive a necessary and sufficient condition for existence of asymptotically optimal minimizers. We also provide a randomized algorithm, called the Miniception, to design minimizers with the best theoretical guarantee to date on density in practical scenarios. Constructing and using the Miniception is as easy as constructing and using a random minimizer, which allows the design of efficient minimizers that scale to the values of k and w used in current bioinformatics software programs. AvailabilityReference implementation of the Miniception and the codes for analysis can be found at https://github.com/kingsford-group/miniception. Contactgmarcais@cs.cmu.edu

bioinformatics↗

bioRxiv2019

VariantStore: A Large-Scale Genomic Variant Search Index

The ability to efficiently query genomic variants from thousands of samples is critical to achieving the full potential of many medical and scientific applications such as personalized medicine. Performing variant queries based on coordinates in the reference or sample sequences is at the core of these applications. Efficiently supporting variant queries across thousands of samples is computationally challenging. Most solutions only support queries based on the reference coordinates and the ones that support queries based on coordinates across multiple samples do not scale to data containing more than a few thousand samples. We present VariantStore, a system for efficiently indexing and querying genomic variants and their sequences in either the reference or sample-specific coordinate systems. We show the scalability of VariantStore by indexing genomic variants from the TCGA-BRCA project containing 8640 samples and 5M variants in 4 Hrs and the 1000 genomes project containing 2500 samples and 924M variants in 3 Hrs. Querying for variants in a gene takes between 0.002 - 3 seconds using memory only 10% of the size of the full representation.

bioinformatics↗

bioRxiv2019

Finding ranges of optimal transcript expression quantification in cases of non-identifiability

Current expression quantification methods suffer from a fundamental but under-characterized type of error: the most likely estimates for transcript abundances are not unique. This means multiple estimates of transcript abundances generate the observed RNA-seq reads with equal likelihood, and the underlying true expression cannot be determined. This problem is called non-identifiability for probabilistic models, and is further exacerbated by incomplete reference transcriptome. That is, reads may be sequenced from unannotated expressed transcripts. Graph quantification is a generalization to transcript quantification, accounting for the reference incompleteness by allowing exponentially many unannotated transcripts to express reads. We propose methods to calculate a "confidence range of expression" for each transcript, representing its possible abundance across equally optimal estimates for both quantification models. This range informs both whether a transcript has potential estimation error due to non-identifiability and the extent of the error. Applying our methods to the Human Body Map data, we observe 35%-50% of transcripts potentially suffer from inaccurate quantification caused by non-identifiability. When comparing the expression between isoforms in one sample, we find that the degree of inaccuracy of 20%-47% transcripts can be so large that the ranking of expression between the transcript and its sibling isoforms cannot be determined. When comparing the expression of a transcript between two groups of RNA-seq samples in differential expression analysis, we observe that the majority of detected differentially expressed transcripts are reliable with a few exceptions after considering the ranges of the optimal expression estimates. The code for computing the range of expression is available at https://github.com/Kingsford-Group/subgraphquant. The code for the involved analyses is available at https://github.com/Kingsford-Group/subgraphquantanalysis.

bioinformatics↗

bioRxiv2019

Estimating mutual information under measurement error

Mutual information is widely used to characterize dependence between biological signals, such as co-expression between genes or co-evolution between amino acids. However, measurement error of the biological signals is rarely considered in estimating mutual information. Measurement error is widespread and non-negligible in some cases. As a result, the distribution of the signals is blurred, and the mutual information may be biased when estimated using the blurred measurements. We derive a corrected estimator for mutual information that accounts for the distribution of measurement error. Our corrected estimator is based on the correction of the probability mass function (PMF) or probability density function (PDF, based on kernel density estimation). We prove that the corrected estimator is asymptotically unbiased in the (semi-) discrete case when the distribution of measurement error is known. We show that it reduces the estimation bias in the continuous case under certain assumptions. On simulated data, our corrected estimator leads to a more accurate estimation for mutual information when the sample size is not the limiting factor for estimating PMF or PDF accurately. We compare the uncorrected and corrected estimator on the gene expression data of TCGA breast cancer samples and show a difference in both the value and the ranking of estimated mutual information between the two estimators.

bioinformatics↗

bioRxiv2019

A statistical method for identifying consistently important features across samples

In many applications, a consistently high measurement across many samples can indicate particularly meaningful or useful information for quality control or biological interpretation. Identification of these strong features among many others can be challenging especially when the samples cannot be expected to have the same distribution or range of values. We present a general method called conserved feature discovery (CFD) for identifying features with consistently strong signals across multiple conditions or samples. Given any real-valued data, CFD requires no parameters, makes no assumptions on the shape of the underlying sample distributions, and is robust to differences across these distributions.We show that with high probability CFD identifies all true positives and no false positives under certain assumptions on the median and variance distributions of the feature measurements. Using simulated data, we show that CFD is tolerant to a small percentage of poor quality samples and robust to false positives. Applying CFD to RNA sequencing data from the Human Body Map project and GTEx, we identify housekeeping genes as highly expressed genes across tissue types and compare to housekeeping gene lists from previous methods. CFD is consistent between the Human Body Map and GTEx data sets, and identifies lists of genes enriched for basic cellular processes as expected. The framework can be easily adapted for many data types and desired feature properties. AvailabilityCode for CFD and scripts to reproduce the figures and analysis in this work are available at https://github.com/Kingsford-Group/cfd. Supplementary informationSupplementary data are available at https://github.com/Kingsford-Group/cfd.

genomics↗

bioRxiv2019

Detecting Transcriptomic Structural Variants in Heterogeneous Contexts via the Multiple Compatible Arrangements Problem

Transcriptomic structural variants (TSVs) -- structural variants that affect expressed regions -- are common, especially in cancer. Detecting TSVs is a challenging computational problem. Sample heterogeneity (including differences between alleles in diploid organisms) is a critical confounding factor when identifying TSVs. To improve TSV detection in heterogeneous RNA-seq samples, we introduce the MO_SCPCAPULTIPLEC_SCPCAP CO_SCPCAPOMPATIBLEC_SCPCAP AO_SCPCAPRRANGEMENTC_SCPCAP PO_SCPCAPROBLEMC_SCPCAP (MCAP), which seeks k genome rearrangements to maximize the number of reads that are concordant with at least one rearrangement. This directly models the situation of a heterogeneous or diploid sample. We prove that MCAP is NP-hard and provide a [Formula]-approximation algorithm for k = 1 and a [Formula]-approximation algorithm for the diploid case (k = 2) assuming an oracle for k = 1. Combining these, we obtain a [Formula]-approximation algorithm for MCAP when k = 2 (without an oracle). We also present an integer linear programming formulation for general k. We completely characterize the graph structures that require k > 1 to satisfy all edges and show such structures are prevalent in cancer samples. We evaluate our algorithms on 381 TCGA samples and 2 cancer cell lines and show improved performance compared to the state-of-the-art TSV-calling tool, SQUID.

bioinformatics↗

bioRxiv2019

Alignment and mapping methodology influence transcript abundance estimation

BackgroundThe accuracy of transcript quantification using RNA-seq data depends on many factors, such as the choice of alignment or mapping method and the quantification model being adopted. While the choice of quantification model has been shown to be important, considerably less attention has been given to comparing the effect of various read alignment approaches on quantification accuracy.\n\nResultsWe investigate the influence of mapping and alignment on the accuracy of transcript quantification in both simulated and experimental data, as well as the effect on subsequent differential expression analysis. We observe that, even when the quantification model itself is held fixed, the effect of choosing a different alignment methodology, or aligning reads using different parameters, on quantification estimates can sometimes be large, and can affect downstream differential expression analyses as well. These effects can go unnoticed when assessment is focused too heavily on simulated data, where the alignment task is often simpler than in experimentally-acquired samples. We also introduce a new alignment methodology, called selective alignment, to overcome the shortcomings of lightweight approaches without incurring the computational cost of traditional alignment.\n\nConclusionWe observe that, on experimental datasets, the performance of lightweight mapping and alignment-based approaches varies significantly and highlight some of the underlying factors. We show this variation both in terms of quantification and downstream differential expression analysis. In all comparisons, we also show the improved performance of our proposed selective alignment method and suggest best practices for performing RNA-seq quantification.

bioinformatics↗

bioRxiv2019

Practical universal k-mer sets for minimizer schemes

Minimizer schemes have found widespread use in genomic applications as a way to quickly predict the matching probability of large sequences. Most methods for minimizer schemes use randomized (or close to randomized) ordering of k-mers when finding minimizers, but recent work has shown that not all non-lexicographic orderings perform the same. One way to find k-mer orderings for minimizer schemes is through the use of universal k-mer sets, which are subsets of k-mers that are guaranteed to cover all windows. The smaller this set the fewer false positives (where two poorly aligned sequences being identified as possible matches) are identified. Current methods for creating universal k-mer sets are limited in the length of the k-mer that can be considered, and cannot compute sets in the range of lengths currently used in practice. We take some of the first steps in creating universal k-mer sets that can be used to construct minimizer orders for large values of k that are practical. We do this using iterative extension of the k-mers in a set, and guided contraction of the set itself. We also show that this process will be guaranteed to never increase the number of distinct minimizers chosen in a sequence, and thus can only decrease the number of false positives over using the current sets on small k-mers.

bioinformatics↗

bioRxiv2019

Context-Aware Seeds for Read Mapping

MotivationMost modern seed-and-extend NGS read mappers employ a seeding scheme that requires extracting t non-overlapping seeds in each read in order to find all valid mappings under an edit distance threshold of t. As t grows (such as in long reads with high error rate), this seeding scheme forces mappers to use more and shorter seeds, which increases the seed hits (seed frequencies) and therefore reduces the efficiency of mappers.\n\nResultsWe propose a novel seeding framework, context-aware seeds (CAS). CAS guarantees finding all valid mapping but uses fewer (and longer) seeds, which reduces seed frequencies and increases efficiency of mappers. CAS achieves this improvement by attaching a confidence radius to each seed. We prove that all valid mappings can be found if the sum of confidence radii of seeds are greater than t. CAS generalizes the existing pigeonhole-principle-based seeding scheme in which this confidence radius is implicitly always 1. Moreover, we design an efficient algorithm that constructs the confidence radius database in linear time. We experiment CAS with E. coli genome and show that CAS reduces seed frequencies by up to 25.4% when compared with the state-of-the-art pigeonhole-principle-based seeding algorithm, the Optimal Seed Solver.\n\nAvailabilityhttps://github.com/Kingsford-Group/CAS_code

bioinformatics↗

bioRxiv2019

Quantifying the Benefit Offered by Transcript Assembly on Single-Molecule Long Reads

Third-generation sequencing technologies benefit transcriptome analysis by generating longer sequencing reads. However, not all single-molecule long reads represent full transcripts due to incomplete cDNA synthesis and the sequencing length limit of the platform. This drives a need for long read transcript assembly. We quantify the benefit that can be achieved by using a transcript assembler on long reads. Adding long-read-specific algorithms, we evolved Scallop to make Scallop-LR, a long-read transcript assembler, to handle the computational challenges arising from long read lengths and high error rates. Analyzing 26 SRA PacBio datasets using Scallop-LR, Iso-Seq Analysis, and StringTie, we quantified the amount by which assembly improved Iso-Seq results. Through combined evaluation methods, we found that Scallop-LR identifies 2100-4000 more (for 18 human datasets) or 1100-2200 more (for eight mouse datasets) known transcripts than Iso-Seq Analysis, which does not do assembly. Further, Scallop-LR finds 2.4-4.4 times more potentially novel isoforms than Iso-Seq Analysis for the human and mouse datasets. StringTie also identifies more transcripts than Iso-Seq Analysis. Adding long-read-specific optimizations in Scallop-LR increases the numbers of predicted known transcripts and potentially novel isoforms for the human transcriptome compared to several recent short-read assemblers (e.g. StringTie). Our findings indicate that transcript assembly by Scallop-LR can reveal a more complete human transcriptome.

bioinformatics↗

bioRxiv2019

Maximum Likelihood Reconstruction of Ancestral Networks by Integer Linear Programming

MotivationThe study of the evolutionary history of biological networks enables deep functional understanding of various bio-molecular processes. Network growth models, such as the Duplication-Mutation with Complementarity (DMC) model, provide a principled approach to characterizing the evolution of protein-protein interactions (PPI) based on duplication and divergence. Current methods for model-based ancestral network reconstruction primarily use greedy heuristics and yield sub-optimal solutions. ResultsWe present a new Integer Linear Programming (ILP) solution for maximum likelihood reconstruction of ancestral PPI networks using the DMC model. We prove the correctness of our solution that is designed to find the optimal solution. It can also use efficient heuristics from general-purpose ILP solvers to obtain multiple optimal and near-optimal solutions that may be useful in many applications. Experiments on synthetic data show that our ILP obtains solutions with higher likelihood than those from previous methods, and is robust to noise and model mismatch. We evaluate our algorithm on two real PPI networks, with proteins from the families of bZIP transcription factors and the Commander complex. On both the networks, solutions from our ILP have higher likelihood and are in better agreement with independent biological evidence from other studies. AvailabilityA Python implementation is available at https://bitbucket.org/cdal/. Contactvaibhav.rajan@nus.edu.sg

bioinformatics↗

bioRxiv2019

Identification of Microbiota-Induced Gene Expression Changes in the Drosophila melanogaster Head

Symbiotic microorganisms exert multifaceted impacts on the physiology of their animal hosts. Recent discoveries have shown the gut microbiota influence host brain function and behavior, but the host and microbial molecular factors required to actuate these effects are largely unknown. To uncover molecular mechanisms that underlie the gut-microbiota-brain axis, we used Drosophila melanogaster and its bacterial microbiota as a model to identify microbiota-dependent gene expression changes in the host brain and head. Specifically, we employed RNA-seq and nanoString nCounter technology to identify Drosophila genes that exhibit altered transcript levels in fly heads upon elimination of the microbiota. The identified genes, some of which exhibited sex-specific differences, have demonstrated or inferred functional roles in the immune response, metabolism, neuronal activity, and stress resistance. Overall, this study reveals microbiota-responsive genes in the fly head, an anatomical structure not previously investigated in this context. Our results serve as a foundation for future investigations of how microbe-driven gene expression changes impact Drosophila biology.

microbiology↗

bioRxiv2019

Topological data analysis reveals principles of chromosome structure throughout cellular differentiation

Three-dimensional chromosome structure has a significant influence in many diverse genomic processes and has recently been shown to relate to cellular differentiation. Many methods for describing the chromosomal architecture focus on specific substructures such as topologically-associating domains (TADs) or compartments, but we are still missing a global view of all geometric features of chromosomes. Topological data analysis (TDA) is a mathematically well-founded set of methods to derive robust information about the structure and topology of data sets, making it well-suited to better understand the key features of chromosome structure. By applying TDA to the study of chromosome structure through differentiation across three cell lines, we provide insight into principles of chromosome folding generally, and observe structural changes across lineages. We identify both global and local differences in chromosome topology through differentiation, identifying trends consistent across human cell lines. AvailabilityScripts to reproduce the results from this study can be found at https://github.com/Kingsford-Group/hictda Contactcarlk@cs.cmu.edu

genomics↗

bioRxiv2019

Detecting anomalies in RNA-seq quantification

Algorithms to infer isoform expression abundance from RNA-seq have been greatly improved in accuracy during the past ten years. However, due to incomplete reference transcriptomes, mapping errors, incomplete sequencing bias models, or mistakes made by the algorithm, the quantification model sometimes could not explain all aspects of the input read data, and misquantification can occur. Here, we develop a computational method to detect instances where a quantification model could not thoroughly explain the input. Specifically, our approach identifies transcripts where the read coverage has significant deviations from the expectation. We call these transcripts "expression anomalies", and they represent instances where the quantification estimates may be in doubt. We further develop a method to attribute the cause of anomalies to either the incompleteness of the reference transcriptome or the algorithmic mistakes, and we show that our method precisely detects misquantifications with both causes. By correcting the misquantifications that are labeled as algorithmic mistakes, the number of false predictions of differentially expressed transcripts can be reduced. Applying anomaly detection to 30 GEUVADIS and 16 Human Body Map samples, we detect 103 genes with potential unannotated isoforms. These genes tend to be longer than average, and contain a very long exon near 3' end that the unannotated isoform excludes. Anomaly detection is a new approach for investigating the expression quantification problem that may find wider use in other areas of genomics.

bioinformatics↗

bioRxiv2019

Locality sensitive hashing for the edit distance

MotivationSequence alignment is a central operation in bioinformatics pipeline and, despite many improvements, remains a computationally challenging problem. Locality Sensitive Hashing (LSH) is one method used to estimate the likelihood of two sequences to have a proper alignment. Using an LSH, it is possible to separate, with high probability and relatively low computation, the pairs of sequences that do not have an alignment from those that may have an alignment. Therefore, an LSH reduces in the overall computational requirement while not introducing many false negatives (i.e., omitting to report a valid alignment). However, current LSH methods treat sequences as a bag of k-mers and do not take into account the relative ordering of k-mers in sequences. And due to the lack of a practical LSH method for edit distance, in practice, LSH methods for Jaccard similarity or Hamming distance are used as a proxy. ResultsWe present an LSH method, called Order Min Hash (OMH), for the edit distance. This method is a refinement of the minHash LSH used to approximate the Jaccard similarity, in that OMH is not only sensitive to the k-mer contents of the sequences but also to the relative order of the k-mers in the sequences. We present theoretical guarantees of the OMH as a gapped LSH. Contactgmarcais@cs.cmu.edu, carlk@cs.cmu.edu

bioinformatics↗

bioRxiv2018

Analysis of the structural variability of topologically associated domains as revealed by Hi-C

Three-dimensional chromosome structure plays an integral role in gene expression and regulation, replication timing, and other cellular processes. Topologically associating domains (TADs), one of the building blocks of chromosome structure, are genomic regions with higher contact frequencies within the region than outside the region. A central question is the degree to which TADs are conserved or vary between conditions. We analyze a set of 137 Hi-C samples from 9 different studies under 3 measures in order to quantify the effects of various sources of biological and experimental variation. We observe significant variation in TAD sets between both non-replicate and replicate samples, and show that this variability does not seem to come from genetic sequence differences. The effects of experimental protocol differences are also measured, demonstrating that samples can have protocol-specific structural changes, but that TADs are generally robust to lab-specific differences. This study represents a systematic quantification of the key factors influencing comparisons of chromosome structure.

genomics↗

bioRxiv2018

Automatically eliminating errors induced by suboptimal parameter choices in transcript assembly

Computational tools used for genomic analyses are becoming increasingly sophisticated and complex. While these applications often provide more accurate results than their predecessors, a new problem is emerging in that these pieces of software have a large number of tunable parameters. Choosing the wrong parameter values for an application may lead to significant results being overlooked or false results being reported. We take some first steps towards generating a truly automated genomic analysis pipeline by developing a method for automatically choosing input-specific parameter values for reference-based transcript assembly. We extend the parameter advising framework, first developed for multiple sequence alignment, to optimize parameter choices for the Scallop transcript assembler. In doing so, we provide the first method for finding advisor sets for applications with large numbers of tunable parameters. By choosing parameter values for each input, the area under the curve (AUC) when comparing assembled transcripts to a reference transcriptome is increased by 28.9% over using only the default parameter choices on 1595 RNA-Seq samples in the Sequence Read Archive. This approach is general, and when applied to StringTie it increases AUC by 13.1% on a set of 65 RNA-Seq experiments from ENCODE. Parameter advisors for both Scallop and StringTie are available on Github1.

bioinformatics↗