Phylogenetic tree reconstruction via graph cut presented using a quantum-inspired computer
Open accessAbstract
Phylogenetic trees are essential tools in evolutionary biology that present information on evolutionary events among organisms and molecules. From a dataset of n sequences, a phylogenetic tree of (2n-5)!! possible topologies exists, and determining the optimum topology using brute force is infeasible. Recently, a recursive graph cut on a graph-represented-similarity matrix has proven accurate in reconstructing a phylogenetic tree containing distantly related sequences. However, identifying the optimum graph cut is challenging, and approximate solutions are currently utilized. Here, a phylogenetic tree was reconstructed with an improved graph cut using a quantum-inspired computer, the Fujitsu Digital Annealer (DA), and the algorithm was named the "Normalized-Minimum cut by Digital Annealer (NMcutDA) method". First, a criterion for the graph cut, the normalized cut value, was compared with existing clustering methods. Based on the cut, we verified that the simulated phylogenetic tree could be reconstructed with the highest accuracy when sequences were diverged. Moreover, for some actual data from the structure-based protein classification database, only NMcutDA could cluster sequences into correct superfamilies. Conclusively, NMcutDA reconstructed better phylogenetic trees than those using other methods by optimizing the graph cut. We anticipate that when the diversity of sequences is sufficiently high, NMcutDA can be utilized with high efficiency.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Onodera et al. reconstructed a phylogenetic tree using graph cut.
“Recently, Onodera etal. reconstructed a phylogenetic tree using graph cut.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [74]
Current research in quantum computing shows significant promise in bioinformatics.
“However, current research in quantum computing shows significant promise in bioinformatics [74].”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [74]
Cites
Scikit-learn: Machine Learning in Python
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Müller, A., Nothman, J., Louppe, G., et al. (2012) · arXiv · doi:10.48550/arxiv.1201.0490 · Cited by 71,016 · see citing works
The neighbor-joining method: a new method for reconstructing phylogenetic trees.
Saitou, N., & Nei, M. (1987) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040454 · Cited by 59,962 · see citing works
MUSCLE: multiple sequence alignment with high accuracy and high throughput
Edgar, R. C. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh340 · Cited by 44,662 · see citing works
MrBayes 3.2: Efficient Bayesian Phylogenetic Inference and Model Choice Across a Large Model Space
Ronquist, F., Teslenko, M., van der Mark, P., Ayres, D. L., Darling, A. E., Höhna, S., Larget, B. R., Liu, L., Suchard, M. A., & Huelsenbeck, J. P. (2012) · Systematic Biology · doi:10.1093/sysbio/sys029 · Cited by 27,933 · see citing works
IQ-TREE: A Fast and Effective Stochastic Algorithm for Estimating Maximum-Likelihood Phylogenies
Nguyen, L.-T., Schmidt, H. A., von Haeseler, A., & Minh, B. Q. (2015) · Molecular Biology and Evolution · doi:10.1093/molbev/msu300 · Cited by 26,046 · see citing works
Hierarchical Grouping to Optimize an Objective Function
Ward, J. H. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500845 · Cited by 21,341 · see citing works
ModelFinder: fast model selection for accurate phylogenetic estimates
Kalyaanamoorthy, S., Minh, B. Q., Wong, T. K. F., von Haeseler, A., & Jermiin, L. S. (2017) · Nature Methods · doi:10.1038/nmeth.4285 · Cited by 18,449 · see citing works
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,842 · see citing works
Least squares quantization in PCM
Lloyd, S. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056489 · Cited by 15,836 · see citing works
The igraph software package for complex network research
Csárdi, G., & Nepusz, T. (2006) · Medical Entomology and Zoology · Cited by 10,078 · see citing works
ape 5.0: an environment for modern phylogenetics and evolutionary analyses in R
Paradis, E., & Schliep, K. P. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty633 · Cited by 9,224 · see citing works
Amino acid substitution matrices from protein blocks.
Henikoff, S., & Henikoff, J. G. (1992) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.89.22.10915 · Cited by 6,218 · see citing works
phangorn: phylogenetic analysis in R
Schliep, K. P. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq706 · Cited by 3,678 · see citing works
BLAST: at the core of a powerful and diverse set of sequence analysis tools
McGinnis, S., & Madden, T. (2004) · Nucleic Acids Research · doi:10.1093/nar/gkh435 · Cited by 2,173 · see citing works
Phylogenetic Analysis: Models and Estimation Procedures
Cavalli-Sforza, L. L., & Edwards, A. W. F. (1967) · Evolution · doi:10.2307/2406616 · Cited by 1,216 · see citing works
Wu, Z., & Leahy, R. M. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.244673 · Cited by 1,144 · see citing works
Fox, N. K., Brenner, S. E., & Chandonia, J.-M. (2014) · Nucleic Acids Research · doi:10.1093/nar/gkt1240 · Cited by 762 · see citing works
Theoretical foundation of the minimum-evolution method of phylogenetic inference.
Rzhetsky, A., & Nei, M. (1993) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040056 · Cited by 673 · see citing works
Chandonia, J. (2003) · Nucleic Acids Research · doi:10.1093/nar/gkh034 · Cited by 529 · see citing works
Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., & Katzgraber, H. G. (2019) · Frontiers in Physics · doi:10.3389/fphy.2019.00048 · Cited by 442 · see citing works
INDELible: A Flexible Simulator of Biological Sequence Evolution
Fletcher, W., & Yang, Z. (2009) · Molecular Biology and Evolution · doi:10.1093/molbev/msp098 · Cited by 416 · see citing works
Simulating Trees with a Fixed Number of Extant Species
Stadler, T. (2011) · Systematic Biology · doi:10.1093/sysbio/syr029 · Cited by 304 · see citing works
Spectral clustering of protein sequences
Paccanaro, A. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj515 · Cited by 177 · see citing works
Protein structure similarities
Koehl, P. (2001) · Current Opinion in Structural Biology · doi:10.1016/s0959-440x(00)00214-1 · Cited by 176 · see citing works
Chandonia, J., Guan, L., Lin, S., Yu, C., Fox, N. K., & Brenner, S. E. (2021) · Nucleic Acids Research · doi:10.1093/nar/gkab1054 · Cited by 173 · see citing works
On Normalized Mutual Information: Measure Derivations and Properties
Kvålseth, T. O. (2017) · Entropy · doi:10.3390/e19110631 · Cited by 157 · see citing works
Direct Calculation of a Tree Length Using a Distance Matrix
Pauplin, Y. (2000) · Journal of Molecular Evolution · doi:10.1007/s002390010065 · Cited by 116 · see citing works
Reconstruction of the Core and Extended Regulons of Global Transcription Factors
Dufour, Y. S., Kiley, P. J., & Donohue, T. J. (2010) · PLoS Genetics · doi:10.1371/journal.pgen.1001027 · Cited by 65 · see citing works
Normalized Cuts Revisited: A Reformulation for Segmentation with Linear Grouping Constraints
Eriksson, A. P., Olsson, C., & Kahl, F. (2010) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-010-0223-5 · Cited by 36 · see citing works
The Balanced Minimum Evolution Problem
Catanzaro, D., Labbé, M., Pesenti, R., & Salazar‐González, J. (2011) · INFORMS journal on computing · doi:10.1287/ijoc.1110.0455 · Cited by 29 · see citing works
Xia, X. (2016) · Molecular Phylogenetics and Evolution · doi:10.1016/j.ympev.2016.07.001 · Cited by 27 · see citing works
RAxML Grove: an empirical phylogenetic tree database
Höhler, D., Pfeiffer, W., Ioannidis, V., Heinz Stockinger, C., & Stamatakis, A. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab863 · Cited by 27 · see citing works
The minimum evolution problem: Overview and classification
Catanzaro, D. (2008) · Networks · doi:10.1002/net.20280 · Cited by 27 · see citing works
Graph Splitting: A Graph-Based Approach for Superfamily-Scale Phylogenetic Tree Reconstruction
Matsui, M., & Iwasaki, W. (2019) · Systematic Biology · doi:10.1093/sysbio/syz049 · Cited by 21 · see citing works
Fast normalized cut with linear constraints
Xu, L., Li, W., & Schuurmans, D. (2009) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvprw.2009.5206561 · Cited by 18 · see citing works
Phylogeny Inference Based on Spectral Graph Clustering
Zhang, S., Zhou, S.-Y., He, J., et al. (2011) · Journal of Computational Biology · doi:10.1089/cmb.2009.0028 · Cited by 14 · see citing works
A tutorial on the balanced minimum evolution problem
Catanzaro, D., Frohn, M., Gascuel, O., & Pesenti, R. (2021) · European Journal of Operational Research · doi:10.1016/j.ejor.2021.08.004 · Cited by 9 · see citing works
The distribution of branch lengths in phylogenetic trees
Paradis, E. (2015) · Molecular Phylogenetics and Evolution · doi:10.1016/j.ympev.2015.08.010 · Cited by 8 · see citing works
On the approximability of the fixed-tree balanced minimum evolution problem
Frohn, M. (2021) · Optimization Letters · doi:10.1007/s11590-020-01677-x · Cited by 8 · see citing works
Rapid evolution of mammalian APLP1 as a synaptic adhesion molecule
Onodera, W., Asahi, T., & Sawamura, N. (2021) · Scientific Reports · doi:10.1038/s41598-021-90737-y · Cited by 8 · see citing works
Self-citationOnodera, W., Hara, N., Aoki, S., et al. (2023) · Data in Brief · doi:10.1016/j.dib.2023.108970 · Cited by 4 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Pal, S., Bhattacharya, M., Lee, S.-S., & Chakraborty, C. (2024) · Molecular Biotechnology · doi:10.1007/s12033-023-00765-4 · Cited by 84 · see citing works
“However, current research in quantum computing shows significant promise in bioinformatics [74].”
- Authors
- Onodera, W., Hara, N., Aoki, S., Asahi, T., & Sawamura, N.
- Affiliations
- Waseda University (JP)
- Fujitsu (Japan) (JP)
- Corresponding author
- Sawamura, Naoya
- Venue
- Molecular Phylogenetics and Evolution
- Publisher
- Elsevier BV
- Published
- 2023-01
- Volume
- 178
- Pages
- 107636
- ISSN
- 1055-7903 (ISSN-L)
- OpenAlex
- W4302024111
- Cited by
- 13
- References
- 41
- Citations by year
- 2026: 3 · 2025: 4 · 2024: 3 · 2023: 3
- FWCI
- 0.82
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- www.elsevier.com/legal/tdmrep-license (tdm)
- www.elsevier.com/open-access/userlicense/1.0/ (am, 291 d)
- doi.org/10.15223/policy-017 (stm-asf)
- doi.org/10.15223/policy-037 (stm-asf)
- doi.org/10.15223/policy-012 (stm-asf)
- doi.org/10.15223/policy-029 (stm-asf)
- doi.org/10.15223/policy-004 (stm-asf)
- Locations
- Molecular Phylogenetics and Evolution (acceptedVersion)
- PubMed (publishedVersion)
- Funders
- Fujitsu
- Topics
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Machine Learning in Bioinformatics
- Keywords
- phylogenetic inference, graph cuts, normalized cut, quantum-inspired computing, combinatorial optimization, protein superfamilies, sequence clustering, similarity matrix
- MeSH terms
- Algorithms, Computers, Phylogeny, Cluster Analysis, Databases, Protein
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
