forester/java/src/org/forester/analysis/AncestralTaxonomyInference.java

   1 // forester -- software libraries and applications
   2 // for genomics and evolutionary biology research.
   3 //
   4 // Copyright (C) 2010 Christian M Zmasek
   5 // Copyright (C) 2010 Sanford-Burnham Medical Research Institute
   6 // All rights reserved
   7 //
   8 // This library is free software; you can redistribute it and/or
   9 // modify it under the terms of the GNU Lesser General Public
  10 // License as published by the Free Software Foundation; either
  11 // version 2.1 of the License, or (at your option) any later version.
  12 //
  13 // This library is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16 // Lesser General Public License for more details.
  17 //
  18 // You should have received a copy of the GNU Lesser General Public
  19 // License along with this library; if not, write to the Free Software
  20 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  21 //
  22 // Contact: phylosoft @ gmail . com
  23 // WWW: www.phylosoft.org/forester
  24
  25 package org.forester.analysis;
  26
  27 import java.io.IOException;
  28 import java.util.ArrayList;
  29 import java.util.HashMap;
  30 import java.util.List;
  31 import java.util.SortedSet;
  32 import java.util.TreeSet;
  33
  34 import org.forester.io.parsers.phyloxml.PhyloXmlDataFormatException;
  35 import org.forester.phylogeny.Phylogeny;
  36 import org.forester.phylogeny.PhylogenyNode;
  37 import org.forester.phylogeny.data.Identifier;
  38 import org.forester.phylogeny.data.Taxonomy;
  39 import org.forester.phylogeny.iterators.PhylogenyNodeIterator;
  40 import org.forester.util.ForesterUtil;
  41 import org.forester.ws.uniprot.UniProtTaxonomy;
  42 import org.forester.ws.uniprot.UniProtWsTools;
  43
  44 public final class AncestralTaxonomyInference {
  45
  46     private static final int                              MAX_CACHE_SIZE           = 100000;
  47     private static final int                              MAX_TAXONOMIES_TO_RETURN = 100;
  48     private static final HashMap<String, UniProtTaxonomy> _sn_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
  49     private static final HashMap<String, UniProtTaxonomy> _code_up_cache_map       = new HashMap<String, UniProtTaxonomy>();
  50     private static final HashMap<String, UniProtTaxonomy> _cn_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
  51     private static final HashMap<String, UniProtTaxonomy> _id_up_cache_map         = new HashMap<String, UniProtTaxonomy>();
  52
  53     synchronized private static void clearCachesIfTooLarge() {
  54         if ( getSnTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  55             getSnTaxCacheMap().clear();
  56         }
  57         if ( getCnTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  58             getCnTaxCacheMap().clear();
  59         }
  60         if ( getCodeTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  61             getCodeTaxCacheMap().clear();
  62         }
  63         if ( getIdTaxCacheMap().size() > MAX_CACHE_SIZE ) {
  64             getIdTaxCacheMap().clear();
  65         }
  66     }
  67
  68     synchronized private static HashMap<String, UniProtTaxonomy> getCnTaxCacheMap() {
  69         return _cn_up_cache_map;
  70     }
  71
  72     synchronized private static HashMap<String, UniProtTaxonomy> getCodeTaxCacheMap() {
  73         return _code_up_cache_map;
  74     }
  75
  76     synchronized private static HashMap<String, UniProtTaxonomy> getIdTaxCacheMap() {
  77         return _id_up_cache_map;
  78     }
  79
  80     synchronized private static HashMap<String, UniProtTaxonomy> getSnTaxCacheMap() {
  81         return _sn_up_cache_map;
  82     }
  83
  84     synchronized private static UniProtTaxonomy getTaxonomies( final HashMap<String, UniProtTaxonomy> cache,
  85                                                                final String query,
  86                                                                final QUERY_TYPE qt ) throws IOException {
  87         if ( cache.containsKey( query ) ) {
  88             return cache.get( query ).copy();
  89         }
  90         else {
  91             List<UniProtTaxonomy> up_taxonomies = null;
  92             switch ( qt ) {
  93                 case ID:
  94                     up_taxonomies = getTaxonomiesFromId( query );
  95                     break;
  96                 case CODE:
  97                     up_taxonomies = getTaxonomiesFromTaxonomyCode( query );
  98                     break;
  99                 case SN:
 100                     up_taxonomies = getTaxonomiesFromScientificName( query );
 101                     break;
 102                 case CN:
 103                     up_taxonomies = getTaxonomiesFromCommonName( query );
 104                     break;
 105                 default:
 106                     throw new RuntimeException();
 107             }
 108             if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
 109                 final UniProtTaxonomy up_tax = up_taxonomies.get( 0 );
 110                 if ( !ForesterUtil.isEmpty( up_tax.getScientificName() ) ) {
 111                     getSnTaxCacheMap().put( up_tax.getScientificName(), up_tax );
 112                 }
 113                 if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
 114                     getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
 115                 }
 116                 if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 117                     getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
 118                 }
 119                 if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 120                     getIdTaxCacheMap().put( up_tax.getId(), up_tax );
 121                 }
 122                 return up_tax;
 123             }
 124             else {
 125                 return null;
 126             }
 127         }
 128     }
 129
 130     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromCommonName( final String query )
 131             throws IOException {
 132         return UniProtWsTools.getTaxonomiesFromCommonNameStrict( query, MAX_TAXONOMIES_TO_RETURN );
 133     }
 134
 135     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromId( final String query ) throws IOException {
 136         return UniProtWsTools.getTaxonomiesFromId( query, MAX_TAXONOMIES_TO_RETURN );
 137     }
 138
 139     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromScientificName( final String query )
 140             throws IOException {
 141         return UniProtWsTools.getTaxonomiesFromScientificNameStrict( query, MAX_TAXONOMIES_TO_RETURN );
 142     }
 143
 144     synchronized private static List<UniProtTaxonomy> getTaxonomiesFromTaxonomyCode( final String query )
 145             throws IOException {
 146         return UniProtWsTools.getTaxonomiesFromTaxonomyCode( query, MAX_TAXONOMIES_TO_RETURN );
 147     }
 148
 149     synchronized public static SortedSet<String> inferTaxonomyFromDescendents( final Phylogeny phy ) throws IOException {
 150         clearCachesIfTooLarge();
 151         final SortedSet<String> not_found = new TreeSet<String>();
 152         for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) {
 153             final PhylogenyNode node = iter.next();
 154             if ( !node.isExternal() ) {
 155                 inferTaxonomyFromDescendents( node, not_found );
 156             }
 157         }
 158         return not_found;
 159     }
 160
 161     synchronized private static void inferTaxonomyFromDescendents( final PhylogenyNode n,
 162                                                                    final SortedSet<String> not_found )
 163             throws IOException {
 164         if ( n.isExternal() ) {
 165             throw new IllegalArgumentException( "attempt to infer taxonomy from descendants of external node" );
 166         }
 167         n.getNodeData().setTaxonomy( null );
 168         final List<PhylogenyNode> descs = n.getDescendants();
 169         final List<String[]> lineages = new ArrayList<String[]>();
 170         int shortest_lin_length = Integer.MAX_VALUE;
 171         for( final PhylogenyNode desc : descs ) {
 172             if ( desc.getNodeData().isHasTaxonomy()
 173                     && ( isHasAppropriateId( desc.getNodeData().getTaxonomy() )
 174                             || !ForesterUtil.isEmpty( desc.getNodeData().getTaxonomy().getScientificName() )
 175                             || !ForesterUtil.isEmpty( desc.getNodeData().getTaxonomy().getTaxonomyCode() ) || !ForesterUtil
 176                             .isEmpty( desc.getNodeData().getTaxonomy().getCommonName() ) ) ) {
 177
 178                 final UniProtTaxonomy up_tax = obtainUniProtTaxonomy( desc.getNodeData().getTaxonomy(), null, null );
 179                 String[] lineage = null;
 180                 if ( up_tax != null ) {
 181                     //lineage = obtainLineagePlusOwnScientificName( up_tax );
 182                     lineage = up_tax.getLineageAsArray();
 183                 }
 184                 if ( ( lineage == null ) || ( lineage.length < 1 ) ) {
 185                     //TODO remove me
 186                     System.out.println( "node " + desc.getNodeData().getTaxonomy().toString() + " has no lineage!" );
 187                     not_found.add( desc.getNodeData().getTaxonomy().asText().toString() );
 188                     return;
 189                 }
 190                 if ( lineage.length < shortest_lin_length ) {
 191                     shortest_lin_length = lineage.length;
 192                 }
 193                 lineages.add( lineage );
 194             }
 195             else {
 196                 String msg = "Node(s) with no or inappropriate taxonomic information found";
 197                 String node = "";
 198                 if ( !ForesterUtil.isEmpty( desc.getName() ) ) {
 199                     node = "\"" + desc.getName() + "\"";
 200                 }
 201                 else {
 202                     node = "[" + desc.getId() + "]";
 203                 }
 204                 msg = "Node " + node + " has no or inappropriate taxonomic information";
 205              //   final List<PhylogenyNode> e = desc.getAllExternalDescendants();
 206                 //TODO remove me!
 207 //                System.out.println();
 208 //                int x = 0;
 209 //                for( final PhylogenyNode object : e ) {
 210 //                    System.out.println( x + ":" );
 211 //                    System.out.println( object.getName() + "  " );
 212 //                    x++;
 213 //                }
 214 //                System.out.println();
 215                 //
 216                 throw new IllegalArgumentException( msg );
 217             }
 218         }
 219         List<String> last_common_lineage = new ArrayList<String>();
 220         String last_common = null;
 221         if ( shortest_lin_length > 0 ) {
 222             I: for( int i = 0; i < shortest_lin_length; ++i ) {
 223                 final String lineage_0 = lineages.get( 0 )[ i ];
 224                 for( int j = 1; j < lineages.size(); ++j ) {
 225                     if ( !lineage_0.equals( lineages.get( j )[ i ] ) ) {
 226                         break I;
 227                     }
 228                 }
 229                // last_common_lineage = lineage_0;
 230                 last_common_lineage.add( lineage_0 ) ;
 231                 last_common =lineage_0;
 232             }
 233         }
 234        // if ( last_common_lineage == null ) {
 235         if ( last_common_lineage.isEmpty() ) {
 236             System.out.println( "No common lineage for:" );
 237             int counter = 0;
 238             for( final String[] strings : lineages ) {
 239                 System.out.print( counter + ": " );
 240                 ++counter;
 241                 for( final String string : strings ) {
 242                     System.out.print( string + " " );
 243                 }
 244                 System.out.println();
 245             }
 246             return;
 247         }
 248         final Taxonomy tax = new Taxonomy();
 249         n.getNodeData().setTaxonomy( tax );
 250         tax.setScientificName( last_common );
 251         final UniProtTaxonomy up_tax = obtainUniProtTaxonomyFromCommonLineage( last_common_lineage );
 252         if ( up_tax != null ) {
 253             if ( !ForesterUtil.isEmpty( up_tax.getRank() ) ) {
 254                 try {
 255                     tax.setRank( up_tax.getRank().toLowerCase() );
 256                 }
 257                 catch ( final PhyloXmlDataFormatException ex ) {
 258                     tax.setRank( "" );
 259                 }
 260             }
 261             if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 262                 tax.setIdentifier( new Identifier( up_tax.getId(), "uniprot" ) );
 263             }
 264             if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 265                 tax.setCommonName( up_tax.getCommonName() );
 266             }
 267             if ( !ForesterUtil.isEmpty( up_tax.getSynonym() ) && !tax.getSynonyms().contains( up_tax.getSynonym() ) ) {
 268                 tax.getSynonyms().add( up_tax.getSynonym() );
 269             }
 270             if ( up_tax.getLineage() != null ) {
 271                 tax.setLineage( new ArrayList<String>() );
 272                 for( final String lin : up_tax.getLineage() ) {
 273                     if ( !ForesterUtil.isEmpty( lin ) ) {
 274                         tax.getLineage().add( lin );
 275                     }
 276                 }
 277             }
 278
 279         }
 280         for( final PhylogenyNode desc : descs ) {
 281             if ( !desc.isExternal() && desc.getNodeData().isHasTaxonomy()
 282                     && desc.getNodeData().getTaxonomy().isEqual( tax ) ) {
 283                 desc.getNodeData().setTaxonomy( null );
 284             }
 285         }
 286     }
 287
 288     synchronized private static boolean isHasAppropriateId( final Taxonomy tax ) {
 289         return ( ( tax.getIdentifier() != null ) && ( !ForesterUtil.isEmpty( tax.getIdentifier().getValue() ) && ( tax
 290                 .getIdentifier().getProvider().equalsIgnoreCase( "ncbi" )
 291                 || tax.getIdentifier().getProvider().equalsIgnoreCase( "uniprot" ) || tax.getIdentifier().getProvider()
 292                 .equalsIgnoreCase( "uniprotkb" ) ) ) );
 293     }
 294
 295     synchronized public static SortedSet<String> obtainDetailedTaxonomicInformation( final Phylogeny phy,
 296                                                                                      final boolean delete )
 297             throws IOException {
 298         clearCachesIfTooLarge();
 299         final SortedSet<String> not_found = new TreeSet<String>();
 300         List<PhylogenyNode> not_found_external_nodes = null;
 301         if ( delete ) {
 302             not_found_external_nodes = new ArrayList<PhylogenyNode>();
 303         }
 304         for( final PhylogenyNodeIterator iter = phy.iteratorPostorder(); iter.hasNext(); ) {
 305             final PhylogenyNode node = iter.next();
 306             final QUERY_TYPE qt = null;
 307             Taxonomy tax = null;
 308             if ( node.getNodeData().isHasTaxonomy() ) {
 309                 tax = node.getNodeData().getTaxonomy();
 310             }
 311             else if ( node.isExternal() ) {
 312                 if ( !ForesterUtil.isEmpty( node.getName() ) ) {
 313                     not_found.add( node.getName() );
 314                 }
 315                 else {
 316                     not_found.add( node.toString() );
 317                 }
 318                 if ( delete ) {
 319                     not_found_external_nodes.add( node );
 320                 }
 321             }
 322             UniProtTaxonomy uniprot_tax = null;
 323             if ( ( tax != null )
 324                     && ( isHasAppropriateId( tax ) || !ForesterUtil.isEmpty( tax.getScientificName() )
 325                             || !ForesterUtil.isEmpty( tax.getTaxonomyCode() ) || !ForesterUtil.isEmpty( tax
 326                             .getCommonName() ) ) ) {
 327                 uniprot_tax = obtainUniProtTaxonomy( tax, null, qt );
 328                 if ( uniprot_tax != null ) {
 329                     updateTaxonomy( qt, node, tax, uniprot_tax );
 330                 }
 331                 else {
 332                     not_found.add( tax.toString() );
 333                     if ( delete && node.isExternal() ) {
 334                         not_found_external_nodes.add( node );
 335                     }
 336                 }
 337             }
 338         }
 339         if ( delete ) {
 340             for( final PhylogenyNode node : not_found_external_nodes ) {
 341                 phy.deleteSubtree( node, true );
 342             }
 343             phy.externalNodesHaveChanged();
 344             phy.hashIDs();
 345             phy.recalculateNumberOfExternalDescendants( true );
 346         }
 347         return not_found;
 348     }
 349
 350     // TODO this might not be needed anymore
 351     //  synchronized private static String[] obtainLineagePlusOwnScientificName( final UniProtTaxonomy up_tax ) {
 352     //      final String[] lineage = up_tax.getLineageAsArray();
 353     //      final String[] lin_plus_self = new String[ lineage.length + 1 ];
 354     //      for( int i = 0; i < lineage.length; ++i ) {
 355     //          lin_plus_self[ i ] = lineage[ i ];
 356     //      }
 357     //      lin_plus_self[ lineage.length ] = up_tax.getScientificName();
 358     //      return lin_plus_self;
 359     //  }
 360     synchronized private static UniProtTaxonomy obtainUniProtTaxonomy( final Taxonomy tax, String query, QUERY_TYPE qt )
 361             throws IOException {
 362         if ( isHasAppropriateId( tax ) ) {
 363             query = tax.getIdentifier().getValue();
 364             qt = QUERY_TYPE.ID;
 365             System.out.println( "query by id: " + query);
 366             return getTaxonomies( getIdTaxCacheMap(), query, qt );
 367         }
 368         else if ( !ForesterUtil.isEmpty( tax.getScientificName() ) ) {
 369             query = tax.getScientificName();
 370             qt = QUERY_TYPE.SN;
 371             System.out.println( "query by sn: " + query);
 372             return getTaxonomies( getSnTaxCacheMap(), query, qt );
 373         }
 374         else if ( !ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ) {
 375             query = tax.getTaxonomyCode();
 376             qt = QUERY_TYPE.CODE;
 377             return getTaxonomies( getCodeTaxCacheMap(), query, qt );
 378         }
 379         else {
 380             query = tax.getCommonName();
 381             qt = QUERY_TYPE.CN;
 382             return getTaxonomies( getCnTaxCacheMap(), query, qt );
 383         }
 384     }
 385
 386     synchronized private static UniProtTaxonomy obtainUniProtTaxonomyFromSn( final String sn) throws IOException {
 387         UniProtTaxonomy up_tax = null;
 388         if ( getSnTaxCacheMap().containsKey( sn ) ) {
 389             up_tax = getSnTaxCacheMap().get( sn ).copy();
 390         }
 391         else {
 392             final List<UniProtTaxonomy> up_taxonomies = getTaxonomiesFromScientificName( sn );
 393             if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
 394                 up_tax = up_taxonomies.get( 0 );
 395                 getSnTaxCacheMap().put( sn, up_tax );
 396                 if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
 397                     getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
 398                 }
 399                 if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 400                     getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
 401                 }
 402                 if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 403                     getIdTaxCacheMap().put( up_tax.getId(), up_tax );
 404                 }
 405
 406             }
 407         }
 408         return up_tax;
 409     }
 410
 411     synchronized private static UniProtTaxonomy obtainUniProtTaxonomyFromCommonLineage( List<String> lineage ) throws IOException {
 412         UniProtTaxonomy up_tax = null;
 413       // -- if ( getSnTaxCacheMap().containsKey( sn ) ) {
 414       // --     up_tax = getSnTaxCacheMap().get( sn ).copy();
 415       // -- }
 416       //  else {
 417             final List<UniProtTaxonomy> up_taxonomies = getTaxonomiesFromScientificName( lineage.get(lineage.size() -1 ) );
 418             //-- if ( ( up_taxonomies != null ) && ( up_taxonomies.size() == 1 ) ) {
 419
 420             if ( ( up_taxonomies != null ) && ( up_taxonomies.size() > 0 ) ) {
 421                 for( UniProtTaxonomy up_taxonomy : up_taxonomies ) {
 422                     boolean match = true;
 423
 424                     I: for( int i = 0; i < lineage.size(); ++i ) {
 425                         if ( !lineage.get( i ).equalsIgnoreCase( up_taxonomy.getLineage().get( i ) )  ) {
 426                             match = false;
 427                             break I;
 428                         }
 429                     }
 430                     if ( match ) {
 431                         if ( up_tax != null ) {
 432                             throw new IOException( "not unique!");
 433                         }
 434                         up_tax = up_taxonomy;
 435                     }
 436                 }
 437
 438                 if ( up_tax == null ) {
 439                     throw new IOException( "not found!");
 440                 }
 441                 //-- up_tax = up_taxonomies.get( 0 );
 442                //-- getSnTaxCacheMap().put( sn, up_tax );
 443                 if ( !ForesterUtil.isEmpty( up_tax.getCode() ) ) {
 444                     getCodeTaxCacheMap().put( up_tax.getCode(), up_tax );
 445                 }
 446                 if ( !ForesterUtil.isEmpty( up_tax.getCommonName() ) ) {
 447                     getCnTaxCacheMap().put( up_tax.getCommonName(), up_tax );
 448                 }
 449                 if ( !ForesterUtil.isEmpty( up_tax.getId() ) ) {
 450                     getIdTaxCacheMap().put( up_tax.getId(), up_tax );
 451                 }
 452
 453             }
 454       //  }
 455         return up_tax;
 456     }
 457
 458     synchronized private static void updateTaxonomy( final QUERY_TYPE qt,
 459                                                      final PhylogenyNode node,
 460                                                      final Taxonomy tax,
 461                                                      final UniProtTaxonomy up_tax ) {
 462         if ( ( qt != QUERY_TYPE.SN ) && !ForesterUtil.isEmpty( up_tax.getScientificName() )
 463                 && ForesterUtil.isEmpty( tax.getScientificName() ) ) {
 464             tax.setScientificName( up_tax.getScientificName() );
 465         }
 466         //  if ( node.isExternal()
 467         if ( ( qt != QUERY_TYPE.CODE ) && !ForesterUtil.isEmpty( up_tax.getCode() )
 468                 && ForesterUtil.isEmpty( tax.getTaxonomyCode() ) ) {
 469             tax.setTaxonomyCode( up_tax.getCode() );
 470         }
 471         if ( ( qt != QUERY_TYPE.CN ) && !ForesterUtil.isEmpty( up_tax.getCommonName() )
 472                 && ForesterUtil.isEmpty( tax.getCommonName() ) ) {
 473             tax.setCommonName( up_tax.getCommonName() );
 474         }
 475         if ( !ForesterUtil.isEmpty( up_tax.getSynonym() ) && !tax.getSynonyms().contains( up_tax.getSynonym() ) ) {
 476             tax.getSynonyms().add( up_tax.getSynonym() );
 477         }
 478         if ( !ForesterUtil.isEmpty( up_tax.getRank() ) && ForesterUtil.isEmpty( tax.getRank() ) ) {
 479             try {
 480                 tax.setRank( up_tax.getRank().toLowerCase() );
 481             }
 482             catch ( final PhyloXmlDataFormatException ex ) {
 483                 tax.setRank( "" );
 484             }
 485         }
 486         if ( ( qt != QUERY_TYPE.ID ) && !ForesterUtil.isEmpty( up_tax.getId() ) && ( tax.getIdentifier() == null ) ) {
 487             tax.setIdentifier( new Identifier( up_tax.getId(), "uniprot" ) );
 488         }
 489         if ( up_tax.getLineage() != null ) {
 490             tax.setLineage( new ArrayList<String>() );
 491             for( final String lin : up_tax.getLineage() ) {
 492                 if ( !ForesterUtil.isEmpty( lin ) ) {
 493                     tax.getLineage().add( lin );
 494                 }
 495             }
 496         }
 497
 498     }
 499
 500     private enum QUERY_TYPE {
 501         CODE, SN, CN, ID;
 502     }
 503 }