X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=forester%2Fjava%2Fsrc%2Forg%2Fforester%2Fphylogeny%2FPhylogenyMethods.java;h=3c6b3cd7fb853fee2255dd6f7c172abfe4057aee;hb=be3291132f4c794f3abfd8e8ff7b1bbcefc49198;hp=a4658f093b17303456faca3145eb0b3620cf3ed0;hpb=e174d62534f7fc6f3de133d523a402a87735b27f;p=jalview.git diff --git a/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java b/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java index a4658f0..3c6b3cd 100644 --- a/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java +++ b/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java @@ -32,6 +32,7 @@ import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; +import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; @@ -47,6 +48,7 @@ import org.forester.phylogeny.data.BranchColor; import org.forester.phylogeny.data.BranchWidth; import org.forester.phylogeny.data.Confidence; import org.forester.phylogeny.data.DomainArchitecture; +import org.forester.phylogeny.data.Event; import org.forester.phylogeny.data.Identifier; import org.forester.phylogeny.data.PhylogenyDataUtil; import org.forester.phylogeny.data.Sequence; @@ -61,10 +63,9 @@ import org.forester.util.ForesterUtil; public class PhylogenyMethods { - private static PhylogenyMethods _instance = null; - private final Set _temp_hash_set = new HashSet(); - private PhylogenyNode _farthest_1 = null; - private PhylogenyNode _farthest_2 = null; + private static PhylogenyMethods _instance = null; + private PhylogenyNode _farthest_1 = null; + private PhylogenyNode _farthest_2 = null; private PhylogenyMethods() { // Hidden constructor. @@ -79,7 +80,7 @@ public class PhylogenyMethods { * @return distance between node1 and node2 */ public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) { - final PhylogenyNode lca = obtainLCA( node1, node2 ); + final PhylogenyNode lca = calculateLCA( node1, node2 ); final PhylogenyNode n1 = node1; final PhylogenyNode n2 = node2; return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) ); @@ -114,6 +115,10 @@ public class PhylogenyMethods { return farthest_d; } + final public static Event getEventAtLCA( final PhylogenyNode n1, final PhylogenyNode n2 ) { + return calculateLCA( n1, n2 ).getNodeData().getEvent(); + } + @Override public Object clone() throws CloneNotSupportedException { throw new CloneNotSupportedException(); @@ -127,6 +132,24 @@ public class PhylogenyMethods { return _farthest_2; } + final public static void deleteNonOrthologousExternalNodes( final Phylogeny phy, final PhylogenyNode n ) { + if ( n.isInternal() ) { + throw new IllegalArgumentException( "node is not external" ); + } + final ArrayList to_delete = new ArrayList(); + for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) { + final PhylogenyNode i = it.next(); + if ( !PhylogenyMethods.getEventAtLCA( n, i ).isSpeciation() ) { + to_delete.add( i ); + } + } + for( final PhylogenyNode d : to_delete ) { + phy.deleteSubtree( d, true ); + } + phy.clearHashIdToNodeMap(); + phy.externalNodesHaveChanged(); + } + /** * Returns the LCA of PhylogenyNodes node1 and node2. * @@ -135,22 +158,68 @@ public class PhylogenyMethods { * @param node2 * @return LCA of node1 and node2 */ - public PhylogenyNode obtainLCA( final PhylogenyNode node1, final PhylogenyNode node2 ) { - _temp_hash_set.clear(); - PhylogenyNode n1 = node1; - PhylogenyNode n2 = node2; - _temp_hash_set.add( n1.getId() ); - while ( !n1.isRoot() ) { - n1 = n1.getParent(); - _temp_hash_set.add( n1.getId() ); + public final static PhylogenyNode calculateLCA( PhylogenyNode node1, PhylogenyNode node2 ) { + if ( node1 == node2 ) { + return node1; } - while ( !_temp_hash_set.contains( n2.getId() ) && !n2.isRoot() ) { - n2 = n2.getParent(); + if ( ( node1.getParent() == node2.getParent() ) ) { + return node1.getParent(); } - if ( !_temp_hash_set.contains( n2.getId() ) ) { - throw new IllegalArgumentException( "attempt to get LCA of two nodes which do not share a common root" ); + int depth1 = node1.calculateDepth(); + int depth2 = node2.calculateDepth(); + while ( ( depth1 > -1 ) && ( depth2 > -1 ) ) { + if ( depth1 > depth2 ) { + node1 = node1.getParent(); + depth1--; + } + else if ( depth2 > depth1 ) { + node2 = node2.getParent(); + depth2--; + } + else { + if ( node1 == node2 ) { + return node1; + } + node1 = node1.getParent(); + node2 = node2.getParent(); + depth1--; + depth2--; + } } - return n2; + throw new IllegalArgumentException( "illegal attempt to calculate LCA of two nodes which do not share a common root" ); + } + + public static final void preOrderReId( final Phylogeny phy ) { + if ( phy.isEmpty() ) { + return; + } + phy.setIdToNodeMap( null ); + int i = PhylogenyNode.getNodeCount(); + for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) { + it.next().setId( i++ ); + } + PhylogenyNode.setNodeCount( i ); + } + + /** + * Returns the LCA of PhylogenyNodes node1 and node2. + * Precondition: ids are in pre-order (or level-order). + * + * + * @param node1 + * @param node2 + * @return LCA of node1 and node2 + */ + public final static PhylogenyNode calculateLCAonTreeWithIdsInPreOrder( PhylogenyNode node1, PhylogenyNode node2 ) { + while ( node1 != node2 ) { + if ( node1.getId() > node2.getId() ) { + node1 = node1.getParent(); + } + else { + node2 = node2.getParent(); + } + } + return node1; } /** @@ -167,20 +236,26 @@ public class PhylogenyMethods { * of this Phylogeny, null if this Phylogeny is empty or if n is * internal */ - public List getOrthologousNodes( final Phylogeny phy, final PhylogenyNode node ) { + public final static List getOrthologousNodes( final Phylogeny phy, final PhylogenyNode node ) { final List nodes = new ArrayList(); + PhylogenyMethods.preOrderReId( phy ); final PhylogenyNodeIterator it = phy.iteratorExternalForward(); while ( it.hasNext() ) { final PhylogenyNode temp_node = it.next(); - if ( ( temp_node != node ) && isAreOrthologous( node, temp_node ) ) { + if ( ( temp_node != node ) && !calculateLCAonTreeWithIdsInPreOrder( node, temp_node ).isDuplication() ) { nodes.add( temp_node ); } } return nodes; } - public boolean isAreOrthologous( final PhylogenyNode node1, final PhylogenyNode node2 ) { - return !obtainLCA( node1, node2 ).isDuplication(); + public static final HashMap createNameToExtNodeMap( final Phylogeny phy ) { + final HashMap nodes = new HashMap(); + for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + nodes.put( n.getName(), n ); + } + return nodes; } public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final File file ) throws IOException { @@ -192,6 +267,20 @@ public class PhylogenyMethods { return trees; } + public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final List files ) + throws IOException { + final List tree_list = new ArrayList(); + for( final File file : files ) { + final PhylogenyFactory factory = ParserBasedPhylogenyFactory.getInstance(); + final Phylogeny[] trees = factory.create( file, parser ); + if ( ( trees == null ) || ( trees.length == 0 ) ) { + throw new PhylogenyParserException( "Unable to parse phylogeny from file: " + file ); + } + tree_list.addAll( Arrays.asList( trees ) ); + } + return tree_list.toArray( new Phylogeny[ tree_list.size() ] ); + } + final static public void transferInternalNodeNamesToConfidence( final Phylogeny phy ) { final PhylogenyNodeIterator it = phy.iteratorPostorder(); while ( it.hasNext() ) { @@ -406,16 +495,6 @@ public class PhylogenyMethods { if ( !ForesterUtil.isEmpty( name ) ) { switch ( field ) { case TAXONOMY_CODE: - //temp hack - // if ( name.length() > 5 ) { - // n.setName( "" ); - // if ( !n.getNodeData().isHasTaxonomy() ) { - // n.getNodeData().setTaxonomy( new Taxonomy() ); - // } - // n.getNodeData().getTaxonomy().setScientificName( name ); - // break; - // } - // n.setName( "" ); setTaxonomyCode( n, name ); break; @@ -525,28 +604,6 @@ public class PhylogenyMethods { } } - public static int calculateDepth( final PhylogenyNode node ) { - PhylogenyNode n = node; - int steps = 0; - while ( !n.isRoot() ) { - steps++; - n = n.getParent(); - } - return steps; - } - - public static double calculateDistanceToRoot( final PhylogenyNode node ) { - PhylogenyNode n = node; - double d = 0.0; - while ( !n.isRoot() ) { - if ( n.getDistanceToParent() > 0.0 ) { - d += n.getDistanceToParent(); - } - n = n.getParent(); - } - return d; - } - public static short calculateMaxBranchesToLeaf( final PhylogenyNode node ) { if ( node.isExternal() ) { return 0; @@ -574,7 +631,7 @@ public class PhylogenyMethods { int max = 0; for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) { final PhylogenyNode node = iter.next(); - final int steps = calculateDepth( node ); + final int steps = node.calculateDepth(); if ( steps > max ) { max = steps; } @@ -586,7 +643,7 @@ public class PhylogenyMethods { double max = 0.0; for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) { final PhylogenyNode node = iter.next(); - final double d = calculateDistanceToRoot( node ); + final double d = node.calculateDistanceToRoot(); if ( d > max ) { max = d; } @@ -594,6 +651,17 @@ public class PhylogenyMethods { return max; } + public static int countNumberOfPolytomies( final Phylogeny phy ) { + int count = 0; + for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( !n.isExternal() && ( n.getNumberOfDescendants() > 2 ) ) { + count++; + } + } + return count; + } + public static DescriptiveStatistics calculatNumberOfDescendantsPerNodeStatistics( final Phylogeny phy ) { final DescriptiveStatistics stats = new BasicDescriptiveStatistics(); for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { @@ -736,31 +804,33 @@ public class PhylogenyMethods { } public static void deleteExternalNodesNegativeSelection( final Set to_delete, final Phylogeny phy ) { - phy.hashIDs(); + phy.clearHashIdToNodeMap(); for( final Integer id : to_delete ) { phy.deleteSubtree( phy.getNode( id ), true ); } - phy.hashIDs(); + phy.clearHashIdToNodeMap(); + phy.externalNodesHaveChanged(); } public static void deleteExternalNodesNegativeSelection( final String[] node_names_to_delete, final Phylogeny p ) throws IllegalArgumentException { - for( int i = 0; i < node_names_to_delete.length; ++i ) { - if ( ForesterUtil.isEmpty( node_names_to_delete[ i ] ) ) { + for( final String element : node_names_to_delete ) { + if ( ForesterUtil.isEmpty( element ) ) { continue; } List nodes = null; - nodes = p.getNodes( node_names_to_delete[ i ] ); + nodes = p.getNodes( element ); final Iterator it = nodes.iterator(); while ( it.hasNext() ) { final PhylogenyNode n = it.next(); if ( !n.isExternal() ) { - throw new IllegalArgumentException( "attempt to delete non-external node \"" - + node_names_to_delete[ i ] + "\"" ); + throw new IllegalArgumentException( "attempt to delete non-external node \"" + element + "\"" ); } p.deleteSubtree( n, true ); } } + p.clearHashIdToNodeMap(); + p.externalNodesHaveChanged(); } public static void deleteExternalNodesPositiveSelection( final Set species_to_keep, final Phylogeny phy ) { @@ -777,9 +847,8 @@ public class PhylogenyMethods { throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" ); } } - phy.hashIDs(); + phy.clearHashIdToNodeMap(); phy.externalNodesHaveChanged(); - // deleteExternalNodesNegativeSelection( to_delete, phy ); } public static List deleteExternalNodesPositiveSelection( final String[] node_names_to_keep, @@ -973,12 +1042,12 @@ public class PhylogenyMethods { if ( !node.getNodeData().isHasTaxonomy() ) { return ""; } - if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) { - return node.getNodeData().getTaxonomy().getTaxonomyCode(); - } else if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getScientificName() ) ) { return node.getNodeData().getTaxonomy().getScientificName(); } + if ( !ForesterUtil.isEmpty( node.getNodeData().getTaxonomy().getTaxonomyCode() ) ) { + return node.getNodeData().getTaxonomy().getTaxonomyCode(); + } else { return node.getNodeData().getTaxonomy().getCommonName(); } @@ -1246,8 +1315,9 @@ public class PhylogenyMethods { double blue = 0.0; int n = 0; if ( node.isInternal() ) { - for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) { - final PhylogenyNode child_node = iterator.next(); + //for( final PhylogenyNodeIterator iterator = node.iterateChildNodesForward(); iterator.hasNext(); ) { + for( int i = 0; i < node.getNumberOfDescendants(); ++i ) { + final PhylogenyNode child_node = node.getChildNode( i ); final Color child_color = getBranchColorValue( child_node ); if ( child_color != null ) { ++n; @@ -1270,6 +1340,8 @@ public class PhylogenyMethods { } if ( remove_me.isExternal() ) { phylogeny.deleteSubtree( remove_me, false ); + phylogeny.clearHashIdToNodeMap(); + phylogeny.externalNodesHaveChanged(); } else { final PhylogenyNode parent = remove_me.getParent(); @@ -1281,7 +1353,7 @@ public class PhylogenyMethods { desc.getDistanceToParent() ) ); } remove_me.setParent( null ); - phylogeny.setIdHash( null ); + phylogeny.clearHashIdToNodeMap(); phylogeny.externalNodesHaveChanged(); } } @@ -1289,7 +1361,8 @@ public class PhylogenyMethods { public static List searchData( final String query, final Phylogeny phy, final boolean case_sensitive, - final boolean partial ) { + final boolean partial, + final boolean search_domains ) { final List nodes = new ArrayList(); if ( phy.isEmpty() || ( query == null ) ) { return nodes; @@ -1349,7 +1422,7 @@ public class PhylogenyMethods { partial ) ) { match = true; } - if ( !match && node.getNodeData().isHasSequence() + if ( search_domains && !match && node.getNodeData().isHasSequence() && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) { final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture(); I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) { @@ -1385,7 +1458,8 @@ public class PhylogenyMethods { public static List searchDataLogicalAnd( final String[] queries, final Phylogeny phy, final boolean case_sensitive, - final boolean partial ) { + final boolean partial, + final boolean search_domains ) { final List nodes = new ArrayList(); if ( phy.isEmpty() || ( queries == null ) || ( queries.length < 1 ) ) { return nodes; @@ -1448,7 +1522,7 @@ public class PhylogenyMethods { partial ) ) { match = true; } - if ( !match && node.getNodeData().isHasSequence() + if ( search_domains && !match && node.getNodeData().isHasSequence() && ( node.getNodeData().getSequence().getDomainArchitecture() != null ) ) { final DomainArchitecture da = node.getNodeData().getSequence().getDomainArchitecture(); I: for( int i = 0; i < da.getNumberOfDomains(); ++i ) { @@ -1473,22 +1547,6 @@ public class PhylogenyMethods { break I; } } - // final String[] bcp_ary = node.getNodeData().getBinaryCharacters() - // .getPresentCharactersAsStringArray(); - // I: for( final String bc : bcp_ary ) { - // if ( match( bc, query, case_sensitive, partial ) ) { - // match = true; - // break I; - // } - // } - // final String[] bcg_ary = node.getNodeData().getBinaryCharacters() - // .getGainedCharactersAsStringArray(); - // I: for( final String bc : bcg_ary ) { - // if ( match( bc, query, case_sensitive, partial ) ) { - // match = true; - // break I; - // } - // } } if ( !match ) { all_matched = false; @@ -1584,19 +1642,43 @@ public class PhylogenyMethods { */ public static int taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference, final Phylogeny to_be_stripped ) { final Set ref_ext_taxo = new HashSet(); - final ArrayList nodes_to_delete = new ArrayList(); for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) { - ref_ext_taxo.add( getSpecies( it.next() ) ); + final PhylogenyNode n = it.next(); + if ( !n.getNodeData().isHasTaxonomy() ) { + throw new IllegalArgumentException( "no taxonomic data in node: " + n ); + } + // ref_ext_taxo.add( getSpecies( n ) ); + if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) { + ref_ext_taxo.add( n.getNodeData().getTaxonomy().getScientificName() ); + } + if ( !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) { + ref_ext_taxo.add( n.getNodeData().getTaxonomy().getTaxonomyCode() ); + } } + System.out.println( " ref_ext_tax:" ); + for( final String string : ref_ext_taxo ) { + System.out.println( string ); + } + final ArrayList nodes_to_delete = new ArrayList(); for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) { final PhylogenyNode n = it.next(); - if ( !ref_ext_taxo.contains( getSpecies( n ) ) ) { + if ( !n.getNodeData().isHasTaxonomy() ) { nodes_to_delete.add( n ); } + else if ( !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getScientificName() ) ) + && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { + nodes_to_delete.add( n ); + } + } + System.out.println( " to delete:" ); + for( final PhylogenyNode string : nodes_to_delete ) { + System.out.println( string.getNodeData().getTaxonomy().getTaxonomyCode() ); } for( final PhylogenyNode phylogenyNode : nodes_to_delete ) { to_be_stripped.deleteSubtree( phylogenyNode, true ); } + to_be_stripped.clearHashIdToNodeMap(); + to_be_stripped.externalNodesHaveChanged(); return nodes_to_delete.size(); }