Limits...
Tanglegrams for rooted phylogenetic trees and networks.

Scornavacca C, Zickmann F, Huson DH - Bioinformatics (2011)

Bottom Line: We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets.For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets.The algorithm is implemented in our program Dendroscope 3, which is freely available from www.dendroscope.org. scornava@informatik.uni-tuebingen.de; huson@informatik.uni-tuebingen.de.

View Article: PubMed Central - PubMed

Affiliation: Center for Bioinformatics (ZBIT), Tübingen University, Sand 14, 72076 Tübingen, Germany. scornava@informatik.uni-tuebingen.de

ABSTRACT

Motivation: In systematic biology, one is often faced with the task of comparing different phylogenetic trees, in particular in multi-gene analysis or cospeciation studies. One approach is to use a tanglegram in which two rooted phylogenetic trees are drawn opposite each other, using auxiliary lines to connect matching taxa. There is an increasing interest in using rooted phylogenetic networks to represent evolutionary history, so as to explicitly represent reticulate events, such as horizontal gene transfer, hybridization or reassortment. Thus, the question arises how to define and compute a tanglegram for such networks.

Results: In this article, we present the first formal definition of a tanglegram for rooted phylogenetic networks and present a heuristic approach for computing one, called the NN-tanglegram method. We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets. For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets.

Availability: The algorithm is implemented in our program Dendroscope 3, which is freely available from www.dendroscope.org.

Contact: scornava@informatik.uni-tuebingen.de; huson@informatik.uni-tuebingen.de.

Show MeSH
A pair of networks for which our approach may fail to find the optimal solution. (a) An optimal ordering and (b) an ordering that needs to be drawn with at least one crossing.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 4: A pair of networks for which our approach may fail to find the optimal solution. (a) An optimal ordering and (b) an ordering that needs to be drawn with at least one crossing.

Mentions: This is not true for networks. Indeed, in this case the Neighbor-Net algorithm may have more than one optimal solution. Theorem 3.5 ensures that any linear ordering π computed as described in Section 3.2 can be realized with zero crossings among connectors, but it does not guarantee that the resulting drawing will have zero crossings involving reticulate edges. For example, for the two networks in Figure 4, both orders (a,b,c,d) and (b,c,d,a) are circular with respect to H=D(Σ(N1))+D(Σ(N2)) and can be obtained from the distance matrix H using Neighbor-Net. Both orderings give a solution with zero crossings among connectors; yet, while a planar drawing for (a,b,c,d) exists [see Fig. 4(a)], a drawing respecting the ordering (b,c,d,a) will contain some crossings involving reticulate edges and thus fail to be optimal [see Fig. 4(b)]. However, if all optimal solutions of Neighbor-Net given H can be considered, then the NN-tanglegram approach will find the solution with cost zero. In such a case, our algorithm can be used to solve the planar layout (Lozano et al., 2008) or drawability problem (Fernau et al., 2010) for two networks [solved in linear time for two binary trees in (Fernau et al., 2010)].Fig. 4.


Tanglegrams for rooted phylogenetic trees and networks.

Scornavacca C, Zickmann F, Huson DH - Bioinformatics (2011)

A pair of networks for which our approach may fail to find the optimal solution. (a) An optimal ordering and (b) an ordering that needs to be drawn with at least one crossing.
© Copyright Policy - creative-commons
Related In: Results  -  Collection

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

Figure 4: A pair of networks for which our approach may fail to find the optimal solution. (a) An optimal ordering and (b) an ordering that needs to be drawn with at least one crossing.
Mentions: This is not true for networks. Indeed, in this case the Neighbor-Net algorithm may have more than one optimal solution. Theorem 3.5 ensures that any linear ordering π computed as described in Section 3.2 can be realized with zero crossings among connectors, but it does not guarantee that the resulting drawing will have zero crossings involving reticulate edges. For example, for the two networks in Figure 4, both orders (a,b,c,d) and (b,c,d,a) are circular with respect to H=D(Σ(N1))+D(Σ(N2)) and can be obtained from the distance matrix H using Neighbor-Net. Both orderings give a solution with zero crossings among connectors; yet, while a planar drawing for (a,b,c,d) exists [see Fig. 4(a)], a drawing respecting the ordering (b,c,d,a) will contain some crossings involving reticulate edges and thus fail to be optimal [see Fig. 4(b)]. However, if all optimal solutions of Neighbor-Net given H can be considered, then the NN-tanglegram approach will find the solution with cost zero. In such a case, our algorithm can be used to solve the planar layout (Lozano et al., 2008) or drawability problem (Fernau et al., 2010) for two networks [solved in linear time for two binary trees in (Fernau et al., 2010)].Fig. 4.

Bottom Line: We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets.For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets.The algorithm is implemented in our program Dendroscope 3, which is freely available from www.dendroscope.org. scornava@informatik.uni-tuebingen.de; huson@informatik.uni-tuebingen.de.

View Article: PubMed Central - PubMed

Affiliation: Center for Bioinformatics (ZBIT), Tübingen University, Sand 14, 72076 Tübingen, Germany. scornava@informatik.uni-tuebingen.de

ABSTRACT

Motivation: In systematic biology, one is often faced with the task of comparing different phylogenetic trees, in particular in multi-gene analysis or cospeciation studies. One approach is to use a tanglegram in which two rooted phylogenetic trees are drawn opposite each other, using auxiliary lines to connect matching taxa. There is an increasing interest in using rooted phylogenetic networks to represent evolutionary history, so as to explicitly represent reticulate events, such as horizontal gene transfer, hybridization or reassortment. Thus, the question arises how to define and compute a tanglegram for such networks.

Results: In this article, we present the first formal definition of a tanglegram for rooted phylogenetic networks and present a heuristic approach for computing one, called the NN-tanglegram method. We compare the performance of our method with existing tree tanglegram algorithms and also show a typical application to real biological datasets. For maximum usability, the algorithm does not require that the trees or networks are bifurcating or bicombining, or that they are on identical taxon sets.

Availability: The algorithm is implemented in our program Dendroscope 3, which is freely available from www.dendroscope.org.

Contact: scornava@informatik.uni-tuebingen.de; huson@informatik.uni-tuebingen.de.

Show MeSH