Kallisto

Kallisto's foundational innovation is the pseudoalignment concept, which bypasses the computationally expensive step of determining a read's exact base-pair alignment. Instead, it rapidly identifies the set of transcripts a read is compatible with by comparing the read's k-mers to a pre-built transcriptome de Bruijn graph index. A read is pseudoaligned if its k-mers match a transcript contiguously, without penalizing mismatches or gaps. This binary compatibility check is orders of magnitude faster than traditional alignment algorithms like Bowtie or STAR, making it ideal for large-scale studies and clinical pipelines where speed is critical.

Kallisto constructs a colored de Bruijn graph from the reference transcriptome during its indexing phase. This graph represents all possible k-mers (default k=31) and their connections across the transcriptome. Each transcript is treated as a path through this graph, and each k-mer is assigned a color indicating which transcripts contain it. During quantification, a read's k-mers are matched against this index to determine transcript compatibility. This graph-based approach efficiently handles the combinatorial complexity of isoform resolution, enabling rapid intersection of read k-mers with transcript paths.

Once reads are pseudoaligned to sets of compatible transcripts, Kallisto employs an Expectation-Maximization (EM) algorithm to resolve ambiguity and estimate transcript abundances. The EM algorithm iteratively:

• E-step: Estimates the probability that each read originated from each of its compatible transcripts, given current abundance estimates.
• M-step: Updates transcript abundance estimates based on the expected read assignments. This probabilistic framework correctly handles multi-mapping reads that are compatible with multiple isoforms, converging to maximum likelihood estimates of transcript-level expression in Transcripts Per Million (TPM) units.

Kallisto provides built-in bootstrap resampling to estimate the technical variance of abundance estimates without requiring multiple sequencing runs. By repeatedly resampling the original reads with replacement and re-running the EM algorithm, Kallisto generates a distribution of abundance estimates for each transcript. This allows downstream differential expression tools like Sleuth to incorporate quantification uncertainty into statistical models, improving the reliability of conclusions drawn from RNA-seq experiments. The bootstrap approach is computationally efficient because it reuses the initial pseudoalignment results.

Kallisto incorporates models to correct for common RNA-seq biases that distort abundance estimates:

• Sequence-specific bias: Adjusts for the non-randomness of read coverage along transcripts caused by hexamer priming biases during library preparation.
• GC-content bias: Corrects for the correlation between fragment GC content and amplification efficiency. These bias models are learned directly from the data during the EM optimization, improving the accuracy of quantification without requiring external calibration datasets. The correction is particularly important for accurate isoform-level estimation where subtle biases can skew relative abundance ratios.

Kallisto has been extended with kallisto | bustools, a workflow specifically designed for single-cell RNA-seq data. This pipeline processes raw sequencing reads through pseudoalignment and generates gene- and transcript-level count matrices compatible with standard single-cell analysis frameworks like Scanpy and Seurat. The workflow handles unique molecular identifiers (UMIs) for deduplication and cellular barcodes for sample demultiplexing, all while maintaining the speed advantages of the core pseudoalignment approach. This makes it a competitive alternative to Cell Ranger for large-scale single-cell atlas projects.

Transcripts Per Million is the standard output unit for Kallisto and most quantification tools. TPM normalizes for both gene length and sequencing depth, ensuring that the sum of all TPM values in a sample equals one million. This allows direct comparison of transcript proportions across samples with different library sizes, unlike RPKM or FPKM which can produce inconsistent cross-sample comparisons.

The EM algorithm is the statistical engine inside Kallisto that resolves multi-mapping reads. It iterates between:

• E-step: Estimating the probability that each read originates from each transcript it pseudoaligns to
• M-step: Updating transcript abundance estimates based on these probabilities This converges to maximum likelihood estimates without ever assigning reads definitively to a single transcript.

The core innovation behind Kallisto's speed. Rather than computing exact base-by-base alignments, pseudoalignment determines whether a read is compatible with a transcript by checking if its k-mers appear in the transcript's de Bruijn graph index. This binary compatibility check is orders of magnitude faster than traditional alignment while retaining sufficient information for accurate quantification.

The high-throughput sequencing assay that Kallisto quantifies. RNA-seq captures the complete transcriptome by sequencing cDNA fragments, producing millions of short reads. The fundamental challenge is that reads from alternative isoforms share sequence, creating ambiguity that Kallisto resolves probabilistically through its EM-based abundance estimation rather than forcing unique alignments.

Systematic non-biological variation introduced by differences in sample processing, reagent lots, or sequencing runs. Kallisto's TPM output can still contain batch effects that confound downstream differential expression analysis. Tools like ComBat-seq or limma's removeBatchEffect are often applied post-quantification to correct for these technical covariates while preserving biological signal.