2,308 research outputs found
simpleaf: a simple, flexible, and scalable framework for single-cell data processing using alevin-fry
No full textThe alevin-fry ecosystem provides a robust and growing suite of programs for single-cell data processing. However, as new single-cell technologies are introduced, as the community continues to adjust best practices for data processing, and as the alevin-fry ecosystem itself expands and grows, it is becoming increasingly important to manage the complexity of alevin-fry’s single-cell preprocessing workflows while retaining the performance and flexibility that make these tools enticing. We introduce simpleaf, a program that simplifies the processing of single-cell data using tools from the alevin-fry ecosystem, and adds new functionality and capabilities, while retaining the flexibility and performance of the underlying tools.
Simpleaf is written in Rust and released under a BSD 3-Clause license. It is freely available from its GitHub repository https://github.com/COMBINE-lab/simpleaf, and via bioconda. Documentation for simpleaf is available at https://simpleaf.readthedocs.io/en/latest/ and tutorials for simpleaf that have been developed can be accessed at https://combine-lab.github.io/alevin-fry-tutorials.This work was supported by the US National Institutes of Health [R01 HG009937], and the US National Science Foundation [CCF-1750472 and CNS-1763680]. Partial funding for open access is provided by the UMD Libraries’ Open Access Publishing Fund. Also, this project has been made possible in part by grant number 2022-252586 from the Chan Zuckerberg Initiative DAF, an advised fund of Silicon Valley Community Foundation.https://doi.org/10.1093/bioinformatics/btad61
Rainbowfish: A Succinct Colored de Bruijn Graph Representation
No full textThe colored de Bruijn graph— a variant of the de Bruijn graph which associates each edge (i.e., k-mer) with some set of colors - is an increasingly important combinatorial structure in computational biology. Iqbal et al. demonstrated the utility of this structure for representing and assembling a collection (population) of genomes, and showed how it can be used to accurately detect genetic variants. Muggli et al. introduced VARI, a representation of the colored de Bruijn graph that adopts the BOSS representation for the de Bruijn graph topology and achieves considerable savings in space over Cortex, albeit with some sacrifice in speed. The memory-efficient representation of VARI allows the colored de Bruijn graph to be constructed and analyzed for large datasets, beyond what is possible with Cortex.
In this paper, we introduce Rainbowfish, a succinct representation of the color information of the colored de Bruijn graph that reduces the space usage even further. Our representation also uses BOSS to represent the de Bruijn graph, but decomposes the color sets based on an equivalence relation and exploits the inherent skewness in the distribution of these color sets. The Rainbowfish representation is compressed based on the 0th-order entropy of the color sets, which can lead to a significant reduction in the space required to store the relevant information for each edge. In practice, Rainbowfish achieves up to a 20x improvement in space over VARI. Rainbowfish is written in C++11 and is available at https://github.com/COMBINE-lab/rainbowfish
Perplexity: Evaluating Transcript Abundance Estimation in the Absence of Ground Truth
No full textThere has been rapid development of probabilistic models and inference methods for transcript abundance estimation from RNA-seq data. These models aim to accurately estimate transcript-level abundances, to account for different biases in the measurement process, and even to assess uncertainty in resulting estimates that can be propagated to subsequent analyses. The assumed accuracy of the estimates inferred by such methods underpin gene expression based analysis routinely carried out in the lab. Although hyperparameter selection is known to affect the distributions of inferred abundances (e.g. producing smooth versus sparse estimates), strategies for performing model selection in experimental data have been addressed informally at best.
Thus, we derive perplexity for evaluating abundance estimates on fragment sets directly. We adapt perplexity from the analogous metric used to evaluate language and topic models and extend the metric to carefully account for corner cases unique to RNA-seq. In experimental data, estimates with the best perplexity also best correlate with qPCR measurements. In simulated data, perplexity is well behaved and concordant with genome-wide measurements against ground truth and differential expression analysis.
To our knowledge, our study is the first to make possible model selection for transcript abundance estimation on experimental data in the absence of ground truth
Where the patterns are: repetition-aware compression for colored de Bruijn graphs
No full textWe describe lossless compressed data structures for the colored de Bruijn graph (or c-dBG). Given a collection of reference sequences, a c-dBG can be essentially regarded as a map from k-mers to their color sets. The color set of a k-mer is the set of all identifiers, or colors, of the references that contain the k-mer. While these maps find countless applications in computational biology (e.g., basic query, reading mapping, abundance estimation, etc.), their memory usage represents a serious challenge for large-scale sequence indexing. Our solutions leverage on the intrinsic repetitiveness of the color sets when indexing large collections of related genomes. Hence, the described algorithms factorize the color sets into patterns that repeat across the entire collection and represent these patterns once instead of redundantly replicating their representation as would happen if the sets were encoded as atomic lists of integers. Experimental results across a range of datasets and query workloads show that these representations substantially improve over the space effectiveness of the best previous solutions (sometimes, even dramatically, yielding indexes that are smaller by an order of magnitude). Despite the space reduction, these indexes only moderately impact the efficiency of the queries compared to the fastest indexes
Fulgor: A Fast and Compact {k-mer} Index for Large-Scale Matching and Color Queries
No full textThe problem of sequence identification or matching - determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence - is relevant for many important tasks in Computational Biology, such as metagenomics and pan-genome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections.
To solve this problem, we describe how recent advancements in associative, order-preserving, k-mer dictionaries can be combined with a compressed inverted index to implement a fast and compact colored de Bruijn graph data structure. This index takes full advantage of the fact that unitigs in the colored de Bruijn graph are monochromatic (all k-mers in a unitig have the same set of references of origin, or "color"), leveraging the order-preserving property of its dictionary. In fact, k-mers are kept in unitig order by the dictionary, thereby allowing for the encoding of the map from k-mers to their inverted lists in as little as 1+o(1) bits per unitig. Hence, one inverted list per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for inverted lists, the index achieves very small space.
We implement these methods in a tool called Fulgor. Compared to Themisto, the prior state of the art, Fulgor indexes a heterogeneous collection of 30,691 bacterial genomes in 3.8× less space, a collection of 150,000 Salmonella enterica genomes in approximately 2× less space, is at least twice as fast for color queries, and is 2-6 × faster to construct
Fast, Parallel, and Cache-Friendly Suffix Array Construction
No full textString indexes such as the suffix array (SA) and the closely related longest common prefix (LCP) array are fundamental objects in bioinformatics and have a wide variety of applications. Despite their importance in practice, few scalable parallel algorithms for constructing these are known, and the existing algorithms can be highly non-trivial to implement and parallelize. In this paper we present CaPS-SA, a simple and scalable parallel algorithm for constructing these string indexes inspired by samplesort. Due to its design, CaPS-SA has excellent memory-locality and thus incurs fewer cache misses and achieves strong performance on modern multicore systems with deep cache hierarchies. We show that despite its simple design, CaPS-SA outperforms existing state-of-the-art parallel SA and LCP-array construction algorithms on modern hardware. Finally, motivated by applications in modern aligners where the query strings have bounded lengths, we introduce the notion of a bounded-context SA and show that CaPS-SA can easily be extended to exploit this structure to obtain further speedups
Adventures of a currency trader : a fable about trading, courage, and doing the right thing / Rob Booker.
No full textIncludes index.Book fair 2012.xv, 221 pages :Praise for ADVENTURES of a CURRENCY TRADER "A truly easy, unique, and enjoyable read! Rob has done it onceagain to teach us in the funniest way possible...
how not to make themost common trading mistakes. If you are tired of reading how-tobooks, this is perfect for you. I highly recommend this book to alltraders. Everyone will learn something about themselves by readingthis book."—Kathy Lien, author, Day Trading the Currency Market,and Chief Strategist, www.dailyfx.com"Adventures of a Currency Trader is a must read foranyone who has ever traded or is thinking about trading in theForex markets. Rob Booker has a unique way of taking years ofmarket knowledge and transforming it into an educational andentertaining experience. It has quickly become a cult classic in mytrading library!"—H. Jack Bouroudjian, Principal, Brewer Investment Group"Brilliant! Rob's humor and humanity shine through in thisparable about trading and life. Filled with wisdom and wit, it's anexhilarating rollercoaster ride through the peaks and valleys ofthe learning curve, with many valuable lessons learned along theway."—Ed Ponsi, President, FXEducator.com"Rob's fable of everyman 'Harry Banes' is destined to become atrading classic. This is both the missing piece and the foundationthat comes before the strategies and methodologies. The search forthe Holy Grail begins and ends in the heart and mind. The journeyis authentic and real and if you're willing to take it with Rob,you will be rewarded in the end. Seldom has psychology and wisdombeen so entertaining!"—Raghee Horner, trader and author of Forex Trading forMaximum Profit and Days of Forex Trading"In a series of insightful and entertaining vignettes, RobBooker teaches both the novice and the experienced trader some hardwon truths about the currency market. It's a must read book writtenby a guy who survived the trenches and went on to prosper in thebiggest and most competitive financial market in the world."—Boris Schlossberg, Senior Currency Strategist, Forex CapitalMarkets LLC, and author of Technical Analysis of the CurrencyMarke
Fulgor: a fast and compact k-mer index for large-scale matching and color queries
No full textAbstract The problem of sequence identification or matching—determining the subset of reference sequences from a given collection that are likely to contain a short, queried nucleotide sequence—is relevant for many important tasks in Computational Biology, such as metagenomics and pangenome analysis. Due to the complex nature of such analyses and the large scale of the reference collections a resource-efficient solution to this problem is of utmost importance. This poses the threefold challenge of representing the reference collection with a data structure that is efficient to query, has light memory usage, and scales well to large collections. To solve this problem, we describe an efficient colored de Bruijn graph index, arising as the combination of a k-mer dictionary with a compressed inverted index. The proposed index takes full advantage of the fact that unitigs in the colored compacted de Bruijn graph are monochromatic (i.e., all k-mers in a unitig have the same set of references of origin, or color). Specifically, the unitigs are kept in the dictionary in color order, thereby allowing for the encoding of the map from k-mers to their colors in as little as 1 + o(1) bits per unitig. Hence, one color per unitig is stored in the index with almost no space/time overhead. By combining this property with simple but effective compression methods for integer lists, the index achieves very small space. We implement these methods in a tool called Fulgor, and conduct an extensive experimental analysis to demonstrate the improvement of our tool over previous solutions. For example, compared to Themisto—the strongest competitor in terms of index space vs. query time trade-off—Fulgor requires significantly less space (up to 43% less space for a collection of 150,000 Salmonella enterica genomes), is at least twice as fast for color queries, and is 2–6 × faster to construct
Rob and Bert in Tokyo
No full textThis essay is steeped in contradiction: it is as much an attempt at mourning, coping, and letting go as it is an exercise in remembrance, rediscovery, and reconnection. One of the many areas of international legal scholarship where Rob Cryer left his mark is his oeuvre on the International Military Tribunal for the Far East (IMTFE). To pay tribute to, and get re-acquainted with, Rob-the-person, I re-read his 2010 article on the ‘dignified dissenter’ in Tokyo, Dutch Judge Bert Röling. In that article, Rob uses the memoranda and the opinion of Bert-the-judge to assess his conceptual and legal contributions to the IMTFE judgment. They also serve him as a vehicle to get a better grasp of the author behind the text and the values and dilemmas that shaped Röling’s positions on the IMTFE bench. What more can we learn and understand about Rob Cryer while ‘reading Rob reading Bert’? What aspects of Röling’s legacy did he choose to foreground, and what qualities did he appreciate most? How did Rob treat his character when shedding light on the more contentious elements of Röling’s work? Even if this essay fails in its therapeutic purpose, it might still add a few mosaic pieces to the collective construction of Rob’s portrait in this volume
Sub-Series 4: Publications : Affirmation and Affirmation News - Documents Found with Newsletters, 1994-1997
No full textA paper discussing the author, Rob Casteel, and his struggle with AIDS
- …
