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: https://sites.google.com/site/cmzmasek/home/software/forester
  25
  26 package org.forester.evoinference.distance;
  27
  28 import org.forester.evoinference.matrix.distance.BasicSymmetricalDistanceMatrix;
  29 import org.forester.evoinference.matrix.distance.DistanceMatrix;
  30 import org.forester.evoinference.matrix.distance.DistanceMatrix;
  31 import org.forester.msa.Msa;
  32
  33 public final class PairwiseDistanceCalculator {
  34
  35     public static final double DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA = 10; // Felsenstein uses -1
  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         for( int col = 0; col < length; ++col ) {
  48             if ( _msa.getResidueAt( row_1, col ) != _msa.getResidueAt( row_2, col ) ) {
  49                 ++nd;
  50             }
  51         }
  52         return ( double ) nd / length;
  53     }
  54
  55     /**
  56      * "Kimura Distance"
  57      * Kimura, 1983
  58      *
  59      * @param row_1
  60      * @param row_2
  61      * @return
  62      */
  63     private double calcKimuraDistance( final int row_1, final int row_2 ) {
  64         final double p = calcFractionalDissimilarity( row_1, row_2 );
  65         final double dp = 1 - p - ( 0.2 * p * p );
  66         if ( dp <= 0.0 ) {
  67             return _value_for_too_large_distance_for_kimura_formula;
  68         }
  69         if ( dp == 1 ) {
  70             return 0; // Too avoid -0.
  71         }
  72         return -Math.log( dp );
  73     }
  74
  75     private double calcPoissonDistance( final int row_1, final int row_2 ) {
  76         final double p = calcFractionalDissimilarity( row_1, row_2 );
  77         final double dp = 1 - p;
  78         if ( dp <= 0.0 ) {
  79             return _value_for_too_large_distance_for_kimura_formula;
  80         }
  81         if ( dp == 1 ) {
  82             return 0; // Too avoid -0.
  83         }
  84         return -Math.log( dp );
  85     }
  86
  87     private DistanceMatrix calcKimuraDistances() {
  88         final int s = _msa.getNumberOfSequences();
  89         final DistanceMatrix d = new BasicSymmetricalDistanceMatrix( s );
  90         copyIdentifiers( s, d );
  91         calcKimuraDistances( s, d );
  92         return d;
  93     }
  94
  95     private DistanceMatrix calcPoissonDistances() {
  96         final int s = _msa.getNumberOfSequences();
  97         final DistanceMatrix d = new BasicSymmetricalDistanceMatrix( s );
  98         copyIdentifiers( s, d );
  99         calcPoissonDistances( s, d );
 100         return d;
 101     }
 102
 103     private DistanceMatrix calcFractionalDissimilarities() {
 104         final int s = _msa.getNumberOfSequences();
 105         final DistanceMatrix d = new BasicSymmetricalDistanceMatrix( s );
 106         copyIdentifiers( s, d );
 107         calcFractionalDissimilarities( s, d );
 108         return d;
 109     }
 110
 111     private void calcKimuraDistances( final int s, final DistanceMatrix d ) {
 112         for( int i = 1; i < s; i++ ) {
 113             for( int j = 0; j < i; j++ ) {
 114                 d.setValue( i, j, calcKimuraDistance( i, j ) );
 115             }
 116         }
 117     }
 118
 119     private void calcPoissonDistances( final int s, final DistanceMatrix d ) {
 120         for( int i = 1; i < s; i++ ) {
 121             for( int j = 0; j < i; j++ ) {
 122                 d.setValue( i, j, calcPoissonDistance( i, j ) );
 123             }
 124         }
 125     }
 126
 127     private void calcFractionalDissimilarities( final int s, final DistanceMatrix d ) {
 128         for( int i = 1; i < s; i++ ) {
 129             for( int j = 0; j < i; j++ ) {
 130                 d.setValue( i, j, calcFractionalDissimilarity( i, j ) );
 131             }
 132         }
 133     }
 134
 135     @Override
 136     public Object clone() throws CloneNotSupportedException {
 137         throw new CloneNotSupportedException();
 138     }
 139
 140     private void copyIdentifiers( final int s, final DistanceMatrix d ) {
 141         for( int i = 0; i < s; i++ ) {
 142             d.setIdentifier( i, _msa.getIdentifier( i ) );
 143         }
 144     }
 145
 146     public static DistanceMatrix calcFractionalDissimilarities( final Msa msa ) {
 147         return new PairwiseDistanceCalculator( msa, DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA )
 148         .calcFractionalDissimilarities();
 149     }
 150
 151     public static DistanceMatrix calcPoissonDistances( final Msa msa ) {
 152         return new PairwiseDistanceCalculator( msa, DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA )
 153         .calcPoissonDistances();
 154     }
 155
 156     public static DistanceMatrix calcKimuraDistances( final Msa msa ) {
 157         return new PairwiseDistanceCalculator( msa, DEFAULT_VALUE_FOR_TOO_LARGE_DISTANCE_FOR_KIMURA_FORMULA )
 158         .calcKimuraDistances();
 159     }
 160
 161     public static DistanceMatrix calcKimuraDistances( final Msa msa,
 162                                                                       final double value_for_too_large_distance_for_kimura_formula ) {
 163         return new PairwiseDistanceCalculator( msa, value_for_too_large_distance_for_kimura_formula )
 164         .calcKimuraDistances();
 165     }
 166
 167     public enum PWD_DISTANCE_METHOD {
 168         KIMURA_DISTANCE, POISSON_DISTANCE, FRACTIONAL_DISSIMILARITY;
 169     }
 170 }