Bonsai reconstructs tree representations for distortion-free visualization and exploration of high-dimensional data.

Single-cell omics methods provide sparse, noisy measurements of high-dimensional cell states, whose underlying distributions remain poorly understood, raising an urgent need for exploratory analysis and visualization methods. However, current methods are ad hoc and uninterpretable, and they distort the structure in the data. We overcome these challenges by representing data on trees and present Bonsai, a method that reconstructs the most likely tree relating any set of high-dimensional objects with arbitrary heterogeneous measurement noise. Bonsai automatically regularizes noise, accurately recovers differentiation trajectories, preserves high-dimensional distances and improves nearest-neighbor identification. When applied to blood cell data, Bonsai not only accurately recovers known lineage relationships but also discovers a subtype of natural killer (NK) cells deriving from the myeloid lineage, pinpointing genes distinguishing myeloid NK from lymphoid NK cells. Bonsai has no tunable parameters, integrates downstream exploratory analyses methods with Bonsai-scout and scales to large datasets, making it applicable to visualizing the structure in any set of high-dimensional objects.