dp.h

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