Dataset Information

Reconciliation with non-binary species trees.

ABSTRACT: Reconciliation extracts information from the topological incongruence between gene and species trees to infer duplications and losses in the history of a gene family. The inferred duplication-loss histories provide valuable information for a broad range of biological applications, including ortholog identification, estimating gene duplication times, and rooting and correcting gene trees. While reconciliation for binary trees is a tractable and well studied problem, there are no algorithms for reconciliation with non-binary species trees. Yet a striking proportion of species trees are non-binary. For example, 64% of branch points in the NCBI taxonomy have three or more children. When applied to non-binary species trees, current algorithms overestimate the number of duplications because they cannot distinguish between duplication and incomplete lineage sorting. We present the first algorithms for reconciling binary gene trees with non-binary species trees under a duplication-loss parsimony model. Our algorithms utilize an efficient mapping from gene to species trees to infer the minimum number of duplications in O(|V(G) | x (k(S) + h(S))) time, where |V(G)| is the number of nodes in the gene tree, h(S) is the height of the species tree and k(S) is the size of its largest polytomy. We present a dynamic programming algorithm which also minimizes the total number of losses. Although this algorithm is exponential in the size of the largest polytomy, it performs well in practice for polytomies with outdegree of 12 or less. We also present a heuristic which estimates the minimal number of losses in polynomial time. In empirical tests, this algorithm finds an optimal loss history 99% of the time. Our algorithms have been implemented in NOTUNG, a robust, production quality, tree-fitting program, which provides a graphical user interface for exploratory analysis and also supports automated, high-throughput analysis of large data sets.

SUBMITTER: Vernot B

PROVIDER: S-EPMC3205801 | biostudies-literature | 2008 Oct

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Reconciliation with non-binary species trees.

Vernot Benjamin B Stolzer Maureen M Goldman Aiton A Durand Dannie D

Journal of computational biology : a journal of computational molecular cell biology 20081001 8

Reconciliation extracts information from the topological incongruence between gene and species trees to infer duplications and losses in the history of a gene family. The inferred duplication-loss histories provide valuable information for a broad range of biological applications, including ortholog identification, estimating gene duplication times, and rooting and correcting gene trees. While reconciliation for binary trees is a tractable and well studied problem, there are no algorithms for re ...[more]

PMID: 18808330

Similar Datasets

Project description:However despotic a social group may be, managing conflicts of interest is crucial to preserve group living benefits, mainly based on cooperation. In despotic groups, post-conflict management via reconciliation (the first post-conflict reunion between former opponents) can occur, even if conciliatory rates are considerably different. Lemur catta is defined as a despotic species because groups are characterized by a strict linear hierarchy maintained by the adult females (the dominant sex) mainly via aggression. Reconciliation was reported in one out of four captive groups of L. catta. Here we investigate which variables influence the occurrence of reconciliation in these despotic groups. We analyzed 2339 Post Conflict (PC)-Matched Control (MC) observation pairs, collected on eight groups (five in the Berenty forest, Madagascar; three hosted at the Pistoia Zoo, Italy). Since L. catta is characterized by steep female dominance but shows female-female coalitionary support, we expected to confirm the presence of reconciliation in the study species. Consistently, we found reconciliation in one captive group and two wild groups, thus providing the first evidence of the presence of this phenomenon in wild L. catta. Moreover, because this species is a seasonal breeder (with mating occurring once a year), we expected seasonal fluctuations in reconciliation levels. Via a GLMM analysis using data from all wild groups and on a captive group followed for more than one year, we found that season (but not rank; individuals' identity, sex, and age; or group identity) significantly affected individual reconciliation rates, and such rates were lowest during the mating period. Thus, reconciliation can be present in groups in which dominants strongly influence and limit social relationships (steep dominance hierarchy) except when the advantages of intra-group cooperation are overcome by competition, as occurs in seasonal breeders when reproduction is at stake. We conclude that in despotic social groups in which coalitions are observed, the right question is not if but when reconciliation can be present.

Dataset Information

Reconciliation with non-binary species trees.

Publications

Reconciliation with non-binary species trees.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets