1
|
Chen Y, Huang JH, Sun Y, Zhang Y, Li Y, Xu X. Haplotype-resolved assembly of diploid and polyploid genomes using quantum computing. Cell Rep Methods 2024:100754. [PMID: 38614089 DOI: 10.1016/j.crmeth.2024.100754] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/08/2023] [Revised: 01/03/2024] [Accepted: 03/20/2024] [Indexed: 04/15/2024]
Abstract
Precision medicine's emphasis on individual genetic variants highlights the importance of haplotype-resolved assembly, a computational challenge in bioinformatics given its combinatorial nature. While classical algorithms have made strides in addressing this issue, the potential of quantum computing remains largely untapped. Here, we present the vehicle routing problem (VRP) assembler: an approach that transforms this task into a vehicle routing problem, an optimization formulation solvable on a quantum computer. We demonstrate its potential and feasibility through a proof of concept on short synthetic diploid and triploid genomes using a D-Wave quantum annealer. To tackle larger-scale assembly problems, we integrate the VRP assembler with Google's OR-Tools, achieving a haplotype-resolved local assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to Hifiasm with phasing accuracy approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.
Collapse
Affiliation(s)
- Yibo Chen
- BGI Research, Shenzhen 518083, China
| | | | - Yuhui Sun
- BGI Research, Shenzhen 518083, China
| | - Yong Zhang
- BGI Research, Wuhan 430047, China; Guangdong Bigdata Engineering Technology Research Center for Life Sciences, BGI Research, Shenzhen 518083, China.
| | - Yuxiang Li
- BGI Research, Wuhan 430047, China; Guangdong Bigdata Engineering Technology Research Center for Life Sciences, BGI Research, Shenzhen 518083, China.
| | - Xun Xu
- BGI Research, Shenzhen 518083, China; BGI Research, Wuhan 430047, China.
| |
Collapse
|
2
|
Lu Y, Chen X, Yu H, Zhang C, Xue Y, Zhang Q, Wang H. Haplotype-resolved genome assembly of Phanera championii reveals molecular mechanisms of flavonoid synthesis and adaptive evolution. Plant J 2024; 118:488-505. [PMID: 38173092 DOI: 10.1111/tpj.16620] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/16/2023] [Revised: 12/15/2023] [Accepted: 12/20/2023] [Indexed: 01/05/2024]
Abstract
Phanera championii is a medicinal liana plant that has successfully adapted to hostile karst habitats. Despite extensive research on its medicinal components and pharmacological effects, the molecular mechanisms underlying the biosynthesis of critical flavonoids and its adaptation to karst habitats remain elusive. In this study, we performed high-coverage PacBio and Hi-C sequencing of P. championii, which revealed its high heterozygosity and phased the genome into two haplotypes: Hap1 (384.60 Mb) and Hap2 (383.70 Mb), encompassing a total of 58 612 annotated genes. Comparative genomes analysis revealed that P. championii experienced two whole-genome duplications (WGDs), with approximately 59.59% of genes originating from WGD events, thereby providing a valuable genetic resource for P. championii. Moreover, we identified a total of 112 genes that were strongly positively selected. Additionally, about 81.60 Mb of structural variations between the two haplotypes. The allele-specific expression patterns suggested that the dominant effect of P. championii was the elimination of deleterious mutations and the promotion of beneficial mutations to enhance fitness. Moreover, our transcriptome and metabolome analysis revealed alleles in different tissues or different haplotypes collectively regulate the synthesis of flavonoid metabolites. In summary, our comprehensive study highlights the significance of genomic and morphological adaptation in the successful adaptation of P. championii to karst habitats. The high-quality phased genomes obtained in this study serve as invaluable genomic resources for various applications, including germplasm conservation, breeding, evolutionary studies, and elucidation of pathways governing key biological traits of P. championii.
Collapse
Affiliation(s)
- Yongbin Lu
- State Key Laboratory for Conservation and Utilization of Subtropical Agro-Bioresources, College of Agriculture, Guangxi University, Nanning, 530004, China
- Guangxi Key Laboratory of Plant Conservation and Restoration Ecology in Karst Terrain, Guangxi Institute of Botany, Guangxi Zhuang Autonomous Region and the Chinese Academy of Sciences, Yanshan, Guilin, 541006, China
| | - Xiao Chen
- Shenzhen Branch, Guangdong Laboratory for Lingnan Modern Agriculture, Genome Analysis Laboratory of the Ministry of Agriculture, Agricultural Genomics Institute at Shenzhen, Chinese Academy of Agricultural Sciences, Shenzhen, 518120, China
| | - Hang Yu
- State Key Laboratory for Conservation and Utilization of Subtropical Agro-Bioresources, College of Agriculture, Guangxi University, Nanning, 530004, China
- Key Laboratory of Crop Cultivation and Physiology, Education Department of Guangxi Zhuang Autonomous Region, Guangxi University, Nanning, 530004, China
| | - Chao Zhang
- State Key Laboratory for Conservation and Utilization of Subtropical Agro-Bioresources, College of Agriculture, Guangxi University, Nanning, 530004, China
- Key Laboratory of Crop Cultivation and Physiology, Education Department of Guangxi Zhuang Autonomous Region, Guangxi University, Nanning, 530004, China
| | - Yajie Xue
- State Key Laboratory for Conservation and Utilization of Subtropical Agro-Bioresources, College of Agriculture, Guangxi University, Nanning, 530004, China
- Key Laboratory of Crop Cultivation and Physiology, Education Department of Guangxi Zhuang Autonomous Region, Guangxi University, Nanning, 530004, China
| | - Qiang Zhang
- Guangxi Key Laboratory of Plant Conservation and Restoration Ecology in Karst Terrain, Guangxi Institute of Botany, Guangxi Zhuang Autonomous Region and the Chinese Academy of Sciences, Yanshan, Guilin, 541006, China
| | - Haifeng Wang
- State Key Laboratory for Conservation and Utilization of Subtropical Agro-Bioresources, College of Agriculture, Guangxi University, Nanning, 530004, China
- Key Laboratory of Crop Cultivation and Physiology, Education Department of Guangxi Zhuang Autonomous Region, Guangxi University, Nanning, 530004, China
| |
Collapse
|
3
|
Okuno M, Mizushima S, Kuroiwa A, Itoh T. Analysis of Sex Chromosome Evolution in the Clade Palaeognathae from Phased Genome Assembly. Genome Biol Evol 2021; 13:6413640. [PMID: 34718546 PMCID: PMC8599748 DOI: 10.1093/gbe/evab242] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Accepted: 10/26/2021] [Indexed: 12/30/2022] Open
Abstract
Birds in the clade Palaeognathae, excluding Tinamiformes, have morphologically conserved karyotypes and less differentiated ZW sex chromosomes compared with those of other birds. In particular, the sex chromosomes of the ostrich and emu have exceptionally large recombining pseudoautosomal regions (PARs), whereas non-PARs are classified into two strata according to the date of their origins: stratum 0 and stratum 1 (S1). However, the construction and analysis of the genome sequences in these regions in the clade Palaeognathae can be challenging because assembling the S1 region is difficult owing to low sequence diversity between gametologs (Z-linked and W-linked sequences). We addressed this issue by applying the Platanus-allee assembler and successfully constructed the haplotype-resolved (phased) assembly for female emu, cassowary, and ostrich using only sequence read data derived from the Illumina platform. Comparative genomic and phylogenetic analyses based on assembled Z-linked and W-linked sequences confirmed that the S1 region of emu and cassowary formed in their common ancestor. Moreover, the interspersed repetitive sequence landscapes in the S1 regions of female emu showed an expansion of younger repetitive elements in the W-linked S1 region, suggesting an interruption in homologous recombination in the S1 region. These results provide novel insights into the trajectory of sex chromosome evolution in the clade Palaeognathae and suggest that the Illumina-based phased assembly method is an effective approach for elucidating the evolutionary process underlying the transition from homomorphic to differentiated sex chromosomes.
Collapse
Affiliation(s)
- Miki Okuno
- School of Life Science and Technology, Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan.,Division of Microbiology, Department of Infectious Medicine, Kurume University School of Medicine, Kurume, Fukuoka, Japan
| | - Shusei Mizushima
- Division of Reproductive and Developmental Biology, Department of Biological Sciences, Faculty of Science, Hokkaido University, Sapporo, Hokkaido, Japan
| | - Asato Kuroiwa
- Division of Reproductive and Developmental Biology, Department of Biological Sciences, Faculty of Science, Hokkaido University, Sapporo, Hokkaido, Japan
| | - Takehiko Itoh
- School of Life Science and Technology, Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan
| |
Collapse
|
4
|
AGUIAR DEREK, WONG WENDYS, ISTRAIL SORIN. Tumor haplotype assembly algorithms for cancer genomics. Pac Symp Biocomput 2014:3-14. [PMID: 24297529 PMCID: PMC4051221] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [MESH Headings] [Grants] [Subscribe] [Scholar Register] [Indexed: 06/02/2023]
Abstract
The growing availability of inexpensive high-throughput sequence data is enabling researchers to sequence tumor populations within a single individual at high coverage. But, cancer genome sequence evolution and mutational phenomena like driver mutations and gene fusions are difficult to investigate without first reconstructing tumor haplotype sequences. Haplotype assembly of single individual tumor populations is an exceedingly difficult task complicated by tumor haplotype heterogeneity, tumor or normal cell sequence contamination, polyploidy, and complex patterns of variation. While computational and experimental haplotype phasing of diploid genomes has seen much progress in recent years, haplotype assembly in cancer genomes remains uncharted territory. In this work, we describe HapCompass-Tumor a computational modeling and algorithmic framework for haplotype assembly of copy number variable cancer genomes containing haplotypes at different frequencies and complex variation. We extend our polyploid haplotype assembly model and present novel algorithms for (1) complex variations, including copy number changes, as varying numbers of disjoint paths in an associated graph, (2) variable haplotype frequencies and contamination, and (3) computation of tumor haplotypes using simple cycles of the compass graph which constrain the space of haplotype assembly solutions. The model and algorithm are implemented in the software package HapCompass-Tumor which is available for download from http://www.brown.edu/Research/Istrail_Lab/.
Collapse
Affiliation(s)
- DEREK AGUIAR
- Department of Computer Science and Center for Computational Molecular Biology, Brown University, Providence, RI 02912, USA
| | - WENDY S.W. WONG
- Inova Translational Medicine Institute, Inova Health Systems, Falls Church, VA 22042, USA
| | - SORIN ISTRAIL
- Department of Computer Science and Center for Computational Molecular Biology, Brown University, Providence, RI 02912, USA
| |
Collapse
|