X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=forester%2Fjava%2Fsrc%2Forg%2Fforester%2Fphylogeny%2FPhylogenyMethods.java;h=e8498c5f5dc6af177de8e310d0cc2b9ae15ef53d;hb=8dbaf0f253f5ec2721b540d1f4ad06ffb35b66b6;hp=c5d676dfbcc1f90b95845aad8049b925098f5076;hpb=5c10c6e6d65f086e4a021d358314f377bb97342d;p=jalview.git diff --git a/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java b/forester/java/src/org/forester/phylogeny/PhylogenyMethods.java index c5d676d..e8498c5 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; @@ -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; @@ -40,12 +41,14 @@ import java.util.SortedMap; import java.util.TreeMap; 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.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; @@ -55,20 +58,58 @@ 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 final Set _temp_hash_set = new HashSet(); - private PhylogenyNode _farthest_1 = null; - private PhylogenyNode _farthest_2 = null; - private PhylogenyMethods() { // Hidden constructor. } + @Override + public Object clone() throws CloneNotSupportedException { + throw new CloneNotSupportedException(); + } + + public static DescriptiveStatistics calculatBranchLengthStatistics( final Phylogeny phy ) { + final DescriptiveStatistics stats = new BasicDescriptiveStatistics(); + for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( !n.isRoot() && ( n.getDistanceToParent() >= 0.0 ) ) { + stats.addValue( n.getDistanceToParent() ); + } + } + return stats; + } + + public static List calculatConfidenceStatistics( final Phylogeny phy ) { + final List stats = new ArrayList(); + for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( !n.isExternal() && !n.isRoot() ) { + if ( n.getBranchData().isHasConfidences() ) { + for( int i = 0; i < n.getBranchData().getConfidences().size(); ++i ) { + final Confidence c = n.getBranchData().getConfidences().get( i ); + if ( ( i > ( stats.size() - 1 ) ) || ( stats.get( i ) == null ) ) { + stats.add( i, new BasicDescriptiveStatistics() ); + } + if ( !ForesterUtil.isEmpty( c.getType() ) ) { + if ( !ForesterUtil.isEmpty( stats.get( i ).getDescription() ) ) { + if ( !stats.get( i ).getDescription().equalsIgnoreCase( c.getType() ) ) { + throw new IllegalArgumentException( "support values in node [" + n.toString() + + "] appear inconsistently ordered" ); + } + } + stats.get( i ).setDescription( c.getType() ); + } + stats.get( i ).addValue( ( ( c != null ) && ( c.getValue() >= 0 ) ) ? c.getValue() : 0 ); + } + } + } + } + return stats; + } + /** * Calculates the distance between PhylogenyNodes node1 and node2. * @@ -77,727 +118,320 @@ public class PhylogenyMethods { * @param node2 * @return distance between node1 and node2 */ - public double calculateDistance( final PhylogenyNode node1, final PhylogenyNode node2 ) { - final PhylogenyNode lca = obtainLCA( node1, 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 ) ); } - 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 ); + /** + * Returns the LCA of PhylogenyNodes node1 and node2. + * + * + * @param node1 + * @param node2 + * @return LCA of node1 and node2 + */ + public final static PhylogenyNode calculateLCA( PhylogenyNode node1, PhylogenyNode node2 ) { + if ( node1 == null ) { + throw new IllegalArgumentException( "first argument (node) is null" ); + } + if ( node2 == null ) { + throw new IllegalArgumentException( "second argument (node) is null" ); + } + if ( node1 == node2 ) { + return node1; + } + if ( ( node1.getParent() == node2.getParent() ) ) { + return node1.getParent(); + } + 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--; } } - _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; + throw new IllegalArgumentException( "illegal attempt to calculate LCA of two nodes which do not share a common root" ); } /** * 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 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 calculateLCAonTreeWithIdsInPreOrder( PhylogenyNode node1, PhylogenyNode node2 ) { + if ( node1 == null ) { + throw new IllegalArgumentException( "first argument (node) is null" ); } - while ( !_temp_hash_set.contains( n2.getId() ) && !n2.isRoot() ) { - n2 = n2.getParent(); + if ( node2 == null ) { + throw new IllegalArgumentException( "second argument (node) is null" ); } - if ( !_temp_hash_set.contains( n2.getId() ) ) { - throw new IllegalArgumentException( "attempt to get LCA of two nodes which do not share a common root" ); + while ( node1 != node2 ) { + if ( node1.getId() > node2.getId() ) { + node1 = node1.getParent(); + } + else { + node2 = node2.getParent(); + } } - return n2; + return node1; } - /** - * Returns all orthologs of the external PhylogenyNode n of this Phylogeny. - * Orthologs are returned as List of node references. - *

- * PRECONDITION: This tree must be binary and rooted, and speciation - - * duplication need to be assigned for each of its internal Nodes. - *

- * Returns null if this Phylogeny is empty or if n is internal. - * @param n - * external PhylogenyNode whose orthologs are to be returned - * @return Vector of references to all orthologous Nodes of PhylogenyNode n - * of this Phylogeny, null if this Phylogeny is empty or if n is - * internal - */ - public List getOrthologousNodes( final Phylogeny phy, final PhylogenyNode node ) { - final List nodes = new ArrayList(); - final PhylogenyNodeIterator it = phy.iteratorExternalForward(); - while ( it.hasNext() ) { - final PhylogenyNode temp_node = it.next(); - if ( ( temp_node != node ) && isAreOrthologous( node, temp_node ) ) { - nodes.add( temp_node ); + public static short calculateMaxBranchesToLeaf( final PhylogenyNode node ) { + if ( node.isExternal() ) { + return 0; + } + short max = 0; + for( PhylogenyNode d : node.getAllExternalDescendants() ) { + short steps = 0; + while ( d != node ) { + if ( d.isCollapse() ) { + steps = 0; + } + else { + steps++; + } + d = d.getParent(); + } + if ( max < steps ) { + max = steps; } } - return nodes; + return max; } - public boolean isAreOrthologous( final PhylogenyNode node1, final PhylogenyNode node2 ) { - return !obtainLCA( node1, node2 ).isDuplication(); + public static int calculateMaxDepth( final Phylogeny phy ) { + int max = 0; + for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) { + final PhylogenyNode node = iter.next(); + final int steps = node.calculateDepth(); + if ( steps > max ) { + max = steps; + } + } + return max; } - public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final File file ) throws IOException { - 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 ); + public static double calculateMaxDistanceToRoot( final Phylogeny phy ) { + double max = 0.0; + for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) { + final PhylogenyNode node = iter.next(); + final double d = node.calculateDistanceToRoot(); + if ( d > max ) { + max = d; + } } - return trees; + return max; } - final static public void transferInternalNodeNamesToConfidence( final Phylogeny phy ) { - final PhylogenyNodeIterator it = phy.iteratorPostorder(); - while ( it.hasNext() ) { - final PhylogenyNode n = it.next(); - if ( !n.isExternal() && !n.getBranchData().isHasConfidences() ) { - if ( !ForesterUtil.isEmpty( n.getName() ) ) { - double d = -1.0; - try { - d = Double.parseDouble( n.getName() ); - } - catch ( final Exception e ) { - d = -1.0; - } - if ( d >= 0.0 ) { - n.getBranchData().addConfidence( new Confidence( d, "" ) ); - n.setName( "" ); - } - } + public static int calculateNumberOfExternalNodesWithoutTaxonomy( final PhylogenyNode node ) { + final List descs = node.getAllExternalDescendants(); + int x = 0; + for( final PhylogenyNode n : descs ) { + if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) { + x++; } } + return x; } - final static public void transferInternalNamesToBootstrapSupport( final Phylogeny phy ) { - final PhylogenyNodeIterator it = phy.iteratorPostorder(); - while ( it.hasNext() ) { - final PhylogenyNode n = it.next(); - if ( !n.isExternal() && !ForesterUtil.isEmpty( n.getName() ) ) { - double value = -1; - try { - value = Double.parseDouble( n.getName() ); - } - catch ( final NumberFormatException e ) { - throw new IllegalArgumentException( "failed to parse number from [" + n.getName() + "]: " - + e.getLocalizedMessage() ); - } - if ( value >= 0.0 ) { - n.getBranchData().addConfidence( new Confidence( value, "bootstrap" ) ); - n.setName( "" ); - } + public static DescriptiveStatistics calculatNumberOfDescendantsPerNodeStatistics( final Phylogeny phy ) { + final DescriptiveStatistics stats = new BasicDescriptiveStatistics(); + for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( !n.isExternal() ) { + stats.addValue( n.getNumberOfDescendants() ); } } + return stats; } - final static public void sortNodeDescendents( final PhylogenyNode node, final DESCENDANT_SORT_PRIORITY pri ) { - class PhylogenyNodeSortTaxonomyPriority implements Comparator { - - @Override - public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) { - if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) { - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) { - return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase() - .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { - return n1.getNodeData().getTaxonomy().getTaxonomyCode() - .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) { - return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase() - .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() ); - } - } - if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) { - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) { - return n1.getNodeData().getSequence().getName().toLowerCase() - .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) { - return n1.getNodeData().getSequence().getSymbol() - .compareTo( n2.getNodeData().getSequence().getSymbol() ); - } - if ( ( n1.getNodeData().getSequence().getAccession() != null ) - && ( n2.getNodeData().getSequence().getAccession() != null ) - && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) - && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) { - return n1.getNodeData().getSequence().getAccession().getValue() - .compareTo( n2.getNodeData().getSequence().getAccession().getValue() ); - } - } - if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) { - return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() ); - } - return 0; + public static int countNumberOfOneDescendantNodes( final Phylogeny phy ) { + int count = 0; + for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { + final PhylogenyNode n = iter.next(); + if ( !n.isExternal() && ( n.getNumberOfDescendants() == 1 ) ) { + count++; } } - class PhylogenyNodeSortSequencePriority implements Comparator { + return count; + } - @Override - public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) { - if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) { - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) { - return n1.getNodeData().getSequence().getName().toLowerCase() - .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) { - return n1.getNodeData().getSequence().getSymbol() - .compareTo( n2.getNodeData().getSequence().getSymbol() ); - } - if ( ( n1.getNodeData().getSequence().getAccession() != null ) - && ( n2.getNodeData().getSequence().getAccession() != null ) - && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) - && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) { - return n1.getNodeData().getSequence().getAccession().getValue() - .compareTo( n2.getNodeData().getSequence().getAccession().getValue() ); - } - } - if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) { - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) { - return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase() - .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { - return n1.getNodeData().getTaxonomy().getTaxonomyCode() - .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) { - return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase() - .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() ); - } - } - if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) { - return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() ); - } - return 0; + 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++; } } - class PhylogenyNodeSortNodeNamePriority implements Comparator { + return count; + } - @Override - public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) { - if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) { - return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() ); - } - if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) { - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) { - return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase() - .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { - return n1.getNodeData().getTaxonomy().getTaxonomyCode() - .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) { - return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase() - .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() ); - } - } - if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) { - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) { - return n1.getNodeData().getSequence().getName().toLowerCase() - .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() ); - } - if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) ) - && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) { - return n1.getNodeData().getSequence().getSymbol() - .compareTo( n2.getNodeData().getSequence().getSymbol() ); - } - if ( ( n1.getNodeData().getSequence().getAccession() != null ) - && ( n2.getNodeData().getSequence().getAccession() != null ) - && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) - && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) { - return n1.getNodeData().getSequence().getAccession().getValue() - .compareTo( n2.getNodeData().getSequence().getAccession().getValue() ); - } - } - return 0; - } - } - Comparator c; - switch ( pri ) { - case SEQUENCE: - c = new PhylogenyNodeSortSequencePriority(); - break; - case NODE_NAME: - c = new PhylogenyNodeSortNodeNamePriority(); - break; - default: - c = new PhylogenyNodeSortTaxonomyPriority(); - } - final List descs = node.getDescendants(); - Collections.sort( descs, c ); - int i = 0; - for( final PhylogenyNode desc : descs ) { - node.setChildNode( i++, desc ); + public static final HashMap createNameToExtNodeMap( final Phylogeny phy ) { + final HashMap nodes = new HashMap(); + final List ext = phy.getExternalNodes(); + for( final PhylogenyNode n : ext ) { + nodes.put( n.getName(), n ); } + return nodes; } - final static public void transferNodeNameToField( final Phylogeny phy, - final PhylogenyMethods.PhylogenyNodeField field ) { - final PhylogenyNodeIterator it = phy.iteratorPostorder(); - while ( it.hasNext() ) { - final PhylogenyNode n = it.next(); - final String name = n.getName().trim(); - 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; - case TAXONOMY_SCIENTIFIC_NAME: - n.setName( "" ); - if ( !n.getNodeData().isHasTaxonomy() ) { - n.getNodeData().setTaxonomy( new Taxonomy() ); - } - n.getNodeData().getTaxonomy().setScientificName( name ); - break; - case TAXONOMY_COMMON_NAME: - n.setName( "" ); - if ( !n.getNodeData().isHasTaxonomy() ) { - n.getNodeData().setTaxonomy( new Taxonomy() ); - } - n.getNodeData().getTaxonomy().setCommonName( name ); - break; - case SEQUENCE_SYMBOL: - n.setName( "" ); - if ( !n.getNodeData().isHasSequence() ) { - n.getNodeData().setSequence( new Sequence() ); - } - n.getNodeData().getSequence().setSymbol( name ); - break; - case SEQUENCE_NAME: - n.setName( "" ); - if ( !n.getNodeData().isHasSequence() ) { - n.getNodeData().setSequence( new Sequence() ); - } - n.getNodeData().getSequence().setName( name ); - break; - case TAXONOMY_ID_UNIPROT_1: { - if ( !n.getNodeData().isHasTaxonomy() ) { - n.getNodeData().setTaxonomy( new Taxonomy() ); - } - String id = name; - final int i = name.indexOf( '_' ); - if ( i > 0 ) { - id = name.substring( 0, i ); - } - else { - n.setName( "" ); - } - n.getNodeData().getTaxonomy() - .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) ); - break; - } - case TAXONOMY_ID_UNIPROT_2: { - if ( !n.getNodeData().isHasTaxonomy() ) { - n.getNodeData().setTaxonomy( new Taxonomy() ); - } - String id = name; - final int i = name.indexOf( '_' ); - if ( i > 0 ) { - id = name.substring( i + 1, name.length() ); - } - else { - n.setName( "" ); - } - n.getNodeData().getTaxonomy() - .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) ); - break; - } - } - } + public static void deleteExternalNodesNegativeSelection( final Set to_delete, final Phylogeny phy ) { + phy.clearHashIdToNodeMap(); + for( final Integer id : to_delete ) { + phy.deleteSubtree( phy.getNode( id ), true ); } + phy.clearHashIdToNodeMap(); + phy.externalNodesHaveChanged(); } - static double addPhylogenyDistances( final double a, final double b ) { - if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) { - return a + b; - } - else if ( a >= 0.0 ) { - return a; - } - else if ( b >= 0.0 ) { - return b; + public static void deleteExternalNodesNegativeSelection( final String[] node_names_to_delete, final Phylogeny p ) + throws IllegalArgumentException { + for( final String element : node_names_to_delete ) { + if ( ForesterUtil.isEmpty( element ) ) { + continue; + } + List nodes = null; + 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 \"" + element + "\"" ); + } + p.deleteSubtree( n, true ); + } } - return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT; + p.clearHashIdToNodeMap(); + p.externalNodesHaveChanged(); } - // Helper for getUltraParalogousNodes( PhylogenyNode ). - public static boolean areAllChildrenDuplications( final PhylogenyNode n ) { - if ( n.isExternal() ) { - return false; - } - else { - if ( n.isDuplication() ) { - //FIXME test me! - for( final PhylogenyNode desc : n.getDescendants() ) { - if ( !areAllChildrenDuplications( desc ) ) { - return false; - } + 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 ); } - return true; } else { - return false; + throw new IllegalArgumentException( "node " + n.getId() + " has no taxonomic data" ); } } + phy.clearHashIdToNodeMap(); + phy.externalNodesHaveChanged(); } - public static int calculateDepth( final PhylogenyNode node ) { - PhylogenyNode n = node; - int steps = 0; - while ( !n.isRoot() ) { - steps++; - n = n.getParent(); + public static List deleteExternalNodesPositiveSelection( final String[] node_names_to_keep, + final Phylogeny p ) { + final PhylogenyNodeIterator it = p.iteratorExternalForward(); + final String[] to_delete = new String[ p.getNumberOfExternalNodes() ]; + int i = 0; + Arrays.sort( node_names_to_keep ); + while ( it.hasNext() ) { + final String curent_name = it.next().getName(); + if ( Arrays.binarySearch( node_names_to_keep, curent_name ) < 0 ) { + to_delete[ i++ ] = curent_name; + } + } + PhylogenyMethods.deleteExternalNodesNegativeSelection( to_delete, p ); + final List deleted = new ArrayList(); + for( final String n : to_delete ) { + if ( !ForesterUtil.isEmpty( n ) ) { + deleted.add( n ); + } } - return steps; + return deleted; } - 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(); + 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 ) ) { + to_delete.add( n ); } - n = n.getParent(); } - return d; + for( final PhylogenyNode d : to_delete ) { + PhylogenyMethods.removeNode( d, phy ); + } + phy.clearHashIdToNodeMap(); + phy.externalNodesHaveChanged(); } - public static short calculateMaxBranchesToLeaf( final PhylogenyNode node ) { - if ( node.isExternal() ) { - return 0; + final public static void deleteNonOrthologousExternalNodes( final Phylogeny phy, final PhylogenyNode n ) { + if ( n.isInternal() ) { + throw new IllegalArgumentException( "node is not external" ); } - short max = 0; - for( PhylogenyNode d : node.getAllExternalDescendants() ) { - short steps = 0; - while ( d != node ) { - if ( d.isCollapse() ) { - steps = 0; - } - else { - steps++; - } - d = d.getParent(); - } - if ( max < steps ) { - max = steps; + 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 ); } } - return max; + for( final PhylogenyNode d : to_delete ) { + phy.deleteSubtree( d, true ); + } + phy.clearHashIdToNodeMap(); + phy.externalNodesHaveChanged(); } - public static int calculateMaxDepth( final Phylogeny phy ) { - int max = 0; - for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) { - final PhylogenyNode node = iter.next(); - final int steps = calculateDepth( node ); - if ( steps > max ) { - max = steps; + public static List getAllDescendants( final PhylogenyNode node ) { + final List descs = new ArrayList(); + final Set encountered = new HashSet(); + if ( !node.isExternal() ) { + final List exts = node.getAllExternalDescendants(); + for( PhylogenyNode current : exts ) { + descs.add( current ); + while ( current != node ) { + current = current.getParent(); + if ( encountered.contains( current.getId() ) ) { + continue; + } + descs.add( current ); + encountered.add( current.getId() ); + } } } - return max; + return descs; } - public static double calculateMaxDistanceToRoot( final Phylogeny phy ) { - double max = 0.0; - for( final PhylogenyNodeIterator iter = phy.iteratorExternalForward(); iter.hasNext(); ) { - final PhylogenyNode node = iter.next(); - final double d = calculateDistanceToRoot( node ); - if ( d > max ) { - max = d; - } + /** + * + * Convenience method + * + * @param node + * @return + */ + public static Color getBranchColorValue( final PhylogenyNode node ) { + if ( node.getBranchData().getBranchColor() == null ) { + return null; } - return max; - } - - public static DescriptiveStatistics calculatNumberOfDescendantsPerNodeStatistics( final Phylogeny phy ) { - final DescriptiveStatistics stats = new BasicDescriptiveStatistics(); - for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { - final PhylogenyNode n = iter.next(); - if ( !n.isExternal() ) { - stats.addValue( n.getNumberOfDescendants() ); - } - } - return stats; - } - - public static DescriptiveStatistics calculatConfidenceStatistics( final Phylogeny phy ) { - final DescriptiveStatistics stats = new BasicDescriptiveStatistics(); - for( final PhylogenyNodeIterator iter = phy.iteratorPreorder(); iter.hasNext(); ) { - final PhylogenyNode n = iter.next(); - if ( !n.isExternal() ) { - if ( n.getBranchData().isHasConfidences() ) { - stats.addValue( n.getBranchData().getConfidence( 0 ).getValue() ); - } - } - } - return stats; - } - - /** - * 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, - * null is returned. - * - */ - public static SortedMap obtainDistinctTaxonomyCounts( final PhylogenyNode node ) { - final List descs = node.getAllExternalDescendants(); - final SortedMap tax_map = new TreeMap(); - for( final PhylogenyNode n : descs ) { - if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) { - return null; - } - final Taxonomy t = n.getNodeData().getTaxonomy(); - if ( tax_map.containsKey( t ) ) { - tax_map.put( t, tax_map.get( t ) + 1 ); - } - else { - tax_map.put( t, 1 ); - } - } - return tax_map; - } - - public static int calculateNumberOfExternalNodesWithoutTaxonomy( final PhylogenyNode node ) { - final List descs = node.getAllExternalDescendants(); - int x = 0; - for( final PhylogenyNode n : descs ) { - if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) { - x++; - } - } - return x; - } - - /** - * Deep copies the phylogeny originating from this node. - */ - static PhylogenyNode copySubTree( final PhylogenyNode source ) { - if ( source == null ) { - return null; - } - else { - final PhylogenyNode newnode = source.copyNodeData(); - if ( !source.isExternal() ) { - for( int i = 0; i < source.getNumberOfDescendants(); ++i ) { - newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) ); - } - } - return newnode; - } - } - - /** - * Shallow copies the phylogeny originating from this node. - */ - static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) { - if ( source == null ) { - return null; - } - else { - final PhylogenyNode newnode = source.copyNodeDataShallow(); - if ( !source.isExternal() ) { - for( int i = 0; i < source.getNumberOfDescendants(); ++i ) { - newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) ); - } - } - return newnode; - } - } - - public static void deleteExternalNodesNegativeSelection( final Set to_delete, final Phylogeny phy ) { - phy.hashIDs(); - for( final Integer id : to_delete ) { - phy.deleteSubtree( phy.getNode( id ), true ); - } - phy.hashIDs(); - } - - 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 ] ) ) { - continue; - } - List nodes = null; - nodes = p.getNodes( node_names_to_delete[ i ] ); - 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 ] + "\"" ); - } - p.deleteSubtree( n, true ); - } - } - } - - 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.hashIDs(); - phy.externalNodesHaveChanged(); - // deleteExternalNodesNegativeSelection( to_delete, phy ); - } - - public static List deleteExternalNodesPositiveSelection( final String[] node_names_to_keep, - final Phylogeny p ) { - final PhylogenyNodeIterator it = p.iteratorExternalForward(); - final String[] to_delete = new String[ p.getNumberOfExternalNodes() ]; - int i = 0; - Arrays.sort( node_names_to_keep ); - while ( it.hasNext() ) { - final String curent_name = it.next().getName(); - if ( Arrays.binarySearch( node_names_to_keep, curent_name ) < 0 ) { - to_delete[ i++ ] = curent_name; - } - } - PhylogenyMethods.deleteExternalNodesNegativeSelection( to_delete, p ); - final List deleted = new ArrayList(); - for( final String n : to_delete ) { - if ( !ForesterUtil.isEmpty( n ) ) { - deleted.add( n ); - } - } - return deleted; - } - - public static List getAllDescendants( final PhylogenyNode node ) { - final List descs = new ArrayList(); - final Set encountered = new HashSet(); - if ( !node.isExternal() ) { - final List exts = node.getAllExternalDescendants(); - for( PhylogenyNode current : exts ) { - descs.add( current ); - while ( current != node ) { - current = current.getParent(); - if ( encountered.contains( current.getId() ) ) { - continue; - } - descs.add( current ); - encountered.add( current.getId() ); - } - } - } - return descs; - } - - /** - * - * Convenience method - * - * @param node - * @return - */ - public static Color getBranchColorValue( final PhylogenyNode node ) { - if ( node.getBranchData().getBranchColor() == null ) { - return null; - } - return node.getBranchData().getBranchColor().getValue(); + return node.getBranchData().getBranchColor().getValue(); } /** @@ -835,24 +469,8 @@ public class PhylogenyMethods { return values; } - /** - * Calculates the distance between PhylogenyNodes n1 and n2. - * PRECONDITION: n1 is a descendant of n2. - * - * @param n1 - * a descendant of n2 - * @param n2 - * @return distance between n1 and n2 - */ - private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) { - double d = 0.0; - while ( n1 != n2 ) { - if ( n1.getDistanceToParent() > 0.0 ) { - d += n1.getDistanceToParent(); - } - n1 = n1.getParent(); - } - return d; + final public static Event getEventAtLCA( final PhylogenyNode n1, final PhylogenyNode n2 ) { + return calculateLCA( n1, n2 ).getNodeData().getEvent(); } /** @@ -890,13 +508,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. */ @@ -935,79 +552,18 @@ 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(); } } /** - * Returns all Nodes which are connected to external PhylogenyNode n of this - * Phylogeny by a path containing only speciation events. We call these - * "super orthologs". Nodes are returned as Vector of references to Nodes. - *

- * PRECONDITION: This tree must be binary and rooted, and speciation - - * duplication need to be assigned for each of its internal Nodes. - *

- * Returns null if this Phylogeny is empty or if n is internal. - * @param n - * external PhylogenyNode whose strictly speciation related Nodes - * are to be returned - * @return Vector of references to all strictly speciation related Nodes of - * PhylogenyNode n of this Phylogeny, null if this Phylogeny is - * empty or if n is internal - */ - public static List getSuperOrthologousNodes( final PhylogenyNode n ) { - // FIXME - PhylogenyNode node = n, deepest = null; - final List v = new ArrayList(); - if ( !node.isExternal() ) { - return null; - } - while ( !node.isRoot() && !node.getParent().isDuplication() ) { - node = node.getParent(); - } - deepest = node; - deepest.setIndicatorsToZero(); - do { - if ( !node.isExternal() ) { - if ( node.getIndicator() == 0 ) { - node.setIndicator( ( byte ) 1 ); - if ( !node.isDuplication() ) { - node = node.getChildNode1(); - } - } - if ( node.getIndicator() == 1 ) { - node.setIndicator( ( byte ) 2 ); - if ( !node.isDuplication() ) { - node = node.getChildNode2(); - } - } - if ( ( node != deepest ) && ( node.getIndicator() == 2 ) ) { - node = node.getParent(); - } - } - else { - if ( node != n ) { - v.add( node ); - } - if ( node != deepest ) { - node = node.getParent(); - } - else { - node.setIndicator( ( byte ) 2 ); - } - } - } while ( ( node != deepest ) || ( deepest.getIndicator() != 2 ) ); - return v; - } - - /** * Convenience method for display purposes. * Not intended for algorithms. */ @@ -1018,73 +574,23 @@ public class PhylogenyMethods { return node.getNodeData().getTaxonomy().getIdentifier().getValue(); } - /** - * Returns all Nodes which are connected to external PhylogenyNode n of this - * Phylogeny by a path containing, and leading to, only duplication events. - * We call these "ultra paralogs". Nodes are returned as Vector of - * references to Nodes. - *

- * PRECONDITION: This tree must be binary and rooted, and speciation - - * duplication need to be assigned for each of its internal Nodes. - *

- * Returns null if this Phylogeny is empty or if n is internal. - *

- * (Last modified: 10/06/01) - * - * @param n - * external PhylogenyNode whose ultra paralogs are to be returned - * @return Vector of references to all ultra paralogs of PhylogenyNode n of - * this Phylogeny, null if this Phylogeny is empty or if n is - * internal - */ - public static List getUltraParalogousNodes( final PhylogenyNode n ) { - // FIXME test me - PhylogenyNode node = n; - if ( !node.isExternal() ) { - return null; - } - while ( !node.isRoot() && node.getParent().isDuplication() && areAllChildrenDuplications( node.getParent() ) ) { - node = node.getParent(); + public final static boolean isAllDecendentsAreDuplications( final PhylogenyNode n ) { + if ( n.isExternal() ) { + return true; } - final List nodes = node.getAllExternalDescendants(); - nodes.remove( n ); - return nodes; - } - - public static String inferCommonPartOfScientificNameOfDescendants( final PhylogenyNode node ) { - final List descs = node.getDescendants(); - String sn = null; - for( final PhylogenyNode n : descs ) { - if ( !n.getNodeData().isHasTaxonomy() - || ForesterUtil.isEmpty( n.getNodeData().getTaxonomy().getScientificName() ) ) { - return null; - } - else if ( sn == null ) { - sn = n.getNodeData().getTaxonomy().getScientificName().trim(); - } - else { - String sn_current = n.getNodeData().getTaxonomy().getScientificName().trim(); - if ( !sn.equals( sn_current ) ) { - boolean overlap = false; - while ( ( sn.indexOf( ' ' ) >= 0 ) || ( sn_current.indexOf( ' ' ) >= 0 ) ) { - if ( ForesterUtil.countChars( sn, ' ' ) > ForesterUtil.countChars( sn_current, ' ' ) ) { - sn = sn.substring( 0, sn.lastIndexOf( ' ' ) ).trim(); - } - else { - sn_current = sn_current.substring( 0, sn_current.lastIndexOf( ' ' ) ).trim(); - } - if ( sn.equals( sn_current ) ) { - overlap = true; - break; - } - } - if ( !overlap ) { - return null; + else { + if ( n.isDuplication() ) { + for( final PhylogenyNode desc : n.getDescendants() ) { + if ( !isAllDecendentsAreDuplications( desc ) ) { + return false; } } + return true; + } + else { + return false; } } - return sn; } public static boolean isHasExternalDescendant( final PhylogenyNode node ) { @@ -1116,58 +622,45 @@ public class PhylogenyMethods { } } - private static boolean match( final String s, - final String query, - final boolean case_sensitive, - final boolean partial ) { - if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) { - return false; - } - String my_s = s.trim(); - String my_query = query.trim(); - if ( !case_sensitive ) { - my_s = my_s.toLowerCase(); - my_query = my_query.toLowerCase(); - } - if ( partial ) { - return my_s.indexOf( my_query ) >= 0; - } - else { - return my_s.equals( my_query ); - } - } - public static void midpointRoot( final Phylogeny phylogeny ) { - if ( phylogeny.getNumberOfExternalNodes() < 2 ) { + if ( ( phylogeny.getNumberOfExternalNodes() < 2 ) || ( calculateMaxDistanceToRoot( phylogeny ) <= 0 ) ) { 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 ) { - 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, @@ -1200,6 +693,74 @@ public class PhylogenyMethods { return nodes; } + /** + * Returns a map of distinct taxonomies of + * all external nodes of node. + * If at least one of the external nodes has no taxonomy, + * null is returned. + * + */ + public static SortedMap obtainDistinctTaxonomyCounts( final PhylogenyNode node ) { + final List descs = node.getAllExternalDescendants(); + final SortedMap tax_map = new TreeMap(); + for( final PhylogenyNode n : descs ) { + if ( !n.getNodeData().isHasTaxonomy() || n.getNodeData().getTaxonomy().isEmpty() ) { + return null; + } + final Taxonomy t = n.getNodeData().getTaxonomy(); + if ( tax_map.containsKey( t ) ) { + tax_map.put( t, tax_map.get( t ) + 1 ); + } + else { + tax_map.put( t, 1 ); + } + } + return tax_map; + } + + /** + * Arranges the order of childern for each node of this Phylogeny in such a + * way that either the branch with more children is on top (right) or on + * bottom (left), dependent on the value of boolean order. + * + * @param order + * decides in which direction to order + * @param pri + */ + public static void orderAppearance( final PhylogenyNode n, + final boolean order, + final boolean order_ext_alphabetically, + final DESCENDANT_SORT_PRIORITY pri ) { + if ( n.isExternal() ) { + return; + } + else { + PhylogenyNode temp = null; + if ( ( n.getNumberOfDescendants() == 2 ) + && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() ) + && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) { + temp = n.getChildNode1(); + n.setChild1( n.getChildNode2() ); + n.setChild2( temp ); + } + else if ( order_ext_alphabetically ) { + boolean all_ext = true; + for( final PhylogenyNode i : n.getDescendants() ) { + if ( !i.isExternal() ) { + all_ext = false; + break; + } + } + if ( all_ext ) { + PhylogenyMethods.sortNodeDescendents( n, pri ); + } + } + for( int i = 0; i < n.getNumberOfDescendants(); ++i ) { + orderAppearance( n.getChildNode( i ), order, order_ext_alphabetically, pri ); + } + } + } + public static void postorderBranchColorAveragingExternalNodeBased( final Phylogeny p ) { for( final PhylogenyNodeIterator iter = p.iteratorPostorder(); iter.hasNext(); ) { final PhylogenyNode node = iter.next(); @@ -1208,8 +769,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; @@ -1226,12 +788,59 @@ public class PhylogenyMethods { } } + public static final void preOrderReId( final Phylogeny phy ) { + if ( phy.isEmpty() ) { + return; + } + phy.setIdToNodeMap( null ); + long i = PhylogenyNode.getNodeCount(); + for( final PhylogenyNodeIterator it = phy.iteratorPreorder(); it.hasNext(); ) { + it.next().setId( i++ ); + } + PhylogenyNode.setNodeCount( i ); + } + + public final static Phylogeny[] readPhylogenies( final PhylogenyParser parser, final File file ) throws IOException { + 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 ); + } + 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() ] ); + } + 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(); } else { final PhylogenyNode parent = remove_me.getParent(); @@ -1243,7 +852,7 @@ public class PhylogenyMethods { desc.getDistanceToParent() ) ); } remove_me.setParent( null ); - phylogeny.setIdHash( null ); + phylogeny.clearHashIdToNodeMap(); phylogeny.externalNodesHaveChanged(); } } @@ -1251,7 +860,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; @@ -1311,7 +921,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 ) { @@ -1347,7 +957,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; @@ -1391,218 +1002,566 @@ public class PhylogenyMethods { match = true; break I; } - } - } - if ( !match && node.getNodeData().isHasSequence() - && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) { - match = true; - } - if ( !match && node.getNodeData().isHasSequence() - && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) { - match = true; - } - if ( !match - && node.getNodeData().isHasSequence() - && ( node.getNodeData().getSequence().getAccession() != null ) - && match( node.getNodeData().getSequence().getAccession().getValue(), - query, - case_sensitive, - partial ) ) { - match = true; - } - if ( !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 ) { - if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) { - match = true; - break I; + } + } + if ( !match && node.getNodeData().isHasSequence() + && match( node.getNodeData().getSequence().getName(), query, case_sensitive, partial ) ) { + match = true; + } + if ( !match && node.getNodeData().isHasSequence() + && match( node.getNodeData().getSequence().getSymbol(), query, case_sensitive, partial ) ) { + match = true; + } + if ( !match + && node.getNodeData().isHasSequence() + && ( node.getNodeData().getSequence().getAccession() != null ) + && match( node.getNodeData().getSequence().getAccession().getValue(), + query, + case_sensitive, + partial ) ) { + match = true; + } + 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 ) { + if ( match( da.getDomain( i ).getName(), query, case_sensitive, partial ) ) { + match = true; + break I; + } + } + } + if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) { + Iterator it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator(); + I: while ( it.hasNext() ) { + if ( match( it.next(), query, case_sensitive, partial ) ) { + match = true; + break I; + } + } + it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator(); + I: while ( it.hasNext() ) { + if ( match( it.next(), query, case_sensitive, partial ) ) { + match = true; + break I; + } + } + } + if ( !match ) { + all_matched = false; + break; + } + } + if ( all_matched ) { + nodes.add( node ); + } + } + return nodes; + } + + /** + * Convenience method. + * Sets value for the first confidence value (created if not present, values overwritten otherwise). + */ + public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) { + setConfidence( node, bootstrap_confidence_value, "bootstrap" ); + } + + public static void setBranchColorValue( final PhylogenyNode node, final Color color ) { + if ( node.getBranchData().getBranchColor() == null ) { + node.getBranchData().setBranchColor( new BranchColor() ); + } + node.getBranchData().getBranchColor().setValue( color ); + } + + /** + * Convenience method + */ + public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) { + node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) ); + } + + /** + * Convenience method. + * Sets value for the first confidence value (created if not present, values overwritten otherwise). + */ + public static void setConfidence( final PhylogenyNode node, final double confidence_value ) { + setConfidence( node, confidence_value, "" ); + } + + /** + * Convenience method. + * Sets value for the first confidence value (created if not present, values overwritten otherwise). + */ + public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) { + Confidence c = null; + if ( node.getBranchData().getNumberOfConfidences() > 0 ) { + c = node.getBranchData().getConfidence( 0 ); + } + else { + c = new Confidence(); + node.getBranchData().addConfidence( c ); + } + c.setType( type ); + c.setValue( confidence_value ); + } + + public static void setScientificName( final PhylogenyNode node, final String scientific_name ) { + if ( !node.getNodeData().isHasTaxonomy() ) { + node.getNodeData().setTaxonomy( new Taxonomy() ); + } + node.getNodeData().getTaxonomy().setScientificName( scientific_name ); + } + + /** + * Convenience method to set the taxonomy code of a phylogeny node. + * + * + * @param node + * @param taxonomy_code + * @throws PhyloXmlDataFormatException + */ + public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code ) + throws PhyloXmlDataFormatException { + if ( !node.getNodeData().isHasTaxonomy() ) { + node.getNodeData().setTaxonomy( new Taxonomy() ); + } + node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code ); + } + + final static public void sortNodeDescendents( final PhylogenyNode node, final DESCENDANT_SORT_PRIORITY pri ) { + class PhylogenyNodeSortTaxonomyPriority implements Comparator { + + @Override + public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) { + if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) { + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) { + return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase() + .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { + return n1.getNodeData().getTaxonomy().getTaxonomyCode() + .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) { + return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase() + .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() ); + } + } + if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) { + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) { + return n1.getNodeData().getSequence().getName().toLowerCase() + .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) { + return n1.getNodeData().getSequence().getSymbol() + .compareTo( n2.getNodeData().getSequence().getSymbol() ); + } + if ( ( n1.getNodeData().getSequence().getAccession() != null ) + && ( n2.getNodeData().getSequence().getAccession() != null ) + && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) + && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) { + return n1.getNodeData().getSequence().getAccession().getValue() + .compareTo( n2.getNodeData().getSequence().getAccession().getValue() ); + } + } + if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) { + return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() ); + } + return 0; + } + } + class PhylogenyNodeSortSequencePriority implements Comparator { + + @Override + public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) { + if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) { + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) { + return n1.getNodeData().getSequence().getName().toLowerCase() + .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) { + return n1.getNodeData().getSequence().getSymbol() + .compareTo( n2.getNodeData().getSequence().getSymbol() ); + } + if ( ( n1.getNodeData().getSequence().getAccession() != null ) + && ( n2.getNodeData().getSequence().getAccession() != null ) + && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) + && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) { + return n1.getNodeData().getSequence().getAccession().getValue() + .compareTo( n2.getNodeData().getSequence().getAccession().getValue() ); + } + } + if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) { + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) { + return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase() + .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { + return n1.getNodeData().getTaxonomy().getTaxonomyCode() + .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) { + return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase() + .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() ); + } + } + if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) { + return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() ); + } + return 0; + } + } + class PhylogenyNodeSortNodeNamePriority implements Comparator { + + @Override + public int compare( final PhylogenyNode n1, final PhylogenyNode n2 ) { + if ( ( !ForesterUtil.isEmpty( n1.getName() ) ) && ( !ForesterUtil.isEmpty( n2.getName() ) ) ) { + return n1.getName().toLowerCase().compareTo( n2.getName().toLowerCase() ); + } + if ( n1.getNodeData().isHasTaxonomy() && n2.getNodeData().isHasTaxonomy() ) { + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getScientificName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getScientificName() ) ) ) { + return n1.getNodeData().getTaxonomy().getScientificName().toLowerCase() + .compareTo( n2.getNodeData().getTaxonomy().getScientificName().toLowerCase() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getTaxonomyCode() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getTaxonomyCode() ) ) ) { + return n1.getNodeData().getTaxonomy().getTaxonomyCode() + .compareTo( n2.getNodeData().getTaxonomy().getTaxonomyCode() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getTaxonomy().getCommonName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getTaxonomy().getCommonName() ) ) ) { + return n1.getNodeData().getTaxonomy().getCommonName().toLowerCase() + .compareTo( n2.getNodeData().getTaxonomy().getCommonName().toLowerCase() ); + } + } + if ( n1.getNodeData().isHasSequence() && n2.getNodeData().isHasSequence() ) { + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getName() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getName() ) ) ) { + return n1.getNodeData().getSequence().getName().toLowerCase() + .compareTo( n2.getNodeData().getSequence().getName().toLowerCase() ); + } + if ( ( !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getSymbol() ) ) + && ( !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getSymbol() ) ) ) { + return n1.getNodeData().getSequence().getSymbol() + .compareTo( n2.getNodeData().getSequence().getSymbol() ); + } + if ( ( n1.getNodeData().getSequence().getAccession() != null ) + && ( n2.getNodeData().getSequence().getAccession() != null ) + && !ForesterUtil.isEmpty( n1.getNodeData().getSequence().getAccession().getValue() ) + && !ForesterUtil.isEmpty( n2.getNodeData().getSequence().getAccession().getValue() ) ) { + return n1.getNodeData().getSequence().getAccession().getValue() + .compareTo( n2.getNodeData().getSequence().getAccession().getValue() ); + } + } + return 0; + } + } + Comparator c; + switch ( pri ) { + case SEQUENCE: + c = new PhylogenyNodeSortSequencePriority(); + break; + case NODE_NAME: + c = new PhylogenyNodeSortNodeNamePriority(); + break; + default: + c = new PhylogenyNodeSortTaxonomyPriority(); + } + final List descs = node.getDescendants(); + Collections.sort( descs, c ); + int i = 0; + for( final PhylogenyNode desc : descs ) { + node.setChildNode( i++, desc ); + } + } + + /** + * Removes from Phylogeny to_be_stripped all external Nodes which are + * associated with a species NOT found in Phylogeny reference. + * + * @param reference + * a reference Phylogeny + * @param to_be_stripped + * Phylogeny to be stripped + * @return nodes removed from to_be_stripped + */ + public static List taxonomyBasedDeletionOfExternalNodes( final Phylogeny reference, + final Phylogeny to_be_stripped ) { + final Set ref_ext_taxo = new HashSet(); + for( final PhylogenyNodeIterator it = reference.iteratorExternalForward(); it.hasNext(); ) { + final PhylogenyNode n = it.next(); + if ( !n.getNodeData().isHasTaxonomy() ) { + throw new IllegalArgumentException( "no taxonomic data in node: " + 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(); ) { + final PhylogenyNode n = it.next(); + 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() ) ) + && !( ( n.getNodeData().getTaxonomy().getIdentifier() != null ) && ref_ext_taxo.contains( n + .getNodeData().getTaxonomy().getIdentifier().getValuePlusProvider() ) ) ) { + nodes_to_delete.add( n ); + } + } + for( final PhylogenyNode n : nodes_to_delete ) { + to_be_stripped.deleteSubtree( n, true ); + } + to_be_stripped.clearHashIdToNodeMap(); + to_be_stripped.externalNodesHaveChanged(); + return nodes_to_delete; + } + + final static public void transferInternalNamesToBootstrapSupport( final Phylogeny phy ) { + final PhylogenyNodeIterator it = phy.iteratorPostorder(); + while ( it.hasNext() ) { + final PhylogenyNode n = it.next(); + if ( !n.isExternal() && !ForesterUtil.isEmpty( n.getName() ) ) { + double value = -1; + try { + value = Double.parseDouble( n.getName() ); + } + catch ( final NumberFormatException e ) { + throw new IllegalArgumentException( "failed to parse number from [" + n.getName() + "]: " + + e.getLocalizedMessage() ); + } + if ( value >= 0.0 ) { + n.getBranchData().addConfidence( new Confidence( value, "bootstrap" ) ); + n.setName( "" ); + } + } + } + } + + final static public void transferInternalNodeNamesToConfidence( final Phylogeny phy ) { + final PhylogenyNodeIterator it = phy.iteratorPostorder(); + while ( it.hasNext() ) { + final PhylogenyNode n = it.next(); + if ( !n.isExternal() && !n.getBranchData().isHasConfidences() ) { + if ( !ForesterUtil.isEmpty( n.getName() ) ) { + double d = -1.0; + try { + d = Double.parseDouble( n.getName() ); + } + catch ( final Exception e ) { + d = -1.0; + } + if ( d >= 0.0 ) { + n.getBranchData().addConfidence( new Confidence( d, "" ) ); + n.setName( "" ); + } + } + } + } + } + + final static public void transferNodeNameToField( final Phylogeny phy, + final PhylogenyNodeField field, + final boolean external_only ) throws PhyloXmlDataFormatException { + final PhylogenyNodeIterator it = phy.iteratorPostorder(); + while ( it.hasNext() ) { + final PhylogenyNode n = it.next(); + if ( external_only && n.isInternal() ) { + continue; + } + final String name = n.getName().trim(); + if ( !ForesterUtil.isEmpty( name ) ) { + switch ( field ) { + case TAXONOMY_CODE: + n.setName( "" ); + setTaxonomyCode( n, name ); + break; + case TAXONOMY_SCIENTIFIC_NAME: + n.setName( "" ); + if ( !n.getNodeData().isHasTaxonomy() ) { + n.getNodeData().setTaxonomy( new Taxonomy() ); + } + n.getNodeData().getTaxonomy().setScientificName( name ); + break; + case TAXONOMY_COMMON_NAME: + n.setName( "" ); + if ( !n.getNodeData().isHasTaxonomy() ) { + n.getNodeData().setTaxonomy( new Taxonomy() ); + } + n.getNodeData().getTaxonomy().setCommonName( name ); + break; + case SEQUENCE_SYMBOL: + n.setName( "" ); + if ( !n.getNodeData().isHasSequence() ) { + n.getNodeData().setSequence( new Sequence() ); + } + n.getNodeData().getSequence().setSymbol( name ); + break; + case SEQUENCE_NAME: + n.setName( "" ); + if ( !n.getNodeData().isHasSequence() ) { + n.getNodeData().setSequence( new Sequence() ); + } + n.getNodeData().getSequence().setName( name ); + break; + case TAXONOMY_ID_UNIPROT_1: { + if ( !n.getNodeData().isHasTaxonomy() ) { + n.getNodeData().setTaxonomy( new Taxonomy() ); + } + String id = name; + final int i = name.indexOf( '_' ); + if ( i > 0 ) { + id = name.substring( 0, i ); + } + else { + n.setName( "" ); } + n.getNodeData().getTaxonomy() + .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) ); + break; } - } - if ( !match && ( node.getNodeData().getBinaryCharacters() != null ) ) { - Iterator it = node.getNodeData().getBinaryCharacters().getPresentCharacters().iterator(); - I: while ( it.hasNext() ) { - if ( match( it.next(), query, case_sensitive, partial ) ) { - match = true; - break I; + case TAXONOMY_ID_UNIPROT_2: { + if ( !n.getNodeData().isHasTaxonomy() ) { + n.getNodeData().setTaxonomy( new Taxonomy() ); + } + String id = name; + final int i = name.indexOf( '_' ); + if ( i > 0 ) { + id = name.substring( i + 1, name.length() ); + } + else { + n.setName( "" ); } + n.getNodeData().getTaxonomy() + .setIdentifier( new Identifier( id, PhyloXmlUtil.UNIPROT_TAX_PROVIDER ) ); + break; } - it = node.getNodeData().getBinaryCharacters().getGainedCharacters().iterator(); - I: while ( it.hasNext() ) { - if ( match( it.next(), query, case_sensitive, partial ) ) { - match = true; - break I; + case TAXONOMY_ID: { + if ( !n.getNodeData().isHasTaxonomy() ) { + n.getNodeData().setTaxonomy( new Taxonomy() ); } + n.getNodeData().getTaxonomy().setIdentifier( new Identifier( name ) ); + break; } - // 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; - break; } } - if ( all_matched ) { - nodes.add( node ); - } } - return nodes; - } - - /** - * Convenience method. - * Sets value for the first confidence value (created if not present, values overwritten otherwise). - */ - public static void setBootstrapConfidence( final PhylogenyNode node, final double bootstrap_confidence_value ) { - setConfidence( node, bootstrap_confidence_value, "bootstrap" ); } - public static void setBranchColorValue( final PhylogenyNode node, final Color color ) { - if ( node.getBranchData().getBranchColor() == null ) { - node.getBranchData().setBranchColor( new BranchColor() ); + static double addPhylogenyDistances( final double a, final double b ) { + if ( ( a >= 0.0 ) && ( b >= 0.0 ) ) { + return a + b; } - node.getBranchData().getBranchColor().setValue( color ); - } - - /** - * Convenience method - */ - public static void setBranchWidthValue( final PhylogenyNode node, final double branch_width_value ) { - node.getBranchData().setBranchWidth( new BranchWidth( branch_width_value ) ); - } - - /** - * Convenience method. - * Sets value for the first confidence value (created if not present, values overwritten otherwise). - */ - public static void setConfidence( final PhylogenyNode node, final double confidence_value ) { - setConfidence( node, confidence_value, "" ); + else if ( a >= 0.0 ) { + return a; + } + else if ( b >= 0.0 ) { + return b; + } + return PhylogenyDataUtil.BRANCH_LENGTH_DEFAULT; } /** - * Convenience method. - * Sets value for the first confidence value (created if not present, values overwritten otherwise). + * Deep copies the phylogeny originating from this node. */ - public static void setConfidence( final PhylogenyNode node, final double confidence_value, final String type ) { - Confidence c = null; - if ( node.getBranchData().getNumberOfConfidences() > 0 ) { - c = node.getBranchData().getConfidence( 0 ); + static PhylogenyNode copySubTree( final PhylogenyNode source ) { + if ( source == null ) { + return null; } else { - c = new Confidence(); - node.getBranchData().addConfidence( c ); - } - c.setType( type ); - c.setValue( confidence_value ); - } - - public static void setScientificName( final PhylogenyNode node, final String scientific_name ) { - if ( !node.getNodeData().isHasTaxonomy() ) { - node.getNodeData().setTaxonomy( new Taxonomy() ); + final PhylogenyNode newnode = source.copyNodeData(); + if ( !source.isExternal() ) { + for( int i = 0; i < source.getNumberOfDescendants(); ++i ) { + newnode.setChildNode( i, PhylogenyMethods.copySubTree( source.getChildNode( i ) ) ); + } + } + return newnode; } - node.getNodeData().getTaxonomy().setScientificName( scientific_name ); } /** - * Convenience method to set the taxonomy code of a phylogeny node. - * - * - * @param node - * @param taxonomy_code + * Shallow copies the phylogeny originating from this node. */ - public static void setTaxonomyCode( final PhylogenyNode node, final String taxonomy_code ) { - if ( !node.getNodeData().isHasTaxonomy() ) { - node.getNodeData().setTaxonomy( new Taxonomy() ); + static PhylogenyNode copySubTreeShallow( final PhylogenyNode source ) { + if ( source == null ) { + return null; + } + else { + final PhylogenyNode newnode = source.copyNodeDataShallow(); + if ( !source.isExternal() ) { + for( int i = 0; i < source.getNumberOfDescendants(); ++i ) { + newnode.setChildNode( i, PhylogenyMethods.copySubTreeShallow( source.getChildNode( i ) ) ); + } + } + return newnode; } - node.getNodeData().getTaxonomy().setTaxonomyCode( taxonomy_code ); } /** - * Removes from Phylogeny to_be_stripped all external Nodes which are - * associated with a species NOT found in Phylogeny reference. + * Calculates the distance between PhylogenyNodes n1 and n2. + * PRECONDITION: n1 is a descendant of n2. * - * @param reference - * a reference Phylogeny - * @param to_be_stripped - * Phylogeny to be stripped - * @return number of external nodes removed from to_be_stripped + * @param n1 + * a descendant of n2 + * @param n2 + * @return distance between n1 and n2 */ - 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() ) ); - } - for( final PhylogenyNodeIterator it = to_be_stripped.iteratorExternalForward(); it.hasNext(); ) { - final PhylogenyNode n = it.next(); - if ( !ref_ext_taxo.contains( getSpecies( n ) ) ) { - nodes_to_delete.add( n ); + private static double getDistance( PhylogenyNode n1, final PhylogenyNode n2 ) { + double d = 0.0; + while ( n1 != n2 ) { + if ( n1.getDistanceToParent() > 0.0 ) { + d += n1.getDistanceToParent(); } + n1 = n1.getParent(); } - for( final PhylogenyNode phylogenyNode : nodes_to_delete ) { - to_be_stripped.deleteSubtree( phylogenyNode, true ); - } - return nodes_to_delete.size(); + return d; } - /** - * Arranges the order of childern for each node of this Phylogeny in such a - * way that either the branch with more children is on top (right) or on - * bottom (left), dependent on the value of boolean order. - * - * @param order - * decides in which direction to order - * @param pri - */ - public static void orderAppearance( final PhylogenyNode n, - final boolean order, - final boolean order_ext_alphabetically, - final DESCENDANT_SORT_PRIORITY pri ) { - if ( n.isExternal() ) { - return; + private static boolean match( final String s, + final String query, + final boolean case_sensitive, + final boolean partial ) { + if ( ForesterUtil.isEmpty( s ) || ForesterUtil.isEmpty( query ) ) { + return false; + } + String my_s = s.trim(); + String my_query = query.trim(); + if ( !case_sensitive ) { + my_s = my_s.toLowerCase(); + my_query = my_query.toLowerCase(); + } + if ( partial ) { + return my_s.indexOf( my_query ) >= 0; } else { - PhylogenyNode temp = null; - if ( ( n.getNumberOfDescendants() == 2 ) - && ( n.getChildNode1().getNumberOfExternalNodes() != n.getChildNode2().getNumberOfExternalNodes() ) - && ( ( n.getChildNode1().getNumberOfExternalNodes() < n.getChildNode2().getNumberOfExternalNodes() ) == order ) ) { - temp = n.getChildNode1(); - n.setChild1( n.getChildNode2() ); - n.setChild2( temp ); - } - else if ( order_ext_alphabetically ) { - // boolean all_ext = true; - // for( PhylogenyNode i : n.getDescendants() ) { - // if ( !i.isExternal() ) { - // all_ext = false; - // break; - // } - // } - // if ( all_ext ) { - PhylogenyMethods.sortNodeDescendents( n, pri ); - // } - } - for( int i = 0; i < n.getNumberOfDescendants(); ++i ) { - orderAppearance( n.getChildNode( i ), order, order_ext_alphabetically, pri ); - } + return my_s.equals( my_query ); } } + public static enum DESCENDANT_SORT_PRIORITY { + TAXONOMY, SEQUENCE, NODE_NAME; + } + public static enum PhylogenyNodeField { CLADE_NAME, TAXONOMY_CODE, @@ -1611,14 +1570,7 @@ public class PhylogenyMethods { SEQUENCE_SYMBOL, SEQUENCE_NAME, TAXONOMY_ID_UNIPROT_1, - TAXONOMY_ID_UNIPROT_2; - } - - public static enum TAXONOMY_EXTRACTION { - NO, YES, PFAM_STYLE_ONLY; - } - - public static enum DESCENDANT_SORT_PRIORITY { - TAXONOMY, SEQUENCE, NODE_NAME; + TAXONOMY_ID_UNIPROT_2, + TAXONOMY_ID; } }