Minimum-Cost Synthetic Genome Planning: An Algorithmic Framework
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911142488571904 |
|---|---|
| author | Patsakis, Michail Mouratidis, Ioannis Georgakopoulos-Soares, Ilias |
| author_facet | Patsakis, Michail Mouratidis, Ioannis Georgakopoulos-Soares, Ilias |
| contents | As synthetic genomics scales toward the construction of increasingly larger genomes, computational strategies are needed to address technical feasibility. We introduce an algorithmic framework for the Minimum-Cost Synthetic Genome Planning problem, aiming to identify the most cost-effective strategy to assemble a target genome from a source genome through a combination of reuse, synthesis, and join operations. By comparing dynamic programming and greedy heuristic strategies under diverse cost regimes, we demonstrate how algorithmic choices influence the cost-efficiency of large-scale genome construction. In parallel, solving the Minimum-Cost Synthetic Genome Planning problem can help us better understand genome architecture and evolution. We applied our framework in case studies on viral genomes, including SARS-CoV-2, to examine how source-target genome similarity shapes construction costs. Our analyses revealed that conserved regions such as ORF1ab can be reconstructed cost-effectively from related templates, while highly variable regions such as the S (spike) gene are more reliant on DNA synthesis, highlighting the biological and economic trade-offs of genome design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06234 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum-Cost Synthetic Genome Planning: An Algorithmic Framework Patsakis, Michail Mouratidis, Ioannis Georgakopoulos-Soares, Ilias Genomics As synthetic genomics scales toward the construction of increasingly larger genomes, computational strategies are needed to address technical feasibility. We introduce an algorithmic framework for the Minimum-Cost Synthetic Genome Planning problem, aiming to identify the most cost-effective strategy to assemble a target genome from a source genome through a combination of reuse, synthesis, and join operations. By comparing dynamic programming and greedy heuristic strategies under diverse cost regimes, we demonstrate how algorithmic choices influence the cost-efficiency of large-scale genome construction. In parallel, solving the Minimum-Cost Synthetic Genome Planning problem can help us better understand genome architecture and evolution. We applied our framework in case studies on viral genomes, including SARS-CoV-2, to examine how source-target genome similarity shapes construction costs. Our analyses revealed that conserved regions such as ORF1ab can be reconstructed cost-effectively from related templates, while highly variable regions such as the S (spike) gene are more reliant on DNA synthesis, highlighting the biological and economic trade-offs of genome design. |
| title | Minimum-Cost Synthetic Genome Planning: An Algorithmic Framework |
| topic | Genomics |
| url | https://arxiv.org/abs/2509.06234 |