kmer.cpp

   1 /*
   2  *  kmer.cpp
   3  *
   4  *
   5  *  Created by Pat Schloss on 12/15/08.
   6  *  Copyright 2008 Patrick D. Schloss. All rights reserved.
   7  *
   8  */
   9
  10 using namespace std;
  11
  12
  13 #include "kmer.hpp"
  14
  15 /**************************************************************************************************/
  16
  17 Kmer::Kmer(int size) : kmerSize(size) { //      The constructor sets the size of the kmer
  18
  19         int power4s[14] = { 1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864 };
  20                                                                                                                                                 //      No reason to waste the time of recalculating
  21         maxKmer = power4s[kmerSize]+1;// (int)pow(4.,k)+1;                                      //      powers of 4 everytime through.  We need an
  22                                                                                                                                                 //      extra kmer if we get a non-ATGCU base
  23 }
  24
  25 /**************************************************************************************************/
  26
  27 string Kmer::getKmerString(string sequence){    //      Calculate kmer for each position in the sequence, count the freq
  28         int length = sequence.length();                         //      of each kmer, and convert it to an ascii character with base '!'.
  29         int nKmers = length - kmerSize + 1;                     //      Export the string of characters as a string
  30         vector<int> counts(maxKmer, 0);
  31
  32         for(int i=0;i<nKmers;i++){                                      //      Go though sequence and get the number between 0 and maxKmer for that
  33                 int kmerNumber = getKmerNumber(sequence, i);//  kmer.  Increase the count for the kmer in the counts vector
  34                 counts[kmerNumber]++;
  35         }
  36
  37         string kmerString = "";
  38         for(int i=0;i<maxKmer;i++){                                     //      Scan through the vector of counts and convert each element of the
  39                 kmerString += getASCII(counts[i]);              //      vector to an ascii character that is equal to or greater than '!'
  40         }
  41
  42         return kmerString;
  43 }
  44
  45 /**************************************************************************************************/
  46
  47 int Kmer::getKmerNumber(string sequence, int index){
  48
  49 //      Here we convert a kmer to a number between 0 and maxKmer.  For example, AAAA would equal 0 and TTTT would equal 255.
  50 //      If there's an N in the kmer, it is set to 256 (if we are looking at 4mers).  The largest we can look at are 8mers,
  51 //      this could be easily increased.
  52 //
  53 //      Example:   ATGCAT (kSize = 6)
  54 //                i:   012345
  55 //
  56 //              Score   = 0*4^(6-0-1) + 3*4^(6-1-1) + 2*4^(6-2-1) + 1*4^(6-3-1) + 0*4^(6-4-1) + 3*4^(6-5-1)
  57 //                              = 0*4^5 +       3*4^4   +       2*4^3   +       1*4^2   +       0*4^1   +       3*4^0
  58 //                              = 0 + 3*256 + 2*64 + 1*16 + 0*4 + 3*1
  59 //                              = 0 + 768 + 128 + 16 + 0 + 3
  60 //                              = 915
  61
  62         int power4s[14] = { 1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864 };
  63
  64         int kmer = 0;
  65
  66         for(int i=0;i<kmerSize;i++){
  67                 if(toupper(sequence[i+index]) == 'A')           {       kmer += (0 * power4s[kmerSize-i-1]);    }
  68                 else if(toupper(sequence[i+index]) == 'C')      {       kmer += (1 * power4s[kmerSize-i-1]);    }
  69                 else if(toupper(sequence[i+index]) == 'G')      {       kmer += (2 * power4s[kmerSize-i-1]);    }
  70                 else if(toupper(sequence[i+index]) == 'U')      {       kmer += (3 * power4s[kmerSize-i-1]);    }
  71                 else if(toupper(sequence[i+index]) == 'T')      {       kmer += (3 * power4s[kmerSize-i-1]);    }
  72                 else if(toupper(sequence[i+index]) == 'N')      {       return (int)power4s[kmerSize];                  }
  73         }
  74         return kmer;
  75 }
  76
  77 /**************************************************************************************************/
  78
  79 string Kmer::getKmerBases(int kmerNumber){
  80
  81 //      Here we convert the kmer number into the kmer in terms of bases.
  82 //
  83 //      Example:        Score = 915 (for a 6-mer)
  84 //                              Base6 = (915 / 4^0) % 4 = 915 % 4 = 3 => T      [T]
  85 //                              Base5 = (915 / 4^1) % 4 = 228 % 4 = 0 => A      [AT]
  86 //                              Base4 = (915 / 4^2) % 4 = 57 % 4 = 1 => C       [CAT]
  87 //                              Base3 = (915 / 4^3) % 4 = 14 % 4 = 2 => G       [GCAT]
  88 //                              Base2 = (915 / 4^4) % 4 = 3 % 4 = 3 => T        [TGCAT]
  89 //                              Base1 = (915 / 4^5) % 4 = 0 % 4 = 0 => A        [ATGCAT] -> this checks out with the previous method
  90
  91         int power4s[14] = { 1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864 };
  92
  93         string kmer = "";
  94
  95         if(kmerNumber == power4s[kmerSize]){//pow(4.,7)){       //      if the kmer number is the same as the maxKmer then it must
  96                 for(int i=0;i<kmerSize;i++){                                    //      have had an N in it and so we'll just call it N x kmerSize
  97                         kmer += 'N';
  98                 }
  99         }
 100         else{
 101                 for(int i=0;i<kmerSize;i++){
 102                         int nt = (int)(kmerNumber / (float)power4s[i]) % 4;             //      the '%' operator returns the remainder
 103                         if(nt == 0)             {       kmer = 'A' + kmer;      }                               //      from int-based division ]
 104                         else if(nt == 1){       kmer = 'C' + kmer;      }
 105                         else if(nt == 2){       kmer = 'G' + kmer;      }
 106                         else if(nt == 3){       kmer = 'T' + kmer;      }
 107                 }
 108         }
 109         return kmer;
 110 }
 111
 112 /**************************************************************************************************/
 113
 114 char Kmer::getASCII(int number)         {       return (char)(33+number);                       }       // '!' is the first printable char and
 115                                                                                                                                                                 // has the int value of 33
 116 /**************************************************************************************************/
 117
 118 int Kmer::getNumber(char character)     {       return ((int)(character-'!'));          }       // '!' has the value of 33
 119
 120 /**************************************************************************************************/