title: Detecting highways of horizontal gene transfer.
abstract: In a horizontal gene transfer (HGT) event, a gene is transferred between two species that do not have an ancestor-descendant relationship. Typically, no more than a few genes are horizontally transferred between any two species. However, several studies identified pairs of species between which many different genes were horizontally transferred. Such a pair is said to be linked by a highway of gene sharing. We present a method for inferring such highways. Our method is based on the fact that the evolutionary histories of horizontally transferred genes disagree with the corresponding species phylogeny. Specifically, given a set of gene trees and a trusted rooted species tree, each gene tree is first decomposed into its constituent quartet trees and the quartets that are inconsistent with the species tree are identified. Our method finds a pair of species such that a highway between them explains the largest (normalized) fraction of inconsistent quartets. For a problem on n species and m input quartet trees, we give an efficient O(m + n(2))-time algorithm for detecting highways, which is optimal with respect to the quartets input size. An application of our method to a dataset of 1128 genes from 11 cyanobacterial species, as well as to simulated datasets, illustrates the efficacy of our method.
authors: The Blavatnik School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.
authors: Mukul S
authors: MS
authors: Bansal
authors: Guy
authors: G
authors: Banay
authors: J Peter
authors: JP
authors: Gogarten
authors: Ron
authors: R
authors: Shamir
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D000458:Cyanobacteria / Q000235:genetics; D019143:Evolution, Molecular; D022761:Gene Transfer, Horizontal; D008957:Models, Genetic; D010802:Phylogeny; D012336:RNA, Ribosomal, 16S / Q000235:genetics
chemical_list: D012336:RNA, Ribosomal, 16S