POTTR: Identifying Recurrent Trajectories in Evolutionary and Developmental Processes using Posets

This paper introduces POTTR, a novel combinatorial algorithm that utilizes incomplete partially ordered sets (posets) and a conflict graph approach to solve the NP-hard maximum k-common induced incomplete subposet problem, thereby identifying statistically significant recurrent genetic trajectories and conserved differentiation routes across diverse biological datasets while effectively resolving uncertainties inherent in tumor phylogenies and lineage tracing.

The Gist

Imagine you are trying to figure out the history of a family, but you don't have a single, perfect family tree. Instead, you have dozens of different, slightly messy sketches drawn by different relatives. Some sketches agree on who came first, but others are confused about the order of cousins, or they group two siblings together as if they were born at the exact same second.

This is exactly the problem scientists face when studying cancer or embryo development. They want to know the "story" of how a tumor grew or how a cell turned into a specific organ. But because evolution is messy and our technology isn't perfect, the data often comes with gaps, contradictions, and "blurry" spots where the order of events is unclear.

Enter POTTR (Posets for Temporal Trajectory Resolution). Think of POTTR as a super-smart detective that can look at all these messy sketches and find the common story that everyone agrees on, even if the details are fuzzy.

Here is how it works, broken down into simple concepts:

1. The Problem: The "Blurry Photo" Effect

In biology, we often look at a group of cells (like a tumor) and try to guess the order in which mutations happened.

• The Ideal: A clear line: Mutation A happened, then Mutation B, then Mutation C.
• The Reality: Sometimes, our tools can't tell if A happened before B, or if they happened at the same time. It's like taking a photo with a shaky hand; you see two people, but you can't tell who is standing in front of whom. In the paper, these "shaky" groups are called clusters.

Most old methods tried to force a decision immediately: "Okay, let's just guess A came before B." But if you guess wrong, you might miss the real pattern.

2. The Solution: The "Conflict Map"

POTTR takes a different approach. Instead of guessing the order right away, it builds a Conflict Map (or a "Conflict Graph").

• Imagine a party: You have guests from different cities (different patients). You want to find a group of guests who all agree on the same seating arrangement.
• The Conflict: If Guest from City 1 says "Alice sits before Bob," but Guest from City 2 says "Bob sits before Alice," they have a conflict.
• The Map: POTTR draws a line between any two people who disagree.
• The Goal: The algorithm looks for the largest possible group of people where no one is connected by a conflict line. This is called an "Independent Set."

By finding this group, POTTR identifies the events that everyone agrees on, without forcing a decision on the blurry parts yet.

3. The Magic Trick: Resolving the Blur

Once POTTR finds this agreed-upon group, it looks at the "blurry" spots (the clusters) again.

• If Patient A has a blurry group (A & B together) and Patient B has a clear order (A before B), POTTR uses Patient B's clarity to "fix" Patient A's blur.
• It effectively says, "Since everyone else agrees A comes before B, let's assume that's true for the blurry group too."

This allows POTTR to discover Recurrent Trajectories—the specific paths of evolution that keep happening over and over again across different patients, even when the data is messy.

4. Why This Matters: Real-World Wins

The authors tested POTTR on two big datasets:

1. Lung Cancer: They found specific sequences of genetic mutations that lead to drug resistance. For example, they discovered that a specific mutation (NFE2L2) often happens after a cluster of other mutations. This is crucial because it tells doctors that if they see that cluster, they should expect that specific mutation next, which might mean the cancer will be resistant to certain drugs.
2. Embryo Development: They looked at how stem cells turn into body parts (like the spine or blood vessels). They found that in normal development, there are two different ways cells can become "somites" (blocks of tissue that become muscle/bone). However, when they added a chemical to the mix, the cells stopped using the second path and stuck to the first one. This helps us understand how chemicals can change the blueprint of life.

The Bottom Line

Think of POTTR as a master puzzle solver.

• Old methods tried to force the puzzle pieces together, often breaking the picture because they didn't account for the pieces that didn't quite fit.
• POTTR waits, looks at all the pieces, finds the ones that definitely fit together, and then uses the clear pictures from some patients to help fill in the missing gaps for others.

It turns a chaotic mess of biological data into a clear, readable story of how cancer evolves or how life develops, helping scientists find better treatments and understand the fundamental rules of biology.

Technical Summary

1. Problem Definition

The paper addresses the challenge of identifying recurrent trajectories (shared orders of events) across multiple biological samples, such as tumor phylogenies in cancer or cell lineage trees in development.

• Context: Biological processes like cancer evolution and organismal development involve sequences of heritable events (e.g., mutations, differentiation). While these processes are stochastic and vary between individuals, specific orders of events often recur and correlate with clinical outcomes.
• Challenges:
  • Heterogeneity: High intra- and inter-tumor heterogeneity means not all patients share the exact same set of mutations.
  • Uncertainty: Inferred phylogenies often contain mutation clusters (groups of mutations with indistinguishable temporal order due to sequencing depth or sampling limitations).
  • Multiple Hypotheses: Phylogenetic inference methods often output multiple plausible trees for a single patient.
  • Limitations of Existing Methods: Current tools often rely on tree intersections (which lose information), assume linear orders, or fail to resolve mutation clusters effectively. Many methods are restricted to tree structures rather than general partial orders.

Formal Goal: Find the largest subset of events that share the same (incomplete) partial order in at least $k$ input samples, while explicitly handling indistinguishable event clusters and selecting the best tree topology from multiple possibilities per sample.

2. Methodology: POTTR Framework

The authors propose POTTR (POsets for Temporal Trajectory Resolution), a combinatorial algorithm based on Partially Ordered Sets (Posets).

A. Mathematical Formulation: Incomplete Posets

• Incomplete Poset ($P$): The authors generalize standard posets to handle uncertainty. An incomplete poset is defined as a tuple $(S, \sim, \to)$, where:
  • $S$ is the set of elements (events/mutations).
  • $\to$ is a strict partial order representing known temporal precedence.
  • $\sim$ is a "hidden order" (equivalence relation) representing indistinguishable elements (clusters).
• Resolution: A resolution of an incomplete poset splits a hidden set (cluster) into ordered subsets, effectively resolving the ambiguity.
• Problem Statement (MkCIIS): The Maximum $k$-Common Induced Incomplete Subposet problem. Given a family of $n$ incomplete posets, find the largest poset $P$ that is an induced subposet of at least $k$ input posets (or their resolutions).
• Complexity: The authors prove that the decision variant of the MkCIIS problem is NP-complete.

B. Algorithmic Approach: Conflict Graph & ILP

To solve the NP-hard problem, POTTR transforms it into a combinatorial optimization problem:

1. Conflict Graph Construction:
   • A multigraph $C(P)$ is constructed where vertices represent elements present in at least two input posets.
   • Edges: An edge exists between two elements if their relationship (order or incomparability) conflicts in any pair of input posets.
   • Labels: Edges are labeled with the pair of input posets causing the conflict.
2. Bijection to Independent Sets:
   • There is a one-to-one correspondence between a Common Induced Incomplete Subposet (CIIS) and an Independent Set in the conflict graph.
   • Selecting a set of nodes with no active conflicts corresponds to finding a valid recurrent trajectory.
3. Integer Linear Programming (ILP):
   • POTTR uses an ILP to simultaneously:
     • Select at least $k$ input posets.
     • Select a maximum independent set of nodes (events) from the conflict graph such that no edges connecting selected nodes are "active" (i.e., the selected posets do not conflict on the selected events).
   • Key Innovation: The model allows the algorithm to "resolve" hidden orders (clusters) dynamically. If a cluster is ambiguous in one tree but ordered in another selected tree, the algorithm adopts the ordered version to maximize the trajectory size.

3. Key Contributions

1. Novel Formalism: Introduction of Incomplete Posets to formally model mutation clusters and hidden orders, generalizing previous tree-based approaches to Directed Acyclic Graphs (DAGs).
2. NP-Hardness Proof: Formal proof that finding the maximum recurrent trajectory under these conditions is NP-hard.
3. Combinatorial Algorithm (POTTR): Development of a conflict-graph-based ILP solver that:
   • Handles multiple trees per patient (selecting the best topology).
   • Resolves mutation clusters by leveraging ordering information across different samples.
   • Avoids heuristics that force linearization of branching structures.
4. Scalability: The method is designed to handle large datasets (e.g., hundreds of trees) where exhaustive enumeration (used by competitors like MASTRO) becomes intractable.

4. Results and Applications

The authors validated POTTR on three distinct datasets:

A. Non-Small Cell Lung Cancer (NSCLC) - TRACERx421

• Data: 401 patients, 469 phylogenetic trees (multi-region whole-exome sequencing).
• Findings:
  • POTTR identified statistically significant recurrent trajectories that MASTRO missed.
  • Example 1: Resolved the order of COL5A2 relative to PIK3CA amplification, linking it to drug resistance mechanisms.
  • Example 2: Resolved a cluster involving NFE2L2, TP53, SOX2, and PIK3CA, inferring that NFE2L2 mutations occur later, which is biologically significant for oxidative stress response.
  • POTTR confirmed that resolving clusters is essential for discovering biologically relevant, longer trajectories.

B. Acute Myeloid Leukemia (AML) - Single-Cell Data

• Data: 123 single-cell trees.
• Comparison: Compared against MASTRO.
• Findings: POTTR identified 34 maximum recurrent trajectories; 33 were statistically significant ($p < 0.05$). In contrast, most trajectories reported by MASTRO were not significant. POTTR successfully handled the uncertainty inherent in single-cell data.

C. Embryoid Development (TLS) - Lineage Tracing

• Data: In vitro Trunk-Like Structures (TLS) with and without chemical perturbations (WNT activator/BMP inhibitor).
• Findings:
  • POTTR successfully analyzed DAGs (not just trees) to find conserved differentiation routes.
  • Discovery: Identified an alternative trajectory where somites emerge from a progenitor shared with endothelial cells (canonical view suggests neural tube origin).
  • Perturbation: Showed that chemical inhibition (TLSCL) suppresses this alternative route, reverting to the stereotypical neuro-mesodermal origin.

5. Significance and Discussion

• Biological Impact: POTTR enables the discovery of subtle, recurrent evolutionary patterns that were previously obscured by mutation clusters or tree uncertainty. This has direct implications for understanding drug resistance (e.g., in NSCLC) and developmental plasticity.
• Methodological Advancement: By moving from tree intersections to incomplete posets and conflict graphs, POTTR provides a rigorous mathematical framework that is more flexible than existing alignment-based or consensus-tree methods.
• Limitations & Future Work:
  • Computational Complexity: As an NP-hard problem, scalability for extremely large datasets may require heuristic approximations.
  • Statistical Significance: Current significance testing relies on permutation tests that are computationally expensive for large trajectories.
  • Infinite Sites Assumption: The current model assumes mutations occur once; relaxing this to allow parallel mutations is a future direction.

In summary, POTTR represents a significant step forward in computational biology by providing a robust, mathematically grounded tool to extract meaningful, recurrent evolutionary and developmental trajectories from noisy, heterogeneous, and uncertain biological data.