Biology subjects

Kingsford, C.

Publications and source records attributed to Kingsford, C..

10 recordsLinked to original sources

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↗

bioRxiv2018

Asymptotically optimal minimizers schemes

MotivationThe minimizers technique is a method to sample k-mers that is used in many bioinformatics software to reduce computation, memory usage and run time. The number of applications using minimizers keeps on growing steadily. Despite its many uses, the theoretical understanding of minimizers is still very limited. In many applications, selecting as few k-mers as possible (i.e. having a low density) is beneficial. The density is highly dependent on the choice of the order on the k-mers. Different applications use different orders, but none of these orders are optimal. A better understanding of minimizers schemes, and the related local and forward schemes, will allow designing schemes with lower density, and thereby making existing and future bioinformatics tools even more efficient.\n\nResultsFrom the analysis of the asymptotic behavior of minimizers, forward and local schemes, we show that the previously believed lower bound on minimizers schemes does not hold, and that schemes with density lower than thought possible actually exist. The proof is constructive and leads to an efficient algorithm to compare k-mers. These orders are the first known orders that are asymptotically optimal. Additionally, we give improved bounds on the density achievable by the 3 type of schemes.\n\nContactgmarcais@cs.cmu.edu ckingsf@cs.cmu.edu

bioinformatics↗

bioRxiv2017

SQUID: Transcriptomic Structural Variation Detection from RNA-seq

Transcripts are frequently modified by structural variations, which leads to a fused transcript of either multiple genes (known as a fusion gene) or a gene and a previously non-transcribing sequence. Detecting these modifications (called transcriptomic structural variations, or TSVs), especially in cancer tumor sequencing, is an important and challenging computational problem. We introduce SQUID, a novel algorithm to accurately predict both fusion-gene and non-fusion-gene TSVs from RNA-seq alignments. SQUID unifies both concordant and discordant read alignments into one model, and doubles the accuracy on simulation data compared to other approaches. With SQUID, we identified novel non-fusion-gene TSVs on TCGA samples.

bioinformatics↗

bioRxiv2017

Graph-Guided Assembly For Novel HLA Allele Discovery

Accurate typing of human leukocyte antigen (HLA), a histocompatibility test, is important because HLA genes play various roles in immune responses, and have also been shown to be associated with many diseases such as cancer. The current gold standard for HLA typing uses DNA sequencing technology combined with sequence enrichment techniques using specially designed primers or probes, causing it to be slow and labor-intensive. Although there exist enrichment-free computational methods that use various types of sequencing data, hyper-polymorphism found in HLA region of the human genome makes it challenging to type HLA genes with high accuracy from whole genome sequencing data. Furthermore, these methods are database-matching approaches where their output is inherently limited by the completeness of already known types, forcing them to find the best matching known alleles from a database, thereby causing them to be unsuitable for discovery of rare or novel alleles. In order to ensure both high accuracy as well as the ability to type novel alleles, we have developed a graph-guided assembly technique for classical HLA genes, which is capable of assembling phased, full-length haplotype sequences of typing exons given high-coverage (>30-fold) whole genome sequencing data. Our method delivers highly accurate HLA typing, comparable to the current state-of-the-art database-matching methods. We also demonstrate that our method can type novel alleles by experimenting on various data including simulated, Illumina Platinum Genomes, and 1000 Genomes data.

bioinformatics↗

bioRxiv2017

LEAP: A Generalization Of The Landau-Vishkin Algorithm With Custom Gap Paneities

MotivationApproximate String Matching is a pivotal problem in the field of computer science. It serves as an integral component for many string algorithms, most notably, DNA read mapping and alignment. The improved LV algorithm proposes an improved dynamic programming strategy over the banded Smith-Waterman algorithm but suffers from support of a limited selection of scoring schemes. In this paper, we propose the Leaping Toad problem, a generalization of the approximate string matching problem, as well as LEAP, a generalization of the Landau-Vishkins algorithm that solves the Leaping Toad problem under a broader selection of scoring schemes.\n\nResultsWe benchmarked LEAP against 3 state-of-the-art approximate string matching implementations. We show that when using a bit-vectorized de Bruijn sequence based optimization, LEAP is up to 7.4x faster than the state-of-the-art bit-vector Levenshtein distance implementation and up to 32x faster than the state-of-the-art affine-gap-penalty parallel Needleman Wunsch Implementation.\n\nAvailabilityWe provide an implementation of LEAP in C++ at github.com/CMU-SAFARI/LEAP.\n\nContacthxin@cmu.edu, calkan@cs.bilkent.edu.tr or onur.mutlu@inf.ethz.ch

bioinformatics↗

bioRxiv2017

Scallop Enables Accurate Assembly Of Transcripts Through Phasing-Preserving Graph Decomposition

We introduce Scallop, an accurate, reference-based transcript assembler for RNA-seq data. Scallop significantly improves reconstruction of multi-exon and lowly expressed transcripts. On 10 human samples aligned with STAR, Scallop produces (on average) 35.7% and 37.5% more correct multi-exon transcripts than two leading transcript assemblers, StringTie [1] and TransComb [2], respectively. For transcripts expressed at low levels in the same samples, Scallop assembles 65.2% and 50.2% more correct multi-exon transcripts than StringTie and TransComb, respectively. Scallop obtains this improvement through a novel algorithm that we prove preserves all phasing paths from reads (including paired-end reads), while also producing a parsimonious set of transcripts and minimizing coverage deviation.

bioinformatics↗

bioRxiv2017

Improving the performance of minimizers andwinnowing schemes

The minimizers scheme is a method for selecting k-mers from sequences. It is used in many bioinformatics software tools to bin comparable sequences or to sample a sequence in a deterministic fashion at approximately regular intervals, in order to reduce memory consumption and processing time. Although very useful, the minimizers selection procedure has undesirable behaviors (e.g., too many k-mers are selected when processing certain sequences). Some of these problems were already known to the authors of the minimizers technique, and the natural lexicographic ordering of k-mers used by minimizers was recognized as their origin. Many software tools using minimizers employ ad hoc variations of the lexicographic order to alleviate those issues.\n\nWe provide an in-depth analysis of the effect of k-mer ordering on the performance of the minimizers technique. By using small universal hitting sets (a recently defined concept), we show how to significantly improve the performance of minimizers and avoid some of its worse behaviors. Based on these results, we encourage bioinformatics software developers to use an ordering based on a universal hitting set or, if not possible, a randomized ordering, rather than the lexicographic order. This analysis also settles negatively a conjecture (by Schleimer et al.) on the expected density of minimizers in a random sequence.\n\nThe software used for this analysis is available on GitHub: https://github.com/gmarcais/minimizers.git.\n\nContact: gmarcais@cs.cmu.edu

bioinformatics↗

bioRxiv2016

Improved Search of Large Transcriptomic Sequencing Databases Using Split Sequence Bloom Trees

Enormous databases of short-read RNA-seq sequencing experiments such as the NIH Sequencing Read Archive (SRA) are now available. These databases could answer many questions about the condition-specific expression or population variation, and this resource is only going to grow over time. However, these collections remain difficult to use due to the inability to search for a particular expressed sequence. While some progress has been made on this problem, it is still not feasible to search collections of hundreds of terabytes of short-read sequencing experiments. We introduce an indexing scheme called Split Sequence Bloom Tree (SSBT) to support sequence-based querying of terabyte-scale collections of thousands of short-read sequencing experiments. SSBT is an improvement over the SBT [1] data structure for the same task. We apply SSBT to the problem of finding conditions under which query transcripts are expressed. Our experiments are conducted on a set of 2,652 publicly available RNA-seq experiments contained in the NIH for the breast, blood, and brain tissues. We demonstrate that this SSBT index can be queried for a 1000 nt sequence in under 4 minutes using a single thread and can be stored in just 39 GB, a five-fold improvement in search and storage costs compared to SBT. We further report that SSBT can be further optimized by pre-loading the entire index to accomplish the same search in 30 seconds.

genomics↗

bioRxiv2016

Efficient Heuristic for Decomposing a Flow with Minimum Number of Paths

Motivated by transcript assembly and multiple genome assembly problems, in this paper, we study the following minimum path flow decomposition problem: given a directed acyclic graph G = (V,E) with source s and sink t and a flow f, compute a set of s-t paths P and assign weight w(p) for p [isin] P such that [Formula], and |P| is minimized. We propose an efficient pseudo-polynomialtime heuristic for this problem based on novel insights. Our heuristic gives a framework that consists of several components, providing a roadmap for continuing development of better heuristics. Through experimental studies on both simulated and transcript assembly instances, we show that our algorithm significantly improves the previous state-of-the-art algorithm. Implementation of our algorithm is available at https://github.com/Kingsford-Group/catfish.

bioinformatics↗

bioRxiv2016

Chromosomal dynamics predicted by an elastic network model explains genome-wide accessibility and long-range couplings

Understanding the three-dimensional (3D) architecture of the chromatin and its relation to gene expression and regulation is fundamental to understanding how the genome functions. Advances in Hi-C technology now permit us to have a glimpse into the 3D genome organization and identify topologically associated domains (TADs), but we still lack an understanding of the structural dynamics of chromosomes. The dynamic couplings between regions separated by large genomic distances (> 50 megabases) have yet to be characterized. We adapted a well-established protein-modeling framework, the Gaussian Network Model (GNM), to the task of modeling chromatin dynamics using Hi-C contact data. We show that the GNM can identify structural dynamics at multiple scales: it can quantify the fluctuations in the positions of gene loci, find large genomic compartments and smaller TADs that undergo en-bloc movements, and identify dynamically coupled distal regions along the chromosomes. We show that the predictions of the GNM correlate well with DNase-seq and ATAC-seq measurements on accessibility, the previously identified A and B compartments of chromatin structure, and pairs of interacting loci identified by ChIA-PET. We describe a method to use the GNM to identify novel cross-correlated distal domains (CCDDs) representing regions of long-range dynamic coupling and show that CCDDs are often associated with increased gene coexpression using a large-scale analysis of 212 expression experiments. Together, these results show that GNM provides a mathematically well-founded unified framework for assessing chromatin dynamics and the structural basis of genome-wide observations.

genomics↗