forester/java/src/org/forester/clade_analysis/AnalysisSingle.java

   1 // $Id:
   2 // FORESTER -- software libraries and applications
   3 // for evolutionary biology research and applications.
   4 //
   5 // Copyright (C) 2017 Christian M. Zmasek
   6 // Copyright (C) 2017 J. Craig Venter Institute
   7 // All rights reserved
   8 //
   9 // This library is free software; you can redistribute it and/or
  10 // modify it under the terms of the GNU Lesser General Public
  11 // License as published by the Free Software Foundation; either
  12 // version 2.1 of the License, or (at your option) any later version.
  13 //
  14 // This library is distributed in the hope that it will be useful,
  15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  17 // Lesser General Public License for more details.
  18 //
  19 // You should have received a copy of the GNU Lesser General Public
  20 // License along with this library; if not, write to the Free Software
  21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  22 //
  23 // Contact: phyloxml @ gmail . com
  24 // WWW: https://sites.google.com/site/cmzmasek/home/software/forester
  25 // --------------------
  26 // TODO
  27 // * Multiple "hits" with different "M" values
  28 // * More tests (including multiple children per node), especially on edge cases
  29 // * Utilize relevant support values for warnings
  30
  31 package org.forester.clade_analysis;
  32
  33 import java.util.ArrayList;
  34 import java.util.Collections;
  35 import java.util.List;
  36
  37 import org.forester.phylogeny.Phylogeny;
  38 import org.forester.phylogeny.PhylogenyNode;
  39 import org.forester.phylogeny.data.Confidence;
  40 import org.forester.util.ForesterUtil;
  41
  42 public final class AnalysisSingle {
  43
  44     public static ResultSingle execute( final Phylogeny p, final String query, final String separator ) {
  45         final PhylogenyNode qnode = p.getNode( query );
  46         if ( qnode.isRoot() ) {
  47             throw new IllegalStateException( "Unexpected error: Query " + query
  48                     + " is root. This should have never happened" );
  49         }
  50         if ( qnode.getParent().isRoot() ) {
  51             throw new IllegalStateException( "Unexpected error: Parent of query " + query
  52                     + " is root. This should have never happened" );
  53         }
  54         PhylogenyNode qnode_p = qnode.getParent();
  55         PhylogenyNode qnode_pp = qnode.getParent().getParent();
  56         while ( qnode_p.getNumberOfDescendants() == 1 ) {
  57             qnode_p = qnode_p.getParent();
  58         }
  59         while ( qnode_pp.getNumberOfDescendants() == 1 ) {
  60             qnode_pp = qnode_pp.getParent();
  61         }
  62         final List<PhylogenyNode> qnode_ext_nodes = qnode_pp.getAllExternalDescendants();
  63         final int lec_ext_nodes = qnode_ext_nodes.size() - 1;
  64         final int p_ext_nodes = p.getNumberOfExternalNodes() - 1;
  65         final List<String> qnode_ext_nodes_names = new ArrayList<>();
  66         for( final PhylogenyNode qnode_ext_node : qnode_ext_nodes ) {
  67             String name = qnode_ext_node.getName();
  68             if ( ForesterUtil.isEmptyTrimmed( name ) ) {
  69                 throw new IllegalArgumentException( "external node(s) with empty names found" );
  70             }
  71             name = name.trim();
  72             if ( !name.equals( query ) ) {
  73                 qnode_ext_nodes_names.add( name );
  74             }
  75         }
  76         final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( qnode_ext_nodes_names, separator );
  77         final ResultSingle res = new ResultSingle();
  78         if ( greatest_common_prefix.length() < 1 ) {
  79             res.addWarning( "No greatest common prefix" );
  80             res.setGreatestCommonPrefix( "" );
  81         }
  82         else {
  83             res.setGreatestCommonPrefix( greatest_common_prefix );
  84         }
  85         if ( qnode_pp.isRoot() ) {
  86             res.addWarning( "Least Encompassing Clade is entire tree" );
  87         }
  88         res.setLeastEncompassingCladeSize( lec_ext_nodes );
  89         res.setTreeSize( p_ext_nodes );
  90
  91         final String conf = obtainConfidence( qnode_pp );
  92         if ( conf != null ) {
  93             res.setGreatestCommonCladeSubtreeConfidence(conf);
  94         }
  95
  96         final String greatest_common_prefix_up[] = analyzeSiblings( qnode_p, qnode_pp, separator );
  97         res.setGreatestCommonPrefixUp( greatest_common_prefix_up[ 0 ] );
  98         if ( greatest_common_prefix_up[ 1 ] != null ) {
  99             res.setGreatestCommonCladeUpSubtreeConfidence( greatest_common_prefix_up[ 1 ] );
 100         }
 101         final String greatest_common_prefix_down[] = analyzeSiblings( qnode, qnode_p, separator );
 102         res.setGreatestCommonPrefixDown( greatest_common_prefix_down[ 0 ] );
 103         if ( greatest_common_prefix_down[ 1 ] != null ) {
 104             res.setGreatestCommonCladeDownSubtreeConfidence( greatest_common_prefix_down[ 1 ] );
 105         }
 106         return res;
 107     }
 108
 109
 110
 111     private final static String[] analyzeSiblings( final PhylogenyNode child,
 112                                                    final PhylogenyNode parent,
 113                                                    final String separator ) {
 114         final int child_index = child.getChildNodeIndex();
 115         final List<String> ext_nodes_names = new ArrayList<>();
 116         final List<PhylogenyNode> descs = parent.getDescendants();
 117         String conf = null;
 118         for( int i = 0; i < descs.size(); ++i ) {
 119             if ( i != child_index ) {
 120                 final PhylogenyNode d = descs.get( i );
 121                 for( final PhylogenyNode n : d.getAllExternalDescendants() ) {
 122                     final String name = n.getName();
 123                     if ( ForesterUtil.isEmptyTrimmed( name ) ) {
 124                         throw new IllegalArgumentException( "external node(s) with empty names found" );
 125                     }
 126                     ext_nodes_names.add( name.trim() );
 127                 }
 128                 if ( descs.size() == 2 ) {
 129                     conf = obtainConfidence( d );
 130                 }
 131             }
 132         }
 133         final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( ext_nodes_names, separator );
 134         return new String[] { greatest_common_prefix, conf };
 135     }
 136
 137     private final static String obtainConfidence( final PhylogenyNode n ) {
 138         if ( n.getBranchData().getConfidences() != null && n.getBranchData().getConfidences().size() > 0 ) {
 139             final List<Confidence> confidences = n.getBranchData().getConfidences();
 140             boolean not_first = false;
 141             Collections.sort( confidences );
 142             final StringBuilder sb = new StringBuilder();
 143             for( final Confidence confidence : confidences ) {
 144                 final double value = confidence.getValue();
 145                 if ( value != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
 146                     if ( not_first ) {
 147                         sb.append( " / " );
 148                     }
 149                     else {
 150                         not_first = true;
 151                     }
 152                     sb.append( ( ForesterUtil.isEmpty( confidence.getType() ) ? "confidence: "
 153                             : confidence.getType() + ": " ) + value );
 154                 }
 155             }
 156             return sb.toString();
 157         }
 158         return null;
 159     }
 160 }