uchime_src/usort.cpp

   1 #if     UCHIMES\r
   2 \r
   3 #include "myutils.h"\r
   4 #include "seqdb.h"\r
   5 #include "seq.h"\r
   6 #include "alpha.h"\r
   7 \r
   8 void SortDescending(const vector<float> &Values, vector<unsigned> &Order);\r
   9 \r
  10 static byte *g_QueryHasWord;\r
  11 static unsigned g_WordCount;\r
  12 \r
  13 unsigned GetWord(const byte *Seq)\r
  14         {\r
  15         unsigned Word = 0;\r
  16         const byte *Front = Seq;\r
  17         for (unsigned i = 0; i < opt_w; ++i)\r
  18                 {\r
  19                 unsigned Letter = g_CharToLetterNucleo[*Front++];\r
  20                 Word = (Word*4) + Letter;\r
  21                 }\r
  22         return Word;\r
  23         }\r
  24 \r
  25 static void SetQuery(const SeqData &Query)\r
  26         {\r
  27         if (g_QueryHasWord == 0)\r
  28                 {\r
  29                 g_WordCount = 4;\r
  30                 for (unsigned i = 1; i < opt_w; ++i)\r
  31                         g_WordCount *= 4;\r
  32 \r
  33                 g_QueryHasWord = myalloc(byte, g_WordCount);\r
  34                 }\r
  35 \r
  36         memset(g_QueryHasWord, 0, g_WordCount);\r
  37 \r
  38         if (Query.L <= opt_w)\r
  39                 return;\r
  40 \r
  41         const unsigned L = Query.L - opt_w + 1;\r
  42         const byte *Seq = Query.Seq;\r
  43         for (unsigned i = 0; i < L; ++i)\r
  44                 {\r
  45                 unsigned Word = GetWord(Seq++);\r
  46                 g_QueryHasWord[Word] = 1;\r
  47                 }\r
  48         }\r
  49 \r
  50 static unsigned GetUniqueWordsInCommon(const SeqData &Target)\r
  51         {\r
  52         if (Target.L <= opt_w)\r
  53                 return 0;\r
  54 \r
  55         unsigned Count = 0;\r
  56         const unsigned L = Target.L - opt_w + 1;\r
  57         const byte *Seq = Target.Seq;\r
  58         for (unsigned i = 0; i < L; ++i)\r
  59                 {\r
  60                 unsigned Word = GetWord(Seq++);\r
  61                 if (g_QueryHasWord[Word])\r
  62                         ++Count;\r
  63                 }\r
  64         return Count;\r
  65         }\r
  66 \r
  67 void USort(const SeqData &Query, const SeqDB &DB, vector<float> &WordCounts, \r
  68   vector<unsigned> &Order)\r
  69         {\r
  70         WordCounts.clear();\r
  71         Order.clear();\r
  72 \r
  73         SetQuery(Query);\r
  74 \r
  75         const unsigned SeqCount = DB.GetSeqCount();\r
  76         for (unsigned SeqIndex = 0; SeqIndex < SeqCount; ++SeqIndex)\r
  77                 {\r
  78                 SeqData Target;\r
  79                 DB.GetSeqData(SeqIndex, Target);\r
  80                 float WordCount = (float) GetUniqueWordsInCommon(Target);\r
  81                 WordCounts.push_back(WordCount);\r
  82                 }\r
  83         SortDescending(WordCounts, Order);\r
  84         }\r
  85 \r
  86 #endif // UCHIMES\r