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