inprogress

[jalview.git] / forester / java / src / org / forester / sdi / GSDI.java

diff --git a/forester/java/src/org/forester/sdi/GSDI.java b/forester/java/src/org/forester/sdi/GSDI.java
index f9cc14e..4caeb72 100644 (file)
--- a/forester/java/src/org/forester/sdi/GSDI.java
+++ b/forester/java/src/org/forester/sdi/GSDI.java
@@ -21,7 +21,7 @@
 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 //
 // Contact: phylosoft @ gmail . com
-// WWW: www.phylosoft.org/forester
+// WWW: https://sites.google.com/site/cmzmasek/home/software/forester
 
 package org.forester.sdi;
 
@@ -59,9 +59,11 @@ public final class GSDI implements GSDII {
                  final boolean strip_gene_tree,
                  final boolean strip_species_tree ) throws SDIException {
         _most_parsimonious_duplication_model = most_parsimonious_duplication_model;
+        if ( gene_tree.getRoot().getNumberOfDescendants() == 3 ) {
+            gene_tree.reRoot( gene_tree.getRoot().getChildNode( 2 ) );
+        }
         final NodesLinkingResult nodes_linking_result = linkNodesOfG( gene_tree,
                                                                       species_tree,
-                                                                      null,
                                                                       strip_gene_tree,
                                                                       strip_species_tree );
         _stripped_gene_tree_nodes = nodes_linking_result.getStrippedGeneTreeNodes();
@@ -141,14 +143,20 @@ public final class GSDI implements GSDII {
      * the species tree must be labeled in preorder.
      * <p>
      * @return 
+     * @throws SDIException 
      * 
      */
     final static GSDIsummaryResult geneTreePostOrderTraversal( final Phylogeny gene_tree,
-                                                               final boolean most_parsimonious_duplication_model ) {
+                                                               final boolean most_parsimonious_duplication_model )
+            throws SDIException {
         final GSDIsummaryResult res = new GSDIsummaryResult();
         for( final PhylogenyNodeIterator it = gene_tree.iteratorPostorder(); it.hasNext(); ) {
             final PhylogenyNode g = it.next();
             if ( g.isInternal() ) {
+                if ( g.getNumberOfDescendants() != 2 ) {
+                    throw new SDIException( "gene tree contains internal node with " + g.getNumberOfDescendants()
+                            + " descendents" );
+                }
                 PhylogenyNode s1 = g.getChildNode1().getLink();
                 PhylogenyNode s2 = g.getChildNode2().getLink();
                 while ( s1 != s2 ) {
@@ -166,6 +174,48 @@ public final class GSDI implements GSDII {
         return res;
     }
 
+    final static GSDIsummaryResult geneTreePostOrderTraversal( final Phylogeny gene_tree,
+                                                               final boolean most_parsimonious_duplication_model,
+                                                               final int min_duplications ) throws SDIException {
+        final GSDIsummaryResult res = new GSDIsummaryResult();
+        for( final PhylogenyNodeIterator it = gene_tree.iteratorPostorder(); it.hasNext(); ) {
+            final PhylogenyNode g = it.next();
+            if ( g.isInternal() ) {
+                if ( g.getNumberOfDescendants() != 2 ) {
+                    throw new SDIException( "gene tree contains internal node with " + g.getNumberOfDescendants()
+                            + " descendents" );
+                }
+                PhylogenyNode s1 = g.getChildNode1().getLink();
+                PhylogenyNode s2 = g.getChildNode2().getLink();
+                while ( s1 != s2 ) {
+                    if ( s1.getId() > s2.getId() ) {
+                        s1 = s1.getParent();
+                    }
+                    else {
+                        s2 = s2.getParent();
+                    }
+                }
+                g.setLink( s1 );
+                determineEvent( s1, g, most_parsimonious_duplication_model, res );
+                if ( res.getDuplicationsSum() > min_duplications ) {
+                    return null;
+                }
+            }
+        }
+        return res;
+    }
+
+    final static NodesLinkingResult linkNodesOfG( final Phylogeny gene_tree,
+                                                  final Phylogeny species_tree,
+                                                  final boolean strip_gene_tree,
+                                                  final boolean strip_species_tree ) throws SDIException {
+        final TaxonomyComparisonBase tax_comp_base = SDIutil.determineTaxonomyComparisonBase( gene_tree );
+        if ( tax_comp_base == null ) {
+            throw new RuntimeException( "failed to establish taxonomy linking base (taxonomy linking base is null)" );
+        }
+        return linkNodesOfG( gene_tree, species_tree, tax_comp_base, strip_gene_tree, strip_species_tree );
+    }
+
     /**
      * This allows for linking of internal nodes of the species tree (as opposed
      * to just external nodes, as in the method it overrides.
@@ -178,15 +228,13 @@ public final class GSDI implements GSDII {
                                                   final TaxonomyComparisonBase tax_comp_base,
                                                   final boolean strip_gene_tree,
                                                   final boolean strip_species_tree ) throws SDIException {
+        if ( tax_comp_base == null ) {
+            throw new IllegalArgumentException( "taxonomy linking base is null" );
+        }
         final Map<String, PhylogenyNode> species_to_node_map = new HashMap<String, PhylogenyNode>();
         final List<PhylogenyNode> species_tree_ext_nodes = new ArrayList<PhylogenyNode>();
         final NodesLinkingResult res = new NodesLinkingResult();
-        if ( tax_comp_base == null ) {
-            res.setTaxCompBase( SDIutil.determineTaxonomyComparisonBase( gene_tree ) );
-        }
-        else {
-            res.setTaxCompBase( tax_comp_base );
-        }
+        res.setTaxCompBase( tax_comp_base );
         // Stringyfied taxonomy is the key, node is the value.
         for( final PhylogenyNodeIterator iter = species_tree.iteratorExternalForward(); iter.hasNext(); ) {
             final PhylogenyNode s = iter.next();
@@ -250,7 +298,8 @@ public final class GSDI implements GSDII {
         if ( strip_gene_tree ) {
             stripTree( gene_tree, res.getStrippedGeneTreeNodes() );
             if ( gene_tree.isEmpty() || ( gene_tree.getNumberOfExternalNodes() < 2 ) ) {
-                throw new SDIException( "species could not be mapped between gene tree and species tree" );
+                throw new SDIException( "species could not be mapped between gene tree and species tree (based on "
+                        + res.getTaxCompBase() + ")" );
             }
         }
         if ( strip_species_tree ) {
@@ -288,7 +337,7 @@ public final class GSDI implements GSDII {
                 final Set<PhylogenyNode> set = new HashSet<PhylogenyNode>();
                 for( PhylogenyNode n : g.getChildNode1().getAllExternalDescendants() ) {
                     n = n.getLink();
-                    while ( n.getParent() != s ) {
+                    while ( ( n.getParent() != s ) && ( n.getParent() != null ) ) {
                         n = n.getParent();
                         if ( n.isRoot() ) {
                             break;
@@ -299,7 +348,7 @@ public final class GSDI implements GSDII {
                 boolean multiple = false;
                 for( PhylogenyNode n : g.getChildNode2().getAllExternalDescendants() ) {
                     n = n.getLink();
-                    while ( n.getParent() != s ) {
+                    while ( ( n.getParent() != s ) && ( n.getParent() != null ) ) {
                         n = n.getParent();
                         if ( n.isRoot() ) {
                             break;