.\" Automatically generated by Pod::Man 4.11 (Pod::Simple 3.35)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" Set up some character translations and predefined strings.  \*(-- will
.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
.\" double quote, and \*(R" will give a right double quote.  \*(C+ will
.\" give a nicer C++.  Capital omega is used to do unbreakable dashes and
.\" therefore won't be available.  \*(C` and \*(C' expand to `' in nroff,
.\" nothing in troff, for use with C<>.
.tr \(*W-
.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
.ie n \{\
.    ds -- \(*W-
.    ds PI pi
.    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
.    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
.    ds L" ""
.    ds R" ""
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds -- \|\(em\|
.    ds PI \(*p
.    ds L" ``
.    ds R" ''
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is >0, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{\
.    if \nF \{\
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{\
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\" ========================================================================
.\"
.IX Title "Bio::Tree::Compatible 3pm"
.TH Bio::Tree::Compatible 3pm "2020-10-28" "perl v5.30.3" "User Contributed Perl Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH "NAME"
Bio::Tree::Compatible \- Testing compatibility of phylogenetic trees
with nested taxa.
.SH "SYNOPSIS"
.IX Header "SYNOPSIS"
.Vb 6
\&  use Bio::Tree::Compatible;
\&  use Bio::TreeIO;
\&  my $input = Bio::TreeIO\->new(\*(Aq\-format\*(Aq => \*(Aqnewick\*(Aq,
\&                               \*(Aq\-file\*(Aq   => \*(Aqinput.tre\*(Aq);
\&  my $t1 = $input\->next_tree;
\&  my $t2 = $input\->next_tree;
\&
\&  my ($incompat, $ilabels, $inodes) = Bio::Tree::Compatible::is_compatible($t1,$t2);
\&  if ($incompat) {
\&    my %cluster1 = %{ Bio::Tree::Compatible::cluster_representation($t1) };
\&    my %cluster2 = %{ Bio::Tree::Compatible::cluster_representation($t2) };
\&    print "incompatible trees\en";
\&    if (scalar(@$ilabels)) {
\&      foreach my $label (@$ilabels) {
\&        my $node1 = $t1\->find_node(\-id => $label);
\&        my $node2 = $t2\->find_node(\-id => $label);
\&        my @c1 = sort @{ $cluster1{$node1} };
\&        my @c2 = sort @{ $cluster2{$node2} };
\&        print "label $label";
\&        print " cluster"; map { print " ",$_ } @c1;
\&        print " cluster"; map { print " ",$_ } @c2; print "\en";
\&      }
\&    }
\&    if (scalar(@$inodes)) {
\&      while (@$inodes) {
\&        my $node1 = shift @$inodes;
\&        my $node2 = shift @$inodes;
\&        my @c1 = sort @{ $cluster1{$node1} };
\&        my @c2 = sort @{ $cluster2{$node2} };
\&        print "cluster"; map { print " ",$_ } @c1;
\&        print " properly intersects cluster";
\&        map { print " ",$_ } @c2; print "\en";
\&      }
\&    }
\&  } else {
\&    print "compatible trees\en";
\&  }
.Ve
.SH "DESCRIPTION"
.IX Header "DESCRIPTION"
\&\s-1NB:\s0 This module has exclusively class methods that work on Bio::Tree::TreeI
objects. An instance of Bio::Tree::Compatible cannot itself represent a tree,
and so typically there is no need to create one.
.PP
Bio::Tree::Compatible is a Perl tool for testing compatibility of
phylogenetic trees with nested taxa represented as Bio::Tree::Tree
objects. It is based on a recent characterization of ancestral
compatibility of semi-labeled trees in terms of their cluster
representations.
.PP
A semi-labeled tree is a phylogenetic tree with some of its internal
nodes labeled, and it can represent a classification tree as well as a
phylogenetic tree with nested taxa, with labeled internal nodes
corresponding to taxa at a higher level of aggregation or nesting than
that of their descendents.
.PP
Two semi-labeled trees are compatible if their topological
restrictions to the common labels are such that for each node label,
the smallest clusters containing it in each of the trees coincide and,
furthermore, no cluster in one of the trees properly intersects a
cluster of the other tree.
.PP
Future extensions of Bio::Tree::Compatible include a
Bio::Tree::Supertree module for combining compatible phylogenetic
trees with nested taxa into a common supertree.
.SH "FEEDBACK"
.IX Header "FEEDBACK"
.SS "Mailing Lists"
.IX Subsection "Mailing Lists"
User feedback is an integral part of the evolution of this and other
Bioperl modules. Send your comments and suggestions preferably to the
Bioperl mailing list.  Your participation is much appreciated.
.PP
.Vb 2
\&  bioperl\-l@bioperl.org                  \- General discussion
\&  http://bioperl.org/wiki/Mailing_lists  \- About the mailing lists
.Ve
.SS "Support"
.IX Subsection "Support"
Please direct usage questions or support issues to the mailing list:
.PP
\&\fIbioperl\-l@bioperl.org\fR
.PP
rather than to the module maintainer directly. Many experienced and 
reponsive experts will be able look at the problem and quickly 
address it. Please include a thorough description of the problem 
with code and data examples if at all possible.
.SS "Reporting Bugs"
.IX Subsection "Reporting Bugs"
Report bugs to the Bioperl bug tracking system to help us keep track
of the bugs and their resolution. Bug reports can be submitted via the
web:
.PP
.Vb 1
\&  https://github.com/bioperl/bioperl\-live/issues
.Ve
.SH "SEE ALSO"
.IX Header "SEE ALSO"
.IP "\(bu" 4
Philip Daniel and Charles Semple. Supertree Algorithms for
Nested Taxa. In: Olaf R. P. Bininda-Emonds (ed.) Phylogenetic
Supertrees: Combining Information to Reveal the Tree of Life,
\&\fIComputational Biology\fR, vol. 4, chap. 7, pp. 151\-171. Kluwer (2004).
.IP "\(bu" 4
Charles Semple, Philip Daniel, Wim Hordijk, Roderic
D. M. Page, and Mike Steel: Supertree Algorithms for Ancestral
Divergence Dates and Nested Taxa. Bioinformatics \fB20\fR(15), 2355\-2360
(2004).
.IP "\(bu" 4
Merce Llabres, Jairo Rocha, Francesc Rossello, and Gabriel
Valiente: On the Ancestral Compatibility of Two Phylogenetic Trees
with Nested Taxa. J. Math. Biol. \fB53\fR(3), 340\-364 (2006).
.SH "AUTHOR \- Gabriel Valiente"
.IX Header "AUTHOR - Gabriel Valiente"
Email valiente@lsi.upc.edu
.SH "APPENDIX"
.IX Header "APPENDIX"
The rest of the documentation details each of the object methods.
.SS "postorder_traversal"
.IX Subsection "postorder_traversal"
.Vb 5
\& Title   : postorder_traversal
\& Usage   : my @nodes = @{ $tree\->postorder_traversal }
\& Function: Return list of nodes in postorder
\& Returns : reference to array of Bio::Tree::Node
\& Args    : none
.Ve
.PP
For example, the postorder traversal of the tree
\&\f(CW\*(C`(((A,B)C,D),(E,F,G));\*(C'\fR is a reference to an array of nodes with
internal_id 0 through 9, because the Newick standard representation
for phylogenetic trees is based on a postorder traversal.
.PP
.Vb 10
\&          +\-\-\-A                    +\-\-\-0
\&          |                        |
\&  +\-\-\-+\-\-\-C                +\-\-\-4\-\-\-2
\&  |   |   |                |   |   |
\&  |   |   +\-\-\-B            |   |   +\-\-\-1
\&  |   |                    |   |
\&  +   +\-\-\-\-\-\-\-D            9   +\-\-\-\-\-\-\-3
\&  |                        |
\&  |     +\-\-\-\-\-E            |     +\-\-\-\-\-5
\&  |     |                  |     |
\&  +\-\-\-\-\-+\-\-\-\-\-F            +\-\-\-\-\-8\-\-\-\-\-6
\&        |                        |
\&        +\-\-\-\-\-G                  +\-\-\-\-\-7
.Ve
.SS "cluster_representation"
.IX Subsection "cluster_representation"
.Vb 6
\& Title   : cluster_representation
\& Usage   : my %cluster = %{ $tree\->cluster_representation }
\& Function: Compute the cluster representation of a tree
\& Returns : reference to hash of array of string indexed by
\&           Bio::Tree::Node
\& Args    : none
.Ve
.PP
For example, the cluster representation of the tree
\&\f(CW\*(C`(((A,B)C,D),(E,F,G));\*(C'\fR is a reference to a hash associating an array
of string (descendent labels) to each node, as follows:
.PP
.Vb 10
\&  0 \-\-> [A]
\&  1 \-\-> [B]
\&  2 \-\-> [A,B,C]
\&  3 \-\-> [D]
\&  4 \-\-> [A,B,C,D]
\&  5 \-\-> [E]
\&  6 \-\-> [F]
\&  7 \-\-> [G]
\&  8 \-\-> [E,F,G]
\&  9 \-\-> [A,B,C,D,E,F,G]
.Ve
.SS "common_labels"
.IX Subsection "common_labels"
.Vb 5
\& Title   : common_labels
\& Usage   : my $labels = $tree1\->common_labels($tree2);
\& Function: Return set of common node labels
\& Returns : Set::Scalar
\& Args    : Bio::Tree::Tree
.Ve
.PP
For example, the common labels of the tree \f(CW\*(C`(((A,B)C,D),(E,F,G));\*(C'\fR
and the tree \f(CW\*(C`((A,B)H,E,(J,(K)G)I);\*(C'\fR are: \f(CW\*(C`[A,B,E,G]\*(C'\fR.
.PP
.Vb 10
\&          +\-\-\-A                 +\-\-\-A
\&          |                     |
\&  +\-\-\-+\-\-\-C             +\-\-\-\-\-\-\-H
\&  |   |   |             |       |
\&  |   |   +\-\-\-B         |       +\-\-\-B
\&  |   |                 |
\&  +   +\-\-\-\-\-\-\-D         +\-\-\-\-\-\-\-\-\-\-\-E
\&  |                     |
\&  |     +\-\-\-\-\-E         |   +\-\-\-\-\-\-\-J
\&  |     |               |   |
\&  +\-\-\-\-\-+\-\-\-\-\-F         +\-\-\-I
\&        |                   |
\&        +\-\-\-\-\-G             +\-\-\-G\-\-\-K
.Ve
.SS "topological_restriction"
.IX Subsection "topological_restriction"
.Vb 6
\& Title   : topological_restriction
\& Usage   : $tree\->topological_restriction($labels)
\& Function: Compute the topological restriction of a tree to a subset
\&           of node labels
\& Returns : Bio::Tree::Tree
\& Args    : Set::Scalar
.Ve
.PP
For example, the topological restrictions of each of the trees
\&\f(CW\*(C`(((A,B)C,D),(E,F,G));\*(C'\fR and \f(CW\*(C`((A,B)H,E,(J,(K)G)I);\*(C'\fR to the labels
\&\f(CW\*(C`[A,B,E,G]\*(C'\fR are as follows:
.PP
.Vb 11
\&          +\-\-\-A             +\-\-\-A
\&          |                 |
\&  +\-\-\-+\-\-\-+             +\-\-\-+
\&  |       |             |   |
\&  |       +\-\-\-B         |   +\-\-\-B
\&  +                     |
\&  |       +\-\-\-E         +\-\-\-\-\-\-\-E
\&  |       |             |
\&  +\-\-\-\-\-\-\-+             +\-\-\-+\-\-\-G
\&          |
\&          +\-\-\-G
.Ve
.SS "is_compatible"
.IX Subsection "is_compatible"
.Vb 5
\& Title   : is_compatible
\& Usage   : $tree1\->is_compatible($tree2)
\& Function: Test compatibility of two trees
\& Returns : boolean
\& Args    : Bio::Tree::Tree
.Ve
.PP
For example, the topological restrictions of the trees
\&\f(CW\*(C`(((A,B)C,D),(E,F,G));\*(C'\fR and \f(CW\*(C`((A,B)H,E,(J,(K)G)I);\*(C'\fR to their common
labels, \f(CW\*(C`[A,B,E,G]\*(C'\fR, are compatible. The respective cluster
representations are as follows:
.PP
.Vb 7
\&  [A]                  [A]
\&  [B]                  [B]
\&  [E]                  [E]
\&  [G]                  [G]
\&  [A,B]                [A,B]
\&  [E,G]                [A,B,E,G]
\&  [A,B,E,G]
.Ve
.PP
As a second example, the trees \f(CW\*(C`(A,B);\*(C'\fR and \f(CW\*(C`((B)A);\*(C'\fR are
incompatible. Their respective cluster representations are as follows:
.PP
.Vb 3
\&  [A]                  [B]
\&  [B]                  [A,B]
\&  [A,B]
.Ve
.PP
The reason is, the smallest cluster containing label \f(CW\*(C`A\*(C'\fR is \f(CW\*(C`[A]\*(C'\fR in
the first tree but \f(CW\*(C`[A,B]\*(C'\fR in the second tree.
.PP
.Vb 5
\& +\-\-\-A         A\-\-\-B
\& |
\& +
\& |
\& +\-\-\-B
.Ve
.PP
As a second example, the trees \f(CW\*(C`(((B,A),C),D);\*(C'\fR and \f(CW\*(C`((A,(D,B)),C);\*(C'\fR
are also incompatible. Their respective cluster representations are as
follows:
.PP
.Vb 7
\&  [A]                  [A]
\&  [B]                  [B]
\&  [C]                  [C]
\&  [D]                  [D]
\&  [A,B]                [B,D]
\&  [A,B,C]              [A,B,D]
\&  [A,B,C,D]            [A,B,C,D]
.Ve
.PP
The reason is, cluster \f(CW\*(C`[A,B]\*(C'\fR properly intersects cluster
\&\f(CW\*(C`[B,D]\*(C'\fR. There are further incompatibilities between these trees:
\&\f(CW\*(C`[A,B,C]\*(C'\fR properly intersects both \f(CW\*(C`[B,D]\*(C'\fR and \f(CW\*(C`[A,B,D]\*(C'\fR.
.PP
.Vb 9
\&          +\-\-\-B             +\-\-\-\-\-\-\-A
\&          |                 |
\&      +\-\-\-+             +\-\-\-+   +\-\-\-D
\&      |   |             |   |   |
\&  +\-\-\-+   +\-\-\-A         |   +\-\-\-+
\&  |   |                 +       |
\&  +   +\-\-\-\-\-\-\-C         |       +\-\-\-B
\&  |                     |
\&  +\-\-\-\-\-\-\-\-\-\-\-D         +\-\-\-\-\-\-\-\-\-\-\-C
.Ve