Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Authors: Da Kuang
GuanWen Qiu
Junhyong Kim
Venue: ICML 2025 poster (2025)
Keywords: Metric learning
Cell lineage reconstruction
scRNA-seq
Representation learning
Primary area: applications->health_medicine

Abstract: How a single fertilized cell gives rise to a complex array of specialized cell types in development is a central question in biology. The cells replicate to generate cell lineages and acquire differentiated characteristics through poorly understood molecular processes. A key approach to studying developmental processes is to infer the tree graph of cell lineage histories, which provides an analytical framework for dissecting individual cells' molecular decisions during replication and differentiation (i.e., acquisition of specialized traits). Although genetically engineered lineage-tracing methods have advanced the field, they are either infeasible or ethically constrained in many organisms. By contrast, modern single-cell technologies can measure high-content molecular profiles (*e.g.*, transcriptomes) in a wide range of biological systems. Here, we introduce *CellTreeQM*, a novel deep learning method based on transformer architectures that learns an embedding space with geometric properties optimized for tree-graph inference. By formulating the lineage reconstruction problem as tree-metric learning, we systematically explore weakly supervised training settings at different levels of information and present the *Cell Lineage Reconstruction Benchmark* to facilitate comprehensive evaluation. This benchmark includes (1) synthetic data modeled via Brownian motion with independent noise and spurious signals; (2) lineage-resolved single-cell RNA sequencing datasets. Experimental results show that *CellTreeQM* recovers lineage structures with minimal supervision and limited data, offering a scalable framework for uncovering cell lineage relationships. To our knowledge, this is the first method to cast cell lineage inference explicitly as a metric learning task, paving the way for future computational models aimed at uncovering the molecular dynamics of cell lineage. Code and benchmarks are available at: https://kuang-da.github.io/CellTreeQM-page

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Da Kuang' Guanwen Qiu
Junhyong Kim
Abstract
for uncovering cell lineage relationships. To our knowledge, this is the first method to cast cell lin- eage inference explicitly as a metric learning task, paving the way for future computational mod- els aimed at uncovering the molecular dynamics of cell lineage. Code and benchmarks are avail- able at: https: / //l////uuu /kuang-dua g titbb.b.. / Ce CellTreeQM page
How single fertilized cell gives rise to complex array of specialized cell types in development is a central question in biology. The cells replicate to generate cell lineages and acquire differenti- ated characteristics through poorly understood molecular processes. key approach to study- ing developmental processes is infer the tree graph of cell lineage histories, which provides analytical framework for dissecting individ- ual cells' molecular decisions during replication and differentiation (i.e., acquisition of specialized traits). Although genetically engineered lineage- tracing methods have advanced the field, they are either infeasible or ethically constrained in many organisms. By contrast, modern single-cell technologies can measure high-content molecu- lar profiles (e.g., transcriptomes) in a wide range of biological systems. Here, we introduce Cell- TreeQM, a novel deep learning method based on transformer architectures that learns an embed- ding space with geometric properties optimized for tree-graph inference. By formulating the lin- eage reconstruction problem tree-metric learn- ing, we systematically explore weakly supervised training settings at different levels of informa- tion and present the Cell Lineage Reconstruc- tion Benchmark facilitate comprehensive eval- uation. This benchmark includes (I) synthetic data modeled via Brownian motion with inde- pendent noise and spurious signals; (2) lineage- resolved single-cell RNA sequencing datasets. Ex- perimental results show that CellTreeQM recov- ers lineage structures with minimal supervision and limited data, offering a scalable framework
1. Introduction
Trachtonal Focus
Our Foous
Ganatype
Phenotype
DNA Sequences
Gene Expression Profies
Call
Cell НAАНИЛЯΔНИЯЯ
Dell
Cell
CellN HANクΛлаAнНОп
Cell
Figure I. Exploring saanotype-based cell lineage reconstruc- tion. This figure highlights the focus our study reconstructing cell lineage trees using phenotype data, specifically gene expres- sion profiles (right panel), in contrast traditional methods that rely genotype data, such as DNA sequences (left panel).
Understanding how a fertilized egg's 's repeated divisions and differentiation, i.e., the process of different cells acquiring unique characteristics (e.g., skin cell, muscle cell), gives rise to a fully formed embryo has been a long-standing goal in biology (Wolpert et al., 2015; Slack & Dale, 2021), key component of this developmental process is the tree- graph of cell lineages, which provides roadmap of how diverse cell types arise from a single progenitor (Clevers, 2011; 1; Shapiro et al., 2013; Wagner & Klein, 2020). The cell replication process cannot be directly observed in most organisms; therefore, inferring or reconstructing the cell lineage tree from features measured on the individual cells is an important challenge. Beyond organismal development,
DDepartment of Computer and Information Science, University of Pennsylvania, Philadelphia, USA 'Department of Biology, Uni- versity of Pennsylvania, Philadelphia, USA. Correspondence to: Da Kuang <<kuandda@ scas. www.n.eduu. Junhyong Kim <junhy- ong @ sas wpen..p >,
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
knowledge of cell lineages has wide biomedical applications including deciphering molecular processes underlying cell injury and repair, tumor development, degenerative diseases, etc. etc. (Zhang et al., 2020; Sivandzade & Cucullo, 2021)
explicitly encourages the learned embedding space to sat- isfy tree-metric properties, and show that stochastic gradient descent efficiently identifies generalizable embeddings.
Lineage Reconstruction Benchmark. We introduce a Lineage Reconstruction Benchmark comprising (a) syn- thetic datasets based on Brownian motion with independent noise and spurious signals, (b) lineage-resolved scRNA- seq datasets. Experimental results on the benchmark demon- strate that CellfrreQM efficiently reconstructs lineage struc- tures under weak supervision and limited data, providing a scalable framework for uncovering cell lineage relation- ships.
Currently, the gold standard for cell lineage tree reconstruc- tion is prospective lineage tracing (Kretzschmar & Watt, 2012). One popular approach leverages CRISPR-Cast to ge- netically engineer "recorders" exogenos DNA sequences that accumulate heritable mutations (Fig. 1, left). Although powerful, these recorders face key limitations. Their muta- tion capacity is constrained by the size of the target array, and the overall mutation rate may be uninformative. Most importantly, since it involves genetic engineering, it can only be used in contexts where such genome manipulation is feasible or ethical (McKenna & Gagnon, 2019; Zafar et al., 2020).
2. Key Challenges
Reconstructing cell lineage tree from phenolypic data con- ceptually parallels phylogenetics, which infers evolutionary relationships from discrete data such as aligned DNA or protein sequences. Classical phylogenetic methods typi- cally rely on well-defined stochastic models of sequence evolution (e.g., Jukes-Cantor) to estimate both topology and branch lengths (Felsenstein, 2003). In contrast, the use of phenotypic data for lineage reconstruction remains largely unexplored. We attribute this gap primarily to two key challenges, outlined below. These challenges collec- tively underscore why comprehensive lineage annotations re- main scarce and why robust methods for lineage reconstruc- tion port-patiuularly under incomplete or noisy labels- are urgently needed.
Meanwhile, before the availability of molecular sequences, there was a rich history of using phenotypes to infer lineage relationships via phylogenetic methods. For foundational results and methodologics in this field, we refer readers to (Kim & Warnow, 1999). Today, advancements in single cell biology have enabled high-content molecular pheno- type measurements from individual cells. For example, the total RNA content of cell, called the transcriptome, con- sisting of a vector of counts of different RNA species, can now be routinely obtained. An open question is whether such high-content molecular phenotyper peen contain suffi- cient information for tree reconstruction, and if so, what algorithm can be used to recover it (Fig. I. right).
Uncharacterized Stochastic Processes in Gene Expres- sion Data In phylogenetics, genetic evolution is often mod- eled using well-defined stochastic processes, which have been empirically validated across diverse datasets. These models provide a principled framework for lineage recon- struction, typically through maximum likelihood estimation.
We show a positive answer to the above question by introduc- ing CellTreeQM (Cell-Tree Quartet Metric), deep learn- ing framework built on transformer architectures that maps transcriptome data to an embedding space where distances reflect tree-like relationships. Our results demonstrate that reconstructing cell lineage structures from transcriptome data alone both tractable and data-efficient.
However, to the best of our knowledge, no well-established iineage-eependent process exists for phenotypic gene ex- pression data. In fact, during cell differentiation in most organisms, cells that acquire particular phenotypic states (i.e. cell types) are often not monophyletic (i.e. they do not orig- inate from a single branch of the cell lineage tree). This can result from biological phenomena such as self-organization and context-dependent processes. Moreover, distantly re- lated cells may converge to similar expression profiles due to functional similarity. For instance, in C. elegans, tran- scriptomic similarity initially correlates with lineage but diverges after gastrulation, illustrating how lineage signals can be lost as cells commit to specialized fates (Packer et al., 2019; Qiu et al., 2022; Bandler et al., 2022).
Our main contributions are as follows:
Formulating the Cell Lineage Tree Reconstruction Prob- lem. We frame the reconstruction of cell lineage trees as a metric learning problem and identify three practical settings: supervised, weakly supervised, and unsupervised (Fig. 2). Within the weakly supervised paradigm, we consider two realistic scenarios. In the high-level partition setting, biol- ogists possess prior knowledge of major clades within the lineage. In the partial-leaf labeled setting, lineage-tracing technologies provide topological labels for a subset of cells, with the objective of extrapolating these relationships to unlabeled leaves.
Proposed Solution. We present CellTreeQM, a feature learning framework for cell lincage tree reconstruction. In- spired by (De Soete, 1983), we design a loss function that
Despite these complications, transcriptomic data has been explored as auxiliary information for genetic lineage recon- struction (Zafar et al., 2020; Pan et al., 2023). Certain gene
2

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Phenetypii
*gg, Transcripttmm
Topelogy
CellieeQH
Deconetructed
High Level Partition Setting
Partial Labeled Leaves Setting
omount of prior information
Only high level.geeeeeoo. wrousiggggngggggoo.oo are asu labse
Only some leavto are evailabuu
Figure 2. Overview of CcIlTrecQM Workflow for Lineage Reconstruction Using Metric Learning
expression patterns have been successfully leveraged to re- construct portions of multicellular structures (Phillips et al., 2019; Shaffer et al., 2020; Rückert et al., 2022; Mold et al., 2024).
3. Related Works
Metric Learning Metric learning, also known con- trastive learning in the field of deep learning, has gained significant attention in recent years. These methods have been applied in both supervised and unsupervised settings, with the overarching goal of learning an embedding space where the distance between embedded points corresponds to desired similarity measure encodes semantic meaning. In this paper, we compare two widely used metric learning posses-triples loss (Schroff et al., 2015) and quadruplet loss (Chen et al.,
While the overall phenotype of the cell may not be con- sistent with cell lineage history, since cell lineages make destery-e key decisions during developmental dif- ferentiation, the cell is likely to contain some kind of history information within its complex molecular states.
Limited ground-truth lineage annotations A second ma- jor challenge is the lack of comprehensive labeled datasets recosstutonntttttii methods. Although technologies like CRISPR-based barcoding enable cell lineage labeling in certain contexts, they remain imprac- tical or ethically restricted for many organisms (McKenna & Gagnon, 2019; Zafar et al., 2020). Consequently, only a handful of single-cell datasets include comprehensive lin- rare exception: through
our proposed approach.
for training and evaluating
In the context of single-cell biology, contrastive learning methods have been applied to scRNA-seq data to construct embeddings that capture nuanced cellular states (Yang et al., 2022; Heimberg al., 2024). However, most existing ap- proaches focus cell-type classification or batch-effect correction rather than hierarchical structure or lineage re- construction, leaving an open question on how contrastive learning can be effectively leveraged for lineage inference.
eage annotations. C. elegans painstaking observation and direct tracking of cell divisions in the 1970s and 1980s, Brenner, Sulston, and colleagues established its complete embryonic lineage (Sulston et al., 1983). Beyond this worm model, fully resolved lineage annotations are virtually nonexistent in other species, and even partial annotations cell types are labeled- are both scarce and often incomplete (Domcke & Shendure, 2023).
Lastly, theoretical results (Bartal, 1996; 1998) have provided constructions that bound graph metrics by expectations over distributions of tree graphs. Observed empirical metrics or metrics in learned latent space could be seen as implying general graph metric and thus being associated with a distribution over tree graphs. Such distribution might be seen as probabilistic estimate of a cell lineage tree.
only certain branches or
A central reason for this scarcity is the inherent difficulty of reliably assigning lineage labels in single-cell data. There are multiple biological barriers. First, the majority of cell division and differentiation happens inside the body where, except some special cases, observation without sacrificing the animal is impossible. Second, cells are typically around 10 meters (10 micrometers) in size, making both visible traits and molecular measurements technically challenging and prone to noise. Lastly, the number of cells in typical multicellular organism is extremely large-for example, the human body comprises approximately 10 cells dolls-making tracking individual lineages extremely difficult.
Computational Methods for Cell Lineage Phylogenetic inference seeks to reconstruct evolutionary relationships among species or cells. The parameter space is vast and in- herently complex due to the combination of discrete topolo- gies and continuous branch lengths, making the problem NP-hard in most formulations (Felsenstein, 2003). Various reconstruction algorithms employing different heuristics and data assumptions have been developed and have achieved reasonable performance on typical phylogenetic datasets in practice. The most widely used approach relies her- itable barcodes (e.g., CRISPR-bass based recorders) and infers
3

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
trees using maximum parsimony or distance-based methods (Jones et al., 2020; Gong et al., 2022). Our method falls within the category of distance-based lineage reconstruction, where the objective is to fit the data to its closest tree metric. Such problems are known to be NP-hard for &1, f2, and &o metrics on unrooted trees. Nonetheless, substantial effort has been devoted to improving approximation algorithms for these problems (Ailon & Charikar. 2005).
clidean distance matrix of the vertices is additive (Chang, 1996).
Lemma 4.1. (Additivity of Expected Distances) For data generated by Markov process on tree T,, the expected squared Euclideun distance between two leaves i and j satisfies the additive distance property:
D8 [[[|x: [1xx=1x,111= =T (i.j)))
where Dr,i, is the shortest path distance in T.
Recently, several studies have explored integrating gene expression data with barcode-based lineage inference to enhance reconstruction accuracy (Zafar et al., 2020; Pan et al., 2023). Notably, the most recent work (Schlüter & Uhler, 2025) investigates whether gene expression alone contains sufficient information for lineage reconstruction and reports promising results. In our study, we conduct similar permutation experiments assess the feasibility of our approach. To the best of our knowledge, we are the first to reconstruct lineage solely from gene expression data and to curate benchmarks for this task under diverse scenarios and varying degrees of supervision.
In practice, real phenotypic data often violate these assump- tions due to non-heritable effects, mcasurement noise, and convergent gene expression. These factors can be more problematic than the challenge of fitting an optimal tree, yet they have received limited attention in the literature. This is likely because phylogenetic data are typically preprocessed and curated by experts, whereas phenotypic data lack such standardized cleaning.
Thus, instead of relying solely on tree-fitting methods, we propose learning an embedding function that maps data points to a space where distances approximate an additive metric. Formally, given phenotype vectors 2; RR" for leaf vertices i, we jointly search for a tree topology T and an embedding function f R2 + E that optimizes:
4. Problem Formulation: Cell Lineage Reconstruction
4.1. Distance-Based Lineage Reconstruction
min [P([(()) 1r + Xi()). f.r
Given a dissimilarity matrix D, the goal of a cestance-based approach is to solve the following optimization problem:
where S2(f) is regularization term that prevents overfitting, weighted by X.
min | - - TET
4.2. Scenarios
where T denotes the space of all tree metrics, also called additive distance matrices. This problem known to be NP- hard in the general case. However, when the deviation from perfect tree metric is small, efficient algorithms exist that reconstruct the exact optimal tree. For instance, sufficient condition for the Neighbor-Joining (NJ) algorithm (Saitou & Nei, 1987) to reconstruct the optimal tree is:
Supervised sefting, We assume that we have the true ad- ditive distances of the edge-weighted tree for every pair of leaves. The model is trained to embed the leaves such that | - 23 || is proportional to the known tree distances. At test time, the task to recover the lineage relationships of new data using the learned embedding.
||d' ll S xx/22
Weakly Supervised Setting. In many biological contexts, we do not have full access to the ground-truth lineage. In- stead, only partial or coarser annotations are available, and we aim to generalize to the unknown vertices. We highlight two practical cases:
where x" denotes the shortest edge length in T' (Atteson, 1999).
motivation for this distance-basee formulation arises from the fact that leaf data generated by Markov tree stochastic process will have its Eg distance close to an additive matrix. Formally, we assume vector-valued Markov process the tree graph, where for a vertex:
High-Level Partition Setting. Biologists may know small number of large "clades" (subtrees). For example, certain groups of cells are known to belong to distinct subtrees of the full tree.
pro parent(z:), tz),
Partial-Leaf Labeled Setting. Some cells (vertices) have identified lineage tree graphs (e.g., datherr cell pairs) obtained from, say, direct lineage-tracing experi- ments, but such information is absent for the majority of cells.
I; is the random state variable, t; is the time scaling to the parent vertex for the i-th element. We assume this probabil- ity is well-defined, either by a continuous-time finite-state Markov process or by a continuous-time Brownian motion process. Under this assumption, the expected squared Eu-
Unsupervised Setting, No explicit lineage information

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
available at all. The model relies solely on the raw pheno- typic data and data-driven estimation of desired metric prop- erties of the embedding. This scenario is the most challeng- ing because the algorithm must disentangle lineage-related signals from confounding variation in the data without any
5.1. Additivity Loss via the Four-Point Condition
The additivity loss is derived from a classic property of an additive distance matrix known the four-point condition (Theorem C.I). Denote quartet of leaf vertices i, k, and define the following distance sums:
direct lineage cues.
S (zi, z3) + D(zk, z1),
4.3. Constructing the Tree
5 = D zx) + D(zj, 21):
After learning the embeddings [z:} in which pairwise dis- tances approximate the true tree distances, the next step is to build the lineage tree T. We use the NJ algorithm by de- fault, which runs in time O(z²) for n taxa. This is typically manageable for moderate dataset sizes. More discussion about phylogeny reconstruction is in $C. Additionally, we present an experimental comparison of different reconstruc- tion methods under the supervised setting in $G.3.
53 -2; zi) + D2zj, =k)-
If D is an additive tree distance matrix, two of these sums match exactly and both exceed the remaining sum. In addition, the ordering of all quartets defines a unique un- rooted tree topology. Considering the relaxed case where -(--) are not additive, we define terms that measure de- viation from additivity. Assume we have an ordering S3. We define:
S 2 S2 2
Leoose measures the gap between the top two sums and as a loss function encourages the two terms to be equal,
4.4. Evaluation Metrics
We evaluate the reconstructed tree î against the ground- truth tree T using the following metrics. Additional details can be found in $G.2.
Lelose- = |S S2/-
Push enforces margin so that the smallest sum (Sx) is sufficiently smaller than the average of the top two,
Robinson-Foulds (RF) Distance. The Robinson-Foulll (RF) distance quantifies the topological difference between two unrooted trees by comparing their sets of partitions, where a partition corresponds to bipartition of the taxa induced by an internal edge. The RF distance counts the number of partitions that differ between the inferred and true trees. We report the normalized RF distance, where indicates identical tree topologies and implies that no partitions are shared between the two trees.
S S2 + mn
Cpush
S
2
where mo >> 0 is a margin hyperparameter.
We combine them into a single quartet loss: Lquanet Letose + Lpsss then average over all (or a sampled subset of)
quartets Q in each training batch:
Luddivity
Σ Q
fquarter
Quartet Distance (QD). Although the RF distance is widely used in the literature, it is known to be insensitive to finer- grained subtree structures. To complement RF distance, we also report the Quartet Distance (QD) (Bryant et al., 2000). Given any four leaf vertices (i.e., a quartet of leaves), there are three possible unrooted tree topologies that describe their relationships. The quartet distance is computed as the fraction of quartets that are resolved differently in the two trees. For large trees, the quartet distance is approximated by randomly sampling a subset of leaf quartets.
Figure 3 illustrates the geometric intuition of the loss. Under ideal additivity, the four points form an unrooted tree (Figure 3a), where S1 D(A, C) + D(B, and S2 D(A, D) + D(B,C) and S Sz. When additiv- ity is violated, this balance is disrupted, and the structure can be imagined as a "box" with an extra edge (Figure 3b), The Leoose term encourages the top two distance sums to become more similar, thereby reducing the asymmetry that creates the box-like distortion. In effect, it ensures that the box is not "fat". Meanwhile, the Lpssh term increases the gap between the smallest sum and the average of the top two, effectively "widening the bridge." This widening en- hances the tree model's robustness to noise and distortions. We note that the ordering S 2 S2 2 S3 can be derived from supervised knowledge of the true quartet tree or from computations of the empirical data in the latent space.
5. Proposed Framework: CellTreeQM
We present CellTreeQM (Cell Tree Quartet Metric), a frame- work designed reconstruct lineage relationships from phenotypic data. Our main objective is to learn embed- ding function based on the assumption of additive pairwise distances. Our approach is to consider quartets of leaves and learn an embedding that optimizes tree-metric properties of known quartets in the latent space.
5.2. Regularization: Deviation Loss
To prevent the learned embedding from drifting too far from the original data, we introduce a deviation loss Ω. This loss
5

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
(a)
(b)
ful relationships based on the feature similarities between cells. We compared the performance of networks with Trans- former encoders as backbones versus those using fully con- nected layers, under a supervised setting on two C. elegans real datasets (see Table.5 in the Appendíx). Networks with attention modules performed much better than the fully con- nected counterparts.
Close
1
Push
Figure 3. Geometric Intuition of the Quartet Loss
6. Cell Lineage Reconstruction Benchmark
penalizes large discrepancies between the original and the induced distance matrix, D(X) and D(J(X)), respectively, in the latent space:
To systematically evaluate lineage-reconstruction methods, we introduce benchmark comprising a synthetic dataset and three scales of tineage-resolved real datasets. Figure shows the training dynamics Ce on both the synthetic and real datasets under the supervised setting. $D provides detailed dataset descriptions, parameter choices, and curation procedures.
1 X) = N II(((X)) - D(X)
where || - || denotes the squared Frobenius norm and N is the number of points. This ensures that the latent space remains faithful to the measured phenotypic similarities and also prevents the learning process from degenerating in scale.
Eineae-Resolved C. elegans Dataset: Among model organisms, C. elegans is uniquely suited for benchmarking lineage reconstruction because its embryonic cell lineage is invariant. We curate three subsets of increasing size-C. elegans Small, Mid, and Large- from transcriptomic atlases by Packer et al. (2019) and Large al. (2024), containing 102, 183, and 295 leaves, respectively. Each subset is fully lineage-resole resolved, providing ground-truth tree topologies. These datasets allow us to measure reconstruction quality at multiple scales.
5.3. Feature Gating
Many high-dimensional phenotypic datasets (e.g., ScRNA- seq) include numerous features that do not reflect lineage- related variation. To address this, we introduce a feature gating module, which adaptively modulates the contribu- tion of each input feature. By emphasizing Linage-relevan signals and down-weighting confounding or redundant at- tributes, the gating module can improve downstream tree reconstruction. To learn an effective feature mask, we use Gumbel-Softmas (Gumbel, 1954) approach that promotes discrete gating decisions (see $F.2). The gating is applied via a simple elementwise product: H; = D; Jt-
Synthetic Brownian-Motion Simulations: We generate synthetic datasets by simulating random branching trees and evolving feature vectors along branches via Brownian mo- tion. To better reflect real-world noise, we add independent Gaussian noise and "alternative-tree" features that follow a separate confounding lineage. By tuning parameters such as the number of leaves and the relative strengths of sig- nal and noise, we generate datasets with varying levels of reconstruction difficulty.
Integrated Objective. Combining Gumbel gating with our core metric-learning objectives, we arrive the overall optimization function:
min (uutmiviyy (f g, X) + ASl(f o X) + ② (sparsity) fig
gales
7. Experiments
This integrated framework allows us to jointly learn which features are most informative for lineage reconstruction and how to embed them to satisfy the quartet-based additivity constraints.
7.1. Baselines
We consider the following two common contrastive losses in metric learning. The details can be found in $G.1. Cell- TreeQM and baselines produce learned embedding spaces from which we extract pairwise distances between leaves.
5.4. Model Architecture
Our proposed framework, CellTreeQM, aims to learn embed- dings from high-din nigh-dimmnsional phenotypic data that facilitate phylogenetic reconstruction. To effectively learn relation- ships among cells, we use sequence of Transformer en- coder blocks as the backbone of the network, illustrated in Figure 11. Unlike classical Transformer models, we do not include positional encodings, as our input leaves are not inherently ordered. Without positional constraints, the self-attention module focuses purely on learning meaning-
Triplet Loss:
We designate the closest pair from each quartet as anchor pretiire and the farthest leaf negative. The loss encourages [| S(P) < (I((A) S(N)].
Quadruplet Loss: Extends Triplet Loss by introducing a second negative leaf, enforcing additional pairwise margins to improve global distance structure.
6

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Training on Simulation
Training elegans
14
(b)
(c)
(d)
18:00
Seariv RF
Selected
Number Seterted
-200
Steps
Steps
Steps
Streps
Training RF
Testing RF
Moan of selected features
Selected Signala
Selected Noise
Selected Feetures
4 Gazes
Figure 4. Supervised training dynamies on simulation and C. elegans Small dataset. Dashed purple is the Pagel's À for Phylogeny signal.
Table 1. Supervised results on the C. elegans Small dataset. Di- reet reconstruction on raw data yields RF = 0.923 and QDist = 0.554. Suffix "-G" denotes feature gating, and "-p" indicates label permutation. The reported values are means across three runs, with standard deviations in parenthescs.
Train RF and low A%RF. This is reasonable because neither contrastive loss explicitly enforces tree topology in the em- bedding space. Additionally, feature gating (-G) typically yields additional gains, especially in RF distance, likely by pruning out non-heritable or noisy gene expressions.
Train RF $
A A&RFT f
A A% QDist f
Permutation experiments validate quartet- fitting. Training CellTreeQM on the random tree T" still embeds the data with moderate fidelity, but less accurately than with the true tree. In contrast, triplet and quadruplet models struggle to align random tree with the data in a similar manner. Sim- ilar trends hold for the C. elegans Mid and Large datasets, where triplet/quadruplet losses improve over raw data but still lag behind CellTreeQM (see Table 8). These results echo the recent findings in (Schlüter & Uhler, 2025) show- ing that true lineage topologies yield lower training losses and more generalizable embeddings, thus confirming there is ample lineage signal in the gene expression data-on our method is not merely overfitting.
CellTreeQM
0.000 (0.00)
0.690 (0.05)
0.867 (0.02)
QMI
0.000 (0.00)
0.757 (0.03)
0.848 (0.01)
CellTreeQM--p
0.013 (0.00)
0.434 (0.04)
0.691 (0.05)
Triplet
0.519 (0.03)
0.179 (0.01)
0.637 (0.02)
Triplet-G
0,545 (0.03)
0.203 (0.03)
0.631 (0.02)
Triplet-p
0.677 (0.06)
0.037 (0.01)
0.385 (0.06)
Quadruplet
0.057 (0.00)
0.454 (0.02)
0.784 (0.01)
Quadruplet-G
0,061 (0.00)
0.484 (0.04)
0.791 (0.01)
Quadruplet-p
0.118 (0.00)
0.149 (0.01)
0.538 (0.02)
7.2. Supervised setting
Similar to (Schlüter& & Uhler, 2025), we conduct experi- ments in a supervised scenario where all quartet topologies are assumed known and we train a model that enforces such topology in the embedding space. While this setting has little empirical significance, its results justify the soundness of our approach. We use A RRF and A%QD (see Eq.3) to measure relative improvement over raw data and Training RF to assess how well the learned embedding preserves the global tree structure implied by the quartets.
Figure 12 (2D t-SNE) shows that CellTreeQM better pre- serves the hicrarchical structure than Triplet or Quadruplet. Figure 13 further illustrates the reconstructed trees, where CellTreeQM yields lineage-consistent subtrees.
7.3. Weakly Supervised
High-Level partition setting. level defined as the number of branching steps from the root. We assume we know how leaves are divided into clades at each level, as well as the relationships among these clades (see Fig. 2 left). Hence, each leaf is assigned to exactly one of these high-level clades, but the tree structure within for each clade remains unknown. Suppose we know that the leaves par- tition into four groups. Given quartet, if there is least one pair of leaves that exactly belong to one group, can uniquely determine the correct topology among the three possible unrooted trees. We call these "known quartets". Otherwise, we call it an "unknown" quartet.
Table 1 shows results on the C. elegans Small dataset, whose direct reconstruction yields high RF (0.923), suggesting almost no lineage information. We train each method both with and without feature gating (-G). Additionally, to test whether our method can overfit to any given topology, we randomly permute (-p) the labels of the leaves of T to obtain an arbitrary tree T' for training. Several key trends emerge:
Cell'reeQM consistently outperforms contrastive losses. By explicitly enforcing the four-point condition across quar- tets, CellTreeQM consistently achieves higher improvement over raw data RR and A%QD) compared to the triplet and quadruplet baselines. Moreover, triplet loss can re- cover moderate level of quartet topology, but its latent space not aligned on the global tree topology with large
We compute the additivity loss only on the known quartets. We then evaluate on the full set of leaves, measuring the overall RF distance and quartet distance (QD) against the
7

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table 2. Weakly supervised results on C. elegans Small under different partition levels. K-QD and U-QD are quartet distances on the known and unknown quartets, respectively. The reported values are means across five runs, with standard deviations in parentheses.
7.4. Unsupervised Setting
Lastly, we present preliminary results under the unsuper- vised regime, where quartet constraints partial subtree information are given. Here, use data-driven estimate of quartet order in the latent space. CellThreQM can still learn a representation that partially adheres to tree-metric properties in the constrained setting of the simulation data, but the performance on real data was limited, suggesting better strategies are needed. See details in $G.5.
Method
R
A%QDI
A%K-OD1
AGU-QDT
Partition Level: 3
CelffreeQM
0,349 (0.02)
0,849 (0.01)
0.994 (0.00)
0,182 (0.03)
Triplet
0.193 (0.02)
0.521 (8.01)
0.582 (0.02)
0.241 (0.00)
Quadraplet
(0.022)
0.619 (0.01)
0.768 (0.01)
-0.65 (0.01)
Purtition Level: 2
CellTreoQM
0.274 (0.03)
1,805 (0.022
0.9%8 (0.08)
0,558 (0.04)
Triplet
0.191
0.399 (0.01)
0.625 (0.01)
0.111
Quadruplet
(0.01)
0.485 (8.01)
0.894 (0.01)
-0.037 (0.01)
Purtition Level:
1.0
35
CellTreeQM
0.164 (0.01)
0.631 (0.05)
0.997 (0.00)
0.483 (0.077
Triplet
0.120 (0.02)
0.356 (0.01)
0,852 (0.01)
0.167 (0.02)
30
Ciaals/Nois
Quadraplet
(0.02)
0.227 (0.01)
(0.02)
0,046 (0.01)
Relative RF
0.8
25
Signals 1ignals
ground-truth tree. Additionally, we separate quartets into known versus unknown and track QD for each group (K-QD for known quartets, U-QD for unknown).
0.6
20
Selected wigdSige
15
0.4
10
Table 2 summarizes performance for varying levels on the C. elegans Small dataset. In all cases, Ce outper- forms contrastive baselines: it more effectively leverages the known quartets while generalizing better to the unknown ones. By contrast, the quadruplet loss fails to generalize to unknown quartets and can even underperform the raw distance. At level 3, triplet loss does better on the unknown quartets than CellTreeQM,, but it does so at the cost to the known quartets, illustrating its difficulty in balancing partial lineage supervision with global tree structure.
0
5
10
15
20
25
30
35
Steps
CellTreeQM
Optimal
Signals
Noise
Figure 5. Training dynamics of CellTreeQM in a purely unsu- pervised setting on a simulated dataset. Optimal is the RF of reconstructed tree only based on signal fcatures.
Partial-Labeled Leaves Setting, In this scenario, only subset of leaves (c.g., 30%, 50%, or 80%) have known lin- eage information, while the remaining leaves are unlabeled (see Fig. 2 right). We classify quartets as Known when all four leaves are labeled, Unknown if none are labeled, and Partial otherwise. During training, we only apply the addi- tivity loss to Known Quartets. After training, embed all leaves and compute overall RF distance and QD, alongside three specialized QD metrics for Known (K-QD), Partial (P-QD), and Unknown (U-QD) quartets.
8. Discussion
Summary. We introduce CellTreeQM, deep learning framework for reconstructing cell lineage trees from phe- notypic features via metric learning. The key idea is that certain geometric structures are well-suited for represent- ing tree-graph relationships. Therefore, we formulate our problem as learning a latent space whose metric properties are optimized for quartets of tree-graphs. To our knowledge, this is the first method to cast cell lineage inference explicitly as metric learning problem. Empirical results in super- vised and weakly supervised settings show that CellTreeQM considerably improves lineage reconstruction accuracy over standard contrastive baselines (e.g., triplet and quadruplet losses). This suggests that transcriptomic data contain cryp- tic lineage information that can be uncovered with carefully designed metric learning models.
As shown in Table 3, CellTTeeQM outperforms the con- trastive baselines across all labeling fractions, particularly at 80% and 50%. At 30% labeling. however, all methods yield limited improvement on P-QD and U-QD, highlighting the difficulty of reconstructing lineage from randomly sampled sparse supervision. Notably, although the Quadrupler loss tended to overfit in the high-level partition scenario, it per- forms strongly here, surpassing Triplet and approaching CellTreeQM moderate labeling fractions.
I Limitations. Despite its advantages, CellTreeQM has several limitations. First, our loss function integrates tree- metric constraints, gating, and distortion regularization. Al- though the distortion term limits the deviation of the latent space geometry from input feature space, it can impede
Additional results. To further validate CellTreeQM, we evaluated the model on two additional CRISPR- based mESC lineage datasets within the high-level partition set- ting. Results are provided in ST.
8

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table Weakly supervised results on elegans Small across different known fractions. K-QD, P-QD and U-QD are quartet distances on the known, partial and unknown quartets, respectively. The reported values are means across ten runs, with standard deviations in parentheses.
Method
Train RFL
A A%RF1
A% A
A A%K-QD1
A A%P-QD1
A%U-QD1
Known Fraction: 0.8
CcllTrecQM
0.024 (0.03)
0.448 (0.06)
0.842 (0.05)
0.999 (0.00)
0.742 (0.07)
0.465 (0.13)
Triplet
0.454 (0.06)
0.175 (0.05)
0.728 (0.03)
0.895 (0.01)
0.624 (0.05)
0.339 (0.14)
Quadruplct
0.066 (0.04)
0.403 (0.03)
0.796 (0.06)
0.953 (0.02)
0.697 (0.09)
0.435 (0.22)
Known Fraction: 0.5
CcllTreeQM
0,012 (0.01)
0.092 (0.05)
0.609 (0.05)
0.999 (0.00)
0.598 (0.06)
0.398 (0.05)
Triplet
0,303 (0.09)
0.049 (0.04)
0,505 (0.05)
0.879 (0.02)
0,493 (0.05)
0,304 (0.06)
Quadruplet
0.023 (0.02)
0.115 (0.04)
0.549 (0.04)
0.934 (0.03)
0.537 (0.04)
0.340 (0.06)
Known Fraction: 0,3
CellTreeQM
0.000 (0.00)
-0.023 (0.02)
0.368 (0.06)
1.000 (0.00)
0,401 (0.06)
0.250 (0.06)
Triplet
0.156 (0.06)
-0.001 (0.02)
0.358 (0.04)
0.889 (0.02)
0.384 (0.04)
0.263 (0.05)
Quadruplct 0.008 (0.02)
-0.020 (0.03)
0.358 (0.03)
0.918 (0.04)
0.386 (0.03)
0.259 (0.02)
learning when lineage signals in real data are significantly distorted. While gating helps suppress random noise in sim- ulations, its impact on real data is mild, suggesting that real "noise" features may be correlated with signal features. Sec- ond, we rely on NJ for final tree construction. Although NJ is widely adopted, it can fail under complex noise conditions. Future research could explore more robust tree-inference methods, such as Bayesian approaches or graph neural net- works. Third, our benchmarks focus on lineage-resolved datasets with well-defined ground truth. Extending Cell- TreeQM more heterogeneous single-cell datasets (c.g., developmental atlases with partial lineage annotations) will be crucial for broader applicability.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning as applied to a specific biomedical problem. There might be potential societal consequences of our work related to enhancing the understanding of human diseases. But we do not foresee any potential impact that requires specific highlighting.
References
Ailon, N. and Charikar, M. Fitting tree metries: Hi- erarchical clustering and phylogeny. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). pp. 73-82, October 2005. doi: 10.1109/ SFCS,2005.36. URL https: / wtteeeeeeeeeeeeeeeeeeeeeeeeeeeee ieee. ozg//docueet/t53333 11530703, ISSN: 0272-5428.
Guidance for Future Work. The modest success of un- supervised CellTreeQM on small, clean simulations opens the door to future improvements. Additional data-driven methods for determining the optimal latent space geometry, as well as more extensive hyperparameter tuning, may fur- ther enhance performance. In real single-cell transcriptome datasets, the phenotype-lineage correlation can be weak, particularly at later stages of development; thus, stronger regularization or heuristic constraints might be needed. Nev- ertheless, our initial findings show that unsupervised ap- proaches can capture coarse lineage structure without plicit topologiaal supervision. We believe that learning metric properties of the latent space, rather than directly trying to infer the tree-graph, can be an effective approach.
Aran, D., Looney, A. P., Liu, L., Wu, E., Fong, V., Hsu, A., Chak, S., Naikawadi, R. P., Wolters, P. J.J Abate, A. R., Butte, A. J., and Bhattacharya, M. Reference-based anal- ysis of lung single-cell sequencing reveals a transitional profibrotic macrophage. Nature Immunology, 20(2):163- 172, February 2019. ISSN 1529-2916.
doi: 10.1038/
s4 $41590-018-02761 URL https: /www. nature. com com/arttcles////ocoooocoo 415p/////5999--0 099000000000 0100011-66661 Publisher:
Nature Publishing Group.
Arendt, D., Musser, J. M., Baker, C. V. H., Bergman, A., Cepko, C., Erwin, D. H., Pavlicex, M., Schlosser, G., Wid- der, S., Laubichler, M. D., and Wagner, G. P. The origin and evolution of cell types. Nature Reviews Genetics, 17 (12):744-757, December 2016. ISSN 1471-0064. doi: 10. 10.1038/mr.22016.227 URL https: /www. nature. com/ http///ttcllees/rg..... 201 6 127. Number: 12 Pub- lisher: Nature Publishing Group.
Acknowledgements
This work was partially supported by the National Institutes of Health (NIH) under grant R01 HD1HDD00811
Atteson, K. The Performance of Neighbor-Joining Methods of Phylogenetic Reconstruction. Algorithmica, 25(2):
9

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
251-278, June 1999. ISSN 1432-0541. doi: 10.1007/ PL00008277. URL pnttps://doi. 00.0 PL00008277.
$41586-019-1184-5. URL https://tm/t //ww www.r...
Publisher:
Nature Publishing Group.
Bandler, C., Vitali, I. Delgado, R. N., Ho, M. C., Dvoretskova, E., Ibarra Molinas, J. S., Frazel, P. W., Mohammadkhani, M., Machold, R., Maedler, S., Lid- delow, S. A.. Nowakowski, T. J., Fishell, G., and Mayer, C. Single-cell delineation of lineage and ge- netic identity in the mouse brain. Nature, 601((893); 404-409, January 2022. ISSN 1476-4687, doi: 10.1038/ $41586-021-04237-- URL http:: http://www........eee com/articnn 002414100000002------1111
Chang. J. T. Full reconstruction of Markov models on evolutionary trees: Identifiability and consistency, Mathematical Biosciences, 137(():51-73, October 1996. ISSN 0025-5564. doi: 10.1016/S0025 00005000000005555400009000777222 URL
htttss://ww.scceenceee
Chen, W., Chen, X., Zhang, J., and Huang, K. Beyond Triplet Loss: A Deep Quadruplet Network for Person Re-identification. In 2017 IEEE Conference on Com- puter Vision and Pattern Recognition (CVPR), pp. 1320- 1329, Honolulu, HI, July 2017. IEEE. ISBN 978-1 1-5386- 0457-1. doi: 10. 10.1109/CVP..2007..44 URL http: i eeeeppl ore eee org/ document///////////////mm 8099628/.
Pub-
lisher: Nature Publishing Group.
Bartal, Y. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science,
pp. 184-193, October 1996. doi: 10. N0.1109/SFCS.199 548477. URL https::tt//.omm beeeepleoe ore. leee. org/ document/548a5 548477. ISSN: 0272-5428.
Clevers, H. The cancer stem cell: premises, promises and challenges. Nature Medicine, 17(3)311-319, March 2011. ISSN 1546-170X. doi: 10.1038/ nm.2304. URL https: //ww: articles/ nm. 2304. Publisher: Nature Publishing Group.
Bartal, Y. On approximating arbitrary metrices by tree metrics. In Proceedings of the thirtieth anmual ACM symposium on Theory of computing, STOC '98, pp- 161-168, New York, NY, USA, May 1998. Associa- tion for Computing Machinery. ISBN 978-0-89791-962 3. doi: 10.1145/276698 276725. URL https://d.. 276725.
com/
Clevers, H., Rafelski, S., Elowitz, M., Klein, A., Shen- dure, J., Trapnell, C., Lein, E., Lundberg, E., Uhlén, M., Martinez-Arias A., Sanes, J. R., Blainey, P., Eber- wine, J., Kim, J., and Love, J. C. What Is Your Con- ceptual Definition of "Cell Type" in the Context a Mature Organism? Cell Systems, 4(3):255-259, 2017. URL attps://uunt kb. se/resollweeeeeeeeee surolveuurn-u nbn so:::se:thh.. diaa 206700. Publisher: CELL PRESS.
acm. wem.orgg/ee. wwgg/oi///i http://o//1..11///211. 1111/111166611
Bergen, V., Lange, M., Peidli, S., Wolf, A., and Theis, J.J. Generalizing RNA velocity to transient cell states through dynamical modeling. Nature Biotechnology, 38( 1408- 1414, December 2020. ISSN 1546- 1646-1696. doi: 10.1038/
$41587-020-0591-3, URL https: www. http://wwwww....t.tteeet nature. com/articles s4 4415577-557 0005557-70000 059--0009111300 Publisher:
Nature Publishing Group.
Crowley, G., Alon, U., and Quake, S. R. An Atlas Cellular Archetypes, December 2024. biorxiv..ivvvii.....ii..i www.biiiwwoooooooooo.oo.o 10. 10.1101/2024.1 12. 04. 626890v1. 2024.12.04.62889 Section: New Results.
URL
Bryant, D., Tsang, J., Kearney, P., and Li, M. Comput- ing the quartet distance between evolutionary trees. In Proceedings of the eleventh annual ACM-SIAM sympo- sium on Discrete algorithmss, SODA '00, pp. 285-286, USA, February 2000. Society for Industrial and Applied Mathematics. ISBN 118-0---877--55--1
Pages:
Cui, H., Wang. C., Maan, H., Pang. K., Luo, F., Duan, N., and Wang, B. scGPT: toward building a foundation model for single-cell multi-omics using generative AI. Nature Methods, 21(8):147011480 doi: 10.1038/
Cavalli-Sforzz L. L. and Edwards, W. Phylogenetic analysis. Models and estimation procedures. American Journal of Human Geneties, 19(3 Pt 1):233-257, May 1967. ISSN 0002-9297, URL https: www.//www.oo ncbi. nlm. nih httphh/////p/aaaraacae//////////
August 2024. ISSN 1548-7105.
s41 4411522-02-02201-0 URL httpps:/wwat http:://wwww......ee nature. com/ htt//articcsssssem 41592 024 02201-0.
Pub-
lisher: Nature Publishing Group.
Chan, M. M., Smith, Z. D., Grosswendt, S., Kretzmer, H., Norman, T. M., Adamson, B., Jost, M., Quinn, J. J., Yang. D., Jones, M. G., Khodaverdian, A., Yosef, N., Meissner, A., and Weissman, J. S. Molecular record- ing of mammalian embryogenesis. Nature, 570(7759): 77-82, June 2019. ISSN 1476-4687.
De Soete, G. A least squares algorithm for fitting additive trees to proximity data. Psychometrika. 48(4):621-626 December 1983. ISSN 0033-3123, 1860-0980. doi: 10.
1007/BE02293884, URL http: 1ink....... http::/iiin.ninineeee.... springer. 100/10.1007/BF02200
doi: 10.1038/
10

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Domeke, S. and Shendure, J. A reference cell will serve science better than reference cell at- las. Cell, 186(61,1103-1114, March 2023, ISSN 0092-8674, 1097-4172. doi: 10.1016ff.cell.2223. 02.016. URL. httpt::t///t/...p. http:://wwwwceeo www.wwellllleeee.... com/ cell/
1-10, November 2024. ISSN 1476-4687. doi: 10.1038/
$41586-004--88111-y URL https://www nature.
024 08411-y. Pub-
lisher: Nature Publishing Group.
Heumos, L., Schaar, A. C., Lance, C.. Litinetskaya, A., Drost, F,, Zappia, L.,, Lücken, M. D., Strobl, D. C., Henao, J., Curion, F., Schiller, H. B., and Theis, F. J. Best practices for single-cell analysis across modalities. Nature Reviews Genelics, 24(8):550- 572, August 2023. ISSN 1471-0064. doi: 10.1038/
abstract/S0092-8855 (23) 00159-1111100 Publisher: Elsevier.
Faith, D. P. Conservation evaluation and phylogenetic diver- sity. Biological Conservation, 61(1):1-10, January 1992. ISSN 0006-3207. doi: 10.101660000332077222999990 URL httpss//www.scceenccireeee ssleance/arriccl///////o02222222
$#1576-023-005866w URL https: //ww. wttp.//tww......././//////. set.c/eeeeeee5661--- 000----2200088-- (
Pub-
lisher: Nature Publishing Group.
Farach, M. Kannan, S., and Warnow, T. A robust model for finding optimal evolutionary trees. Algo- rithmica, 13(1-2):155-179 February 1995. ISSN
Hu, C., Li, T. Xu, Y., Zhang, X., Li, F., Bai, J., Chen, J., Jiang, W., Yang, K., Ou, Q. Li, X., Wang, P., and Zhang. Y. CellMarker 2.0: an updated database of manu- ally curated cell markers in human/mouse and web tools based on scRNA-seq data. Nucleic Acids Research, 51 (D1):D870-D876, January 2023. ISSN 0305-1048, doi: 10. 10.1093/nar/gkacc44,, URL https::///// /ooi org/10,
0178-4617. doi: 10.1007/BF01188585 URL
http://wwe scopus. http:/ppsw..om/i/aa//////eeee/ee url hut2ago=0222112222garrreeeeeed
Felsenstein, J. Inferring Phylogenies. Sinauer Associates is an imprint of Oxford University Press, Sunderland, Mass, 1st edition edition, September 2003. ISBN 978-0-87893- 177-4.
lanevski, A., Giri, A. K., and Aittokallio, T. Fully- automated and ultra-fast cell-type identification using specific marker combinations from single-cell tran- scriptomic data. Nature Communications,, 13(1):1246,
Gascuel, O. Concerning the NJ Algorithm and its Unweighted Version, UNJ.
https::/citteseex..sstt 1997. URL
March 2022.
ISSN 2041-1723. doi: 10.1038/
4414677022-28803--2 URL https: //ww. nature. com http//atcceesss4110 / 677022-2880---
Pub-
lisher: Nature Publishing Group.
Gong, W., Kim, H. J., Garry, D. J., and Kwak, I.-Y. Sin- gle cell lineage reconstruction using distance-based al- gorithms and the package, DCLEAR. BMC Bioinfor- matics, 23(1):103, March 2022. ISSN 1471-2105. doi: 2220299999922222233.... URL https://ddo. /doā. 1tt.:11///1111902200000
Ilse, M., Tomezak, J. M., and Welling, M. Attention- based Deep Multiple Instance Learning, June 2018. URL http: / arxiv org/ abs 1ww../1cc...0 04712. arXiv: 102.0470..
Jones, M. G., Khodaverdian, A., Quinn, J., Chan, M. M., Hussmann, J. A., Wang. R., Xu, C., Weissman, J. S., and Yosef, N. Inference of single-cell phylogenies from lineage tracing data using Cassiopeia. Genome Biology, (1(1); April 2020. ISSN 1474-760X. doi: 10.1186/ s $13059-020-020000 URL https: //wii/oiiio/ org/10. 1186/
Gumbel, E. J. Statistical Theory of Extreme Values and Some Practical Applications. A Series of Lectures. Technical Report PB175818, National Bureau of Standards, Washington, D. C. Applied Mathematics Div.,
1954. URL https: //nttll/////ree//e/eeeeeee itis gov /NTT// httpaa///eaarceeeeesssiiiieeeeee PB175818 8 xhtml. Num Pages: 60.
Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. Super- vised Contrastive Learning, March 2021. URL http:// arxiv. wttg/bs//g/oooooooo 11362. urXiv:2004.11366 [cs].
He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R. Momen- tum Contrast for Unsupervised Visual Representation Learning, March 2020. URL http: http://axxvvvrrro/e abs/1 91 05722. arXiv:1911.05722 [es].
Heimberg, G., Kuo, T., DePianto, D. J., Salem, O., Heigl, T., Diamant, N., Scalia, G., Biancalani, T., Turley, S. J., Rock, J. R., Corrada Bravo, H., Kaminker, J., Vander Hei- den, J. A., and Regev, A. cell atlas foundation model for scalable search of similar human cells. Nature, pp.
Kim, J. and Warnow, T. Tutorial on Phylogenetic Tree Estimation. 1999.
Kosiorek, A. R., Sabour, S., Teh, Y. W. and Hin- ton, G. E. Stacked Capsule Autoencoders, Decem-

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
ber 2019. URL http:h//attt..orrreree//
May 2009. ISSN 1432-0541. doi: 10.1007/
06818. 18 arXiv:1906.06818 [es, stat].
s00453-007-9116-4 URL https: http://doo...rgg//// 000-0004453-00-111-
Kretzschmar, K. and Watt, F. M. Lineage tracing. Cell, 148(1-2):33-45, January 2012. ISSN 1097-4172. doi: 10.10166f.cel12011.....00
Mold. E., Weissman, M. H., Ratz, M., Hagemann- Jensen, M., Härd, J., Eriksson, C.-J,, Toosi, H., Berghen- stråhle, J., Ziegenhain, C., Berlin, L. v., Martin, M., Blom, K., Lagergren, J.. Lundeberg. J., Sandberg, R. Michaëlsson, J., and Frisén, J. Clonally heritable gene expression imparts a layer of diversity within cell types. Cell Systems, 15(2): 165. 10, February 2024. ISSN 2405-4712, 2405-4720. doi: 10.1016/j.cels 2024.........2....000 URL SoLhtts::// ce httpat/sswwweeccee...co//eaa//// abstract/S2445--25 (24) 00025- 5. Publisher: Elsevier.
La Manno, G., Soldatov, R., Zeisel, A., Braun, E., Hochgerner, H., Petukhov, V.. Lidschreiber, K., Kas- triti, M. E., Lönnerberg, P., Furlan, A., Fan, J., Borm, L. E., Liu, Z., van Bruggen, D., Guo, J., He, X., Barker, R., Sundström, E., P., Adameyko, L.. Linnarsson, S., and Kharchenko, P. V. RNA velocity of single cells. Nature, 560(7719):494- 498, August 2018. ISSN 1476-4687. doi: 10.1038/ $41586-008-0041446 URL https:: / http://wtttreeee
G., Cramer,
com/articles//4411 10----0----0 018-041800 4-14-6.... Publisher:
O'Meara, B. C. TESTING FOR DIFFERENT RATES OF CONTINUOUS TRAIT EVOLUTION USING LIKELI- HOOD. 2006.
Nature Publishing Group.
Large, C. R. L.,, Khanal, R., Hillier, L., Huynh, C., Kubo, C., Kim, J., Waterston, R. H., and Murray, J. I. Lineage-resolved analysis of embryonic gene expression evolution in C. elegans and briggsae, February 2024. URL https: / www. biorxiv. org/ hetg//oonen////////
Packer, J. S., Zhu, Q., Huynh, C., Sivaramakrishnan, P. Preston, E., Dueck, H., Stefanik, D., Tan, K., Trapnell, C., Kim, J., Waterston, R. H., and Murray, J. I. A lineage-resolved molecular atlas of C. ele- gans embryogenesis at single-cell resolution. Science, 365(6459))eaax 1971, September 2019. doi: 10.1126/ 197 URL https: science. org htg/doi/100 1ww.:112666/ 112...12///cieneee aax1 9711 Pub- lisher: American Association for the Advancement of Science.
10. 10.1101/200 /2024. 02. 03. 0.....77699988 578695v1.
Pages:
2024.02.03.578695 Section: New Results.
Lee, J., Lee, Y., Kim, J., Kosiorek, A. R., Choi, S., and Teh, Y. W. Set Transformer: Framework for Attention-based Permutation-Innariinn Neural Networks, May 2019, URL http:// /at::i///xxvv/ arxiv. org//br///.... tabs/181.. 00825. 1rXiv1810000888 [cs, stat].
Pan, X., Li, H., and Zhang. X. TedSim: temporal dy- namics simulation of single-cell RNA sequencing data and cell division history. Nucleic Acids Research, 50 (8): (8):4272-4288, May 2022. ISSN 0305-1048. doi: 10.1093/nar/gkac2355. URL httph: 1093 (093/naz/gkac233
Lieberman, and Wiley, O. (eds.). Phylogenet- ies: theory and practice of phylogenetic systematics.
Wiley- Blackwell,,, Hoboken, N.J, 2nd ed edition, 2011. ISBN 9780470905968 978111801 118017668 97811 11111101111 108808883 9781118017876 9781283026642 97811 18 9786613026644.
11111118481000 1481048100 doi: 01000/99711180078988
Pan, X., Li, H., Putta, P., and Zhang, X. Lin- Race: cell division history reconstruction of single cells using paired lineage barcode and gene expres- sion data. Nature Communications, 14(1):8388, De- cember 2023. ISSN 2041-1723.
Lopez, R., Regier, J., Cole, M. B., Jordan, M. I., and Yosef, N. Deep generative modeling for single-cell transcriptomics. Nature Methods, 15(12):1053-100 December 2018. ISSN 1548-7105. doi: 10.1038/ <41592-018-0222--2 URL https: www. http://ttt.....e//////////// nature.
doi: 10.1038/
s41467-023-44173- URL https: h/wp::::////ww////////// www...............m..aaaa.. com htt./articll /eee////1
Pub-
com/ com/articles// s 11441192---0 592--19---222 9-22-2.2222222 Publisher:
lisher: Nature Publishing Group.
Nature Publishing Group.
Phillips, N. E., Mandic, A., Omidi, S., Naef, F., and Suter, D. M. Memory and relatedness of transcriptional activity in mammalian cell lineages. Nature Communications, 10 (1): 208, March 2019. ISSN 2041-1723. doi: 10.1038/
McKenna, A. and Gagnon, J. A. Recording develop- ment with single cell dynamic lineage tracing. De- velopment (Cambridge, England), 146(12):evv1697)
June 2019. ISSN 0950-1991. doi: 10.1242/ 169.10.730. URL hwtphhtts//// ncbi. wwm.mimmni....mmmmmmmmmmmmmmmmmm gov/pmc/
$41467-019-09119-88 URL ht //tp:p::::/www/ www. nature. com http//rrtceessssss1
- 09189-8. Pub-
lisher: Nature Publishing Group.
Mihaescu, R. Levy, D., and Pachter, L. Why Neighbor-Joining Works. Algorithmica, 54(1):1-24,
Qian, Q., Hu, J., Jin, R., Pei, J., and Zhu, S. Distance metric learning using dropout: a structured regularization
12

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
approach. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 323-332, New York New York USA, August 2014. ACM. ISBN 978-1-4503-2256-9, doi: 10. 1114426623333002222377777 URL htt.t:tttt////tt .cm. acm. heg/doi/100 /ttp:/.............1.1111 2623678.
Sattath, S. and Tversky, A. Additive similarity trees. Psy- chometrika, 42(3):319-345, September 1977. ISSN 1860-0980. doi: 10.1007/BF022993654, URL https: //doi. www.o////...oo.....ooooo 1tt.://.1111110111111 100.0011007///229555550
Schlüter, H. M. and Uhler, C. Integrating representation learning, permutation, and optimization to detect lineage-related gene expression patterns. Nature Communicattonss 16(1):1062, January 2025. ISSN 2041-1723. doi: 10. 0010088841447--0255668888 cles/ cos/articcess URL https:/ www.. nature com/art. coom/articlss s 641467-024 56388-66888- 7. Publisher: Nature Publish-
Qiu, C., Cao, J., Martin, B. K., Li, T., Welsh, I. C., Srivatsan, S., Huang, X., Calderon, D., Noble, W. S., Disteche, C. M., Murray, S. A., Spielmann, M., Moens, C. B., Trapnell, C., and Shendure, J. Sys- tematic reconstruction of cellular trajectories across mouse embryogenesis. Nature Genetics, 54(3):328- 341, March 2022. ISSN 1546-1718. doi: 10.1038/
ing Group.
Schroff, F., Kalenichenko, D., and Philbin, J. FaceNet: A Unified Embedding for Face Recognition and Clustering. pp. 815-823, 2015. URL https: //ttpp::/www.. cv hww.fouudatiooo.ogggoeeeeeeeeeee
$41588-022-01018-- URL https: www.nature.....mt..m.. com/art c 00244111222-0000110000 00112-00018xx Pub-
lisher: Nature Publishing Group.
content_
Qiu, X., Mao, Q. Tang, Y., Wang, I.., Chawla, R., Pliner, H. A., and Trapnell, C. Reversed graph embedding re- solves complex single-cell trajectories. Nature Methods, 14(10):97--982, October 2017. ISSN 1548-7105. doi: 10.1038/nmeth.44002 URL https: ////w//wwww nature. satrticles/nneen /ww.t//e.hh.....mmmmmm 1aameth.4400 4402. Publisher: Nature Publishing Group.
Unified [itiedd_21550 Unified_2015_cc httiiiee__2115_cc__ppprrr.e.
Shaffer, M., Emert, B. L., Reyes Hueros, R. A., Cote, C., Harmange, G., Schaff, L.., Sizemore, A. E., Gupte, R., Torre, E., Singh, A., Bassett, D. S., and Raj, A. Memory Sequencing Reveals Heritable Single- Cell Gene Expression Programs Associated with Distinct Cellular Behaviors. Cell, (82(4):947-959.e))) August 2020. ISSN 0092-8674.
com/artion ceeeeeeeeeeeeee
Quake, S. R. The cellular dogma.
Cell, 187
(23):6421-644) 66223, November 2024. ISSN 0092-
doi: 10. 10.10166j.ce11.22220.7
8674, 1097-4172. doi: 10.1016/j.cll.22244,
003. URL wwr.ntttpss/www.eceeeeddddie ccctece//rrtidee//////2222222222
029. URL https: www. cell com/ cell/
Destract/S0050 16755000228674000 (24) 01211- X. Publisher:
Shapiro, E., Biezuner, T., and Linnarsson, S. Single-cell sequencing- technologies will revolutionize whole- organism science. Nature Reviews. Genetics, 14(9):618 8- 630, September 2013. ISSN 1471-0064. doi: 10.1038/ nrg3542.
Elsevier.
Rafelski, S. M. and Theriot, J. A. Establishing a con- ceptual framework for holistic cell states and state transitions. Cell, 187(11):233-2265 ISSN 0092-8674, 1097-4172. doi: c0.104. 04.035. URL https::t///// www.ccel.. com c abstract / /w00//00900067 (24) 60461- 6. Publisher: Elsevier.
May 2024.
Sivandzade, F. and Cucullo, L. Regenerative Stem Cell Therapy for Neurodegeneraaiie Diseases: An Overview. International Journal of Molecular Sciences,
22(4):2153, February 2021. ISSN 1422-0067. doi:
10.3390/jms220421133. URL httph: htttpp::/www.... .cbb.. nim. ni www.h..w../.c....... art cltsc 79776771997666...
Rückert, T., Lareau, C. A., Mashreghi, M.-F., Lud- wig, L. S., and Romagnani, C. Clonal expansion and epigenetic inheritance of long-lasting NK cell memory. Nature Immunology, 23((1):1551-1563 November 2022. ISSN 1529-2916.
Slack, J. M. W. and Dale, L. Essential Developmental Biology. John Wiley & Sons, November 2021. ISBN 978- 1-119-51284 Google-Boode Books-ID: SWIQEAAAQBAJ.
doi: 10.1038/
5415900-22--01327-7 URL URL htwp::ttpt/.o.......m /ttptttss::///////te http://wwwwatt/e/ee/////e/e com/articles///cocoocccoooo wesiicceesss115e00 022 01327-7.
Pub-
Street, K., Risso, D., Fletcher, R. B., Das, D., Ngai, J., Yosef, N., Purdom, E.,, and Dudoit, S. Slingshot: cell lineage and pseudotime inference for single-cell transcriptomics. BMC Genomics, 19(1), June 2018. ISSN 1471- URL https:
lisher: Nature Publishing Group.
Saitou, N. and Nei, M. The neighbor-joining method: new method for reconstructing phylogenetic trees. Molec- ular Biology and Evolution, 4(4):406-425, July 1987.
2164. doi: 10. 00011188//12844-18887777777 / //doi. org / 10 1ee.11111661 htt.://222644--0 4702-0077
ISSN 0737-4038, doi: 10. 10.1103//oxfordoomaaammmoolooo a040454. URL https:://bo..org/11.00055 oxfordjournalse www.s....bb......oommmm.........
Sulston, J. E., Schierenberg, E., White, J. G., and Thomson, J. N. The embryonic cell lineage of the
13

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
nematode Caenorhabditis elegans. Developmental
s132877-020-01941-y, URL httph:tt///oo/ btcps:://ooii org/10. 1
Biology, 100(1):64-19, November 1983. ISSN
0012-1606. doi: 10. 1011066/0112-1006639990001
URL https: wwwp//wwwww..oo/ http://wwwwwwnnnnieeeeeeeee wwweeeiewewwnnccecooooooooo sci
Zhao, B.. Song. K., Wei, D.-Q.. Xiong, Y. and Ding, J. scCobra allows contrastive cell embedding learning with domain adaptation for single cell data integration and harmonization. Communications Biology, 8(1):1- 18, February 2025. ISSN 2399-3642. doi: 10.1038/ 542003-025-07692211 URL https: http::///wwwwwwwtweeee 0000--2225-222-2-- 07692-x. lisher: Nature Publishing Group.
/00p://i//111111 6068390000 4.
Theodoris, C. V., Xiao, L., Chopra, A., Chaffin, M. D., Al Sayed, Z. R., Hill, M. C., Mantineo, H., Brydon, E. M., Zeng, Z., Liu, X. S., and Ellinor, P. T. Transfer learning enables predic- tions in network biology. Nature, 618(7965):616- 624, June 2023. ISSN 1476-4687.
Pub-
doi: 10.1038/ $415566-023-06139--2 URL https: www..aturee.. com/articles/ sstiiceeee//11666 00006-022---2
Zhao, H., Jiang. L., J., Tom, P. H. S., and Koltun, V. Point Transformer. pp. 16259-16268, 2021. URL https:
Pub-
/ / thevf.. com/ comm///otet/////// Iccv_2021_paper.htte
lisher: Nature Publishing Group.
Wagner, D. E. and Klein, A. M. Lineage ing meets single-cell omics: opportunities and chal- lenges. Nature Reviews Genetics, 21(7):410-277,
Bacell_ppper.ee paper.ttmm?re... htrl?
July 2020. ISSN 1471-0064. doi: 10.1038/
$41576-000-0022--2 URL http:/ /wwp///wwww//////////////////w http://www........///.tt// nature.
commaatiices/s41111 00077-000--21 0200-22.2222 Number:
Publisher: Nature Publishing Group.
Wolpert, L., Tickle, C., and Arias, A. M. Principles of Development. Oxford University Press, 2015. ISBN 978- 0-19-870988-6. Google-Books-ID Wb06BWAAAQBAI.
Yang, M., Yang, Y., Xie, C., Ni, M., Liu, J., Yang, H., Mu, F., and Wang, J. Contrastive learning enables rapid mapping to multimodal single-cell atlas of mul- timillion scale. Nature Machine Intelligence, 4(8):696- 709, August 2022. ISSN 2522-5839, doi: 10.1038/ 142256-022-0051821 URL https: // /www//ww.../ nature. com/ htt//articlee sac.ceeess422555 s42256- 1222-00518-2
Pub-
lisher: Nature Publishing Group.
Zafar, H., Lin, C., and Bor-Joseph, Z. Single-cell lin- cage tracing by integrating CRISPR-CasT mutations with transcriptomic data. Nature Communications, 11(1): 3055, June 2020. ISSN 2041-1723,
doi: 10.1038/
1114677-20-16821-5. URL http:::ttt///tee http:/wwww...tt.//////////t/ nature. com/articles s414 4200
Num-
ber: Publisher: Nature Publishing Group.
Zeng. H. What fine it? Cell, (85(15):2739-2733 July 2022. ISSN 0092-8674.
cell type and how to de-
doi: c0.10166).ell.2222.66. 031. URL https: w/ww://wwwwwwwwww/tttttptwwwww www.sceeiieeireccccmmmmm http://///wwwccceneerreee..... com/
Zhang, Y., Zeng, F., Han, X., Weng. J., and Gao, Y.
Lineage tracing: technology tool for exploring the development, regeneration, and disease of the diges- tive system. Stem Cell Research Therapy, 11(1): 438, October 2020. ISSN 1757-6512. doi: 10.1186/
14

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
A. Related Works
Beyond the core comparisons in the main text, we here provide a broader review of related works.
Metric Learning Metrie learning is broad field focused on learning representations in which distances capture meaningful similarity relationships. In recent years, a subset of metric learning techniques known contrastive learning has gained significant traction in deep learning. These methods have been applied in both supervised (Khosla et al., 2021) and unsupervised (He et al., 2020) settings, with the main objective being to embed similar examples closer together while pushing dissimilar ones farther apart. In this paper, we compare two widely used metric learning objectives- loss (Schroff et al., 2015) and Quadruplet loss (Chen et al.,
our proposed approach.
Representation Learning for scRNA-seq ScRNA-seq data are high-dimensional and subject to diverse technical and biological noise. Common strategies to handle this complexity often involve dimensionality reduction (e.g., PCA (Heumos et al., 2023)), or deep generative models (e.g., scVT (Lopez et al., ()), which embed cells in a lower-dimensional space that preserves essential variability.
Recently, large-scale pretrained models have emerged in single-cell analysis. Transformer-base architectures such as Geneformer (Theodoris et al., 2023) and scGPT (Cui et al., 2024) learn embeddings from massive single-cell corpora, facilitating tasks such as eel- classification, data integration, and cross- cross- modality predictions. Meanwhile, supervised contrastive learning on scRNA-seq has been applied to capture nuanced cellular states, offering efficient data usage and strong generalization (Yang et al., 2022; Heimberg et al., 2024; Zhao et al., 2025).
Nevertheless, most existing approaches rely on a notion of similarity derived from overall transcriptomic profiles, which does not necessarily align with lineage relationships (as discussed in the next paragraph). Although these methods successfully map cellular states and correct for technical artifacts, they do not directly address how to exploit these representations for cell lineage reconstruction.
Trajectory Inference vs. Lineage Reconstruction Methods such RNA velocity (La Manno et al., 2018; Bergen et al., 2020) and trajectory inference (Qiu et al., 2017; Street et al., 2018) reveal continuous trajectories in the molecular state space of the transcriptomes. Although these tools capture average progression trends, they do not directly yield a cell-by-cell lineage hierarchy. Rather, they provide trajectory embeddings that broadly reflect state set evolution, rather than the lineage history of cells. Moreover, genes driving these gene trajectory embeddings are typically selected based on high global variance, potentially missing the key drivers for lineage-specifte processes.
Cell Types vs. Cell Linages In standard single-cell analysis, cell types are typically inferred by grouping cells with similar transcriptomic profiles, either through unsupervised clustering (Heumos et al., 2023) or reference-based classification methods (Aran et al., 2019; lanevski et al., 2022; Hu et al., 2023). While these approaches effectively capture functional similarities, they do not explicitly account for the developmental origins of each cell. In other words, two cells with nearly identical gene expression patterns may not necessarily share a recent common ancestor. In contrast, cell lineages focus on the actual historical branching process by which cells emerge and differentiate- thus requiring methods that go beyond mere transcriptomic similarity capture genealogical relationships.
Phylogenetic Inference Reconstructing the lineage history of species or cells is a phylogenetic inference problem. The parameter space is vast and inherently complex due to the combination of discrete topologies and continuous branch lengths, making the problem NP-hard in most formulations (Felsenstein, 2003). Despite this, various data assumptions and heuristic-based reconstruction algorithms have been developed, achieving reasonable performance on typical phylogenetic datasets. The most widely used approaches infer trees using maximum parsimony, maximum likelihood, Bayesian inference, or distance-based methods (Jones al., 2020; Gong et al., 2022).
Our method falls within the category of distance-based based lineage reconstruction, where the goal is to fit the data to its closest tree metric. Finding the optimal tree metric is NP-hard under E1, f2, and Eoo norms for unrooted trees, but significant progress has been made in improving approximation algorithms (Ailon & Charikar, 2005). For instance, (De Socte, 1983) proposed greedy approach by directly using gradient descent to find the closest additive distance matrix. However, instead of explicitly optimizing pairwise distances, our approach learns an embedding function that maps data points into a space where the geometric properties facilitate tree inference.
15

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Notably, the most recent work (Schlüter & Uhler, 2025) investigates how identify phylogenetically informative features under fully supervised setting using permutation approaches. In study, conduct similar permutation experiments assess the feasibility of our approach, but with the added objective of not only characterizing the features but also directly reconstructing the tree.
B. Terminology
Tree graph algorithms in biology originate from the mathematical systematics field dealing with lineage reconstruction of whole organisms, represented by species taxons, while the cell lineage reconstruction problem arises from the field of molecular and developmental biology. These two different areas have distinct but also overlapping terminology (Kim & Warnow, 1999; Clevers et al., 2017; Zeng, 2022; Domeke & Shendure, 2023; Rafelski & Theriot, 2024). Here, we establish the following definitions to avoid confusion.
Single-Cell Biology
Characterization of cell's molecular phenotype. This phenotype typically varies with time and space. comprised of measurements of gene expression, metabolism, and other functional properties.
Cell state:
Cell lineage: The sequential path of cell divisions that traces given cell's s ancestry back to the zygote. Some times, cell lineage is used to refer to parts of the path. For example, "neuronal lineage" might refer to the parts of the path that distictly lead to cell groups identified as neuronal cell type (see next).
Cell type: A classification of cells based on cell phenotype and sometimes also cell lineages. In general, cells of the same type typically share functional and structural characteristies but does not necessarily imply lineage relationships. However, in some biological cases, particular cell type might be established by its particular lineage relationship rather than just the cell phenotype.
Phylogenetics and Evolutionary Biology
Phylogeny: A tree-structured graph describing the evolutionary history and relationships among a set of biological entities. In Systematics, these entities are typically taxons (see next). In particular, a phylogeny is typically a leaf- labeled tree graph, in the sense that only the leaves of the tree are measured and named entities and interior vertices are hypothetical unnamed ancestors.
When the entities are cells, a phylogeny can be seen as a cell lineage tree.
Cell lineage tree: A specialized tree-structured graph where each node represent cell group of cells, and edges represent cell division events. The root corresponds to the common ancestral cell for all cells in the tree. Ultimately, all cells lead to the fertilized egg as the root. Branches typically depict temporal progression leading to changes in cell state termed differentiation. Sometimes, branches might represent a collection of cell divisions.
The nodes in a lineage tree. An internal vertex usually corresponds to a cell division point, producing two (or more) daughter cells. A leaf vertex (or leaf) typically represents a terminally differentiated cell. However, if the cells are sampled from middle of the cell replication process, the leaf vertex may represent transient cell(s).
Vertices:
Taxon (plural: taxa): taxon is an abstract unit in Systematics, referring to a distinct group of organisms that has been annotated by an expert for the purposes of classification. canonical example a species or an isolated population. Here we use it to denote the biological entity represented by a vertex of the cell lineage tree. This entity might be a single cell or it might be a class of cells denoted as a cell type.
Clade: A subset of lineage tree that includes common ancestor and all its descendant leaves.
C. Preliminaries of Phylogeny
A tree is a connected graph where every pair nodes is connected by a unique path. Among other things, this restriction implies that in tree there are no links (1,, u))) that connect a node e; to itself. An additive tree is connected undirected
16

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
network where every pair of nodes is connected by unique path(Sattath & Tversky, 1977). Since there exists only one path between any nodes, the minimum path length distance between two nodes is equal to the length of the unique path that connects them. These distances are often referred to path length distances or additive tree distances.
In evolutionary biology, a phylogeny is a bifurcating tree that models the evolutionary relationships among a set of species or other biological entities. The leaves of this tree represent extant (or observed) entities, while the internal nodes represent their hypothetical common ancestors. Such trees help us understand how these entities have diverged over time.
With the advent of large-scale genomic data, the field of phylogenomics has emerged. Phylogenomies integrates phylogenetic analysis with genome-wide data, allowing for more accurate and comprehensive inferences about evolutionary history. Rather than focusing on single gene (as in classical phylogenetics), phylogenomics considers data from multiple genes, entire genomes, or high-dimensional molecular measurements, providing richer context for reconstructing the evolutionary relationships among species.
In this section, we introduce fundamental concepts for distance- based phylogeny reconstruction an approach that finds an additive tree by mapping n x n distance matrix to n x n additive distance matrix (Kim & Warnow, 1999; De Soete, 1983). These concepts form the theoretical basis of the learning objectives proposed in this work.
C.1. Distance Matrices and Additivity
Given set of nodes, each represented by a vector w. we can derive an n distance matrix M, where Mi denotes the distance between nodes and j. M is valid metric, must satisfy the following properties:
Symmetric: Mj M,; and Ma 0;
Triangle Inequality: My M, M
Now, suppose F, represents the leaves of a phylogeny and w is the lowest common ancestor of two nodes u and u, we expect Ma Man Mar. This property introduces the concept of additive metric. A distance matrix M is additive if there exists phylogeny T such that:
Each edge (u,v) is associated with a positive edge weight &wv.
For every pair of nodes u, v, the distance Mav equals the sum of the edge weights along the unique path from in T.
For distance matrices with fewer than four leaves, M must be additive. However, for matrices with four or more leaves, M may not be additive. Buneman's 's 4- 4-point condition provides criterion to determine additivity:
Theorem C.1 (4-Point Condition). A distance matrix M is additive if and only if the following holds: For any distinct leaves j, ki we can label them such that:
Mj + Mfr = Ma + MyN 2 Mi3 + Ma-
This condition ensures that, among any four leaves, the two largest sums of pairwise distances are equal. This property is fundamental for the additivity, guaranteeing that M corresponds to an additive tree. When M satisfies this condition, the additive tree can be uniquely reconstructed in On?²) time.
C.2. Non-Additivity and Approximate Solutions
In practical phylogenomies, observed distance matrices M often deviate from perfect additivity. In such cases, the objective becomes finding an additive matrix Mr that corresponds to a tree 7 that minimizes the sum of squared errors (SSQ), defined
as:
min || M M|
is known that finding the optimal T is P-hrd for various norms (p 1, oo) (Farach et al., 1995).
However, given fixed tree topology T, can least solve for the optimal edge lengths E that best fit M. This subproblem can be formulated as non-negative least squares (NNLS) problem:
min E20
|| E
Myes l
17

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
where:
E is an m-ddimensional vector of edge lengths (m is the number of edges in T).
Myec the vectorized form of M, containing (2) pairwise distances.
Pr is a (2) x m path matrix encoding the tree's topology. Each row corresponds to a pair (i. of leaves, and each column corresponds to an edge e in T. The entry [Pr](s.):e if edge e lies on the path between and j. and otherwise.
This NNLS problem is convex and can be solved efficiently. The difficulty lies choosing the optimal topology T. Because the space of possible tree topologies grows super-exponentially Since enumerating and evaluating all possible trees not practical for larger n, heuristic methods are employed to approximate the solution. One of the widely used heuristics the Neighhor-Joining (NJ) method (Saitou & Nei, 1987). The NJ algorithm is efficient and makes assumptions about the edge lengths. As shown in (Gascuel, 1997), NJ reconstructs the unique tree when given an additive distance matrix. Moreover, (Atteson, 1999) proved that if a distance matrix M is nearly additive, there exists an additive distance matrix Dy such that:
M Drl 2T))22
where ((T) is the minimum edge length in T. All distance matrices M that satisfy this condition share the same tree topology, meaning T' is the unique tree corresponding to these distances. The NJ algorithm has an optimal reconstruction radius in the sense that: (a) given a nearly additive distance function it reconstructs the unique tree T and (b) there can be more than one tree for which M - Drl < d holds if 8 2 ((T)/2.
C.3. From Genomic Data to Latent Representations
In classical phylogenomics, evolutionary distances are estimated from genomic sequences using probabilistic models. However, in the context of single-cell data, the observed distance matrix often deviates substantially from additivity due to factors such as measurement noise, high dimensionality, and features unrelated to lineage. In this work, we propose learning a nonlinear mapping that projects high-dimensional observations into a latent space, and then computing distances in that space. The goal is for these learned distances to reflect the underlying lineage structure more accurately than distances directly computed from the original data. In essence, aim transform empirical dissimilarities into additive phylogenetic distances, thereby bridging the gap between observed data and their development histories.
C.4. Constructing the Tree with NJ
After learning the embeddings {z:} } in which pairwise distances approximate the true tree distances, the next step is to build the lineage tree T. A standard choice is the Neighbor-Joining (NJ) algorithm (Saitou & Nei, 1987), a greedy approach that iteratively merges pairs of nodes clusters based on pairwise distance matrix. Neighbor-Joining does not assume equal branch lengths and can yield accurate topologies even when distances are only approximately additive.
The algorithm is guaranteed to recover the correct tree topology when the distances perfectly adhere to an additive tree metric, and it often performs well even when this assumption is not strictly met. In general, the method has been shown to work well with finite datasets, and it is one of the most widely used distance methods for tree graph inference.
While NJ is polynomial-time algorithm, its time complexity is (n²) for n taxa. This is typically manageable for moderate dataset sizes, but it may become computationally expensive for very large trees (Atteson, 1999; Mihaescu et al., 2009).
D. Dataset Details
D.I. Sineage-Resolvedd C. elegans Dataset
Among model organisms, the nematode C. elegans is uniquely suited for benchmarking lineage-reoonstrrution methods because its embryonic development follows an invariant pattern. Using the transcriptomic atlas by Packer et al. (2019) and (Large et al.. 2024), we define three datasets with supervised tree-graph ground truth of varying sizes:
C. elegans Large (295 leaves). This dataset, drawn directly from (Packer et al., 2019), provides a broad coverage of terminal lineages, offering moderately sized yet comprehensive benchmark.
18

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
C. elegans Small (102 leaves). To create a simpler, more tractable dataset, we prune the original C. elegans lineage include only nodes that have a clearly defined mapping annotated cell types. This smaller tree is useful for rapid prototyping and evaluating basic performance. Details of curation can be seen in later of this subsection.
C. elegans Mid (183 leaves). Building on the lineage-resolved atlas for both C. elegans and C. briggsae by Large et al. (2024), we curate a set of 183 leaves that can be consistently mapped to both species. We use just the C. elegans portion here, providing an intermediate-sized dataset that balances coverage and complexity.
Preprocessing Following standard filtering criteria, we retain about 13,000 genes per dataset by removing those with minimal counts (fewer than 10 UMIs) or zero variance across cells.
Summary Statistics. Table summarizes key statistics for each elegans dataset, including the number of cells per leaf, total leaves, Colless index (Lieherman & Wiley, 2011), tree diameter, depth, Faith's Phylogenetic Diversity (PD)(Faith, 1992), and mean pairwise distance.
The Colless index is a measure of tree imbalance, where smaller value indicates a more balanced (symmetric) tree. Indeed, the relatively low Colless indices suggest that the C. elegans lineage is quite symmetric, and our pruned subsets remain well-distributed across the leaves. Faith's 's PD is a measure of biodiversity, defined as the sum of branch lengths in a phylogenetic tree.
We provide two sets of tree metrics. In the Based Reference Tree section, branch lengths are to be 1s in the complete reference tree (containing 669 leaves), and these lengths retrained and accumulated while pruning so that the distances among leaves in our curated datasets reflect the distances in the complete reference tree. In the Based on Topology section, we recompute statistics under the assumption that all branch lengths are equal to I in the curated dataset, allowing us to evaluate the inherent structure of each pruned tree independently of the original branch lengths.
Table 4. Statistics of Datasets in the Cell Lineage Tree Reconstruction Benchmark. Values in parentheses indicate standard deviations where applicable.
Based on Reference Tree
Based on Topology
Dataset
N Cells/Leea
Leaves
Colless
Diameter
Depth
Faith's PD
Mean PD
Diameter
Depth
Faith's PD
Mean
C. elegans Small
107
102
0.047
21
7.92 (2.07)
293
15.52
19
6.66 (2.01)
202
12.27
C. elegans Mid
101
183
0.018
19
8.21 (1.81)
424
14.23
18
8.01 (1.66)
364
13.53
C. elegans Large
117
295
0.010
20
7.91 (1.69)
735
15.84
7.62 (1.64)
588
14.77
The curation of C. elegans Small. In Packer et al. (2019), three cell ontologies are available: (1) cell identities by barcode, (2) cell type annotations (from Packer et al.), and (3) Lineage Node Names on the full embryonic tree (from Sulston et al.). As illustrated in Figure 6, the relationship between Cell Identities and Cell Type Annotations is many-to-one, determined by manual annotation. Meanwhile, the relationship between Cell Type Annotations and Lineage Node Names is many-to many-to-many
On one hand, a single Cell Type Annotation may correspond to multiple lineage nodes due to symmetry (e.g., Cx could be either Ca Cp). On the other hand, one lineage node can be associated with multiple Cell Type Annotations because each annotation is defined distribution of cell states, which may overlap.
To create relatively small, clean dataset while preserving the overall lineage structure of C. elegans, we selected only those cell type annotations that map to a single lineage node. We then constructed a lineage tree using these "clean" lineage nodes. This effectively serves as pruning the annotation tree. After pruning, we randomly drop a few clades to make sure the final lineage tree is in binary structure. As shown in Table 4, the curated C.elegans Small dataset spans most major cell lines of C. elegans while relatively easier to reconstruct than the full lineage tree.
D.2. Simulation: Brownian Motion on Lineage Tree
We developed a synthetic dataset that encompasses both heritable and non-heritable features to model cell lineage relation- ships in a structured, probabilistic manner. Each Ieaf u in this dataset is assigned three types of features:
(S "... Sumaan)
(Nu. N Nu.unee
(A
signal variables
Gaussian noise
altemative-tree noise
providing comprehensive representation that includes both true lineage signals and potential confounding factors.
19

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Call Barcode
Many-to-one
Cell Type Armotation
Many-to-Many
Lineage Embryonk
Figure Entity relationships among the annotations Packer et al. (2019).
D.2.1. CELL LINAGE SIGNALS
We represent the cell lineage full binary tree with Aleaves terminal nodes. Each edge in the tree is assigned length i ~ Uniform(1, ), which can be viewed as developmental or temporal distance hetween parent and child nodes. To simulate heritable changes, we apply Brownian motion, standard approach for continuous-charatter evolution (O Meara, 2006; Pan et al., 2022).
Starting from a zero vector at the root, each child node's signal vector obtained by adding a Gaussian increment (0, tj) the parent's ss signal vector along the branch j. Let i denote the index of one out of Tsignal Brownian motion realizations, thereby defining a signal feature S; that encodes lineage information. Formally, Brownian motion at edge j is
s((hild)
| ((parent) + (0, for i = I,..., Reigmal-
This part of simulation is governed by the hyperparameters (Miignal Nevves Wwalk). After generating all signal features, we compute the pairwise distance matrix and use Neighbor-Joining to reconstruct the lineage tree. The reconstructed tree is compared with the true tree using the Robinson-Foulds (RF) distance. grid-sweep of the hyperparameters was conducted, and the results are presented in Fig. 8.
Figure illustrates several key factors affecting lineage reconstruction accuracy. Increasing the number of signals Nesignals generally reduces the average RF distance, reflecting better reconstructions. Conversely, as the number of leaves Meavee grows, the RF distance tends to rise, indicating the challenges of reconstructing larger and more complex trees. The parameter log Wmax can help distinguish lineages by amplifying their differencces-partiiull small- but its benefits come with random variation. Consequently, beyond a certain threshold, increasing log Wmax does not further reduce the RF distance; instead, an inherent "floor" of imperfect reconstruction persists. Finally, there is a saturation effect: beyond some point, neither adding more leaves nor more signals consistently pushes the RF distance toward zero, highlighting the limit imposed by Brownian motion's stochasticity and the maximum possible branch length Wmax.
when Rsignals Vleaaves is
D.2.2. INDEPENDENT GAUSSIAN NOISES
We introduce heritabrt noise features that are independent of the lineage. Each noise variable follows Gaussian distribution with mean 0 and standard deviation o' = 5.0astaal- Symbolically,
N o)) for i = 1,..., Rggusssinn
D.2.3. ALTERNATIVE TREE NOISE
In addition to independent Gaussian noise, we introduce a second type of noise structured by an alternative free. This alternative tree noise, or "anti-signal," represents confounding factors that give rise to correlated features unrelated to the true lineage. Examples include environmental or microenvironmental influences (e.g., regional nutrient availability). cell-cycle synchronization, technical batch effects. These factors cluster cells according topology distinct from the actual lineage, thus posing challenge for tree reconstruction.
Key parameters. To generate alternative tree noise, we first partition the set of leaves into one or more subsets. In our running example, we split the leaves into two partitions of equal size, i.e., [0.5, 0.5). For each partition, we construct
20

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Signal
Signal Tree
S
1
A
Alternative
Cell A
Cell B
Cell C
Cell D
Sample branch length by G--Unform11, Wima>)
signals variables Brownian Motion 5(child) 5(parent) ..(0..))
t1
L3
t2
t3
t2
A Cell Call Call Topology Tree
Cell Cell Call
Model Tree
Sample Tree
Figure 7. Overall schematic of the lineage tree simulation. The simulation starts with a Topology Tree defining cell relationships. Each edge assigned a random length, producing Model Tree. Signal variables (S.) are then generated along the branches Brownian motion process, resulting in the Sample Tree. Finally, Gaussian noise (N₂) and alternative tree noise (A,) are added independently, yielding complete feature matrix for each leaf, Alternative trees are constructed separately to simulate confounding topologies.
an alternative tree of specified size (equal the number of leaves in the largest partition, set in the example) and create new of "alternative" feature columns, AltSigs. Each leaf in the original (signal) tree thus has corresponding "alternative" leaf in the alternative tree. We can optionally have multiple alternative trees per partition, but in the example, we set this number to 1.
Generation procedure. Similar to the main (signal) tree, each alternative tree has its own branch lengths drawn from some distribution (e.g., Uniform(1, ((iit) )). For every leaf in the true (signal) tree, there is corresponding leaf u, in the alternative tree. We then generate "alternative" features for each such leaf by simulating a Brownian Brownian-motion motion-like process, or another model as desired, along the branches of the alternative tree. These "anti-signals" are thus correlated according to the alternative topology rather than the true lineage topology. In the final dataset, each leaf u accumulates an additional vector of alternative noise features,
Au,1, Au,2, Au,nasss"
Because these features reflect different branching structure than the true cell lineage, they act as confounders in any tree reconstruction method that does not isolate genuine signals from extraneous structure. By controlling the number of partitions, leaves per alternative tree, number of alternative signals, and total number of alternative trees, one can tune the difficulty distinguishing true lineage signal from these carefully structured "anti-signal" features. (Fig. 9)
D.2.4. SUPERVISED SETTING
To evaluate lineage reconstruction methods in supervised setting, generate two sets of signal variables: one for training and one for testing (Fig. 10). First, we generate signal variables using the Brownian motion process described earlier. Then, for each signal variable, we add small amount of Gaussian noise, (0, 0.1 x Tsignal), where ōsignal represents the mean standard deviation the generated signal features across all leaves and signal dimensions. This creates replicate of the signal variables with slight perturbations, suitable for evaluating a method's s ability to generalize from training data to unseen test data. The training and testing datasets, therefore, have the same underlying lineage structure but differ the specific
21

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
avg_rf rf vs log 2(max_ walk) for different n signall and n leaves
n_leaves 8
leaves 16
leaveees 32
1.0
1.0
1.0
0.8
0.8
avg. ff
0.6
0.6
0.4
0.4
n_signals
0.2
0.2
-
0.0
l_leaves= 64
n_leaves 128
n_leaves = 256
32
64
1.0
1.0
1.0
128
256
0.8
0.8
0.8
512
1024
avg.1 ff
0.6
0.6
0.6
0.0
log_max mwx walk
log_max max_maxxpaaa walk
log_max max walk
Figure 8. Mean Cobinson-Foulde (RF) distance between reconstructed and true lineage trees function of log Waa for varying numbers of signals Reignal and leaves Vieeess Each panel represents different value of nevess while distinct lines within each panel correspond to different numbers of signals. Here, Whax the maximum possible edge length in the Each data point shows the average RF distance across 25 trails (5 distinct model tree x 5 replicate sample tree per model tree.
22

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Signal Tree
Alternative Trees
Gane
AmtSigt
AnniSig?
Ant
Air1 LaafA
C
Air Laara
CellB
Air1 LeariC
Cell
Nr1 Leaf
Dell
Andsigz
AntiSias
Alz2 LeafA
Nt2 Leaf
N:2 Leaf'C
Nr2 Leaf
Figure Schematic of Alternative Tree Noise Generation. The left panel depicts the true signal tree, representing the actual lineage relationships between cells. The middle panel shows the feature matrices for signal genes (left) and alternative tree noise or "anti-signals" (right). Arrows indicate the mapping of leaves from the signal illustrates the alternative trees, which are constructed independently for each partition of leaves. These alternative trees have different topologies and branch lengths than the true signal tree, resulting correlated noise features that can confound lineage reconstruction.
the corresponding leaves in the alternative
The right panel
signal values due the added noise. Gaussian and alternative tree noises added independently to both the training and testing datasets as described in the previous subsections.
To complement real-data experiments, we generate synthetic datasets that capture both heritable and non-heritable features under controlled conditions (Fig.7):
Signal Features. A "true" lineage (signal tree) is simulated with random branch lengths (edgh-weights); We generated samples of Brownian motion along the edges where expected standard deviation of the stochastic process is parameterized by the branch lengths.
Independent Gaussian Noise. Added to each leaf independently, these features are uncorrelated with the true lineage.
Alternative- Therrative-TTre Noise. Features generated from separate, "alternative" tree, modeling confounding patterns that could mislead reconstruction algorithms.
By tuning parameters (e.g., number of leaves, signal dimensionality, noise variance), systematically adjust difficulty and isolate key performance factors. Full details the synthetic data generation, parameter choices, and hyperparameter sweeps appear $D.2 and Table 7.
E. Problem Formulation Details
We consider an underlying lineage tree T that describes the data-generating process, where a single progenitor cell initiates binary replication while also modifying molecular states such that diverse of daughter cells is generated. In this bifurcating tree, each internal node corresponds to ancestral mother cells and edges represent mother-daughter relationships. The leaves of the tree correspond to sampled cells, typically terminally differentiated cells (i.e., cells that no longer replicate). Our goal is to recover this tree structure T using high-dimensional phenotypic data, such as transcriptomic profiles, measured on the leaves.
E.1. Prior Information
The problem of lineage reconstruction from single-cell phenotypic data poses challenges reminiscent of classical systematics in biology, field historically concerned with organizing biological diversity based on observable traits. (Zeng, 2022; Domeke & Shendure, 2023; Quake, 2024) The low correlation between phenotype and cell lineage complicates the task. Selecting signal features is NP-hard; reconstructing the phylogeny also well-known NP-hard problem. But we are
23

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Signals
Ind. gaussian noise
Alt. tree noise
Brownie Motion Realization
Gena1
Gene2
Gere3
Gened
Sumpling noise N(,, 0.1xo)
CellA
Training Dataset
Fell
Signals Ind. gaussian noise
Alt. tree noise
Sampling noise ((D, 0.1xa)
Coll
Cell
Signal Tree
Testing Dataset
Figure 10. Illustration of the supervised setting for simulation. After generating signal variables through Brownian motion on the signal tree, a small amount of Gaussian noise is added create a replicate of signal features. One is used training, and the other for testing. Both the training and testing datasets then receive independent additions of Gaussian noise and alternative tree noise.
not pessimistic about finding some heuristic solutions under some reasonable constraints. After all, the very essence of systematics is address this type of challenge.
notable strength of framework (F is its ability to explicitly quantify the amount of prior topological information through the number of quartets with known structures. In fully supervised setting, assume complete knowledge of tree branch lengths and exact pairwise path lengths between terminal nodes. This scenario, while idealized, sets performance upper bound for our model. Transitioning to weak supervision, we relax these requirements, retaining only knowledge of quartet topology (i.e., the relative order of distance sums) without branch length information. This allows optimization quartet constraints.
based on marginal properties of the
Yet, the assumption of complete quartet topology knowledge remains stringent and rarely achievable in practice. In biological systems, partial qualitative information often exists that can group entities into distinct clades categories, (Cavalli-Sforza & Edwards, 1967) For example, binary characters like cettebrate-invereebee delineating immune cells. It is not uncommon to expect that we know some coarse groupings about the data. By leveraging these groupings, we can infer the topology of selected quartets. For instance, choosing two nodes from one clade and two from another ensures a butterfly configuration between the clades.
distinctions among animals surface markers
Thus, the quantity of known quartets can serve as a direct measure prior information. In this work, we demonstrate that complete quartet topology enables accurate lineage reconstruction. Furthermore, when partial topology is available, employ dictionary learning and quartet compatibility iteratively expand the topology and refine the representation. This layered approach highlights the robustness of our framework across varying levels of supervision, paving the way for broader applications in cases where prior information is sparse or incomplete.
But still, knowing the topology of all the quartets is a stringent requirement that rarely is fulfilled reality. However, biology, we usually know some qualitative characters which can induce a partition entities into distinet groups (Cavalli-Sforzz Edwards, 1967; Crowley et al., 2024). For example, the morphological feature cneebrate-iverttbriee defines a binary (two-state) character. Some surface markers can be used distinguish between broad lineage clades. We then can leverage grouping information by picking two nodes from one clade and picking two from another clade. The selected quartet must form into butterfly bridge between the clades. We will have the topology of some of the quartets. So the number of known quartets can be quantitatively represented as the prior information. In this work, we set up the framework and showed that the problem is solvable we know all the quartet topology. Then we show that when some of the quartets are known, we can use dictionary learning and quartet compatibility to learn the representation while expanding the topology information.
24

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
An intermediate scenario involves having only partial or grouped prior knowledge-such knowing that certain leaves belong to few large clades without having complete quartet-level constraints. In this case, we initially focus quartets formed from these known clades, where intra-clade topologies are more likely to be stable.
E.2. Cell Aggregation
Another challenge we have set aside far is defining an appropriate representation for each lineage node. In Figure 1, we presuppose that single phenotype vector is readily available for every cell type. However, such assumption glosses over a key biological complexity: the definition of cell types remains contentious. The rapid expansion of single-cell technologies I has vastly improved our capacity to measure cellular heterogeneity at scale, yet cell-type nomenclature often relies on a few canonical markers (Arendt et al., 2016) practice still widely debated (Domcke & Shendure, 2023).
From a developmental perspective, "lineage" offers more objective concept: it captures the ground truth history and potential future of cell, quantifying how individual cells emerge and give rise to others within the same organism. Unfortunately; in most animals, obtaining a complete lineage-based taxonomy is not feasible. Visual tracking of cell divisions is only possible for transparent organisms such as the nematode Caenorhabditis elegans, where every cell division and fate has been cataloged in single canonical lineage (Packer et al., 2019). This near-complete knowledge also extends to the closely related species, C. briggsae, which also displays a nearly invariant lineage (Large et al., 2024).
In our experiments, we leverage precisely these lineage-annotated single-cell RNA-seq datasets from (Packer et al., 2019) and (Large et al., 2024) as real-data benchmarks. Let {æ"} )== denote the observed molecular profiles of n individual cells, with each profile a² IR.. Suppose we have mapping from cells to their respective lineage nodes (i.e., cell types). For lineage node v, let S. denote the subset of cells assigned v. We then form an aggregate representation
xt Aggregate( ; E S,),
where the aggregation could be as simple as computing the arithmetic mean if the cells exhibit minimal ambiguity in their type assignments. Indeed, in many practical single-cell atlas pipelines, straightforward average of cells that share unambiguous lineage labels is often used (Packer et al., 2019; Large et al., 2024).
Nonetheless, complications arise because cell types are not always distinct clusters in high-dimensions space- indiiviuua cells may lie near the boundaries between nominally different types. Thus, assigning cells to discrete categories can be nontrivial, especially as the number of cell types grows. An alternative view is to treat cell aggregation as a set-based or multiple-instance problem (Kosiorek et al., 2019; Lee et al., 2019; Ilse et al., 2018; Zhao et al., 2021), in which each "bag" (set of cells) is mapped a single label (the lineage node). Such methods provide flexible strategies for aggregating multiple cell profiles, accommodating overlap and uncertainty in cell-type definitions.
E.3. Fraction of Unknown Quartets on Full Balanced Binary Tree
Suppose we have full binary tree with N leaves. Suppose we know the topology down to level L. So there are k 2 clades level I.. Each clade has N leaves. The number of all the quartets is
2t
N
71
Q
~
4
24
When L = 1, the fraction of known quartets is
(m:22 (2/2)
3 nn 2)
3n
Q
0.335
8 (n- 1)(n 3)
8n²
So the fraction of unknown quartet Qo = 1- Q = 0.625.
Nature Method of the Year 2013: single-cell sequencing; 2019; single-cell multimodal omics; 2020: spatially resolved transcriptomics.
25

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
When L the number of unknown quartets is:
k
71
Qo
+
(N
n)
3
(4)-type
(G+ Deyye
+
11
(N n1)
3
n
R 24
x
+
24
x
(N).
24
6
24 x n²
24 x (N/22)1
N 2
N
24
24
24
(24)²
24 23L"
n
N 24 x (N/22)3
N
2
N 1
2
x
6
(24)3
6
2
Therefore, the fraction of unknown quartets is roughly
N8
N
4
Qo
24
2
24
230
+
+
N4
23L
22L
23L
22L-2²
21
Therefore, the fraction of unknown quartets independent to the size of the tree.
L = 1, Qu = 0.625.
L Qo 0.265.
T. 3, Qo = 0.064.
F. Model
F.1. Model Architecture
Our proposed framework, Cel aims learn embeddings from high-dimensional phenotypic data that facilitate phylogenetic reconstruction. To effectively learn relationships among cells, use sequence of Transformer encoder blocks as the backbone of the network, illustrated in Figure 11. Unlike classical Transformer models, we do not include positional encodings, as our input cells are not inherently ordered. Without positional constraints, the self-attention mechanism can focus purely on learning meaningful relationships based on the feature similarities between cells.
Moreover, we incorporate two types of dropout regularization: Data Dropout, which applied in the attention encoder to prevent overfitting on input features; Metric Dropout, dropout layer added after the network's s output layer(Qian et al., 2014). Empirically, found out that Metric Dropout improves the model's performance. We call the dropout layer after the output layer the metric dropout. The dropout in the attention encoder is called data dropout.
For comparison, we also implemented a CellTreeQM-FC model with straightforward feedforward architecture. It consists of a stack of eight fully connected layers, each with a hidden dimension of 1024. Nonlinear activation functions (ReLU) are applied between layers to introduce model capacity and expressiveness.
We compared the performance between the network with Transformer encoder backbones and Fully connected layers as backbone a real dataset under a supervised setting. The network with the attention module performs better than FC. This indicates that while this FC is simple and relatively fast, it learns the pairwise distances within each quartet without modeling the global pairwise relationship.
For leave permutation, we randomly shuffle the labels of leaves. For cell permutation, we randomly shuffle the rows within each column. For gene permutation, we randomly shuffle the columns within each row. Those configurations serve as null experiments to see the performance of the model when we break the original pattern in the data.
26

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table RF distances for various datasets and embeddings. Lower values indicate that similar the ground truth topology. Permutation experiments are conduced with CellTreeQM-taansfoome Experiments on C.elegans Small are repeated 3 times. Values in parentheses are standard errors.
Cell'TreeMM- transformer
QMM fc
Leaves Permutation
Cell
Gene Permutation
N leaves
Dir. Recon.
Permutation
C.elegans Small
102
0,929
0.246 (0.012)
0.400 (0.026) 0.647
0.510 (0.058)
0.927 (0.014)
0.937 (0.012) 0.973
C.elegans Large
295
0.955
0.571
0.876
0.969
Layor No m
Additin
Linrar Embedding
Dropout
Output Layer
Sequence
Transformer Encoder Block
Sequence cells
Additon
x8
Dropout
(a) Architecture
(b) Transformer Encoder
Figure 11. (a) The architecture of PiyloDist (b) Transformer Encoder Block
F.2. Feature Gating
While enforcing an additive structure and preserving original distances remain central to our approach, many high- dimensional phenotypic datasets (e.g., ScRNA-seq) include numerous features that not reflect lineage-related variation. To address this, we introduce a feature gating module, which adaptively modulates the contribution of each input feature. By emphasizing lineage-relevant signals and down-weighting confounding or redundant attributes, the gating module can improve downstream tree reconstruction. To learn effective feature mask, use Gumbel-SSfftaat (Gumbel, 1954) approach that promotes discrete gating decisions. Applying the gating is a simple elementwise product: ã; fi.
Gumbel Gating. To learn an effective feature mask, we use Gumbel-Softmax (Gumbel, 1954) approach that promotes discrete gating decisions:
g GumbelSoftmax (MLP(E), r, hard = True).
where E is an embedding for each feature, MLP projects this embedding into 2-dimensional logits & (one for "off" and one for "on"), and 7 is temperature parameter. In the hard-sampling regime (hard True), the gating weights become nearly binary (0 or 1), effectively pruning or retaining each feature. Applying the gating a simple elementwise product: z; Zg Di-
Sparsity Penalty. To encourage gating out superfluous features, we introduce sparsity penalty:
Σ 9:
2 (sparsity)
Aspar input dim
gates
where Aspar a tunable coefficient. Lower total activation (E 9:) results a smaller penalty, thus incentivizing the network keep fewer features "on." This penalty helps reduce noise and highlight relevant signals for lineage reconstruction.
27

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
F.3. Loss Function Component Study
To further dissect the contributions of each component in our framework, we conduct ablation study using the C.elegans Small dataset under supervised setting. Table reports the RF distances from trees reconstructed under various modified configurations of CellTreeQM, isolating the effects of the "close" and "push" terms of the quartet loss, well as the regularization term f2.
The ablation results confirm that each component of our loss function plays a significant role in shaping the latent space. The combination of the "close" and "push" quartet constraints is essential to effectively approximate an additive metric, while the regularization ensures that the learned representation remains grounded in the original phenotypic data. Together, these components enable CellTreeQM achieve superior topology recovery compared baseline or partially ablated models.
Table Loss component study on the C.elegans-Dev dataset. Lower RF distance values indicate better topological similarity to the ground truth. The reported values are means across runs, with standard deviations in parentheses.
Quartet Sampling
Deviation
Additivity
Close
Push
margin
Relative RF 1
baseline
mismatched
0.01
10
0.5
0.274 (0.021)
(a)
al
0.839 (0.01 I)
a2
0.846 (0.008)
(b)
bl
0.005
0.838 (0.008)
62
0.01
0.836 (0.008)
b3
0.1
0.707 (0.006)
b4
0.5
0.277 (0.016)
b5
0.253 (0.016)
b6
0.525 (0.203)
(d)
d1
0
0.514 (0.042)
d2
10
0.547 (0.019)
1
0.433 (0.031)
c2
2
0.377 (0.026)
e3
5
0,321 (0.023)
e4
20
0.249 (0.019)
e5
30
0.257 (0.017)
fl
0
0.267 (0.012)
f2
0.1
0.263 (0.017)
0.275 (0.030)
14
0.7
0,287 (0.040)
15
0,314 (0.018)
g1
matched
0.860 (0.018)
g2
all
0.306 (0.022)
G. Results
G.1. Baselines
Triplet Loss For each quartet of leaves, first identify the two leaves with the smallest ground-truth distance (based on the known quartet ordering) and treat them the anchor (A) and positive (P). We then select the leaf that is farthest from A to serve as the negative (N). Denoting the learned embeddings as ʃ()) and using a margin m, the triplet loss is defined as: Lm = E(.PNN [II5(A) - s(P) (IA F(V) + mg)
where [+ denotes the hinge function max(0,-). Each quartet thus provides local distance orderings that the learned embedding space must respect.
Quadruplet Loss We extend the triplet formulation by incorporating a second negative. From each quartet, after we identify the closest pair (A, P), we designate two negatives, N and N'. chosen among the more-distant leaves. One common
28

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
form of the quadruplet loss is:
Equad
Σ
[1(((A) -(P)) (I((A) f(N) -1(A))
(A.P,N.N))
+ ((P)) 15(N) S(N) +
where a and [ are margins. The first bracket encourages the anchor-positive distance to be smaller than the anchor-negative distance, as in triplet loss, while the second bracket enforces additional separation between (A, P) and the second negative pair (N", thereby enhancing global distance structure.
CellfreeeM and both baselines produce a learned embedding space from which we extract pairwise distances between leaves.
G.2. Evaluation
We assess the reconstructed tree t against ground-truth tree 7 using metrics such as:
Robinson-Foulds (RF) Distance. The RF distance quantifies the topological difference between two unrooted trees by comparing their sets of partitions, where partition corresponds to split in the tree that divides the taxa into two complementary subsets. The metric counts how many partitions differ between the inferred and the true trees. We will generally present normalized RF distance, where 0 implies identical tree topology and implies that no partitions are shared between the two trees.
Quartet Distance (QD). The RF distance is widely used due to its conceptual simplicity and biologist's focus on lineage relationships (i.e., tree topology). However, it does have limitations. Because it treats all partitions equally, does not distinguish between topological differences that might have different biological relevance. More importantly, the distance measure is sensitive to tree differences that arise by cut-and-paste operation. For example, if one leaf vertex is moved from one side of the tree to another, RF might be 1, even if the remaining tree structure is identical. Thus, to consider more detailed subtree structure, we introduce quartet distancc(Bryant et al., 2000). Given any four leaf vertices (i.e. quartet of leaves), there are three possible arrangements of their unrooted tree-graph relationships. Given two tree graphs, we consider all possible quartets leaves and compute the percent of quartet tree graphs that are different as the quartet distance. For large trees, we may approximate the quartet distance by a sample of the leaf vertices.
For reference, we also compare to "direct reconstruction" approach that uses raw Euclidean distances in gene-expression space, denoted as base RF and base QD. We use A ARRF and A%QD to measure the relative improvement in RF or QD over direct raw-data reconstruction (higher is better).
bese
recoon
QD
QD
A RRF
A% QD
RFhase
QD
Label Permutation as Null Experiments To verify that our method is genuinely learning lineage information (rather than artifacts of high-ding -inheniinnsi data), we permute the mapping of data rows to lineage leaves, effectively scrambling the ground-truth relationships as leaves permutation. The permutations break the biological (or simulated) structure that underlies the lineage tree.
G.3. Supervised Setting
Simulation Table 7 summarizes the performance of our method under four simulated scenarios (A-D), each parameterized by distinct signal, noise, and alternate tree noise settings. In each scenario, we vary the dimensionality of the signal features (dag)) Gaussian noise (dmoise), ), and alternate tree noise (dAusig), as well as the scaling factors a (for noise standard deviation) and B (for branch lengths in the alternate tree). We define the signal-to-noise ratio (SNR) by the ratio of the total signal dimensionality to the of noise and alternate tree noise dimensions, SNR daig/( dnuise T dansiy ). The total feature dimensionality d thus reflects both signal and noise features combined.
Under "CellTreeMM" we compare two modes: JF (using all features) and G (applying a Gumbel-based feature gate). The final three columns ("Recall," "Precis.," A) further illustrate how well the gating module identifies true signal features. We observe that using all features without gating (F) can be prone to noise contamination when dgoise and dausig are large, while the humbel-based gate (9) achieves higher Recall and Precision of signal features and remains relatively stable (as seen in
29

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
A). These trends hold across the different scenarios, with certain variations in performance as the SNR, scaling factors and B. and total dimensionality d change. For additional scenarios with Meaves 128 and 256, as well as per-run standard deviations, we refer readers to the appendix.
Table 7. Performance comparison on simulated data with Tileaves = 6-1 (scenarios A-D). Each row shows parameter choices for the signal (w, dsig), Gaussian noise (duoise; a), and alternate noise (S, T, daisig: (5). is the scaling factor of noise stander deviation such that dnose = sig. B is the scaling factor of the branch length range of the alternative tree such that Wah = -B.. We define SNR as SNR = dig/(dause T x dansig) Here, denotes the total feature dimensionality. "Direct Recon." measures reconstruction when using only the signal features (Signal) vs. when using both signal and noise (Noisy). "CellTreeQM"" (J, G) indicates whether all features are used (F) or a Gumbel-based feature gate is applied (g). Each value is averaged over five runs, "G-Gate Performance" columns show: (Recalf) the percentage of signal features selected (out of all signal features) at the persoreronnnnng training step; (Precis.) the percentage of selected features that are signal features at that same step; (A g) the standard deviation of the number of gate changes over the final one-third of training steps. Each value is averaged over five runs, Additional results (including standard deviations) for Filcoves 128 and 256 are provided in the appendix.
Signal
Gauss, Noise
Alt. Tree Noise
Summary
Direct Recon.
CellTheeQM
G-Gate Performance Precis.
dag
desis
g
T
darsi:
8
SNR
Signal
Noisy
JF
G
Recall
Ag
20
0.5
20
0.5
0.291
0.615
0.318
0.126
0.85
0.946
1.276
2
50
0.5
50
0.5
150
0,095
0.103
0.041
0.804
0.951
2.158
2
100
100
0.5
100
100
0.5
300
0.028
0.275
0.037
0.014
0.824
0.884
3.624
2
20
100
0.5
0.2
120
0.292
0.534
0.512
0.182
0.94
0.775
3.064
5
50
500
1
0.1
550
0.156
0.865
0.884
0,370
0.9
0.424
17,267
10
100
2000
2
0.05
2100
0.157
0.980
0.960
0.867
0.794
0.130
105.705
2
20
20
20
0.5
40
0.315
0.567
0.233
0,108
0.89
0.981
1.217
C
5
50
50
100
0.5
150
0.177
0.951
0.603
0.056
0.848
0.954
3.605
100
300
0.144
0.997
0.856
0.263
0.844
0.738
12.961
2
0.5
20
0.17
140
0,308
0.600
0.249
0.98
0.663
3.407
5
50
500
1
50
100
0.08
650
0.174
0.948
0.921
0.403
0.828
0.403
22,853
10
100 2000
2
100
200
2
0.05
2300
0.144
0.984
0.974
0.875
0.772
0.112
129.442
Real Data Results for the supervised setting on all real datasets are summarized in Table 8. For the C. elegans Small and Mid datasets, we report the mean and standard deviation over three independent runs. For the C. elegans Large dataset, we report results from single run due the high computational cost stem-nt from both the large number of training quartets (corresponding to 295 leaves) and the inefficient implementation of RF distance used during evaluation.
Permutation experiments validate quartet-based fitting. Training CellTreeQM label permuted tree T" still embeds the data with moderate fidelity (A%RF), reflecting information in an unlabeled tree, but less accurately than with the true tree. In contrast, triplet and quadruplet models struggle to align a random tree with the data. Similar trends hold for the C. elegans Mid and Large datasets, where triplet/uaarrppee losses improve over raw data but still lag behind CellTreeMM (see Table 8). These results echo the recent findings in (Schlüter & Uhler, 2025) showing that true lineage topologies yield lower training losses and more generalizable embeddings, thus confirming there is ample lineage signal in the gene expression data-our method is not merely overfitting.
Visualization on C. elegans Small CellTreeQM embeds the leaves into 228-iimensional space. To have some intuition about the latent space, we project the embeddings to 20 principal components (via PCA), followed by 2D t-SNE projection. Figure 12 displays the results on C. elegans Small, coloring cells by common ancestors at different hierarchical levels. While triplet and quadruplet losses capture some broad structure, CellTreeQM more effectively organizes the leaves according to the underlying tree hierarchy.
In addition to these embeddings, Figure 13 illustrates the final lineage trees reconstructed from the learned distances of CellTreeQM, Triplet, and Quadruplet. Each leaf is colored according to its major lineage annotation in C. elegans. Notably, CellTreeQM yields a more faithful global topology, with tighter, lineage-consistent subtrees. By contrast, trees reconstructed under triplet or quadruplet losses exhibit more dispersed leaf placements, sometimes grouping distantly related lineages together. These visual differences align with our quantitative findings in Table 1 and underscore CellTreeQM's 's advantage in accurately capturing the hierarchical relationships among cells.
Reconstruction methods To evaluate the learned embeddings across different tree reconstruction algorithms, we compared five methods Bettooss-Neeghhor--ooini -eigghor- (NJ), UPGMA, FastME, Ward, and Single linkage- on the C. elegans Small dataset.
30

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Across all five reconstruction methods, CellTreeQM consistently achieves the lowest RF distances on both training and testing sets, demonstrating robust learning and generalization capabilities. As shown in Figure 14, the radar plot highlights the relative RF improvement of CellTreeQM compared to models trained with Triplet and Quadruplet losses across all reconstruction methods.
Interestingly, the Ward method slightly outperforms NJ in some settings, despite NJ being theoretically optimal for additive trees. This may suggest that our learned embeddings support variance-based clustering more effectively in certain scenarios. We leave more detailed analysis of this behavior to future work.
G.4. Weakly Supervised Setting
G.4.1. HIGH LEVEL PARTITION SETTING.
We report the muowt-quartet distance (K-QDist and the unknown-quarter distance (U-QDist). Unsurprisingly, K- K-QDist remains near zero for successful methods, since those quartets are directly supervised. Meanwhile, U-QDist steadily decreases deeper prior levels, indicating that Ccl generalizes better fits unconstrained quartets as more high-level clades become known. We also measure ARF = RFO RF, the improvement over raw-data baseline. This gap grows with increased prior, demonstrating that additional top-level constraints help the model recover more correct branching patterns.
To gauge how well the model recovers the unknown internal structure within each clade, we also track local subtree errors at various "levels" of the reconstructed tree. Even though these subclades were not all explicitly supervised, the table reveals that CellTreeeM obtains lower Robinson Sobilson-Foulds distances on these deeper substructures particularly in the presence of more known quartets.
We report the fraction of known quartets at levels of the full balanced dataset with 64 leaves and for the three C. elegans datasets in Table 9.
Performance on Simulated Data. The results for the high-level partition setting are shown in Figure 15. The dataset is simulated with Teeavss = 64 and a maximum walk of 2 per branch. Each leaf contains 50 signal features and 500 Gaussian noise features, with the same mean and standard deviation as the signal features. Additionally, each leaf has 50 spurious features derived from an alternative tree. There are two alternative trees, each with 32 leaves and the same maximum walk as the true tree. Each experiment is repeated 10 times, and the mean and standard deviation are shown as the central value and error bars in the figure.
Performance on C. elegans Data. Under the high-level partition setting, the results for C. elegans Small are shown in Figure 20 and Table 10. The results for C. elegans Mid are shown in Figure 21 and Table 11. The results for C. elegans Large are shown in Figure 21 and Table 12. The experiments for C. elegans Small are repeated 10 times. The experiments for C. elegans Mid are repeated 3 times. The experiments for C. elegans Large are run once due to the high computational cost.
G.4.2. PARTIAL LABELED LEAVES SETTING.
In many biological systems, researchers may know coarse-grained lineage structure up to a certain "level" of the tree but not the fine-grained branching events beneath it. Concretely, let us define level as the number of branching steps from the root, We assume we know how leaves are divided into clades at level, as well as the relationships among these clades (see Fig. 2, left). Hence, each leaf is assigned to exactly one of these high-level clades, but the tree structure within each clade remains unknown.
When forming quartets under this partial knowledge, some quartets still have ambiguous structure ("unknown quartets"). Specifically, a quartet is unknown all four leaves lie in the same clade if three of the leaves come from the same clade, because the high-level partition does not determine the precise branching among these leaves. Quartets with leaves spanning different clades (e.g., two leaves from one clade and two from another) become "known quartets," whose topological order can be inferred from the clade-level prior. In our weakly supervised training, we compute the additivity loss only on these known quartets, since their correct topology is implied by the high-level partitions.
The experiments for C. elegans Small are repeated 10 times. The experiments for C. elegans Mid are repeated 5 times. We did not run any experiment on C. C.elegans Large because the results on elegans Small and Mid. demonstrate the difficulty
31

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
of this setting. Table 13 reports the Known, Partial, and Unknown counts and proportions for different known fractions in elegans Small and Mid. datasets.
Performance on Simulated Data. The results for the partial-labeled setting are shown in Figure 19 with known fractions as 35%, 55%, 85%. The dataset is simulated with Rleaes = 128 and a maximum walk of 2 per branch. Each Ieaf contains 50 signal features and 500 Gaussian noise features, with the same mean and standard deviation as the signal features. Additionally, each leaf has 50 spurious features derived from an alternative tree. There are two alternative trees, each with 64 leaves and the same maximum walk as the true tree. Each experiment repeated 10 times, and the mean and standard deviation are shown as the central value and error bars in the figure.
Performance on C. elegans Data. The results for C.elegans Small and Mid summarized in Table 14 and 15 for fraction 30%, 50%, 80%. The results are also visualized by bar plots in Figure. 20 and 21. The experiments for C. elegans Small are repeated 10 times. The experiments for C. elegans Mid are repeated 5 times.
G.S. Unsupervised Setting
Here, we provide preliminary exploration assess whether the CellTreeQM framework can be extended to unsupervised learning scenario. We use Brownian motion simulation to generate a phylogenetic tree with 128 leaves with unit length. Each leaf is represented by 32 signal features and 32 Gaussian noise features, with the noise standard deviation set to 10. A direct reconstruction using the noisy data yields an RF value of 0,968. As baselines, we applied PCA with 5, 10, and 20 principal components, well as Gaussian random projections with 2, 5, and 10 dimensions; all of these produced an RF value of 1. When we reconstruct the tree only based on the signal features, we got the optimal reconstruction accuracy RF 0.128.
To adapt CellTreeQM to the unsupervised setting, we make two main modifications to simplify the model compared to its supervised and weakly supervised versions:
1. We replace transformer encoder fully connected backbone of 3 layers, each with 32 hidden units.
2. We replace the Gumbel-Softmax feature gating with learnable linear projection matrix G' E gdxd where d is the number of input features.
Because we do not have ground-truth distances among leaves in the unsupervised scenario, we approximate additivity by sorting the quartet distances {S1, S2, S3} (see 5. based on their values in the embedding space. Following the same idea as in DeSeto's ' algorithm, we define the "close" term as: and take
Lquaret
L.close
Ladditivity Q
1
Σ C
quuaret
4=1
where Q is the total number of quartets.
We regularize the projection matrix G to encourage excluding noise features without excessively penalizing omissions. Specifically, we initialize G as the identity matrix and apply an Lı penalty ||G - /|I Note that, unlike in the supervised and weakly supervised settings-where feature gating is applied directly to the input-here we apply feature gating only to the deviation component. Concretely, we compare the learned embedding f(X) to its linear projection GX via
1 R(S X) / - 1F
where D is an operator (e.g., pairwise distance) applied the corresponding space. The overall loss function then combines the additivity loss, the embedding deviation term, and the regularization on G:
min
Luativiit (f,X) + XΩ(S,X) + ||G - /111-]] f.G
Figure 22 illustrates how CellTreeMM learns in a purely unsupervised setting over the course of training on a simulated dataset. The figure shows that CeM even without any labels or supervision, progressively approaches the signal-only
32

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
baseline, suggesting that the model's gating mechanism and the unsupervised objective successfully filtering out noise and capturing the underlying signal.
H. Training Setups
We evaluated our method in two settings: supervised and weakly supervised. For both settings, we tested on simulated and real datasets. Unless otherwise noted, we did not extensively tune the hyperparameters.
Supervised Setting.
We use Transformer with 8 layers and 2 attention heads. The projection layer and hidden layer are both 256-dimensional, and the model outputs 128-dimensional embeddings. We apply a data dropout of 0.3 and metric dropout 0.2. When necessary, we set the gate regularization weight to 5.
Simulation:
Real data: The Transformer also has 8 layers and 2 attention heads, but with 1024-dimensional projection and hidden layers, producing 128ddimensional outputs. Here, we use a data dropout of 0.1 and metric dropout of 0.1. When needed, the gate regularization weight is 0.01.
Weakly Supervised Setting.
We use a Transformer with layers and 2 attention heads. The projection and hidden layers are both 256-dimensional, and the model outputs 128 228-dimensional embeddings. We apply a data dropout of 0.3 and metric dropout of 0.2. When required, the gate regularization weight is 8.
Simulation:
Real data: The Transformer has 8 layers and attention heads, with projection and hidden layers of 256 dimensions, producing 128 128-dimensional outputs. We use a data dropout of 0.3 and a metric dropout of 0.2, and set the gate regularization weight to 0.01 when needed.
More Results
In the main text, we demonstrated that CellTrecQM considerably improves lineage reconstruction accuracy over standard contrastive baselines on C.elegans datasets. We also showed that the high-level partition setting is a practical and effective form of weak supervision, whereas the partially leaf-labeled setting remains too challenging to be useful practice.
To further validate the generalizability and discovery potential of CellTreeQM, we evaluated the model on two additional CRISPR-based lineage datasets derived from mouse embryonic stem cell (mESC) clone 1D5 with non-targeting sgRNA: 3435_NT.TI (151 cells) and 3435_NT_TG NT-T6 (91 cells), obtained from Chan et al. (2019). Proxy ground truth trees were reconstructed using Cassiopeia. Due to ambiguity in the tree structure, we sampled binary trees from the full lineage. Quantitative results are shown in Table 16, 17. The corresponding barplots are shown in figure 23 and 24.
These experiments reinforce our findings on the C. elegans data: CellTreeQM consistently outperforms baseline methods, particularly in generalizing to unseen quartets. We applied CellTreeQM without sptaset- tuning. We expect that further gains may be possible with targeted optimization.
33

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table 8. Supervised results on Cell Lineage Benchmark. Direct reconstruction on raw data yields Base RF and Base Qist. Suffix "-G" denotes feature gating, and "-p" indicates label permutation. Standard deviations are in parentheses, Experiments are repeat times expect C. elegans Large.
Method
Train RF,
Test RF|
Test QD+
AFRF1
A % QD1
C. elegans Small, Base RF=0.923;
Base QD=0.554
CellTTeeQM
0.000 (0.00)
0.286 (0.05)
0.074 (0.01)
0.690 (0.05)
0.867 (0.02)
0.000 (0.00)
0.226 (0.02)
0.084 (0.01)
0.757 (0.03)
0.848 (0.01)
0.013 (0.00)
0.566 (0.04)
0.208 (0.03)
0.434 (0.04)
0.691 (0.05)
Triplet
0.519 (0.03)
0.741 (0.01)
0.201 (0.01)
0.179 (0.01)
0.637 (0.02)
Triplet-G
0.545 (0.03)
0.724 (0.00)
0.207 (0.01)
0.203 (0.03)
0.631 (0.02)
Triplet-p
0.677 (0.06)
0.963 (0.01)
0,413 (0.04)
0.037 (0.01)
0.385 (0.06)
Quadruplet
0.057 (0.00)
0.492 (0.03)
0.120 (0.00)
0.454 (0.02)
0.784 (0.01)
Quadruplet-G
0.061 (0.00)
0,471 (0.04)
0.116 (0.00)
0.484 (0.04)
0.791 (0.01)
Quadruplet-p
0.118 (0.00)
0.848 (0.01)
0.310 (0.01)
0. (0.01)
0.538 (0.02)
elegans Mid, Base RF=0.967,
Base QD=0.579
CellTreeQM
0.022 (0.00)
0.513 (0.01)
0.155 (0.00)
0.457 (0.02)
0.730 (0.01)
QcIlTreeQM-G
0.031 (0.01)
0.472 (0.00)
0.130 (0.01)
0.490 (0.01)
0.773 (0.01)
QeIp
0.035 (0.01)
0.831 (0.00)
0.356 (0.02)
0.165 (0.00)
0.466 (0.03)
Triplet
0.650 (0.02)
0.811 (0.00)
0.189 (0.00)
0.095 (0.01)
0.673 (0.01)
Triplet-G
0.693 (0.02)
0.809 (0.01)
0.183 (0.00)
0.112 (0.01)
0.682 (0.00)
Triplet-p
0.878 (0.03)
0.970 (0.01)
0.438 (0.01)
0.026 (0.01)
0.344 (0.01)
Quadruplet
0.146 (0.01)
0.557 (0.01)
0.179 (0.01)
0.396 (0.01)
0.690 (0.01)
Quadruplet-G
0.174 (0.04)
0.537 (0.01)
0.166 (0.01)
0.423 (0.02)
0.711 (0.02)
Quadruplet-p
0.283 (0.03)
0.915 (0.01)
0.395 (0.00)
0.082 (0.01)
0.409 (0.01)
C. elegans Large, Base RF=0.949;
Base QD=0.586
CellTrecQM
0.113
0.568
0.111
0.401
0.811
CeIlTreeQM-G
0.140
0.521
0.115
0.439
0.805
CeIpTreeQM-p
0.195
0.863
0.262
0.137
0.606
Triplet
0.822
0.863
0.229
0.077
0.608
Triplet-G
0.808
0.873
0.196
0.073
0.664
Triplet-p
0.979
0.993
0,424
0.007
0.365
Quadruplet
0.432
0.675
0.155
0.284
0.736
Quadruplet-G
0.377
0.712
0.144
0.249
0.754
Quadruplet-p
0.620
0.932
0.317
0.068
0.523
34

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Raw Data
CallTreeQM
Triplet
Quadruplet
t-
Cell Types in Level
AB
P1
Raw Data
CellTreeQM
Triplet
Quadruplet
t-SNE
Cell Types in Level ABaxx
ABPx
EMS
P2
Raw Data
CellTreeQM
Triplet
Quadruplet
t-SNE
Cell Types in Level
ABpxp
ABarpx
Exx
Cx
Dx
ABpxax
MSx
Raw Data
CellTreeQM
Triplet
Quadruplet
t-SNE
f
Cell Types in Level 4
ABpxpa
ABpxapa
MSxa
Epxpp
Dxxa
ABpxpp
ABarpaa
MSxp
Oxa
Dxxp
ABpxaap
ABarppx
Eaxaa
Cxp
Figure t-SNE visualization of CellTrecQM embeddings for elegans Small. The embeddings first reduced to 20 principal
components via PCA before applying t-SNE, Each panel corresponds to different hierarchical level, with colors representing common ancestors at that level.
35

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
CellTeeQM
Triplet
Quadruplet
Figure Reconstructed circular lineage tree for elegans dataset using the learned embeddings from CellTreeQM. Each leaf is color-coded according to its major lineage (e.g., AB, MS, E, C, D), with the circular layout highlighting the hierarchical structure. The faithful grouping leaves into cohesive subtrees demonstrates effectiveness of CellTreeQM capturing global genealogical relationships from the data.
ARF
Train
Test
UPGMA
FestME
RF distance
Inchods
UPGIA Singt
Word
0.2
GeTTeeON Ouotharett
Single
CelTreaQM
Quadruplet
Tripet
0.0
CalThreqq
Quadruplet
Triplet
Figure 14. Comparison of reconstruction accuracy (measured by RF distance) across five tree-building algorithms. Left: A ARF radar plot comparing CellTreeQM, Triplet, and Quadruplet models. Middle Right: bar plots RF distances on train test sets, respectively.
Table 9, Fraction Known Quartets at Levels.
Brownian64
C. elegans Small
C. elegans Mid
C. elegans Large
leaves
64
102
182
295
quartets
635,376
4,249,575
44,224,635
309,177,995
Counts
Prop.
Counts
Prop.
Counts
Prop.
Counts
Prop.
Level
238,266
0.375
1,417,233
0.3335
11,814,336
0.2613
77,232,663
0.2498
Level 2
467,001
0.735
2,515,748
0.592
31,859,427
0.7204
220,351,157
0.7127
Level 3
594,711
0.936
3,526,722
0.8299
39,815,438
0.9003
280,238,934
0.9064
Level 4
635,376
1.000
4,057,919
0.9549
43,012,880
0.9726
301,634,051
0.9756
36

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Across Levels
AQDist Across Levels
AU-QDist Across Levels
AK-QDist Across Levels
1.0
1.0
1.0
1.0
0.8
0.8
0.4
0.2
0.4
0.2
0.2
0.0
0.2
-0.2
0.0
0.0
Level of Information
CellTreeQM
Cel Tee-OOG
Triplet
Quadruplet
Figure 15. Results for high-level partition setting on simulation with 64 leaves.
AQDist
AK-QDist Models
QDist
1.0
0.8
0.0
Level
Level
Level
Level
Level
Level
CallTeeeM
CeITTeeQM-G
Triplet
Triplet-G
Quadruplet
Quadruplet-G
Figure 16. Results high-level partition setting on C.elegans Small dataset. x-axis the level of partition.
ARF Across Models
AQDist Across Models
AK-QDist Across Models
AU-QDist Across Models
0.8
0.6
0.4
0.2
0.0
-0.2
CallTreeQM
CoIITraOMM-G
Triplt
Tripat-G
Quadruplat
Quadruplat-G
Figure 17. Results for high-level partition setting on C.elegans Mid dataset. x-axis the level of partition.
ARF Across Models
AQDist Across Models
AK-Q Across Models
AU-QDist Across Models
Level
Level 2
Level 3
Level
Level 2
Level 3
Level
Level 2
Level 3
Level
Level 2
Level 3
CollTheeOM
ColITreCMM-G
Tripitt
Triplat-G
Quadrupist
Quadruplet-G
Figure 18. Results for high-level partition setting C.elegans Large dataset, x-axis is the level of partition.
37

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table 10. Weakly supervised High-level partition results on C. elegans Small under different partition levels. K-QD and U-QD are quartet distances on the known and unknown quartets, respectively. he reported values are means across three runs, with standard deviations in parentheses.
Method
RE1
RFF
QD!
A % Q
A A%K-QD1
A A-U-QDT
Partition Level: 3
CellTreeQM
0.592(0.02)
0.349(0.02)
0.083(0.00)
0.849(0.01)
0.994(0.00)
0.182(0.03)
CcIITreeQM-G
0.576(0.02)
0.374(0.01)
0.086(0.00)
0.844(0.01)
0.993(0.00)
0.161(0.02)
Triplet
0.735(0.01)
0.263(0.01) 0.193)).02)
0.521(0.01)
0.582(0.02)
0.241(0.00)
Triplet-G
0.723(0.02)
0.208(0.03)
0.260(0.01)
0,526(0.01)
0.584(0.01)
0.255(0.01)
Quadruplet
0.832(0.02)
0.209(0.00) 0.090(0.02)
0.619(0.01)
0.768(0.01)
-0.065(0.01)
Quadruplet-G
0.828(0.01)
0.091(0.01)
0.208(0.00)
0.620(0.00)
0.772(0.00)
-0.076(0.02)
Partition Level: 2
CcllTreeQM
0.657(0.02)
0.107(0.01) 0.274(0.03)
0.805(0.02)
0.998(0.00)
0.558(0.04)
QM-
0.653(0.02)
0.289(0.02)
0.110(0.01)
0.799(0.03)
0.996(0.00)
(.545(0.06)
Triplet
0.745(0.01)
0.191(0.01)
0.329(0.00)
0.399(0.01)
0.623(0.01)
0.111(0.01)
Triplet-G
0.756(0.01)
0.174(0.01)
0.337(0.01)
0.386(0.02)
0.606(0.02)
0.102(0.02)
Quadruplct
0.857(0.01)
0.058(0.01)
0.282(0.00)
0,485(0.01)
0.894(0.01)
-0.037(0.01)
Quadruplet-G
0.863(0.00)
0.057(0.01)
0.287(0.00)
0.478(0.01)
0.894(0.01)
-0.056(0.01)
Partition Level: 1
CcllTreeQM
0.772(0.02)
0.164(0.01)
0.202(0.03)
0.631(0.05)
0.997(0.00)
0.485(0.07)
QMIITreeQM-G
0.788(0.02)
0.133(0.02)
0.186(0.01)
0.661(0.02)
0.997(0.00)
0.527(0.03)
Triplet
0.814(0.02)
0.120(0.02)
0.353(0.01)
0.356(0.01)
0.832(0.01)
0.167(0.02)
Triplet-G
0.808(0.02)
0.105(0.02)
0.348(0.00)
0.365(0.01)
0.843(0.02)
0.173(0.00)
Quadruplet
0.853(0.01)
0.070(0.02)
0.424(0.00)
0.227(0.01)
0.678(0.02)
0.046(0.01)
Quadruplet-G
0.865(0.01)
0.055(0.02)
0.423(0.01)
0,228(0.0))
0.675(0.04)
0.051(0.01)
Table 11. Weakly supervised High-level partition results on C. elegans Large under different partition levels. K-QD and U-QD are quartet distances on the known and unknown quartets, respectively.
Method
RFL
R%FFt
QD4
A A%QDt
A%K-QD1
A A%U-QD1
Partition Level:
CellTreeQM
0.793)
0.132(0.00)
0.071(0.00)
0.875(0.00)
0.989(0.00)
-0.132(0.02)
CcIITreeQM-G
0.798(0.01)
0.122(0.02)
0.070(0.00)
0.877(0.00)
0.992(0.00)
-0.137(0.02)
Triplet
0.806(0.01)
0.114(0.01)
0.244(0.00)
0.571(0.00)
0.616(0.00)
(0170)
Triplet-G
0.830(0.02)
0.091(0.01)
0.243(0.01)
0.573(0.01)
0.620(0.01)
0.158(0.01)
Quadruplet
(.801)
0.051(0.02)
0.290(0.00)
0.489(0.01)
0,554(0.01)
-0.094(0.00)
Quadruplet-G
0.863(0.01)
0.047(0.01)
0.292(0.00)
0.486(0.00)
0.552(0.00)
-0.100(0.01)
Partition Level:
Cell/reeQM
0.850(0.01)
0.072(0.02)
0.124(0.01)
0.781(0.02)
0.996(0.00)
0.227(0.06)
CeM
0..00)
0.070(0.00)
0.115(0.01)
0.797(0.02)
0.996(0.00)
0.280(0.07)
Triplet
0.820(0.01)
0.098(0.01)
0.239(0.01)
0.576(0.01)
0.760(0.01)
0.099(0.01)
Triplet-G
0.859)0.01)
0.055(0.01)
0.237(0.00)
0.581
0.761(0.00)
0.113(0.01)
Quadruplet
0.917(0.00)
-0.010(0.01)
0.235(0.00)
0.586(0.00)
0.864(0.00)
-0.137(0.01)
Quadruplet-G G
0.926(0.01)
-0.018(0.01)
0.234(0.00)
0,587(0.01)
0.868(0.00)
-0.141(0.02)
Partition Level:
CollTreeQM
0.902(0.00)
0.006(0.01)
0.261(0.011
0.539(0.02)
0.999(0.00)
0.414(0.03)
CellTreeeM-G
0.904(0.00)
0.014(0.01)
0.298(0.00)
0.474(0.01)
0.999(0.00)
0.331(0.01)
Triplet
0.850(0.01)
0.063(0.01)
0.364(0.00)
0.357(0.00)
0.831(0.01)
0.228(0.00)
Triplet-G
0.869)0.00)
0.035(0.01)
0.369(0.00)
0.350(0.01)
0.821(0.02)
0.222(0.01)
Quadruplet
0.896(0.01)
0.015(0.03)
0.437(0.00)
0.229(0.00)
0.618(0.03)
0.123(0.01)
Quadruplet-G
0.885(0.01)
0.022(0.02)
0.433(0.01)
0.235(0.01)
0.637(0.02)
0.127(0.01)
38

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table 12. Weakly supervised High-level partition results C. elegans Large under different partition levels. K-QD and U-QD
are quartet distances on the known and unknown quartets, respectively. he reported values are means across three runs, with standard deviations in parentheses.
Method
RF
SRRFT
QD
A A%QDT
A A%K-QD1
A%U-QDT
Partition Level:
Cell'TreeM
0.884
0.055
0.066
0.887
0.992
0.744
QM-
0.884
0.051
0.067
0.884
0.987
0.748
Triplet
0.846
0.105
0.272
0.531
0.573
0.576
Triplet-G
0.853
0.095
0.275
0.524
0.565
0.564
Quadruplet
0.887
0.062
0.312
0,461
0,519
0.746
Quadruplet-G
0.887
0.044
0.316
0.454
0.511
0.745
Partition Level:
CellTreeQM
0.918
0.025
0.117
0.798
0.992
0.646
QM-
0.921
0.022
0.124
0.786
0.997
0.620
Triplet
0.860
0.087
0.259
0,553
0.684
0.364
Triplet-G
0.856
0.088
0.263
0.547
0.680
0.357
Quadruplet
0.928
0.022
0.242
0.583
0.854
0.400
Quadruplet-G
0.918
0.018
0.239
0.589
0.862
0,412
Partition Level:
CcllTreeQM
0.901
0.037
0.379
0.345
0.999
0.127
QMI
0.908
0.026
0.363
0.372
0.999
0.164
Triplet
0.908
0.050
0.390
0.327
0.890
0.140
Triplet-G
0.897
0.040
0.397
0.314
0.857
0.133
Quadruplet
0.918
0.025
0.465
0.200
0.641
0.053
Quadruplet-G
0.932
0.007
0.472
0.184
0.614
0.041
Table 13. Known, Partial, and Unknown counts proportions for different known fractions C. elegans datasets.
C. elegans Small
C. elegans Mid
Known Fraction
Count
Prop.
Count
Prop.
Known Fraction: 0.8
Known
1,663,740
0.392
18,163,86
0.402
Partial
2,579,850
0.607
26,982,990
0.597
Unknown
5,985
0.001
66,045
0.001
Known Fraction:
0.5
Known
249,900
0.059
2,672,670
0.059
Partial
3,749,775
0.882
39,746,070
0.879
Unknown
249,900
0.059
2,794,155
0.062
Known Fraction:
0.3
Known
27,405
0.006
316,251
0.007
Partial
3,193,380
0.752
33,887,268
0.750
Unknown
1,028,790
0.242
11,009,376
0.244
39

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
ARF Across Models
AQDist Across Models
Ak-QDist Across Models
AP-QDist Across Models
AU-QDist Across Models
0.6
35%
65%
85%6
35%
65%
85%
35%
65%
85%
35%
65%
85%
35%
65%
85%
CellfreeQM
CelTTreeQM-G
Triplet
Triplet-G
Quadruplet
Quadruplet-G
Figure 19. Results for partially leaf-labeled setting simulation with 128 leaves dataset. x-axis is the percentage of known leaves.
ARF
AQDist
AK-QDist
AP-QDist
AU-QDist
0.2
30%
50%
80%
50%
80%
30%
50%
80%
30%
50%
60%
30%
50%
80%
CellTree@M
CelfTreeQM-G
Triplet
Triplet-G
Quedruplet
Quedruplet-G
Figure 20. Results for partially leaf-labeled setting on C. elegans Small datasct. x-axis the percentage of known leaves.
AQDist Models
AK-QDist Models
AP-QDist Models
AU-QDist Models
1.0
AQDiet Imean 20)
DK-ODat std)
AP ofat (mean sld)
AU- Al-ODII OLOD mean st0)
(meen a std)
0.4
30%
50%
90%
30%
50%
80%
30%
50%
80%
30%
50%
80%
30%
50%
80%
CellTreeQ
CelMTeeQM
Triplet
Triplet
Quadrupiet
Quadruplet
Figure 21. Results for partially leaf-labeled setting on C. elegans Mid dataset. x-axis the percentage of known leaves.
40

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table 14. Weakly supervised Partial-labeled setting results across known fractions for C. clegans Small. The reported values are means across ten runs, with standard deviations in parentheses.
Method
Train RF|
A RFF
1%QD
A%K-QD1
A%P-QD1
A%U-QD1
Known Fraction: 0.8
CcllTreeQM
0.024(0.03)
0.448(0.06)
0.842(0.05)
0.999(0.00)
0.742(0.07)
0.465(0.13)
CellTreeQM-G
0.031(0.04)
0.411(0.07)
0.837(0.03)
0.999(0.00)
0.700(0.06)
0.371
Triplet
0.454(0.06)
0.175(0.05)
0.728(0.03)
0.895(0.01)
0.624(0.05)
0.339(0.14)
Triplet-G
0.419(0.07)
0.201(0.05)
0.739(0.03)
0.895(0.02)
0.618(0.05)
0.394(0.09)
Quadruplet
0.066(0.04)
0.403(0.03)
0.796(0.06)
0.953(0.02)
0.697(0.09)
0.435(0.22)
Quadruplet-G
0.060(0.04)
0.411(0.033
0.784(0.04)
0.936(0.01)
0.662(0.05)
0.320(0.09)
Known Fraction: 0.5
CellTreeQM
0.012(0.01)
0.092(0.05)
0.609(0.05)
0.999(0.00)
0.598(0.06)
0.398(0.05)
CelITreeQM-G
0.016(0.01)
0. 0.100(0.04)
0.602(0.04)
0.999(0.00)
0.571(0.03)
0.352
Triplet
0.303(0.09)
0.049(0.04)
0.505(0.05)
0.879(0.02)
0,493(0.05)
0.304(0.06)
Triplet-G
0.319(0.09)
0.067(0.03)
0.520(0.05)
0.883(0.02)
0.499(0.05)
0.308(0.055
Quadruplet
0.023(0.02)
0.115(0.04)
0.549(0.04)
0.934(0.03)
0.537(0.04)
0.340(0.06)
Quadruplet-G
0.039(0.03)
0.103(0.04)
0.540(0.05)
0.942(0.02)
0.515(0.04)
0.299(0.05)
Known Fraction: 0.3
CellTreeQM
0.000(0.00)
-0.023(0.02)
0.368(0.06)
1.000(0.00)
0.401(0.06)
0.250(0.06)
CeIITreeQM-G
0.008(0.02)
-..020(0002)
0.336(0.08)
0.999(0.00)
0.340(0.08)
0.180(0.07)
Triplet
0.156(0.06)
-0.00((0002)
0.358(0.04)
0.889(0.02)
0.384(0.04)
0.263(0.05)
Triplet-G
0.169(0.09)
-0.017(0.03)
0.352(0.03)
0.890(0.03)
0.363(0.03)
0.220(0.04)
Quadruplet
0.008(0.02)
-0.020(0.03)
0.358(0.03)
0.918(0.04)
0.386(0.03)
0.259(0.02)
Quadruplet-G
0.029(0.05)
-0.016(0.03)
0.364(0.06)
0.940(0.03)
0.362(0.06)
0.208(0.07)
35
1.0
30
Signals/Noiss
Relative RF
25
Selected Signals/
20
0.6
15
0.4
10
5
10
15
20
25
30
Steps
CellTreeQM
Optimal
Signals
Noise
Figure 22, Training dynamics of MellTreeQM in purely unsupervised setting on simulated dataset. The left axis reports the relative RF of the reconstructed tree (blue) compared the optimal RF (orange dotted line), while the right axis indicates the number of selected signal (green dashed) and noise (blue dashed) features over training steps. Early on, more noise features are included, resulting in poorer performance; as training proceeds, CellTreeQM discards the noise approaches the optimal reconstruction.

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table 15. Weakly supervised Partial-labeled setting results across known fractions for C. clegans Mid. The reported values means across five runs, with standard deviations in parentheses
Method
Train RF4
A RFF
A A%QD
A%K-QD1
A%P-QD1
A%U-QD1
Known Fraction: 0.8
CellTreeQM
0.108(0.02)
0.339(0.03)
0.840(0.02)
1.000(0.00)
0.733(0.04)
0.407(0.07)
CelITreeQM-G
0.150(0.05)
0.309(0.04)
0.847(0.06)
1.000(0.00)
0.718(0.10)
0,441(0.13)
Triplet
0.628(0.02)
0.090(0.02)
0.804(0.02)
0.921(0.01)
0.725(0.04)
0.503(0.10)
Triplet-G
0.656(0.02)
0.082(0.01)
0.801(0.03)
0.918(0.01)
0.681
0.431(0.11)
Quadruplet
0.169(0.02)
0.345(0.03)
0.803(0.03)
0.981(0.01)
0.684(0.05)
0.343(0.09)
Quadruplet-G
0.250(0.07)
0.271(0.07)
0.817(0.02)
0.980(0.00)
0.691(0.03)
0.351(0.07)
Known Fraction: 0.5
CellTreeQM
0.055(0.01)
0.069(0.02)
(.589(0.03)
1.000(0.00)
0.579(0.03)
0.349(0.03)
QMI
0.180(0.10) 10)
0.029(0.01)
0.609(0.07)
(0991(0.01)
0.573(0.06)
0.344(0.07)
Triplet
0.491(0.03)
0.025(0.03)
0.569(0.02)
0.923(0.01)
0.560(0.02)
0.361(0.04)
Triplet-G
0.509(0.06)
-0.004(0.02)
0.571(0.08)
0.923(0.01)
0.520(0.08)
0.308(0.11)
Quadruplet
0.093(0.02)
0.058(0.03)
0.587(0.03)
0.988(0.00)
0.576(0.03)
0.365(0.05)
Quadruplet-G
0.180(0.10)
0.052(0.02)
0.562(0.02)
0.984(0.01)
0.526(0.04)
0.296(0.05)
Known Fraction: 0.3
CellTreeQM
0.000(0.00)
-.026(0.022)
0.385(0.05)
1.000(0.00)
0.420(0.05)
0.259(0.06)
CcIITreeQM-G
0.027(0.03)
-0.03600.02)
0.400(0.04)
0.999(0.00)
0.393(0.04)
0.227(0.05)
Triplet
0.275(0.10)
-0.028(0.02)
0.378(0.07)
0.935(0.01)
0.412(0.07)
0.257(0.07)
Triplet-G
0.306(0.13)
-0.029(0001)
0.311(0.06)
0.932(0.01)
0.332(0.05)
0.164(0.06)
Quadruplet
0.008(0.02)
-0.022(0.04)
0.366(0.02)
0.979(0.01)
0.402(0.03)
0.239(0.02)
Quadruplet-G
0.067(0.06)
-0.045(0.02)
0.403(0.05)
0.987(0.01)
0.424(0.05)
0.265(0.05)
ARF Across Models
AQDIst Across Models
4K: ADstt Across Models
AU- AU-QDist Across Models
1.0
0.9
0.5
0.4
0.2
0.0
Level
Level 2
Level
Level
Level 2
Level 3
Level 1
Level 2
Level 3
Level 1
Level 2
Level 3
CellTreeQM
CelTTreeQMiG
Triplet
Trolet-G
Quadrualet
Quedruplet-G
Figure 23, Results for high-level partitioning setting on CRISPR dataset 3435_NT_TI. x-axis is the level of partition.
42

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
Table 16. Weakly supervised high-level partitioning setting results on CRISPR dataset -435_NT_TI under different partition levels. K-QD and U-QD quartet distances on the known and unknown quartets, respectively. The reported values means across three runs, with standard deviations in parentheses.
Method
RF1
ARRFT
QD!
A A%QDT
A%K-QD1
A % UU-QD
Partition Level: 3
CcllTrecQM
(0.91
0.204(0.01)
0.199(0.01)
0.603(0.02)
0.992(0.00)
0.261(0.04)
CeIITreeQM-G
0.784
0.211(0.01)
0.193(0.00)
0.616(0.01)
0.994(0.00)
0.282(0.02)
Triplet
0.914(0.00)
0.079(0.00)
0.355(0.00)
0.292(0.01)
0.779(0.02)
-0.139(0.02)
Triplet-G
0.921(0.00)
0.345(0.01) 0.073(0.00)
0.311(0.01)
0.771(0.02)
-0.096(0.03)
Quadruplct
0.921(0.00)
0.073(0.00)
0.359(0.00)
0.284(0.01)
0.812(0.01)
-0. 10.
Quadruplet-G
0.928(0.00)
0.066(0.00)
0.353(0.00)
0.296(0.01)
0.810(0.00)
-0.158(0.01)
Partition Level: 2
CcllTreeQM
0.863)0.01)
0.132(0.01)
0.632(0.01) (.180)0.00)
0.994(0.00)
0.356(0.01)
CeIITreeQM-G
0.856(0.01)
0.138(0.01)
0.636(0.01) 0.182(0.00)
0.996(0.00)
0.361(0.01)
Triplet
0.937(0.00)
0.057(0.00)
0.350(0.01)
0.302(0.01)
0.831(0.00)
-0.103(0.01)
Triplet-G
0.944(0.01)
0.050(0.01)
0.299(0.02) 0.351(0.01)
0.848(0.00)
-0.121(0.03)
Quadruplet
0.935(0.00)
0.059(0.00)
0.346(0.00)
0.310(0.00)
0.931(0.01)
-0.165(0.00)
Quadruplet-G
0,944(0.00)
0.050(0.00)
0.342(0.00)
0,317(0.01)
0,934(0.00)
-.155(0.00)
Partition Level: 1
CellTRee&M
0.896(0.01)
0.098(0.01)
0.279(0.00)
0.444(0.00)
0.999(0.00)
0.310(0.01)
CellTreeQM-G
0.908(0.01)
0.086(0.01)
0.432(0.02) 0.285)
(.999(0.00)
0.295(0.03)
Triplet
0.973(0.000
0.020(0.00)
0.117(0.01) 0.443(0.01)
0.872(0.03)
-0.065(0.01)
Triplet-G
0.966(0.01)
0.027(0.01)
0.439(0.01)
0.124(0.01)
0.873(0.00)
-0.057(0.01)
Quadruplet
0.968(0.01)
0.025(0.01)
0.441(0.00)
0.121(0.01)
0.968(0.01)
-0.084(0.01)
Quadruplet-G
0.977(0.00)
0.016(0.00)
0.441(0.00)
0.120(0.00)
0.973(000)
-0.086(0.00)
Table 17, Weakly supervised high-level partitioning setting results on CRISPR dataset 1035_NT_TT under different partition levels. K-QD and U-QD are quartet distances the known and unknown quartets, respectively. The reported values means across three runs, with standard deviations in parentheses.
Method
RF4
A % &RFt
QDL
A % QDt
A A%K-QD1
A UU-QD
Partition Level:
CcllTreeQM
0.705(0.01)
0.287(0.01)
0.151(0.02)
0.740(0.03)
(.984(0.01)
0.236(0.11)
QM-
0.682(0.01)
0.310(0.01)
0.124(0.01)
0.787(0.02)
(.989(0.00)
(.369(0.06)
Triplet
0.780(0.01)
0.211(0.01)
0.281(0.01)
0.517(0.02)
0.730(0.03)
0.077(0.03)
Triplet-G
0.780(0.01)
0.211(0.01)
0.280(0.01)
0.520(0.01)
0.734(0.01)
0.075(0.02)
Quadruplet
0.852(0.01)
0. 0,13000.11)
0.318(0.01)
0.454(0.02)
0.748(0.01)
-0.155(0.03)
Quadruplet-G
0.867(0.01)
0. (..001)))
0.317(0.00)
0.456(0.00)
0.753(0.01)
-0.159(0.00)
Partition Level:
CellTre=QM
0.211(0.01) 0.780)0.01)
0.227(0.01)
0.611(0.022
0.993(0.00)
0.253(0.03)
CcI
0.792(0.01)
0.199(0.01)
0.220(0.00)
0.623(0.01)
(.991(0.00)
0.276(0.02)
Triplet
0.837(0.01)
0.153(0.01)
0.379(0.01)
0.349(0.01)
0.673()
0.046(0.02)
Triplet-G
0.852(0.00)
0. 138(000)
0.378(0.01)
0.352(0.02)
0.694(0.02)
0.030(0.02)
Quadruplet
0.898(0.01)
0.092(0.01)
0.397(0.01)
0.319(0.01)
0.820(0.02)
-0. -0.151(0.02)
Quadruplet-G
0.902(0.01)
0.088(0.01)
0.379(0.01)
0,350(0.01)
0.858(0.01)
-0. 0..22().
Partition Level:
CellTreeQM
0.845(0.01)
0.146(0.01)
0.501 0.291(0.011
1.000(0.00)
0.429(0.01)
CellTreeQM-G
0.962(0.01)
0.027(0.01)
0.542(0.03)
0.070(0.05)
0.998(0.00)
-0.06300.06
Triplet
0.947(0.01)
0.042(0.01)
0.521(0.01)
0.106(0.02)
0.862(0.07)
-0.003(0.01)
Triplet-G
0.958(0.01)
0.031(0.01)
0.534(0.01)
0.084(0.02)
0.816(0.02)
-0.020(0.02)
Quadruplet
0.977(0.00)
0.011(0.00)
0.604(0.03)
-.036(00.0)
0.142(0.22)
-0.061(0.03)
Quadruplet-G
0.970(0.01)
0.019(0.01)
0.613(0.01)
-0.52(0002)
0.299(0.06)
-0.103(0.02)
43

---

Reconstructing Cell Lineage Trees from Phenotypic Features with Metric Learning
ARF Across Models
AQDist Across Models
АK: QDist Across Models
AU-QDist Across Models
1.0
0.9
0.5-
0.4
Level
Level
Level
CellTreeQM
CelffreeQM-G
Triplet
Triplt--G
Quadruplet
Quedruplet-G
Figure Results for high-level partitioning setting on CRISPR dataset 3435_NT_T6. x-axis the of partition.
44


Reviews:
[{"review_id": "JzLTB4cYy0", "reviewer": "Reviewer_RR5y", "summary": "This paper poses the reconstruction of lineage trees from phenotypic data as a metric learning problem, and devises a contrastive loss function to learn a metric given partial information about the topology of the lineage tree. The authors test this algorithm on ground truth data from C. elegans, as well as simulated data of branching random processes, and find that it performs quite well relative to reasonable baselines.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Concern 1: Overstated claim about unsupervised learning\n> Although acknowledged as preliminary, unsupervised performance is mentioned in the abstract.\n### Response\n\nWe appreciate the comment concerning the limited investigation of the unsupervised setting. We demonstrate the unsupervised setting with the brownian motion dataset and we are capable of filtering out independent noise during training, demonstrated by the dash lines in Figure 5. We agree that the investigation under unsupervised setting is still preliminary so we have reworded the abstract and other parts of the manuscript describing our unsupervised results. \n\n**In Abstract:** “we systematically explore, supervised, weakly supervised, and unsupervised…” → “we systematically explore weakly supervised training settings at different levels of information..”\n\n**Section 7.4:**\n\nFrom:\n\n“Although the problem is more difficult—and in practice, purely unsupervised lineage inference\nfrom phenotypes alone can be error-prone—we find that CellTreeQM can still learn a representation that partially respects tree-metric properties. See details in §F.5.\n\nTo:\n\n“Here, we used a data-driven estimate of quartet order in the latent space. CellTreeQM can still learn a representation that partially respects tree-metric properties in the limited setting of the simulation data but performance on real data was not significant, suggesting better strategies are needed. See details in §F.5.”\n\n**Discussion section:**\n\nFrom: \n\n“Empirical results in supervised, weakly supervised, and unsupervised settings show that CellTreeQM considerably improves…”\n\nTo:\n\nEmpirical results in supervised and weakly supervised settings show that CellTreeQM considerably improves…”\n\n## Concern 2: Comparing to clustering methods\n> Not thoroughly evaluated or compared to clustering methods widely used in single-cell analysis.\n\n### Response\nAs noted by the reviewer, we did not compare to various unsupervised clustering methods widely used in single cell literature. One of the key reasons is that the clustering methods, as currently used, are applied to whole transcriptomes. Carefully examined biological processes such as in C. elegans, show that phenotypic types are not the same as cell-lineage clades (also, we appreciate all the reviewers mentioning this fundamental concept in their comments). \n\nIn fact, this disjunction is the central problem in cell lineage estimation. While we have not systematically studied clustering methods, we have now added examples of applying cell trajectory methods–we note that these methods work in the original feature space and attempts to create a piecewise one-dimensional (i.e., tree-graph) parameterization of the full phenotypic state, rather than trying to extract lineage-specific information. Please see our response to ekW4 Concern 1 and FYFt Concern 2.\n\n## Concern 3: Missing literature\n> I might suggest papers to further augment the case that phenotypic information alone is insufficient to reconstruct the lineage, as in the purely unsupervised case. https://www.nature.com/articles/s41586-021-04237-0 presents one example.\n### Response\nWe thank the reviewer for this paper and we added this reference and revised the Key Challenges section to better reflect this comment.\n\n## Concern 4: Scalability\n> I'm curious about the application of this method to settings in which we know the cell type lineage tree, but in a particular dataset may have millions of cells. This is a example of partial information about the cellular tree. With this method still be applicable.\n### Response\nThank you for this interesting question. We believe there are several approaches and barriers. First, as discussed above, typical cell types are not monophyletic, therefore cell type lineage tree is likely to be a mixture of cell tree lineages. As shown in [this figure](https://anonymous.4open.science/api/repo/celltreeqm-rebuttal-7D65/file/cell_type-vs-cell_lineage.png?v=50c079c2).\n\nNevertheless, we could use its hierarchy as prior knowledge to designate known quartets. Ideally, the latent space with additive tree metric should be universal and therefore learnable with subsets of the millions of cells–perhaps using the strategy of random mini-batches. The key barrier will be the application of phylogeny algorithms. Even the heuristic algorithms are O(n^2)~O(n^3), which might be practically impossible for millions. Currently, large-scale phylogenies such as viral isolate phylogenies are built using a mixture of inferring “backbone” trees and using insertional type of approaches. We hope to continue our studies to include extreme scale up problems.", "claims_and_evidence": "I think the most important claim of this paper is that the presented problem is indeed an important one, and on this I wholeheartedly agree. The cited literature is thorough and wonderfully bridges the biological motivation with the computational problem at hand. Phenotypic information is widely available, yet it is important to have methods such as these that bridge those with more targeted approaches and prior knowledge about cell lineage. I present this in the claims section rather than the relation to broader literature because it is a key source of originality in this paper to identify and tackle a problem that has not been addressed by several machine, learning papers already.\n\nthere are many more specific claims made in the paper, and for the most part, these are well supported by the experiments presented. the supervised and semi supervised settings are particularly convincing. \n\nI think the one overstated claim in this paper is that this method is useful in unsupervised settings. well the authors do remark that this is preliminary, it is still mentioned in the abstract as contribution of this paper. However, the unsupervised setting is not thoroughly evaluated, and little attempt is made to compare with a large number of hierarchical clustering approaches that are widely used in single cell analysis. Nonetheless, I do not think the unsupervised setting is the main contribution of this paper.", "methods_and_evaluation_criteria": "the combination of the branching diffusion process simulation with ground truth lineage information in flatworms is nice to see. I furthermore appreciate the choice of quantitative evaluations on these two data sets. these are well suited to the problem at hand.", "theoretical_claims": "no novel theoretical claims are made.", "experimental_designs_or_analyses": "the experimental designs are sound.", "relation_to_broader_scientific_literature": "The construction of lineage trees is an important problem in developmental biology, yet it is rare to have experimental validated trees down to the cellular level. Thus, there is a real need for papers that can augment limited experimental data. I particularly appreciate the starting point of this manuscript, which recognizes that phenotypic information does not correlate well in certain cases with lineage. thus, this paper targets an important problem in biology with novel methods and ideas with in machine learning, pioneering an important path forward for both fields.", "essential_references_not_discussed": "the literature is very thorough already. I might suggest papers to further augment the case that phenotypic information alone is insufficient to reconstruct the lineage, as in the purely unsupervised case. https://www.nature.com/articles/s41586-021-04237-0 presents one example.", "other_strengths_and_weaknesses": "the principal strength of this work is in its ideation of a novel research direction for a real problem in developmental biology, presented by the available methods and the perhaps surprising to similarity between phenotype and lineage in single cell data. The author is apply interesting machine, learning ideas in novel ways to address this problem.\r\n\nI cannot identify many weaknesses in this paper. The ability of this method to work in purely unsupervised settings is somewhat untested, and in the setting for which other methods exist these are not compared.", "other_comments_or_suggestions": "line 340: “known quartetes” -> “known quartets”\nline 316: \"we training an model\" -> \"we train a model\"", "questions_for_authors": "I'm curious about the application of this method to settings in which we know the cell type lineage tree, but in a particular dataset may have millions of cells. This is a example of partial information about the cellular tree. With this method still be applicable.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pszoTyAdVN", "reviewer": "Reviewer_vktx", "summary": "The authors propose an algorithm CellTreeQM to reconstruct lineage relationships from phenotype data (unlike genotype data, which has been the main focus in the area of lineage reconstruction). The main new idea in the paper is the use of loss function based on four point condition which ensures that embedding eventually resembles an unrooted tree. At the same time this four point loss may create a distortion from allowing the model to fit to the original data; so the authors have an additional distortion loss term as well. This careful design of loss function is in my opinion the main new idea in the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Concern 1: No theoretical results\n> they do not appear to claim any significant new theoretical results (no new theorems/proofs).\n\n### Response\nWhile we do not present new theorems or proofs, our contribution lies in empirically demonstrating that the four-point condition serves as a strong prior for learning a generalizable embedding function—one that can correctly predict unseen quartet topologies. We hope we are demonstrating two new ideas: (1) with respect to learning tree-graphs, jointly learning the whole tree might be limited both algorithmically and by available supervised knowledge, but decomposition to quartet tree sub-trees allows utilization of partial information; (2) rather than using standard contrastive learning paradigm, explicitly utilizing a tree-graph metric theorem significantly improves the learning results.\n\nFollowing this comment, we have added additional test data (vktx Concern 3) and also additional phylogeny methods  (FYFt Concern 3) as well as other single cell trajectory methods (FYFt Concern 2) for comparison. We note that actual empirical data with validated annotated lineages are extremely rare, but we understand that greater degree of testing would be desirable. \n\n## Concern 2: Missing literature\n> While the references on tree and random forest embedding are discussed in the literature cited; it would be appropriate to discuss the connection between them directly; as I can imagine a randomized tree embedding (Bartal et al be cited) to be used instead of just a tree embedding. The output would be a probability distribution over trees as opposed to a single tree.\n\n### Response\nThank you for this suggestion for the background literature that we were not aware of. Indeed, an observed empirical distance matrix could be considered a graph metric and bounded  by expectation over a distribution over a tree graph. This distribution might be mapped to a distribution of possible cell-lineage tree graphs in a similar framework as Bayesian phylogenetic algorithms. In our case, our assumption is that the original feature space and the resulting empirical metric does not reflect the lineage tree-graph, even as, say, a dominating metric. However, it might be possible to have a construction that computes a graph metric from the learned latent space and then associate it to a distribution over a tree metric ensemble. One might have to develop additional criteria for the tree metric such as “concentration” to incorporate into a learning scheme.\n\nWhile the full exposition as above is out of the scope of our current work, we have added the following references to our background literature:\n\n- Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic\napplications. In Proceedings of the 37th IEEE Symposium on Foundations of\nComputer Science (FOCS), pages 184–193, 1996.\n- Yair Bartal. On approximating arbitrary metrics by tree metrics. In Proceedings of\nthe 30th ACM Symposium on Theory of Computing (STOC), pages 161–168, 1998.\n\n## Concern 3: Limited dataset\n> However, the authors have used just one dataset C.elegans for their experiments and do not prove any new theory results either. This makes me wonder if the contribution crosses the threshold for acceptance to ICML. Hence my rating.\n\n### Response\nWe thank the reviewer for this important point. In response, we have significantly expanded our experiments to include two additional reference datasets (including a CRISPR-based lineage tracing dataset from Yang et al., 2022), four more phylogenetic methods, and two trajectory inference methods.\n\nFor the CRISPR dataset, we used cell lineages 3435_NT_T1 (151 cells) and 3435_NT_T6 (91 cells), both derived from mESC clone 1D5 with non-targeting sgRNA. Ground truth trees were reconstructed using Cassiopeia. Due to ambiguity in the tree structure, we sampled binary trees from the full lineage.\n\nWe conducted weakly supervised learning with high-level partition prior in level 1, 2, and 3 with three repetitions. The detailed results are shown in [3435_NT_T1 BarPlot](https://anonymous.4open.science/r/celltreeqm-rebuttal-7D65/3435_NT_T1_barplot.png), [3435_NT_T1 Table](https://anonymous.4open.science/r/celltreeqm-rebuttal-7D65/3435_NT_T1_table.png), [3435_NT_T6 Barplot](https://anonymous.4open.science/r/celltreeqm-rebuttal-7D65/3435_NT_T6_barplot.png), [3435_NT_T6 Table](https://anonymous.4open.science/r/celltreeqm-rebuttal-7D65/3435_NT_T6_table.png). \n\nAs in the C. elegans datasets, we show that we can achieve significant learning and CellTreeQM has better results, especially generalizing to unknown quartets than other baseline approaches. We note that due to the limited time for this response, we have not been able to consider tuning the model for these datasets and we expect better performance might be achieved with additional work.\n\nPlease see FYFt Concern 2 for single cell trajectory methods and FYFt Concern 3 for phylogeny methods.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "While the authors discuss relevant theory background and how the tree reconstruction problem relates to existing theory, they do not appear to claim any significant new theoretical results (no new theorems/proofs).", "experimental_designs_or_analyses": "The experiments on C.elegans dataset are adequately explained in the supplement.", "relation_to_broader_scientific_literature": "Adequate (but also see comment below re metric embeddings)", "essential_references_not_discussed": "While the references on tree and random forest embedding are discussed in the literature cited; it would be appropriate to discuss the connection between them directly; as I can imagine a randomized tree embedding (Bartal et al be cited) to be used instead of just a tree embedding. The output would be a probability distribution over trees as opposed to a single tree.", "other_strengths_and_weaknesses": "The paper uses reasonably deep theory background to solve an interesting problem -- lineage reconstruction. However, the authors have used just one dataset C.elegans for their experiments and do not prove any new theory results either. This makes me wonder if the contribution crosses the threshold for acceptance to ICML. Hence my rating.", "other_comments_or_suggestions": "See question about using random forests instead of trees above", "questions_for_authors": "see above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vcjQKwdNDz", "reviewer": "Reviewer_ekW4", "summary": "This paper introduces **CellTreeQM**, a novel deep learning-based method for reconstructing cell lineage trees using single-cell RNA sequencing data. \nThe method leverages a **Transformer architecture** combined with **metric learning** to optimize the geometry of an embedding space, enabling accurate reconstruction of lineage trees even with limited supervision or noisy data. \nUnlike traditional approaches relying on CRISPR barcoding or heuristic distance-based methods, CellTreeQM explicitly formulates lineage reconstruction as a metric learning problem and incorporates **triplet and quadruplet loss functions** to enforce tree-like relationships in the embedding space. \nThe authors also establish a benchmark for lineage reconstruction and demonstrate that CellTreeQM outperforms existing methods in terms of accuracy, robustness, and scalability.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Concern 1: Lack of comparisons to SOTA methods\n> There are many state-of-the-art (SOTA) cell lineage methods that have not been compared.\n### Response\nThank you for raising the concern regarding comparisons to state-of-the-art (SOTA) cell lineage methods. Below, we clarify why existing methods are not directly comparable to our approach. \n\n**Phenotype-Based vs. Genotype-Based Cell Lineage Methods**\n\nIn the second paragraph of the Introduction and Section 3, we review computational methods for cell lineage reconstruction, which primarily rely on genotype information. In contrast, we focus on phenotype-based lineage reconstruction—a fundamentally different and much more challenging problem setting. To our knowledge, and as noted by Reviewers RR5y and FYFt, CellTreeQM is the first work to formulate and solve this specific task. \n\nWe propose that both observed empirical data and biological process considerations suggest that the standard full feature space (i.e., the transcriptome) does not directly contain cell lineage information. Current time-trajectory algorithms are not focused on recovering the historical cell lineage relationships. Rather, the algorithms try to find a piecewise one-dimensional parameterization of cells in the transcriptome feature space as a model of “phenotype dynamics” solely based on trivial metric (such as l1 and l2 distance); i.e., how the phenotypes of the cells might dynamically evolve through cell system processes without a reference to underlying cell lineage processes. In fact, phenotype dynamics might occur without any cell division. \n\n**Baseline Selection**\n\nWe chose triplet and quadruplet contrastive losses as baselines because these are widely used in related contrastive learning tasks. As we show, CellTreeQM’s tailored assumption about the structure of cell lineage data leads to superior performance compared to these generic approaches.\n\n**Clarifying the Role of Trajectory Inference**\n\nBy “SOTA,” the reviewer may also be referring to trajectory inference methods. (Other methods that operate over sequence data are not applicable to the gene expression data studied in our paper.) While trajectory inference and lineage reconstruction are closely related, they address distinct goals. We provide a detailed comparison in Appendix C.1 (moved from the main text due to space constraints). Indeed, Reviewers RR5y and FYFt also noted the conceptual differences between these two tasks.\n- Methodological Differences\n\nTrajectory inference is typically an **unsupervised** pipeline comprising (1) data preprocessing, (2) dimensionality reduction, (3) cell clustering, and (4) learning a graph representation of cluster relationships. Such methods usually yield average progression trends rather than a cell-by-cell hierarchical lineage.\n- Mismatch in Assumptions\n\nTrajectory inference assumes the cells dynamically change within the full feature space and the goal is to trace this dynamics. The dynamics can be decoupled from cell lineage history. However, if the dataset has the cells at every stage of cell development, the algorithms could approximate the cell lineage histories, assuming the local changes in phenotypes are due to cell lineage development. However, as noted in various examples in the paper, even under this setting, the full feature space cell distributions typically do not reflect cell lineage history, requiring additional learning as we propose in our paper. \n\n## Concern 2: No ablation of the Transformer encoder and compare to VAE\n\n### Response\nWe thank the reviewer for considering the model architecture of CellTreeQM. We would like to clarify that the motivation and empirical support for using a Transformer encoder are provided in Section 5.4. Specifically, we compared fully connected (FC) networks and Transformer encoders on both the C. elegans Small and Large datasets, and found that Transformers consistently outperformed FCs, as shown in Table 5.\n\nWhile we acknowledge the relevance of concurrent works such as TreeAVE, which focus on generative modeling with hierarchical latent variables, our goal differs. CellTreeQM does not aim to model the full generative process. Rather, we assume that lineage-related signals lie in a subspace of the observed features. Instead of relying on reconstruction losses typical in VAE-based models, we introduce the Deviation Loss, \\Omega, to prevent the learned embedding from drifting too far from the original data.\n\n## Concern 3: No results of feature gating for weakly supervised scenario\n\n### Response\nWe apologize for the confusion. Due to space constraints, we omitted the results of feature gating in the weakly supervised setting from the main text. However, these results are included in Tables 10–14 of the appendix. While feature gating provides marginal gains on real datasets, they demonstrate that the gating mechanism can still contribute positively, particularly in settings where the signal-to-noise ratio is low.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. The Four-Point Condition ensures that distance matrix can be constructed into a tree, but whether it is applicable to the current task is unclear, as there has been no previous exploration in this regard.", "experimental_designs_or_analyses": "1. This paper's experimental section only discusses comparisons with Quadruplet and Triplet, but in reality, there are many state-of-the-art (SOTA) cell lineage methods that have not been compared.\n2. Many trajectory inference methods for constructing cell lineage from single-cell expression data ultimately yield tree-shaped results. Could we perform a simple comparison with these methods, e.g monocle3, Slingshot?\n3. The Transformer encoder module has not been ablated, and while Transformers are well-known for their effectiveness on large datasets, methods like VAE may be more effective on the current small dataset.", "relation_to_broader_scientific_literature": "1. **Advancements in Cell Lineage Reconstruction**: The paper builds upon existing methods, which uses CRISPR barcoding for lineage tracing, by introducing a deep learning-based approach that leverages **metric learning** and **Transformer architectures** to improve accuracy and robustness in lineage reconstruction.\n\n2. **Integration with Metric Learning**: It extends the application of **metric learning** techniques, commonly used in classification and clustering tasks, to the domain of cell lineage reconstruction, enhancing the ability to capture tree-like relationships in high-dimensional data.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "1. Why wasn't the effect of feature gates compared in the weakly supervised scenario?", "other_comments_or_suggestions": "No.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IpN9AuXxfc", "reviewer": "Reviewer_FYFt", "summary": "This work addresses an important problem: reconstructing cell lineage trees, which provide insights of how diverse cell types arise from a single progenitor. More to the point, the authors set an additional challenge, which is to use transcriptomic data to construct cell linage trees, which sets them apart from the classical lineage inference methods that rely on genetic barcoding, CRISPR-based lineage tracing, or phylogenetic distance methods. In other words, they attempt to answer the question  whether high-content molecular phenotypes give enough information for tree reconstruction and in doing  so they define a novel method that can be used to build cell lineage trees using such data.\n\nThe crux of the proposed method is to rely on the traditional framework of distance-based lineage reconstruction, which is a known NP-hard problem for which many approximation algorithms exist, such as the neighbor-joining algorithm, which they also use in their work. The novelty, however, consists in shifting the problem to a metric-learning one, whereby the idea is to learn an embedding function that maps data points to a space where distances approximate an additive metric. By doing so, the intuition is that it will facilitate the task of tree construction, if quartet constraints -- which are crucial for accurate lineage inference -- are well learned or provided. In an ideal scenario where all tree quartets are known, the approach should work near-perfectly. However, in more realistic settings where many quartets must be inferred, errors can propagate, and the final tree may only be an approximation of the true lineage structure.\n\nIn summary, the metric learning problem relies on the definition of two loss terms that strive at verifying the four-point condition (or quartet constraint). In addition, the authors propose a regularization term to prevent the learned embedding to drift too much away from the original data, and a gating mechanism (a sort of feature selection mechanism) that emphasize only lineage-relevant features of the high-dimensional transcriptomic data they use.\n\nExperiments are mainly devoted to verify the benefits of the proposed embedding method, rather than comparing the overall approach to state of the art. Then, they compare to traditional metric learning methods inspired by contrastive learning losses. Since CellTreeQM also uses a metric-learning approach, comparing against standard loss functions provides a fair assessment of whether their tree-based additivity loss truly improves tree reconstruction.\n\n## POST REBUTTAL\nThank you for the rebuttal and the discussions. I maintain my positive score for this paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Concern 1: Joint optimization claim\n### Response\nWe thank the reviewer for recognizing the importance of the cell lineage reconstruction problem and for raising this valuable point about our optimization formulation. We agree that Section 4.1 could be clearer in distinguishing between joint and staged optimization strategies, and we appreciate the opportunity to clarify our intent.\n\nAs the reviewer correctly notes, CellTreeQM adopts a two-stage framework: \n\n1. Learn an embedding space using quartet-based constraints that promotes tree-like geometry;\n2. Apply a standard phylogenetic algorithm (e.g., Neighbor-Joining) to reconstruct the tree from the learned pairwise distances.\n\nAlthough staged in practice, we emphasize that **most of the tree inference is effectively encoded in the embedding step**. Once the embedding space approximates tree-additive distances, standard reconstruction methods reliably recover the topology (as shown in Appendix A.2, line 742). Figure 4 further illustrates that both Train RF and Test RF steadily decrease during training, indicating that the learned representation is progressively converging toward a tree-consistent structure. This is conceptually aligned with heuristic quartet-based methods (e.g. Quartet Puzzling), which also tackle the NP-hard tree reconstruction problem by optimizing over informative subsets of constraints.\n\nTo better reflect our approach, we updated the manuscript to clearify that we revise the following object function \n$$\\min_{f, T} \\|D(f(x)) - D_T\\|_2^2 + \\lambda \\Omega(f),$$\n\ninto quartet-based formulation\n\n$$\\min_{f}\\sum_{q \\in \\mathcal{Q}}\\mathcal L( D\\bigl(f(x_q)\\bigr), D_{T0}\\bigl(x_q\\bigr))+\\lambda \\Omega(f),$$\nwhere $Q$ is the set of known quartets and $D_{T0}$ is the pairwise distance for the known quartets.\n\nWhen $T$ is known, this objective reduces to a supervised metric learning problem. However, as we highlight in the manuscript, full lineage trees are often unavailable in biological datasets. Instead, researchers may have access to partial lineage information—such as clade-level groupings—while finer substructures remain uncertain. In these settings, we found quartet constraints offer a flexible and localized way to encode supervision and capture tree-additive properties. \n\n## Concern 2: comparison between trajectory inference and cell lineage reconstruction\n### Response \nAs discussed in our response to Reviewer ekW4’s Concern 1, trajectory inference and lineage reconstruction address fundamentally different problems. To further illustrate this distinction, we conducted additional experiments using the C. elegans Small dataset.\n\nUsing Monocle3, we constructed a principal graph from unsupervised clusters and colored cells by lineage annotation ([figure](https://anonymous.4open.science/api/repo/celltreeqm-rebuttal-7D65/file/monocle.png?v=b00073b0)). The resulting graph shows that many terminal lineages are incorrectly represented as internal nodes, highlighting a mismatch with known lineage structure.\n\nBecause Monocle3 cannot incorporate known labels into graph construction, we also computed lineage centroids and built a minimum spanning tree (MST) to model their relationships ([HotSpot](https://anonymous.4open.science/api/repo/celltreeqm-rebuttal-7D65/file/mst.png?v=431c273e), [ASCII](https://anonymous.4open.science/api/repo/celltreeqm-rebuttal-7D65/file/mst_ascii.png?v=f4902aed)). Again, several terminal lineages are placed as internal nodes. HotSpot only shows the densely connect dots and ASCII shows the full MST.\n\nThese results confirm that standard trajectory inference methods do not accurately reflect true lineage trees and are also not directly comparable to lineage reconstruction.\n\n## Concern 3: Limited tree reconstruction methods\n### Response\nWe appreciate the suggestion to evaluate additional reconstruction algorithms beyond Neighbor-Joining (NJ). We assessed four alternatives—UPGMA, FastME, Ward, and Single linkage on the C. elegans Small dataset ([figure](https://anonymous.4open.science/api/repo/celltreeqm-rebuttal-7D65/file/reconstruct_method.png?v=d604180e)).\n\nAcross all methods, CellTreeQM consistently achieves lower RF distances on both train and test sets, consistently demonstrating strong learning and generalization ability. The radar plot shows relative RF improvement across all five reconstruction algorithms comparing with Triplet and Quadruplet.\n\nInterestingly, Ward’s method slightly outperforms NJ, despite NJ’s theoretical alignment with additive trees. This suggests our embeddings may better support variance-based clustering in certain settings. We plan to investigate further in future work.\n\n## Concern 4: Lack of gold-standard lineage tree comparison\n### Response\nWe thank the reviewer for this important point. Please see our response of vktx Concern3.", "claims_and_evidence": "I think that most claims are partially supported by evidence in this work.\n\n* Claim 1: inferring or reconstructing the cell lineage tree from features measured on the individual cells is an important challenge that they address in this work. This is the essence of the proposed method, that uses transcriptomic data.\n\n* Claim 2: the open question the authors address is whether high-content molecular phenotypes give enough information for tree reconstruction. The experiments provide a positive answer to this question.\n\n* Claim 3: Cell-TreeQM efficiently reconstructs lineage structures under weak supervision and limited data, providing a scalable framework for uncovering cell lineage relationships. This is supported by the experiments in section 7.", "methods_and_evaluation_criteria": "Let me separate methods from evaluation.\n\nOn the methodological side, the proposed idea to project high-dimensional data into a latent representation that is amenable to preserve an appropriate distance relationship between data points is appropriate, relevant and novel, to the best of my knowledge. The proposed methodology is clearly exposed, except for a detail.\nThe overall narrative of section 4.1 is to perform a joint optimization of tree construction and metric learning, as defined in the last optimization expression at the end of the section. However, the proposed method is *not* a joint optimization: first, the authors propose a method to learn an embedding, and subsequently, this embedding is used within the distance-based lineage reconstruction formulation and fed to the well-known neighbor-joining algorithm.\nThe authors take steps to ensure that the learned distances conform to a tree metric, which helps mitigate the issue of separating the embedding and tree reconstruction steps. However, it still does not fully jointly optimize the tree and the embedding function together. Instead, it shapes the embedding space to be more tree-like before applying a separate tree reconstruction algorithm. This is a reasonable approximation, but not a true joint optimization approach, which would require incorporating the actual tree inference step directly into the learning process.\n\nOn the experimental side, the authors do a good job in evaluating the proposed embedding against that learned through traditional contrastive losses. Although the selected metric learning baselines make sense for their approach, a more complete experimental evaluation could have included comparisons to state-of-the-art trajectory inference methods , which would help show how well CellTreeQM recovers lineage structure compared to methods that infer differentiation trajectories. Since the paper already discusses trajectory inference in Appendix C, a quantitative comparison would strengthen their claims. Moreover, instead of just using the neighbor-joining algorithm, they could have tested alternative distance-based tree reconstruction methods, which could have revealed whether their learned embeddings work well across different methods.\nFinally, if a dataset existed which had both phenotypic features and genetic barcodes, they could compare their phenotypic-based tree to a gold-standard lineage tree inferred from CRISPR mutations, which could have shown whether their learned embeddings truly capture lineage relationships or if they primarily reflect phenotypic similarity.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes, I checked experimental design and analyses and they are appropriate in my opinion. As mentioned above, the authors mainly focus on metric learning, and compare their proposed learned embeddings to that learned with alternative contrastive losses, showing that the key idea of enforcing the quartet constraints is indeed important. They do so in a variety of settings, for both synthetic and real data.", "relation_to_broader_scientific_literature": "This is a multidisciplinary project, lying at the intersection of machine learning and biology. I think the authors did a very good job in the main paper, and the interested reader can find much more in the appendix, especially Appendix A (which is an short introduction to the context of their study) and in Appendix C.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "This is a good work, the only comments I outlined above are:\n\n* Method: pay attention to the claim of a joint optimization problem, versus breaking the problem in two stages.\n\n* Experiments: while it is valid to compare the proposed method to metric learning baselines, I think this work would be much more valuable to the biology community if the experimental section was extended to cover 1) alternative tree construction algorithms (not only neighbor-joining), and 2) more end-to-end comparisons, although this is hindered by the probable absence of relevant datasets that could be used both by comparing phenotypic-based tree to a gold-standard lineage tree inferred from CRISPR mutations.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* Can you please provide clarifications about the remark of a joint optimization problem vs. breaking the problem into first learning an appropriate embedding, and then applying a well-known tree construction algorithm? Did I misinterpret your approach? If not, can you maybe add some comments about the sub-optimality of the resulting lineage reconstruction when compared to a truly joint optimization approach?\n\n* Would it be possible to add experiments that use an alternative tree construction algorithm than the neighbor-joining one? You may just keep everything you've learned through the embedding, and apply another technique to further confirm the versatility of the learned embeddings.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper proposes an approach reconstruct cell lineage relationships from phenotypic data. The main contribution is a new loss function that formulates lineage reconstruction as tree-metric learning problem and enables supervised and weakly supervised learning. The reviewers are generally supportive of the paper but criticized the limited empirical evaluation as well as the potentially overlooked link to trajectory inference methods. During the rebuttal period, the authors could show that the method can be applied successfully on additional datasets and clarified how their problem setting differs from that tackled by trajectory inference methods. As a result, all reviewers that engaged in the discussion are now in support of the paper. Hence, I recommend accepting it.
Decision: Accept (poster)