RIATA-HGT: A fast and accurate heuristic for reconstructing horizontal gene transfer. Horizontal gene transfer (HGT) plays a major role in microbial genome diversification, and is claimed to be rampant among various groups of genes in bacteria. Further, HGT is a major confounding factor for any attempt to reconstruct bacterial phylogenies. As a result, detecting and reconstructing HGT events in groups of organisms has become a major endeavor in biology. The problem of detecting HGT events based on incongruence between a species tree and a gene tree is computationally very hard (NP-hard). Efficient algorithms exist for solving restricted cases of the problem. par We propose RIATA-HGT, the first polynomial-time heuristic to handle all HGT scenarios, without any restrictions. The method accurately infers HGT events based on analyzing incongruence among species and gene trees. Empirical performance of the method on synthetic and biological data is outstanding. Being a heuristic, RIATA-HGT may overestimate the optimal number of HGT events; empirical performance, however, shows that such overestimation is very mild. par We have implemented our method and run it on biological and synthetic data. The results we obtained demonstrate very high accuracy of the method. Current version of RIATA-HGT uses the PAUP tool, and we are in the process of implementing a stand-alone version, with a graphical user interface, which will be made public. The tool, in its current implementation, is available from the authors upon request.
Keywords for this software
References in zbMATH (referenced in 5 articles , 1 standard article )
Showing results 1 to 5 of 5.
- Makarenkov, Vladimir; Boc, Alix; Legendre, Pierre: A new algorithm for inferring hybridization events based on the detection of horizontal gene transfers (2014)
- Della Vedova, Gianluca; Dondi, Riccardo; Jiang, Tao; Pavesi, Giulio; Pirola, Yuri; Wang, Lusheng: Beyond evolutionary trees (2010)
- Bonet, María Luisa; John, Katherine St.: Efficiently calculating evolutionary tree measures using SAT (2009)
- Kanj, Iyad A.; Nakhleh, Luay; Than, Cuong; Xia, Ge: Seeing the trees and their branches in the network is hard (2008)
- Nakhleh, Luay; Ruths, Derek; Wang, Li-San: RIATA-HGT: A fast and accurate heuristic for reconstructing horizontal gene transfer (2005)