forester/java/src/org/forester/evoinference/distance/PairwiseDistanceCalculator.java

   1 // $Id:
   2 // forester -- software libraries and applications
   3 // for genomics and evolutionary biology research.
   4 //
   5 // Copyright (C) 2010 Christian M Zmasek
   6 // Copyright (C) 2010 Sanford-Burnham Medical Research 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: phylosoft @ gmail . com
  24 // WWW: www.phylosoft.org/forester
  25
  26 package org.forester.evoinference.distance;
  27
  28 import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix;
  29 import org.forester.msa.Msa;
  30 import org.forester.sequence.Sequence;
  31
  32 public final class PairwiseDistanceCalculator {
  33
  34     public static final double DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA = 10;          // Felsenstein uses -1
  35     private static final char  GAP                                                     = Sequence.GAP;
  36     private final Msa          _msa;
  37     private final double       _value_for_too_large_distance_for_kimura_formula;
  38
  39     private PairwiseDistanceCalculator( final Msa msa, final double value_for_too_large_distance_for_kimura_formula ) {
  40         _msa = msa;
  41         _value_for_too_large_distance_for_kimura_formula = value_for_too_large_distance_for_kimura_formula;
  42     }
  43
  44     private double calcFractionalDissimilarity( final int row_1, final int row_2 ) {
  45         final int length = _msa.getLength();
  46         int nd = 0;
  47         int n = 0;
  48         char aa_1;
  49         char aa_2;
  50         for( int col = 0; col < length; ++col ) {
  51             aa_1 = _msa.getResidueAt( row_1, col );
  52             aa_2 = _msa.getResidueAt( row_2, col );
  53             if ( ( aa_1 != GAP ) && ( aa_2 != GAP ) ) {
  54                 if ( aa_1 != aa_2 ) {
  55                     nd++;
  56                 }
  57                 n++;
  58             }
  59         }
  60         if ( n == 0 ) {
  61             return 1;
  62         }
  63         return ( double ) nd / n;
  64     }
  65
  66     /**
  67      * "Kimura Distance"
  68      * Kimura, 1983
  69      *
  70      * @param row_1
  71      * @param row_2
  72      * @return
  73      */
  74     private double calcKimuraDistance( final int row_1, final int row_2 ) {
  75         final double p = calcFractionalDissimilarity( row_1, row_2 );
  76         final double dp = 1 - p - ( 0.2 * p * p );
  77         if ( dp <= 0.0 ) {
  78             return _value_for_too_large_distance_for_kimura_formula;
  79         }
  80         if ( dp == 1 ) {
  81             return 0; // Too avoid -0.
  82         }
  83         return -Math.log( dp );
  84     }
  85
  86     private double calcPoissonDistance( final int row_1, final int row_2 ) {
  87         final double p = calcFractionalDissimilarity( row_1, row_2 );
  88         final double dp = 1 - p;
  89         if ( dp <= 0.0 ) {
  90             return _value_for_too_large_distance_for_kimura_formula;
  91         }
  92         if ( dp == 1 ) {
  93             return 0; // Too avoid -0.
  94         }
  95         return -Math.log( dp );
  96     }
  97
  98     private BasicSymmetricalDistanceMatrix calcKimuraDistances() {
  99         final int s = _msa.getNumberOfSequences();
 100         final BasicSymmetricalDistanceMatrix d = new BasicSymmetricalDistanceMatrix( s );
 101         copyIdentifiers( s, d );
 102         calcKimuraDistances( s, d );
 103         return d;
 104     }
 105
 106     private BasicSymmetricalDistanceMatrix calcPoissonDistances() {
 107         final int s = _msa.getNumberOfSequences();
 108         final BasicSymmetricalDistanceMatrix d = new BasicSymmetricalDistanceMatrix( s );
 109         copyIdentifiers( s, d );
 110         calcPoissonDistances( s, d );
 111         return d;
 112     }
 113
 114     private BasicSymmetricalDistanceMatrix calcFractionalDissimilarities() {
 115         final int s = _msa.getNumberOfSequences();
 116         final BasicSymmetricalDistanceMatrix d = new BasicSymmetricalDistanceMatrix( s );
 117         copyIdentifiers( s, d );
 118         calcFractionalDissimilarities( s, d );
 119         return d;
 120     }
 121
 122     private void calcKimuraDistances( final int s, final BasicSymmetricalDistanceMatrix d ) {
 123         for( int i = 1; i < s; i++ ) {
 124             for( int j = 0; j < i; j++ ) {
 125                 d.setValue( i, j, calcKimuraDistance( i, j ) );
 126             }
 127         }
 128     }
 129
 130     private void calcPoissonDistances( final int s, final BasicSymmetricalDistanceMatrix d ) {
 131         for( int i = 1; i < s; i++ ) {
 132             for( int j = 0; j < i; j++ ) {
 133                 d.setValue( i, j, calcPoissonDistance( i, j ) );
 134             }
 135         }
 136     }
 137
 138     private void calcFractionalDissimilarities( final int s, final BasicSymmetricalDistanceMatrix d ) {
 139         for( int i = 1; i < s; i++ ) {
 140             for( int j = 0; j < i; j++ ) {
 141                 d.setValue( i, j, calcFractionalDissimilarity( i, j ) );
 142             }
 143         }
 144     }
 145
 146     @Override
 147     public Object clone() throws CloneNotSupportedException {
 148         throw new CloneNotSupportedException();
 149     }
 150
 151     private void copyIdentifiers( final int s, final BasicSymmetricalDistanceMatrix d ) {
 152         for( int i = 0; i < s; i++ ) {
 153             d.setIdentifier( i, ( String ) _msa.getIdentifier( i ) );
 154         }
 155     }
 156
 157     public static BasicSymmetricalDistanceMatrix calcFractionalDissimilarities( final Msa msa ) {
 158         return new PairwiseDistanceCalculator( msa, DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA )
 159                 .calcFractionalDissimilarities();
 160     }
 161
 162     public static BasicSymmetricalDistanceMatrix calcPoissonDistances( final Msa msa ) {
 163         return new PairwiseDistanceCalculator( msa, DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA )
 164                 .calcPoissonDistances();
 165     }
 166
 167     public static BasicSymmetricalDistanceMatrix calcKimuraDistances( final Msa msa ) {
 168         return new PairwiseDistanceCalculator( msa, DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA )
 169                 .calcKimuraDistances();
 170     }
 171
 172     public static BasicSymmetricalDistanceMatrix calcKimuraDistances( final Msa msa,
 173                                                                       final double value_for_too_large_distance_for_kimura_formula ) {
 174         return new PairwiseDistanceCalculator( msa, value_for_too_large_distance_for_kimura_formula )
 175                 .calcKimuraDistances();
 176     }
 177
 178     public enum PWD_DISTANCE_METHOD {
 179         KIMURA_DISTANCE, POISSON_DISTANCE, FRACTIONAL_DISSIMILARITY;
 180     }
 181 }