uchime_src/dp.h

   1 #ifndef dp_h\r
   2 #define dp_h\r
   3 \r
   4 #define SAVE_FAST       0\r
   5 \r
   6 #include "myutils.h"\r
   7 #include "mx.h"\r
   8 #include "seqdb.h"\r
   9 #include "diagbox.h"\r
  10 #include "path.h"\r
  11 #include "alnparams.h"\r
  12 #include "alnheuristics.h"\r
  13 #include "hspfinder.h"\r
  14 \r
  15 typedef void (*OnPathFn)(const string &Path, bool Full);\r
  16 \r
  17 enum XType\r
  18         {\r
  19         XType_Full=1,\r
  20         XType_Fwd=2,\r
  21         XType_Bwd=3,\r
  22         };\r
  23 \r
  24 // public\r
  25 float ViterbiBrute(const byte *A, unsigned LA, const byte *B, unsigned LB, \r
  26   unsigned DiagLo, unsigned DiagHi, const AlnParams &AP, PathData &PD);\r
  27 \r
  28 float ViterbiSimple(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  29   const AlnParams &AP, PathData &PD);\r
  30 \r
  31 float ViterbiSimpleBand(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  32   const AlnParams &AP, unsigned DiagLo, unsigned DiagHi, PathData &PD);\r
  33 \r
  34 float ViterbiFast(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  35   const AlnParams &AP, PathData &PD);\r
  36 \r
  37 float ViterbiFastBand(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  38   unsigned DiagLo, unsigned DiagHi, const AlnParams &AP, PathData &PD);\r
  39 \r
  40 float ViterbiFastMainDiag(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  41   unsigned BandRadius, const AlnParams &AP, PathData &PD);\r
  42 \r
  43 float XDropFwdSimple(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  44   const AlnParams &AP, float XDrop, unsigned &Leni, unsigned &Lenj, PathData &PD);\r
  45 \r
  46 float XDropBwdSimple(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  47   const AlnParams &AP, float XDrop, unsigned &Leni, unsigned &Lenj, PathData &PD);\r
  48 \r
  49 float XDropFwdFast(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  50   const AlnParams &AP, float XDrop, unsigned &Leni, unsigned &Lenj, PathData &PD);\r
  51 \r
  52 float XDropBwdFast(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  53   const AlnParams &AP, float XDrop, unsigned &Leni, unsigned &Lenj, PathData &PD);\r
  54 \r
  55 void XDropAlign(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  56   unsigned AncLoi, unsigned AncLoj, unsigned AncLen, const AlnParams &AP,\r
  57   float XDrop, HSPData &HSP, PathData &PD);\r
  58 \r
  59 float SWSimple(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  60   const AlnParams &AP, unsigned &Loi, unsigned &Leni, unsigned &Lenj,\r
  61   unsigned &Hij, PathData &PD);\r
  62 \r
  63 float SWFast(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  64   const AlnParams &AP, unsigned &Loi, unsigned &Leni, unsigned &Lenj,\r
  65   unsigned &Hij, PathData &PD);\r
  66 \r
  67 void SWFast2(const SeqData &SA, const SeqData &SB, const AlnParams &AP,\r
  68   HSPData &HSP, PathData &PD);\r
  69 \r
  70 void SWSimple2(const SeqData &SA, const SeqData &SB, const AlnParams &AP,\r
  71   HSPData &HSP, PathData &PD);\r
  72 \r
  73 float SWUngapped(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  74   const float * const *SubstMx, unsigned &LoA, unsigned &LoB, unsigned &Len);\r
  75 \r
  76 void SWUngapped2(const SeqData &SA, const SeqData &SB, const AlnParams &AP,\r
  77   HSPData &HSP);\r
  78 \r
  79 float SWFastNTB(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  80   const AlnParams &AP);\r
  81 \r
  82 void GlobalAlignBand(const byte *A, unsigned LA, const byte *B, unsigned LB,\r
  83   const AlnParams &AP, unsigned BandRadius, PathData &PD);\r
  84 \r
  85 bool GlobalAlign(const SeqData &Query, const SeqData &Target, const AlnParams &AP,\r
  86   const AlnHeuristics &AH, HSPFinder &HF, float MinFractId, float &HSPFractId,\r
  87   PathData &PD);\r
  88 \r
  89 bool GlobalAlign(const SeqData &Query, const SeqData &Target, string &Path);\r
  90 \r
  91 void GetBruteMxs(Mx<float> **M, Mx<float> **D, Mx<float> **I);\r
  92 void GetSimpleDPMxs(Mx<float> **M, Mx<float> **D, Mx<float> **I);\r
  93 void GetSimpleBandMxs(Mx<float> **M, Mx<float> **D, Mx<float> **I);\r
  94 void GetXDropFwdSimpleDPMxs(Mx<float> **M, Mx<float> **D, Mx<float> **I);\r
  95 #if     SAVE_FAST\r
  96 void GetFastMxs(Mx<float> **M, Mx<float> **D, Mx<float> **I);\r
  97 void GetFastBandMxs(Mx<float> **M, Mx<float> **D, Mx<float> **I);\r
  98 #endif\r
  99 \r
 100 // private\r
 101 void TraceBackBit(unsigned LA, unsigned LB, char State, PathData &PD);\r
 102 void TraceBackBitSW(unsigned LA, unsigned LB, unsigned Besti, unsigned Bestj,\r
 103   unsigned &Leni, unsigned &Lenj, PathData &PD);\r
 104 void EnumPaths(unsigned L1, unsigned L2, bool SubPaths, OnPathFn OnPath);\r
 105 void AllocBit(unsigned LA, unsigned LB);\r
 106 \r
 107 const byte TRACEBITS_DM = 0x01;\r
 108 const byte TRACEBITS_IM = 0x02;\r
 109 const byte TRACEBITS_MD = 0x04;\r
 110 const byte TRACEBITS_MI = 0x08;\r
 111 const byte TRACEBITS_SM = 0x10;\r
 112 const byte TRACEBITS_UNINIT = ~0x1f;\r
 113 \r
 114 extern Mx<byte> g_Mx_TBBit;\r
 115 extern float *g_DPRow1;\r
 116 extern float *g_DPRow2;\r
 117 extern byte **g_TBBit;\r
 118 \r
 119 static inline void Max_xM(float &Score, float MM, float DM, float IM, byte &State)\r
 120         {\r
 121         Score = MM;\r
 122         State = 'M';\r
 123 \r
 124         if (DM > Score)\r
 125                 {\r
 126                 Score = DM;\r
 127                 State = 'D';\r
 128                 }\r
 129         if (IM > Score)\r
 130                 {\r
 131                 Score = IM;\r
 132                 State = 'I';\r
 133                 }\r
 134         }\r
 135 \r
 136 static inline void Max_xD(float &Score, float MD, float DD, byte &State)\r
 137         {\r
 138         if (MD >= DD)\r
 139                 {\r
 140                 Score = MD;\r
 141                 State = 'M';\r
 142                 }\r
 143         else\r
 144                 {\r
 145                 Score = DD;\r
 146                 State = 'D';\r
 147                 }\r
 148         }\r
 149 \r
 150 static inline void Max_xI(float &Score, float MI, float II, byte &State)\r
 151         {\r
 152         if (MI >= II)\r
 153                 {\r
 154                 Score = MI;\r
 155                 State = 'M';\r
 156                 }\r
 157         else\r
 158                 {\r
 159                 Score = II;\r
 160                 State = 'I';\r
 161                 }\r
 162         }\r
 163 \r
 164 #endif // dp_h\r