X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=forester%2Fjava%2Fsrc%2Forg%2Fforester%2Fphylogeny%2FPhylogenyMethods.java;h=08fe7f01cc5f1029080a107fa6f45e61f63a9189;hb=b80a84de8b4d07847496bc04f51b45bacd146ff3;hp=1dbcfa3ba002b5c6c74870c5962f138aa0213ed2;hpb=89f36e42fb462f8d7b59def3ead995fb16a87b59;p=jalview.git diff --git a/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java b/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java index 1dbcfa3..08fe7f0 100644 --- a/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java +++ b/forester/java/src/org/forester/phylogeny/PhylogenyMethods.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.phylogeny; @@ -44,6 +44,8 @@ import org.forester.io.parsers.PhylogenyParser; import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException; import org.forester.io.parsers.phyloxml.PhyloXmlUtil; import org.forester.io.parsers.util.PhylogenyParserException; +import org.forester.phylogeny.data.Accession; +import org.forester.phylogeny.data.Annotation; import org.forester.phylogeny.data.BranchColor; import org.forester.phylogeny.data.BranchWidth; import org.forester.phylogeny.data.Confidence; @@ -58,76 +60,19 @@ import org.forester.phylogeny.factories.PhylogenyFactory; import org.forester.phylogeny.iterators.PhylogenyNodeIterator; import org.forester.util.BasicDescriptiveStatistics; import org.forester.util.DescriptiveStatistics; -import org.forester.util.FailedConditionCheckException; import org.forester.util.ForesterUtil; public class PhylogenyMethods { - private static PhylogenyMethods _instance = null; - private PhylogenyNode _farthest_1 = null; - private PhylogenyNode _farthest_2 = null; - private PhylogenyMethods() { // Hidden constructor. } - /** - * Calculates the distance between PhylogenyNodes node1 and node2. - * - * - * @param node1 - * @param node2 - * @return distance between node1 and node2 - */ - public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) { - final PhylogenyNode lca = calculateLCA( node1, node2 ); - final PhylogenyNode n1 = node1; - final PhylogenyNode n2 = node2; - return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) ); - } - - public double calculateFurthestDistance( final Phylogeny phylogeny ) { - if ( phylogeny.getNumberOfExternalNodes() < 2 ) { - return 0.0; - } - _farthest_1 = null; - _farthest_2 = null; - PhylogenyNode node_1 = null; - PhylogenyNode node_2 = null; - double farthest_d = -Double.MAX_VALUE; - final PhylogenyMethods methods = PhylogenyMethods.getInstance(); - final List ext_nodes = phylogeny.getRoot().getAllExternalDescendants(); - for( int i = 1; i < ext_nodes.size(); ++i ) { - for( int j = 0; j < i; ++j ) { - final double d = methods.calculateDistance( ext_nodes.get( i ), ext_nodes.get( j ) ); - if ( d < 0.0 ) { - throw new RuntimeException( "distance cannot be negative" ); - } - if ( d > farthest_d ) { - farthest_d = d; - node_1 = ext_nodes.get( i ); - node_2 = ext_nodes.get( j ); - } - } - } - _farthest_1 = node_1; - _farthest_2 = node_2; - return farthest_d; - } - @Override public Object clone() throws CloneNotSupportedException { throw new CloneNotSupportedException(); } - public PhylogenyNode getFarthestNode1() { - return _farthest_1; - } - - public PhylogenyNode getFarthestNode2() { - return _farthest_2; - } - public static DescriptiveStatistics calculatBranchLengthStatistics( final Phylogeny phy ) { final DescriptiveStatistics stats = new BasicDescriptiveStatistics(); for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { @@ -168,6 +113,21 @@ public class PhylogenyMethods { } /** + * Calculates the distance between PhylogenyNodes node1 and node2. + * + * + * @param node1 + * @param node2 + * @return distance between node1 and node2 + */ + public static double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) { + final PhylogenyNode lca = calculateLCA( node1, node2 ); + final PhylogenyNode n1 = node1; + final PhylogenyNode n2 = node2; + return ( PhylogenyMethods.getDistance( n1, lca ) + PhylogenyMethods.getDistance( n2, lca ) ); + } + + /** * Returns the LCA of PhylogenyNodes node1 and node2. * * @@ -308,6 +268,18 @@ public class PhylogenyMethods { return stats; } + public final static void collapseSubtreeStructure( final PhylogenyNode n ) { + final List eds = n.getAllExternalDescendants(); + final List d = new ArrayList(); + for( final PhylogenyNode ed : eds ) { + d.add( calculateDistanceToAncestor( n, ed ) ); + } + for( int i = 0; i < eds.size(); ++i ) { + n.setChildNode( i, eds.get( i ) ); + eds.get( i ).setDistanceToParent( d.get( i ) ); + } + } + public static int countNumberOfOneDescendantNodes( final Phylogeny phy ) { int count = 0; for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { @@ -332,16 +304,15 @@ public class PhylogenyMethods { 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(); + final List ext = phy.getExternalNodes(); + for( final PhylogenyNode n : ext ) { nodes.put( n.getName(), n ); } return nodes; } - public static void deleteExternalNodesNegativeSelection( final Set to_delete, final Phylogeny phy ) { - phy.clearHashIdToNodeMap(); - for( final Integer id : to_delete ) { + public static void deleteExternalNodesNegativeSelection( final Set to_delete, final Phylogeny phy ) { + for( final Long id : to_delete ) { phy.deleteSubtree( phy.getNode( id ), true ); } phy.clearHashIdToNodeMap(); @@ -369,24 +340,6 @@ public class PhylogenyMethods { p.externalNodesHaveChanged(); } - public static void deleteExternalNodesPositiveSelection( final Set species_to_keep, final Phylogeny phy ) { - // final Set to_delete = new HashSet(); - for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) { - final PhylogenyNode n = it.next(); - if ( n.getNodeData().isHasTaxonomy() ) { - if ( !species_to_keep.contains( n.getNodeData().getTaxonomy() ) ) { - //to_delete.add( n.getNodeId() ); - phy.deleteSubtree( n, true ); - } - } - else { - throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" ); - } - } - phy.clearHashIdToNodeMap(); - phy.externalNodesHaveChanged(); - } - public static List deleteExternalNodesPositiveSelection( final String[] node_names_to_keep, final Phylogeny p ) { final PhylogenyNodeIterator it = p.iteratorExternalForward(); @@ -409,11 +362,27 @@ public class PhylogenyMethods { return deleted; } + public static void deleteExternalNodesPositiveSelectionT( final List species_to_keep, final Phylogeny phy ) { + final Set to_delete = new HashSet(); + for( final PhylogenyNodeIterator it = phy.iteratorExternalForward(); it.hasNext(); ) { + final PhylogenyNode n = it.next(); + if ( n.getNodeData().isHasTaxonomy() ) { + if ( !species_to_keep.contains( n.getNodeData().getTaxonomy() ) ) { + to_delete.add( n.getId() ); + } + } + else { + throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" ); + } + } + deleteExternalNodesNegativeSelection( to_delete, phy ); + } + final public static void deleteInternalNodesWithOnlyOneDescendent( final Phylogeny phy ) { final ArrayList to_delete = new ArrayList(); for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) { final PhylogenyNode n = iter.next(); - if ( !n.isExternal() && ( n.getNumberOfDescendants() == 1 ) ) { + if ( ( !n.isExternal() ) && ( n.getNumberOfDescendants() == 1 ) ) { to_delete.add( n ); } } @@ -444,7 +413,7 @@ public class PhylogenyMethods { public static List getAllDescendants( final PhylogenyNode node ) { final List descs = new ArrayList(); - final Set encountered = new HashSet(); + final Set encountered = new HashSet(); if ( !node.isExternal() ) { final List exts = node.getAllExternalDescendants(); for( PhylogenyNode current : exts ) { @@ -550,13 +519,12 @@ public class PhylogenyMethods { return farthest; } - public static PhylogenyMethods getInstance() { - if ( PhylogenyMethods._instance == null ) { - PhylogenyMethods._instance = new PhylogenyMethods(); - } - return PhylogenyMethods._instance; - } - + // public static PhylogenyMethods getInstance() { + // if ( PhylogenyMethods._instance == null ) { + // PhylogenyMethods._instance = new PhylogenyMethods(); + // } + // return PhylogenyMethods._instance; + // } /** * Returns the largest confidence value found on phy. */ @@ -666,36 +634,44 @@ public class PhylogenyMethods { } public static void midpointRoot( final Phylogeny phylogeny ) { - if ( phylogeny.getNumberOfExternalNodes() < 2 ) { - return; - } - final PhylogenyMethods methods = getInstance(); - final double farthest_d = methods.calculateFurthestDistance( phylogeny ); - final PhylogenyNode f1 = methods.getFarthestNode1(); - final PhylogenyNode f2 = methods.getFarthestNode2(); - if ( farthest_d <= 0.0 ) { + if ( ( phylogeny.getNumberOfExternalNodes() < 2 ) || ( calculateMaxDistanceToRoot( phylogeny ) <= 0 ) ) { return; } - double x = farthest_d / 2.0; - PhylogenyNode n = f1; - if ( PhylogenyMethods.getDistance( f1, phylogeny.getRoot() ) < PhylogenyMethods.getDistance( f2, phylogeny - .getRoot() ) ) { - n = f2; - } - while ( ( x > n.getDistanceToParent() ) && !n.isRoot() ) { - x -= ( n.getDistanceToParent() > 0 ? n.getDistanceToParent() : 0 ); - n = n.getParent(); + int counter = 0; + final int total_nodes = phylogeny.getNodeCount(); + while ( true ) { + if ( ++counter > total_nodes ) { + throw new RuntimeException( "this should not have happened: midpoint rooting does not converge" ); + } + PhylogenyNode a = null; + double da = 0; + double db = 0; + for( int i = 0; i < phylogeny.getRoot().getNumberOfDescendants(); ++i ) { + final PhylogenyNode f = getFurthestDescendant( phylogeny.getRoot().getChildNode( i ) ); + final double df = getDistance( f, phylogeny.getRoot() ); + if ( df > 0 ) { + if ( df > da ) { + db = da; + da = df; + a = f; + } + else if ( df > db ) { + db = df; + } + } + } + final double diff = da - db; + if ( diff < 0.000001 ) { + break; + } + double x = da - ( diff / 2.0 ); + while ( ( x > a.getDistanceToParent() ) && !a.isRoot() ) { + x -= ( a.getDistanceToParent() > 0 ? a.getDistanceToParent() : 0 ); + a = a.getParent(); + } + phylogeny.reRoot( a, x ); } - phylogeny.reRoot( n, x ); phylogeny.recalculateNumberOfExternalDescendants( true ); - final PhylogenyNode a = getFurthestDescendant( phylogeny.getRoot().getChildNode1() ); - final PhylogenyNode b = getFurthestDescendant( phylogeny.getRoot().getChildNode2() ); - final double da = getDistance( a, phylogeny.getRoot() ); - final double db = getDistance( b, phylogeny.getRoot() ); - if ( Math.abs( da - db ) > 0.000001 ) { - throw new FailedConditionCheckException( "this should not have happened: midpoint rooting failed: da=" - + da + ", db=" + db + ", diff=" + Math.abs( da - db ) ); - } } public static void normalizeBootstrapValues( final Phylogeny phylogeny, @@ -729,25 +705,6 @@ public class PhylogenyMethods { } /** - * Returns the set of distinct taxonomies of - * all external nodes of node. - * If at least one the external nodes has no taxonomy, - * null is returned. - * - */ - public static Set obtainDistinctTaxonomies( final PhylogenyNode node ) { - final List descs = node.getAllExternalDescendants(); - final Set tax_set = new HashSet(); - for( final PhylogenyNode n : descs ) { - if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) { - return null; - } - tax_set.add( n.getNodeData().getTaxonomy() ); - } - return tax_set; - } - - /** * Returns a map of distinct taxonomies of * all external nodes of node. * If at least one of the external nodes has no taxonomy, @@ -847,7 +804,7 @@ public class PhylogenyMethods { return; } phy.setIdToNodeMap( null ); - int i = PhylogenyNode.getNodeCount(); + long i = PhylogenyNode.getNodeCount(); for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) { it.next().setId( i++ ); } @@ -879,9 +836,19 @@ public class PhylogenyMethods { public static void removeNode( final PhylogenyNode remove_me, final Phylogeny phylogeny ) { if ( remove_me.isRoot() ) { - throw new IllegalArgumentException( "ill advised attempt to remove root node" ); + if ( remove_me.getNumberOfDescendants() == 1 ) { + final PhylogenyNode desc = remove_me.getDescendants().get( 0 ); + desc.setDistanceToParent( addPhylogenyDistances( remove_me.getDistanceToParent(), + desc.getDistanceToParent() ) ); + desc.setParent( null ); + phylogeny.setRoot( desc ); + phylogeny.clearHashIdToNodeMap(); + } + else { + throw new IllegalArgumentException( "attempt to remove a root node with more than one descendants" ); + } } - if ( remove_me.isExternal() ) { + else if ( remove_me.isExternal() ) { phylogeny.deleteSubtree( remove_me, false ); phylogeny.clearHashIdToNodeMap(); phylogeny.externalNodesHaveChanged(); @@ -953,6 +920,10 @@ public class PhylogenyMethods { match = true; } if ( !match && node.getNodeData().isHasSequence() + && match( node.getNodeData().getSequence().getGeneName(), query, case_sensitive, partial ) ) { + match = true; + } + if ( !match && node.getNodeData().isHasSequence() && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) { match = true; } @@ -975,6 +946,38 @@ public class PhylogenyMethods { } } } + // + if ( !match && node.getNodeData().isHasSequence() + && ( node.getNodeData().getSequence().getAnnotations() != null ) ) { + for( final Annotation ann : node.getNodeData().getSequence().getAnnotations() ) { + if ( match( ann.getDesc(), query, case_sensitive, partial ) ) { + match = true; + break; + } + if ( match( ann.getRef(), query, case_sensitive, partial ) ) { + match = true; + break; + } + } + } + if ( !match && node.getNodeData().isHasSequence() + && ( node.getNodeData().getSequence().getCrossReferences() != null ) ) { + for( final Accession x : node.getNodeData().getSequence().getCrossReferences() ) { + if ( match( x.getComment(), query, case_sensitive, partial ) ) { + match = true; + break; + } + if ( match( x.getSource(), query, case_sensitive, partial ) ) { + match = true; + break; + } + if ( match( x.getValue(), query, case_sensitive, partial ) ) { + match = true; + break; + } + } + } + // if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) { Iterator it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator(); I: while ( it.hasNext() ) { @@ -1053,6 +1056,10 @@ public class PhylogenyMethods { match = true; } if ( !match && node.getNodeData().isHasSequence() + && match( node.getNodeData().getSequence().getGeneName(), query, case_sensitive, partial ) ) { + match = true; + } + if ( !match && node.getNodeData().isHasSequence() && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) { match = true; } @@ -1075,6 +1082,38 @@ public class PhylogenyMethods { } } } + // + if ( !match && node.getNodeData().isHasSequence() + && ( node.getNodeData().getSequence().getAnnotations() != null ) ) { + for( final Annotation ann : node.getNodeData().getSequence().getAnnotations() ) { + if ( match( ann.getDesc(), query, case_sensitive, partial ) ) { + match = true; + break; + } + if ( match( ann.getRef(), query, case_sensitive, partial ) ) { + match = true; + break; + } + } + } + if ( !match && node.getNodeData().isHasSequence() + && ( node.getNodeData().getSequence().getCrossReferences() != null ) ) { + for( final Accession x : node.getNodeData().getSequence().getCrossReferences() ) { + if ( match( x.getComment(), query, case_sensitive, partial ) ) { + match = true; + break; + } + if ( match( x.getSource(), query, case_sensitive, partial ) ) { + match = true; + break; + } + if ( match( x.getValue(), query, case_sensitive, partial ) ) { + match = true; + break; + } + } + } + // if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) { Iterator it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator(); I: while ( it.hasNext() ) { @@ -1206,6 +1245,11 @@ public class PhylogenyMethods { return n1.getNodeData().getSequence().getSymbol() .compareTo( n2.getNodeData().getSequence().getSymbol() ); } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) { + return n1.getNodeData().getSequence().getGeneName() + .compareTo( n2.getNodeData().getSequence().getGeneName() ); + } if ( ( n1.getNodeData().getSequence().getAccession() != null ) && ( n2.getNodeData().getSequence().getAccession() != null ) && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) @@ -1235,6 +1279,11 @@ public class PhylogenyMethods { return n1.getNodeData().getSequence().getSymbol() .compareTo( n2.getNodeData().getSequence().getSymbol() ); } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) { + return n1.getNodeData().getSequence().getGeneName() + .compareTo( n2.getNodeData().getSequence().getGeneName() ); + } if ( ( n1.getNodeData().getSequence().getAccession() != null ) && ( n2.getNodeData().getSequence().getAccession() != null ) && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) @@ -1301,6 +1350,11 @@ public class PhylogenyMethods { return n1.getNodeData().getSequence().getSymbol() .compareTo( n2.getNodeData().getSequence().getSymbol() ); } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getGeneName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getGeneName() ) ) ) { + return n1.getNodeData().getSequence().getGeneName() + .compareTo( n2.getNodeData().getSequence().getGeneName() ); + } if ( ( n1.getNodeData().getSequence().getAccession() != null ) && ( n2.getNodeData().getSequence().getAccession() != null ) && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) @@ -1349,13 +1403,16 @@ public class PhylogenyMethods { 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() ); } + if ( ( n.getNodeData().getTaxonomy().getIdentifier() != null ) + && !ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getIdentifier().getValue() ) ) { + ref_ext_taxo.add( n.getNodeData().getTaxonomy().getIdentifier().getValuePlusProvider() ); + } } final ArrayList nodes_to_delete = new ArrayList(); for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) { @@ -1364,7 +1421,9 @@ public class PhylogenyMethods { nodes_to_delete.add( n ); } else if ( !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getScientificName() ) ) - && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { + && !( ref_ext_taxo.contains( n.getNodeData().getTaxonomy().getTaxonomyCode() ) ) + && !( ( n.getNodeData().getTaxonomy().getIdentifier() != null ) && ref_ext_taxo.contains( n + .getNodeData().getTaxonomy().getIdentifier().getValuePlusProvider() ) ) ) { nodes_to_delete.add( n ); } } @@ -1520,6 +1579,24 @@ public class PhylogenyMethods { return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT; } + static double calculateDistanceToAncestor( final PhylogenyNode anc, PhylogenyNode desc ) { + double d = 0; + boolean all_default = true; + while ( anc != desc ) { + if ( desc.getDistanceToParent() != PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT ) { + d += desc.getDistanceToParent(); + if ( all_default ) { + all_default = false; + } + } + desc = desc.getParent(); + } + if ( all_default ) { + return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT; + } + return d; + } + /** * Deep copies the phylogeny originating from this node. */