forester/java/src/org/forester/clade_analysis/AnalysisMulti.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 import java.util.SortedMap;
  37 import java.util.regex.Matcher;
  38 import java.util.regex.Pattern;
  39
  40 import org.forester.phylogeny.Phylogeny;
  41 import org.forester.phylogeny.PhylogenyNode;
  42 import org.forester.phylogeny.data.Confidence;
  43 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  44 import org.forester.util.ForesterUtil;
  45 import org.forester.util.UserException;
  46
  47 public final class AnalysisMulti {
  48
  49     private final static String UNKNOWN                                = "?";
  50     public final static double  DEFAULT_CUTOFF_FOR_SPECIFICS           = 0.5;
  51     public final static String  DEFAULT_SEPARATOR                      = ".";
  52     public final static Pattern DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE = Pattern.compile( "_#\\d+_M=(.+)" );
  53
  54     public static ResultMulti execute( final Phylogeny p ) throws UserException {
  55         return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, DEFAULT_SEPARATOR, DEFAULT_CUTOFF_FOR_SPECIFICS );
  56     }
  57
  58     public static ResultMulti execute( final Phylogeny p, final String separator ) throws UserException {
  59         return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, separator, DEFAULT_CUTOFF_FOR_SPECIFICS );
  60     }
  61
  62     public static ResultMulti execute( final Phylogeny p, final String separator, final double cutoff_for_specifics )
  63             throws UserException {
  64         return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, separator, cutoff_for_specifics );
  65     }
  66
  67     public static ResultMulti execute( final Phylogeny p, final double cutoff_for_specifics ) throws UserException {
  68         return execute( p, DEFAULT_QUERY_PATTERN_FOR_PPLACER_TYPE, DEFAULT_SEPARATOR, cutoff_for_specifics );
  69     }
  70
  71     public static ResultMulti execute( final Phylogeny p,
  72                                        final Pattern query,
  73                                        final String separator,
  74                                        final double cutoff_for_specifics )
  75             throws UserException {
  76         cleanUpExternalNames( p, separator );
  77         final List<PhylogenyNode> qnodes = p.getNodes( query );
  78         String query_name_prefix = null;
  79         for( final PhylogenyNode n : qnodes ) {
  80             final String name = n.getName();
  81             final Matcher matcher = query.matcher( name );
  82             if ( matcher.find() ) {
  83                 final String prefix = name.substring( 0, matcher.start() );
  84                 if ( ForesterUtil.isEmpty( prefix ) ) {
  85                     throw new UserException( "query nodes with empty label prefix found: \"" + prefix + "\"" );
  86                 }
  87                 if ( query_name_prefix == null ) {
  88                     query_name_prefix = prefix;
  89                 }
  90                 else if ( !query_name_prefix.equals( prefix ) ) {
  91                     throw new UserException( "query nodes with different label prefixes found: \"" + query_name_prefix
  92                             + "\" and \"" + prefix + "\"" );
  93                 }
  94             }
  95         }
  96         final ResultMulti res = new ResultMulti();
  97         res.setQueryNamePrefix( query_name_prefix );
  98         for( int i = 0; i < qnodes.size(); ++i ) {
  99             final PhylogenyNode qnode = qnodes.get( i );
 100             if ( qnode.isRoot() ) {
 101                 throw new UserException( "query " + query + " is root" );
 102             }
 103             if ( qnode.getParent().isRoot() ) {
 104                 throw new UserException( "parent of query " + query + " is root" );
 105             }
 106             PhylogenyNode qnode_p = qnode.getParent();
 107             PhylogenyNode qnode_pp = qnode.getParent().getParent();
 108             //This is to deal with internal nodes with 1 descendant.
 109             while ( qnode_p.getNumberOfDescendants() == 1 ) {
 110                 qnode_p = qnode_p.getParent();
 111             }
 112             while ( qnode_pp.getNumberOfDescendants() == 1 ) {
 113                 qnode_pp = qnode_pp.getParent();
 114             }
 115             final List<String> qnode_ext_nodes_names = new ArrayList<>();
 116             for( final PhylogenyNode qnode_ext_node : qnode_pp.getAllExternalDescendants() ) {
 117                 final String name = qnode_ext_node.getName();
 118                 final Matcher m = query.matcher( name );
 119                 if ( !m.find() ) {
 120                     qnode_ext_nodes_names.add( name );
 121                 }
 122             }
 123             final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( qnode_ext_nodes_names, separator );
 124             final Matcher matcher = query.matcher( qnode.getName() );
 125             String conf_str = null;
 126             if ( matcher.find() ) {
 127                 conf_str = matcher.group( 1 );
 128             }
 129             else {
 130                 throw new IllegalStateException( "pattern did not match -- this should have never happened!" );
 131             }
 132             final double conf = Double.parseDouble( conf_str );
 133             if ( !ForesterUtil.isEmpty( greatest_common_prefix ) ) {
 134                 res.addGreatestCommonPrefix( greatest_common_prefix, conf );
 135             }
 136             else {
 137                 res.addGreatestCommonPrefix( UNKNOWN, conf );
 138             }
 139             final String greatest_common_prefix_up = analyzeSiblings( qnode_p, qnode_pp, separator, query );
 140             if ( !ForesterUtil.isEmpty( greatest_common_prefix_up ) ) {
 141                 res.addGreatestCommonPrefixUp( greatest_common_prefix_up, conf );
 142             }
 143             else {
 144                 res.addGreatestCommonPrefixUp( UNKNOWN, conf );
 145             }
 146             final String greatest_common_prefix_down = analyzeSiblings( qnode, qnode_p, separator, query );
 147             if ( !ForesterUtil.isEmpty( greatest_common_prefix_down ) ) {
 148                 res.addGreatestCommonPrefixDown( greatest_common_prefix_down, conf );
 149             }
 150             else {
 151                 res.addGreatestCommonPrefixDown( UNKNOWN, conf );
 152             }
 153         }
 154         res.analyze( cutoff_for_specifics );
 155         return res;
 156     }
 157
 158     private final static void cleanUpExternalNames( final Phylogeny p, final String separator ) throws UserException {
 159         final Pattern pattern1 = Pattern.compile( "\\Q" + separator + "\\E" + "\\s+" );
 160         final Pattern pattern2 = Pattern.compile( "\\s+" + "\\Q" + separator + "\\E" );
 161         final Pattern pattern3 = Pattern.compile( "\\Q" + separator + separator + "\\E" );
 162         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 163         while ( it.hasNext() ) {
 164             final PhylogenyNode node = it.next();
 165             final String name = node.getName().trim();
 166             if ( ForesterUtil.isEmpty( name ) ) {
 167                 throw new UserException( "external node(s) with empty annotation found" );
 168             }
 169             if ( name.endsWith( separator ) ) {
 170                 throw new UserException( "illegally formatted annotation found: annotations cannot end with separator: "
 171                         + name );
 172             }
 173             if ( name.startsWith( separator ) ) {
 174                 throw new UserException( "illegally formatted annotation found: annotations cannot start with separator: "
 175                         + name );
 176             }
 177             if ( pattern1.matcher( name ).find() ) {
 178                 throw new UserException( "illegally formatted annotation found: separator followed by whitespace: "
 179                         + name );
 180             }
 181             if ( pattern2.matcher( name ).find() ) {
 182                 throw new UserException( "illegally formatted annotation found: whitespace followed by separator: "
 183                         + name );
 184             }
 185             if ( pattern3.matcher( name ).find() ) {
 186                 throw new UserException( "illegally formatted annotation found: empty annotation level: " + name );
 187             }
 188             node.setName( name.replaceAll( "\\s+", " " ) );
 189         }
 190     }
 191
 192     private final static String analyzeSiblings( final PhylogenyNode child,
 193                                                  final PhylogenyNode parent,
 194                                                  final String separator,
 195                                                  final Pattern query ) {
 196         final int child_index = child.getChildNodeIndex();
 197         final List<String> ext_nodes_names = new ArrayList<>();
 198         final List<PhylogenyNode> descs = parent.getDescendants();
 199         for( int i = 0; i < descs.size(); ++i ) {
 200             if ( i != child_index ) {
 201                 final PhylogenyNode d = descs.get( i );
 202                 for( final PhylogenyNode n : d.getAllExternalDescendants() ) {
 203                     final String name = n.getName();
 204                     final Matcher m = query.matcher( name );
 205                     if ( !m.find() ) {
 206                         ext_nodes_names.add( name );
 207                     }
 208                 }
 209             }
 210         }
 211         final String greatest_common_prefix = ForesterUtil.greatestCommonPrefix( ext_nodes_names, separator );
 212         return greatest_common_prefix;
 213     }
 214
 215     private final static String obtainConfidence( final PhylogenyNode n ) {
 216         if ( ( n.getBranchData().getConfidences() != null ) && ( n.getBranchData().getConfidences().size() > 0 ) ) {
 217             final List<Confidence> confidences = n.getBranchData().getConfidences();
 218             boolean not_first = false;
 219             Collections.sort( confidences );
 220             final StringBuilder sb = new StringBuilder();
 221             for( final Confidence confidence : confidences ) {
 222                 final double value = confidence.getValue();
 223                 if ( value != Confidence.CONFIDENCE_DEFAULT_VALUE ) {
 224                     if ( not_first ) {
 225                         sb.append( " / " );
 226                     }
 227                     else {
 228                         not_first = true;
 229                     }
 230                     sb.append( ( ForesterUtil.isEmpty( confidence.getType() ) ? "confidence: "
 231                             : confidence.getType() + ": " ) + value );
 232                 }
 233             }
 234             return sb.toString();
 235         }
 236         return null;
 237     }
 238
 239     public final static void performMapping( final Pattern pattern,
 240                                              final SortedMap<String, String> map,
 241                                              final Phylogeny p,
 242                                              final boolean verbose )
 243             throws UserException {
 244         if ( verbose ) {
 245             System.out.println();
 246             System.out.println( "Id to annotation mapping:" );
 247         }
 248         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 249         while ( it.hasNext() ) {
 250             final PhylogenyNode node = it.next();
 251             final String name = node.getName().trim();
 252             if ( ForesterUtil.isEmpty( name ) ) {
 253                 throw new UserException( "external node with empty name found" );
 254             }
 255             final Matcher m = pattern.matcher( name );
 256             if ( !m.find() ) {
 257                 if ( !map.containsKey( name ) ) {
 258                     throw new UserException( "no mapping for \"" + name + "\" found" );
 259                 }
 260                 node.setName( map.get( name ).trim() );
 261                 if ( verbose ) {
 262                     System.out.println( name + " -> " + node.getName() );
 263                 }
 264             }
 265         }
 266         if ( verbose ) {
 267             System.out.println();
 268         }
 269     }
 270
 271     public final static void performExtraProcessing1( final Pattern pattern,
 272                                                       final Phylogeny p,
 273                                                       final String extra_sep,
 274                                                       final boolean keep,
 275                                                       final String annotation_sep,
 276                                                       final boolean verbose )
 277             throws UserException {
 278         if ( verbose ) {
 279             System.out.println();
 280             System.out.println( "Extra annotation processing:" );
 281         }
 282         final PhylogenyNodeIterator it = p.iteratorExternalForward();
 283         while ( it.hasNext() ) {
 284             final PhylogenyNode node = it.next();
 285             final String name = node.getName().trim();
 286             if ( ForesterUtil.isEmpty( name ) ) {
 287                 throw new UserException( "external node with empty name found" );
 288             }
 289             final Matcher m = pattern.matcher( name );
 290             if ( !m.find() ) {
 291                 final StringBuilder sb = new StringBuilder();
 292                 final int last_index = name.lastIndexOf( extra_sep );
 293                 if ( last_index >= 0 ) {
 294                     final String annotation = name.substring( last_index + 1 ).trim();
 295                     if ( ForesterUtil.isEmptyTrimmed( annotation ) ) {
 296                         throw new UserException( "illegal format:" + name );
 297                     }
 298                     if ( keep ) {
 299                         final String extra = name.substring( 0, last_index ).trim();
 300                         sb.append( annotation );
 301                         if ( !ForesterUtil.isEmpty( extra ) ) {
 302                             sb.append( annotation_sep );
 303                             sb.append( extra );
 304                         }
 305                     }
 306                     else {
 307                         sb.append( annotation );
 308                     }
 309                     node.setName( sb.toString() );
 310                     if ( verbose ) {
 311                         System.out.println( name + " -> " + node.getName() );
 312                     }
 313                 }
 314             }
 315         }
 316         if ( verbose ) {
 317             System.out.println();
 318         }
 319     }
 320 }