+ /**
+ * Computes the cost of mapping the gene tree gene_tree onto the species
+ * tree species_tree. Before this method can be called, the mapping has to
+ * be calculated with method "infer(boolean)".
+ * <p>
+ * Reference. Zhang, L. (1997) On a Mirkin-Muchnik-Smith Conjecture for
+ * Comparing Molecular Phylogenies. Journal of Computational Biology 4
+ * 177-187.
+ *
+ * @return the mapping cost "L"
+ */
+ public int computeMappingCostL() {
+ _species_tree.levelOrderReID();
+ _mapping_cost = 0;
+ computeMappingCostHelper( _gene_tree.getRoot() );
+ return _mapping_cost;
+ }
+
+ /**
+ * Returns the number of duplications.
+ *
+ * @return number of duplications
+ */
+ public int getDuplicationsSum() {
+ return _duplications_sum;
+ }
+
+ /**
+ * Returns the gene tree.
+ *
+ * @return gene tree
+ */
+ public Phylogeny getGeneTree() {
+ return _gene_tree;
+ }
+
+ /**
+ * Returns the species tree.
+ *
+ * @return species tree
+ */
+ public Phylogeny getSpeciesTree() {
+ return _species_tree;
+ }
+
+ @Override
+ public String toString() {
+ final StringBuffer sb = new StringBuffer();
+ sb.append( getClass() );
+ sb.append( ForesterUtil.LINE_SEPARATOR );
+ sb.append( "Duplications sum : " + getDuplicationsSum() );
+ sb.append( ForesterUtil.LINE_SEPARATOR );
+ sb.append( "mapping cost L : " + computeMappingCostL() );
+ return sb.toString();
+ }
+
+ /**
+ * Traverses the subtree of PhylogenyNode g in postorder, calculating the
+ * mapping function M, and determines which nodes represent speciation
+ * events and which ones duplication events.
+ * <p>
+ * Preconditions: Mapping M for external nodes must have been calculated and
+ * the species tree must be labelled in preorder.
+ * <p>
+ * (Last modified: 01/11/01)
+ *
+ * @param g
+ * starting node of a gene tree - normally the root
+ */
+ void geneTreePostOrderTraversal( final PhylogenyNode g ) {
+ PhylogenyNode a, b;
+ if ( !g.isExternal() ) {
+ geneTreePostOrderTraversal( g.getChildNode( 0 ) );
+ geneTreePostOrderTraversal( g.getChildNode( 1 ) );
+ a = g.getChildNode( 0 ).getLink();
+ b = g.getChildNode( 1 ).getLink();
+ while ( a != b ) {
+ if ( a.getId() > b.getId() ) {
+ a = a.getParent();
+ }
+ else {
+ b = b.getParent();
+ }
+ }
+ g.setLink( a );
+ // Determines whether dup. or spec.
+ Event event = null;
+ if ( ( a == g.getChildNode( 0 ).getLink() ) || ( a == g.getChildNode( 1 ).getLink() ) ) {
+ event = Event.createSingleDuplicationEvent();
+ ++_duplications_sum;
+ }
+ else {
+ event = Event.createSingleSpeciationEvent();
+ }
+ g.getNodeData().setEvent( event );
+ }
+ } // geneTreePostOrderTraversal( PhylogenyNode )
+
+ /**
+ * Calculates the mapping function for the external nodes of the gene tree:
+ * links (sets the field "link" of PhylogenyNode) each external
+ * PhylogenyNode of gene_tree to the external PhylogenyNode of species_tree
+ * which has the same species name.
+ * @throws SDIException
+ */
+ final void linkNodesOfG() throws SDIException {
+ final Map<String, PhylogenyNode> speciestree_ext_nodes = new HashMap<String, PhylogenyNode>();
+ final TaxonomyComparisonBase tax_comp_base = determineTaxonomyComparisonBase();
+ // Put references to all external nodes of the species tree into a map.
+ // Stringyfied taxonomy is the key, node is the value.
+ for( final PhylogenyNodeIterator iter = _species_tree.iteratorExternalForward(); iter.hasNext(); ) {
+ final PhylogenyNode s = iter.next();
+ final String tax_str = SDIutil.taxonomyToString( s, tax_comp_base );
+ if ( speciestree_ext_nodes.containsKey( tax_str ) ) {
+ throw new IllegalArgumentException( "taxonomy [" + s.getNodeData().getTaxonomy()
+ + "] is not unique in species phylogeny" );
+ }
+ speciestree_ext_nodes.put( tax_str, s );
+ }
+ // Retrieve the reference to the node with a matching stringyfied taxonomy.
+ for( final PhylogenyNodeIterator iter = _gene_tree.iteratorExternalForward(); iter.hasNext(); ) {
+ final PhylogenyNode g = iter.next();
+ final String tax_str = SDIutil.taxonomyToString( g, tax_comp_base );
+ final PhylogenyNode s = speciestree_ext_nodes.get( tax_str );
+ if ( s == null ) {
+ throw new IllegalArgumentException( "taxonomy [" + g.getNodeData().getTaxonomy()
+ + "] not present in species tree" );
+ }
+ g.setLink( s );
+ }
+ }
+
+ /**
+ * Updates the mapping function M after the root of the gene tree has been
+ * moved by one branch. It calculates M for the root of the gene tree and
+ * one of its two children.
+ * <p>
+ * To be used ONLY by method "SDIunrooted.fastInfer(Phylogeny,Phylogeny)".
+ * <p>
+ * (Last modfied: 10/02/01)
+ *
+ * @param prev_root_was_dup
+ * true if the previous root was a duplication, false otherwise
+ * @param prev_root_c1
+ * child 1 of the previous root
+ * @param prev_root_c2
+ * child 2 of the previous root
+ * @return number of duplications which have been assigned in gene tree
+ */
+ int updateM( final boolean prev_root_was_dup, final PhylogenyNode prev_root_c1, final PhylogenyNode prev_root_c2 ) {
+ final PhylogenyNode root = getGeneTree().getRoot();
+ if ( ( root.getChildNode1() == prev_root_c1 ) || ( root.getChildNode2() == prev_root_c1 ) ) {
+ calculateMforNode( prev_root_c1 );
+ }
+ else {
+ calculateMforNode( prev_root_c2 );
+ }
+ Event event = null;
+ if ( prev_root_was_dup ) {
+ event = Event.createSingleDuplicationEvent();
+ }
+ else {
+ event = Event.createSingleSpeciationEvent();
+ }
+ root.getNodeData().setEvent( event );
+ calculateMforNode( root );
+ return getDuplicationsSum();
+ } // updateM( boolean, PhylogenyNode, PhylogenyNode )
+
+ // Helper method for updateM( boolean, PhylogenyNode, PhylogenyNode )
+ // Calculates M for PhylogenyNode n, given that M for the two children
+ // of n has been calculated.
+ // (Last modified: 10/02/01)
+ private void calculateMforNode( final PhylogenyNode n ) {
+ if ( !n.isExternal() ) {
+ final boolean was_duplication = n.isDuplication();
+ PhylogenyNode a = n.getChildNode1().getLink();
+ PhylogenyNode b = n.getChildNode2().getLink();
+ while ( a != b ) {
+ if ( a.getId() > b.getId() ) {
+ a = a.getParent();
+ }
+ else {
+ b = b.getParent();
+ }
+ }
+ n.setLink( a );
+ Event event = null;
+ if ( ( a == n.getChildNode1().getLink() ) || ( a == n.getChildNode2().getLink() ) ) {
+ event = Event.createSingleDuplicationEvent();
+ if ( !was_duplication ) {
+ ++_duplications_sum;
+ }
+ }
+ else {
+ event = Event.createSingleSpeciationEvent();
+ if ( was_duplication ) {
+ --_duplications_sum;
+ }
+ }
+ n.getNodeData().setEvent( event );
+ }
+ } // calculateMforNode( PhylogenyNode )
+