Fast and accurate resolution of ecDNA sequence using Cycle-Extractor

Cycle-Extractor is a fast and accurate mixed-integer linear programming tool that reconstructs ecDNA structures from both short- and long-read sequencing data, outperforming existing methods in speed and achieving superior resolution of large, high-copy oncogenic circles validated by experimental evidence.

The Gist

Imagine your body's cells are like busy cities, and the DNA inside them is the master blueprint for how the city runs. Usually, this blueprint is neatly organized into 23 pairs of long, twisted ladders (chromosomes) stored in a central library.

But in some cancers, a chaotic event happens. Pieces of this blueprint get ripped out of the library, twisted into circles, and start floating around the cell like rogue islands. These are called ecDNAs (extrachromosomal DNAs).

Here's the scary part: These rogue islands are like "cheat codes" for cancer. They often carry extra copies of genes that tell the cancer to grow super fast and ignore medicine. Because they float freely, they don't divide evenly when the cell splits. One daughter cell might get a mountain of these cheat codes, while the other gets none. This makes the cancer evolve rapidly and become very dangerous.

The Problem: The "Puzzle" is Broken

To stop these rogue islands, scientists need to know exactly what they look like. What genes are on them? How are they arranged?

However, trying to figure out the shape of these ecDNAs from DNA sequencing data is like trying to rebuild a shredded, circular map where:

1. The pieces are huge: Some segments are massive.
2. The pieces repeat: The same gene might appear 50 times in a row.
3. The pieces are mixed up: The order is scrambled.
4. There are many copies: The cell has dozens of slightly different versions of these islands floating around at the same time.

Previous computer tools tried to solve this puzzle, but they were either too slow (taking hours or days) or they got stuck and couldn't find the best solution. It was like trying to solve a Rubik's cube while blindfolded.

The Solution: Cycle-Extractor (CE)

The authors of this paper built a new tool called Cycle-Extractor (CE). Think of CE as a super-smart, high-speed robot detective designed specifically to solve this circular puzzle.

Here is how it works, using a simple analogy:

1. The Map (The Graph)
First, the tool takes the messy DNA data and draws a "map" of connections. Imagine a subway map where the stations are chunks of DNA and the lines are the connections between them. Some lines are straight (normal DNA), and some are wild jumps (where the DNA got cut and pasted weirdly).

2. The Detective Work (The Algorithm)
The goal is to find the "loops" or "circles" in this subway map that represent the ecDNA.

• Old tools were like a slow, cautious hiker trying every possible path one by one. They often got stuck in dead ends or took forever to find the best loop.
• Cycle-Extractor is like a helicopter pilot with a supercomputer. It uses a mathematical trick (called Mixed-Integer Linear Programming) to instantly calculate the heaviest and longest possible loop. It asks: "Which path explains the most DNA copies in the fastest way?"

3. The "Long-Read" Superpower
The tool can work with two types of data:

• Short Reads: Like looking at a map made of tiny, disconnected post-it notes. You have to guess how they connect.
• Long Reads: Like looking at a map where some post-it notes are actually long strips of paper that span across the whole city.
  CE is amazing because it can use these long strips to guide its path, resolving the tricky parts that short notes miss. It's the difference between guessing a sentence from scattered words and reading the whole sentence clearly.

The Results: Faster and Better

The researchers tested this new tool against the old champions:

• Speed: CE is 40 times faster than the previous best tool. If the old tool took an hour to solve a puzzle, CE does it in seconds.
• Accuracy: It finds the correct shape of the ecDNA more often than the others.
• Real-World Proof: They tested it on a specific cancer cell line (PC3) that has a rogue island carrying the MYC gene (a major cancer driver).
  • The old method (using short reads) thought the island was about 690,000 letters long.
  • CE (using long reads) realized the island was actually 4.2 million letters long—a massive difference!
  • They even did a physical experiment (CRISPR-Catch) to cut the real DNA and measure it, and CE was right. The old method had missed a huge chunk of the puzzle.

Why This Matters

This isn't just about solving a math problem. By accurately mapping these rogue DNA islands, doctors and scientists can:

1. Understand the Enemy: Know exactly which "cheat codes" the cancer is using.
2. Develop Better Drugs: Design treatments that specifically target these circular structures.
3. Predict the Future: See how fast the cancer might evolve and become resistant to treatment.

In short, Cycle-Extractor is a fast, accurate, and powerful new lens that lets us finally see the hidden, chaotic architecture of cancer's most dangerous weapons.

Technical Summary

1. Problem Statement

Extrachromosomal DNA (ecDNA) consists of circular DNA molecules that lack centromeres and drive oncogene amplification, tumor evolution, and therapeutic resistance in approximately 14–17% of human cancers. Reconstructing the precise sequence and structure of these circular molecules from Whole Genome Sequencing (WGS) data is critical for understanding cancer biology but remains computationally challenging due to three main factors:

1. Structural Complexity: ecDNAs contain numerous breakpoints, complex rearrangements, and large duplicated segments with varying orientations.
2. Heterogeneity: Multiple distinct ecDNA species often coexist within a single tumor, sharing genomic segments but differing in copy number and structure.
3. Algorithmic Limitations: Existing tools struggle to accurately extract cycles from "amplicon graphs" (graphs representing amplified regions and novel adjacencies).
   • Short-read methods (e.g., AmpliconArchitect) often miss breakpoints in repetitive regions.
   • Long-read methods (e.g., CoRAL) offer better resolution but rely on Mixed-Integer Quadratically Constrained Programming (MIQCP), which is computationally expensive and requires specialized solvers, limiting accessibility and speed.

2. Methodology: Cycle-Extractor (CE)

The authors introduce Cycle-Extractor (CE), a tool designed to reconstruct ecDNA cycles from amplicon graphs derived from either short-read (Illumina) or long-read (ONT/PacBio) sequencing data.

Core Algorithm

CE operates in an iterative framework consisting of two main steps:

1. Optimization Step (MILP Formulation):

   • CE transforms the reconstruction problem into a Mixed-Integer Linear Programming (MILP) problem. This is a key innovation over CoRAL, which uses quadratic constraints.
   • Objective: Maximize the Length-Weighted Copy Number (LWCN) of a cyclic walk while satisfying a maximum number of subwalk constraints (derived from long reads).
   • Variables: The model assigns a global copy number ($F$) to the cycle and determines the multiplicity of each edge. It ensures that edge copy numbers are integer multiples of $F$.
   • Constraints: Includes capacity limits (edge copy number $\le$ observed coverage), flow balance (inflow = outflow at nodes), and connectivity constraints to ensure a single valid cycle.
   • Linearization: Quadratic terms (specifically regarding edge multiplicity) are linearized using auxiliary variables, allowing the use of standard, fast MILP solvers.

2. Traversal Step:

   • Once the optimal set of edges and their multiplicities are identified, CE constructs an ordered, signed list of edges (an Eulerian traversal).
   • It uses a modified Hierholzer's algorithm to sample possible traversals and selects the one that satisfies the maximum number of subwalk constraints (guiding the order of segments).

Handling Heterogeneity and Connectivity

• Iterative Extraction: After identifying the heaviest cycle, CE subtracts its copy number from the graph edges and repeats the process to extract subsequent cycles until the graph's total LWCN is largely explained (default $\ge 90\%$).
• Connectivity Enforcement (CEc): To prevent the algorithm from outputting multiple disconnected cycles in a single iteration (which might artificially inflate LWCN), a variant called CEc adds constraints to enforce exactly one cycle per iteration.
• CN Enhancement: The default CE method allows multiple disjoint cycles initially but enhances their copy numbers to the minimum edge capacity within that cycle, selecting the heaviest result.

3. Key Contributions

• Algorithmic Innovation: Successfully reformulated the ecDNA cycle extraction problem from MIQCP to MILP. This maintains accuracy while drastically reducing computational complexity.
• Dual-Modality Support: CE is compatible with both short-read (Illumina) and long-read (ONT/PacBio) data. It leverages long-read "subwalk constraints" to resolve ambiguities in segment ordering.
• Speed and Accessibility: By utilizing standard MILP solvers, CE eliminates the need for specialized quadratic programming solvers, making it accessible to a broader range of researchers.
• Heterogeneity Modeling: The iterative approach allows CE to disentangle complex ecDNA populations where multiple species share genomic regions.

4. Results

The authors evaluated CE against CoRAL (long-read), Decoil (long-read), and AmpliconArchitect (AA) (short-read) using simulated data and real cancer cell lines.

Performance on Simulated Data

• Accuracy: CE performed comparably to CoRAL across three metrics: Cycle Interval Overlap (CIO), Reconstruction Length Error (RLE), and Cyclic Longest Common Subsequence (LCS).
• Improvement: CE outperformed Decoil and AA on all metrics.
• Subwalk Satisfaction: CE satisfied 7.6% more subwalk constraints than CoRAL, leading to better reconstruction of complex structures.

Performance on Cancer Cell Lines

• Long-Read Data: CE and CoRAL produced similar high-quality results (heavy, long cycles). CE was able to reconstruct larger, more complete ecDNA structures than AA.
• Short-Read Data: CE significantly outperformed AA, producing cycles with higher LWCN (mean 0.704 vs. 0.598 for AA). This highlights CE's ability to optimize cycle extraction even when breakpoint data is sparse.
• Case Study (PC3): Using ONT data, CE reconstructed a 4.2 Mbp ecDNA molecule containing MYC with 47 copies. In contrast, the short-read reconstruction was only 690 Kbp with 12 copies.
• Experimental Validation: The long-read CE reconstruction for PC3 was validated via CRISPR-CATCH experiments. The predicted fragment sizes from CRISPR cuts matched the experimental gel electrophoresis results, confirming the existence of the large ecDNA structure.

Computational Efficiency

• Speed: CE is ~40 times faster than CoRAL.
  • CE average runtime: 0.13 to 75 seconds (58% of samples finished in <1 second).
  • CoRAL average runtime: Up to 32.5 minutes.
• Scalability: CE handles complex graphs (e.g., PC3 with 310 edges) efficiently, whereas CoRAL often hits time limits or requires significantly longer runtimes.

5. Significance

• Clinical Utility: Accurate ecDNA reconstruction is essential for identifying patients eligible for emerging ecDNA-targeted therapies (e.g., ecDNA-directed inhibitors). CE provides a fast, reliable method for this detection.
• Biological Insight: By reconstructing larger and more accurate ecDNA structures (as seen in the PC3 case), CE enables better study of oncogene amplification, enhancer hijacking, and the 3D architecture of ecDNA hubs.
• Accessibility: The shift from MIQCP to MILP democratizes access to high-quality ecDNA reconstruction, removing the barrier of specialized solver requirements.
• Future Directions: The authors plan to integrate CE into the AmpliconSuite workflow and extend the method to better quantify intratumoral heterogeneity by analyzing conflicting subwalk constraints.

In summary, Cycle-Extractor represents a significant leap forward in cancer genomics, offering a fast, accurate, and accessible solution for reconstructing the complex circular genomes that drive tumor progression.