swMATH ID: 29624
Software Authors: Xu, A., Moret, B.
Description: GASTS: parsimony scoring under rearrangements. The accumulation of whole-genome data has renewed interest in the study of genomic rearrangements. Comparative genomics, evolutionary biology, and cancer research all require models and algorithms to elucidate the mechanisms, history, and consequences of these rearrangements. However, rearrangements lead to NP-hard problems, so that current approaches, such as the MGR tool, are limited to small collections of genomes and low-resolution data of a few hundred syntenic blocks. We describe the first algorithm for rearrangement analysis that scales up, in both time and accuracy, to modern high-resolution genomic data. Our main contribution is GASTS, an algorithm for scoring a fixed phylogenetic tree: given a tree and a collection of genomes, one for each leaf of the tree, each genome given by an ordered list of syntenic blocks, GASTS infers genomes for the internal nodes of the tree so as to minimize the sum, taken over all tree edges, of the pairwise genomic distances between tree nodes. We present the results of extensive testing on both simulated and real data showing that our algorithm runs several orders of magnitude faster than existing approaches and scales up linearly instead of exponentially with the size of the genomes involved; on the small instances that current approaches can complete in a day, our algorithm also returns much better scores. In simulations, our tree scores stay within 0.5
Homepage: https://link.springer.com/chapter/10.1007/978-3-642-23038-7_29
Related Software: MSOAR; OrthoMCL; FastTree; GRAPPA; RAxML; Mauve; OrthoDB; eggNOG; HyDe; UFBoot2; S-Cluster++; SplitsTree; MrBayes; MCScanX; CYNTENATOR; i-ADHoRe; Blast2GO; PhyloNetworks; MURPAR; StarBEAST2
Cited in: 4 Publications

Citations by Year