Limits...
Bootstrap-based support of HGT inferred by maximum parsimony.

Park HJ, Jin G, Nakhleh L - BMC Evol. Biol. (2010)

Bottom Line: An ad hoc solution to this problem that has been used entails inspecting the improvement in the parsimony length as more reticulation events are added to the model, and stopping when the improvement is below a certain threshold.A number of samples is generated from the given sequence alignment, and reticulation events are inferred based on each sample.Finally, the support of each reticulation event is quantified based on the inferences made over all samples.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, Rice University, 6100 Main Street, MS 132, Houston, Texas 77005, USA.

ABSTRACT

Background: Maximum parsimony is one of the most commonly used criteria for reconstructing phylogenetic trees. Recently, Nakhleh and co-workers extended this criterion to enable reconstruction of phylogenetic networks, and demonstrated its application to detecting reticulate evolutionary relationships. However, one of the major problems with this extension has been that it favors more complex evolutionary relationships over simpler ones, thus having the potential for overestimating the amount of reticulation in the data. An ad hoc solution to this problem that has been used entails inspecting the improvement in the parsimony length as more reticulation events are added to the model, and stopping when the improvement is below a certain threshold.

Results: In this paper, we address this problem in a more systematic way, by proposing a nonparametric bootstrap-based measure of support of inferred reticulation events, and using it to determine the number of those events, as well as their placements. A number of samples is generated from the given sequence alignment, and reticulation events are inferred based on each sample. Finally, the support of each reticulation event is quantified based on the inferences made over all samples.

Conclusions: We have implemented our method in the NEPAL software tool (available publicly at http://bioinfo.cs.rice.edu/), and studied its performance on both biological and simulated data sets. While our studies show very promising results, they also highlight issues that are inherently challenging when applying the maximum parsimony criterion to detect reticulate evolution.

Show MeSH
A phylogenetic tree (a) and a phylogenetic network obtained from it by adding a horizontal edge H from edge B to edge E.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC2874802&req=5

Figure 1: A phylogenetic tree (a) and a phylogenetic network obtained from it by adding a horizontal edge H from edge B to edge E.

Mentions: A phylogenetic network is a rooted, directed, acyclic graph, leaf-labeled by a set of taxa, coupled with a set of temporal constraints [20]. In the case of HGT, a phylogenetic network is obtained by adding a set of horizontal, or lateral, edges to an underlying species tree, where those horizontal edges capture the horizontal transfer events that may have occurred during the evolution of a certain gene under study. More precisely, if T is a phylogenetic (species) tree, we obtain a phylogenetic network N with a single HGT edge from tree T by selecting two edges e1 = (u1, v1) and e2 = (u2, v2) in T, splitting each of them, so that these two edges are replaced by four edges , , , , and finally a horizontal edge (x1, x2) is added. For example, in Figure 1, an HGT edge H is added in this fashion from edge B to edge E in the phylogenetic tree; the rectangular nodes in the phylogenetic network correspond to the splitting points of the two original edges B and E. It is important to note that when repeating this process to add other HGT edges, the procedure never splits a horizontal edge.


Bootstrap-based support of HGT inferred by maximum parsimony.

Park HJ, Jin G, Nakhleh L - BMC Evol. Biol. (2010)

A phylogenetic tree (a) and a phylogenetic network obtained from it by adding a horizontal edge H from edge B to edge E.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC2874802&req=5

Figure 1: A phylogenetic tree (a) and a phylogenetic network obtained from it by adding a horizontal edge H from edge B to edge E.
Mentions: A phylogenetic network is a rooted, directed, acyclic graph, leaf-labeled by a set of taxa, coupled with a set of temporal constraints [20]. In the case of HGT, a phylogenetic network is obtained by adding a set of horizontal, or lateral, edges to an underlying species tree, where those horizontal edges capture the horizontal transfer events that may have occurred during the evolution of a certain gene under study. More precisely, if T is a phylogenetic (species) tree, we obtain a phylogenetic network N with a single HGT edge from tree T by selecting two edges e1 = (u1, v1) and e2 = (u2, v2) in T, splitting each of them, so that these two edges are replaced by four edges , , , , and finally a horizontal edge (x1, x2) is added. For example, in Figure 1, an HGT edge H is added in this fashion from edge B to edge E in the phylogenetic tree; the rectangular nodes in the phylogenetic network correspond to the splitting points of the two original edges B and E. It is important to note that when repeating this process to add other HGT edges, the procedure never splits a horizontal edge.

Bottom Line: An ad hoc solution to this problem that has been used entails inspecting the improvement in the parsimony length as more reticulation events are added to the model, and stopping when the improvement is below a certain threshold.A number of samples is generated from the given sequence alignment, and reticulation events are inferred based on each sample.Finally, the support of each reticulation event is quantified based on the inferences made over all samples.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, Rice University, 6100 Main Street, MS 132, Houston, Texas 77005, USA.

ABSTRACT

Background: Maximum parsimony is one of the most commonly used criteria for reconstructing phylogenetic trees. Recently, Nakhleh and co-workers extended this criterion to enable reconstruction of phylogenetic networks, and demonstrated its application to detecting reticulate evolutionary relationships. However, one of the major problems with this extension has been that it favors more complex evolutionary relationships over simpler ones, thus having the potential for overestimating the amount of reticulation in the data. An ad hoc solution to this problem that has been used entails inspecting the improvement in the parsimony length as more reticulation events are added to the model, and stopping when the improvement is below a certain threshold.

Results: In this paper, we address this problem in a more systematic way, by proposing a nonparametric bootstrap-based measure of support of inferred reticulation events, and using it to determine the number of those events, as well as their placements. A number of samples is generated from the given sequence alignment, and reticulation events are inferred based on each sample. Finally, the support of each reticulation event is quantified based on the inferences made over all samples.

Conclusions: We have implemented our method in the NEPAL software tool (available publicly at http://bioinfo.cs.rice.edu/), and studied its performance on both biological and simulated data sets. While our studies show very promising results, they also highlight issues that are inherently challenging when applying the maximum parsimony criterion to detect reticulate evolution.

Show MeSH