forester/java/src/org/forester/clade_analysis/Analysis.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 // * Better system for "clade label creation" (e.g. 1.3.4 + 1.3.6 -> 1.3), use
  31 //   specific separator (eg . | _ )
  32
  33 package org.forester.clade_analysis;
  34
  35 import java.util.ArrayList;
  36 import java.util.List;
  37
  38 import org.forester.phylogeny.Phylogeny;
  39 import org.forester.phylogeny.PhylogenyNode;
  40 import org.forester.util.ForesterUtil;
  41
  42 public final class Analysis {
  43
  44     public static Result execute( final Phylogeny p, final String query ) {
  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         final PhylogenyNode qnode_p = qnode.getParent();
  55         final PhylogenyNode qnode_pp = qnode.getParent().getParent();
  56         final List<PhylogenyNode> qnode_ext_nodes = qnode_pp.getAllExternalDescendants();
  57         final int lec_ext_nodes = qnode_ext_nodes.size() - 1;
  58         final int p_ext_nodes = p.getNumberOfExternalNodes() - 1;
  59         final List<String> qnode_ext_nodes_names = new ArrayList<>();
  60         for( final PhylogenyNode qnode_ext_node : qnode_ext_nodes ) {
  61             String name = qnode_ext_node.getName();
  62             if ( ForesterUtil.isEmptyTrimmed( name ) ) {
  63                 throw new IllegalArgumentException( "external node(s) with empty names found" );
  64             }
  65             name = name.trim();
  66             if ( !name.equals( query ) ) {
  67                 qnode_ext_nodes_names.add( name );
  68             }
  69         }
  70         final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( qnode_ext_nodes_names );
  71         final Result res = new Result();
  72         if ( greatest_common_prefix.length() < 1 ) {
  73             res.addWarning( "No greatest common prefix" );
  74             res.setGreatestCommonPrefix( "" );
  75         }
  76         else {
  77             res.setGreatestCommonPrefix( greatest_common_prefix );
  78         }
  79         if ( qnode_pp.isRoot() ) {
  80             res.addWarning( "Least Encompassing Clade is entire tree" );
  81         }
  82         res.setLeastEncompassingCladeSize( lec_ext_nodes );
  83         res.setTreeSize( p_ext_nodes );
  84         final String greatest_common_prefix_a = analyzeSiblings( qnode_p, qnode_pp );
  85         res.setGreatestCommonPrefixUp( greatest_common_prefix_a );
  86         final String greatest_common_prefix_b = analyzeSiblings( qnode, qnode_p );
  87         res.setGreatestCommonPrefixDown( greatest_common_prefix_b );
  88         return res;
  89     }
  90
  91     private final static String analyzeSiblings( final PhylogenyNode child, final PhylogenyNode parent ) {
  92         final int qnode_p_index = child.getChildNodeIndex();
  93         final List<String> qnode_ext_nodes_names_a = new ArrayList<>();
  94         final List<PhylogenyNode> descs = parent.getDescendants();
  95         for( int i = 0; i < descs.size(); ++i ) {
  96             if ( i != qnode_p_index ) {
  97                 final PhylogenyNode d = descs.get( i );
  98                 for( final PhylogenyNode n : d.getAllExternalDescendants() ) {
  99                     final String name = n.getName();
 100                     if ( ForesterUtil.isEmptyTrimmed( name ) ) {
 101                         throw new IllegalArgumentException( "external node(s) with empty names found" );
 102                     }
 103                     qnode_ext_nodes_names_a.add( name.trim() );
 104                 }
 105             }
 106         }
 107         final String greatest_common_prefix_a = ForesterUtil.greatestCommonPrefix( qnode_ext_nodes_names_a );
 108         return greatest_common_prefix_a;
 109     }
 110 }