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