Source-linked AI summary
Near-optimal RNA-Seq quantification
Nicolas Bray, Harold Pimentel, Páll Melsted, Lior Pachter
TL;DR
RNA-Seq quantification can be approached by pseudoaligning reads through k-mer compatibility classes and quantifying using equivalence classes. The approach reduces read processing to hash lookups for only two k-mers while retaining sufficient statistics for computation.
Problem
The paper addresses how RNA-Seq reads can be assigned to compatible transcripts for efficient quantification.
Method
The approach pseudoaligns reads through k-mer compatibility-class lookups and intersections, then quantifies using equivalence-class counts.
Results
Hash lookups for only two k-mers support the pseudoalignment procedure.
Takeaways & Limitations
Equivalence-class counts provide sufficient statistics, allowing subsequent computations to use a much smaller data representation.
Takeaways & Limitations
In rare cases, kallisto encounters a mismatch between compatibility classes where agreement is expected.
Abstract
from arXiv · showhide
We present a novel approach to RNA-Seq quantification that is near optimal in speed and accuracy. Software implementing the approach, called kallisto, can be used to analyze 30 million unaligned paired-end RNA-Seq reads in less than 5 minutes on a standard laptop computer while providing results as accurate as those of the best existing tools. This removes a major computational bottleneck in RNA-Seq analysis.
Online Methods · Index construction
kallisto constructs its index from a colored transcriptome de Bruijn graph, compresses identically colored linear stretches into contigs, and stores k-mer locations in a hash table. For error-free reads, discrepancies between read equivalence classes and k-compatibility intersections require an unlikely transcript arrangement that implies a short directed cycle.
- Index construction: The index construction begins by forming a colored de Bruijn graph from the transcriptome, with colors corresponding to transcripts.Each node represents a k-mer, and each k-mer receives one color for every transcript in which it occurs.
- Index construction: Contigs are formed from linear graph stretches whose k-mers have identical colorings.This construction associates all k-mers within a contig with the same equivalence class.
- Index construction: Two different contigs can share an equivalence class, so identical coloring does not uniquely identify a contig.The converse of the contig-to-equivalence-class association is therefore not guaranteed.
- Index construction: kallisto stores a hash table mapping each k-mer to its containing contig and position within that contig.This data structure is called the “kallisto index”.
- Index construction: For error-free reads, the read equivalence class can differ from the intersection of its k-compatibility classes.The discrepancy is constrained by the arrangement of transcript k-mers.
- Index construction: For a read of length l, such a discrepancy requires two transcripts to contain the same l-k+1 k-mers in different orders.This condition specifies when the read and compatibility-class assignments can diverge.
- Index construction: With large k, the required transcript arrangement is unlikely because it would imply a directed cycle shorter than l-k+1 in the T-DBG.The same implication provides a testable criterion.
Pseudoalignment
Kallisto pseudoaligns reads by intersecting k-compatibility classes retrieved from its index, using both ends for paired-end fragments. Positional information enables skipping redundant k-mers, so most reads require only two hash lookups while mismatches trigger a full examination.
- Pseudoalignment: Kallisto pseudoaligns reads by looking up each k-mer’s k-compatibility class in the index and intersecting the identified classes.For paired-end fragments, it performs the lookup for both ends and intersects all resulting classes.
- Pseudoalignment: Positional information in the index lets kallisto skip redundant k-mers within T-DBG contigs that share the same k-compatibility class.The skip extends to the minimum of the junction distance or the distance to the read end, with a final k-mer consistency check.
- Pseudoalignment: When a skipped k-mer has an unexpected k-compatibility class, kallisto defaults to examining every k-mer in the read.This fallback handles rare mismatches and preserves consistency with the T-DBG.
- Pseudoalignment: For most reads, kallisto performs hash lookups for only two k-mers.This optimization is reported in Supplementary Figure 6.
Quantification
kallisto quantifies transcript abundances from pseudoalignments by optimizing a likelihood over equivalence-class counts rather than individual reads. It uses EM optimization with a defined convergence criterion and reports abundances in TPM units.
- Quantification: kallisto estimates transcript-selection probabilities αt by iteratively optimizing the RNA-Seq likelihood with the EM algorithm.The likelihood uses transcript effective lengths and a fragment–transcript compatibility matrix.
- Quantification: Equivalence-class counts are sufficient statistics, reducing computation from tens of millions of reads to usually hundreds of thousands of equivalence classes.Similar likelihood terms are factored together by equivalence class, whose counts summarize observed fragments.
- Quantification: EM iterations terminate when every transcript with αtN > 0.01 changes by less than 1% between successive iterations.N denotes the total number of fragments.
- Quantification: Transcript abundances are reported in transcripts per million (TPM) units.TPM is the output abundance unit used by kallisto.
Bootstrap
kallisto generates bootstrap samples efficiently from equivalence-class counts after pseudoalignment, then recomputes transcript abundances with the EM algorithm. Bootstrap output is compressed in HDF5 and can be processed or converted to plaintext.
- Sampling: Bootstrap sampling draws N counts from a multinomial distribution over equivalence classes, with class probabilities proportional to original counts.Samples are generated after fragments have been categorized by equivalence class and pseudoalignment is complete.
- Abundance estimation: The EM algorithm recomputes transcript abundances for each newly generated bootstrap sample.Bootstrap efficiency reflects both the fast EM algorithm and the use of equivalence-class counts as sufficient statistics.
- Implementation: The number of bootstrap replicates is specified as a kallisto program option.The implementation exposes bootstrap count as a configurable command-line setting.
- Output: Bootstrap output is compressed in HDF5 and can be read by other programs or converted to plaintext using kallisto.The passage specifically gives R as an example of a program that can read the HDF5 files.
Simulations and analysis
The paper’s simulation parameters and procedures are made available for reproducing its results and figures through a Snakefile repository.
- The parameters used for the paper’s results and figures are available in a Snakefile.
- The procedures used to generate the paper’s results and figures are also provided.
- The analysis resources are available at the kallisto_paper_analysis GitHub repository.
Software
The kallisto program is available for download from the Pachter Lab website.
- kallisto is available for download from http://pachterlab.github.io/kallisto.