Quartet fiduccia-mattheyses revisited for larger phylogenetic studies

Abstract

Withtherecentbreakthroughsinsequencingtechnology,phylogenyestimationatalargerscalehas becomeahugeopportunity.Therefore,foraccurateestimationoflargescalephylogeny,substantial endeavourisbeingdevotedinintroducingnewalgorithmsorupgradingcurrentapproaches.Inthis work, we endeavour to improve the QFM (Quartet Fiduccia and Mattheyses) algorithm to resolve phylogenetictreesofbetterqualitywithbetterrunningtime.QFMwasalreadybeingappreciatedby researchers for its good tree quality, but fell short in larger phylogemonic studies due to its excessively slowrunningtime.Wehavere-designedQFMsothatitcanamalgamatemillionsofquartettreesover thousands of taxa into a species tree with a great level of accuracy within a short amount of time. Named QFM Fast and Improved (QFM-FI), our version is 20,000x faster than the previous version and400xfasterthanthewidelyusedvariantofQFMimplementedbyPAUP*onlargerdatasets.We have also provided a theoretical analysis of the running time of QFM-FI. ToassessthequalityofthetreesproducedbyQFM-FI,wehaveconductedacomparativestudyof QFM-FIwithotherstate-of-the-artphylogenyreconstructionmethods,suchasQFM,QMC,wQMC andASTRAL,onsimulatedaswellasrealbiologicaldatasets.Ourresultsshowthatinaddition to improving the running time, QFM-FI improves on the tree quality of QFM and produces trees thatare comparablewith state-of-the-artmethods.QFM-FIis opensource andavailable athttps: //github.com/sharmin-mim/qfm_java.