1 //uchime by Robert C. Edgar http://drive5.com/uchime This code is donated to the public domain.
\r
11 #include "diagbox.h"
\r
13 #include "alnparams.h"
\r
14 #include "alnheuristics.h"
\r
15 #include "hspfinder.h"
\r
17 typedef void (*OnPathFn)(const string &Path, bool Full);
\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
30 float ViterbiSimple(const byte *A, unsigned LA, const byte *B, unsigned LB,
\r
31 const AlnParams &AP, PathData &PD);
\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
36 float ViterbiFast(const byte *A, unsigned LA, const byte *B, unsigned LB,
\r
37 const AlnParams &AP, PathData &PD);
\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
42 float ViterbiFastMainDiag(const byte *A, unsigned LA, const byte *B, unsigned LB,
\r
43 unsigned BandRadius, const AlnParams &AP, PathData &PD);
\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
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
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
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
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
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
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
69 void SWFast2(const SeqData &SA, const SeqData &SB, const AlnParams &AP,
\r
70 HSPData &HSP, PathData &PD);
\r
72 void SWSimple2(const SeqData &SA, const SeqData &SB, const AlnParams &AP,
\r
73 HSPData &HSP, PathData &PD);
\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
78 void SWUngapped2(const SeqData &SA, const SeqData &SB, const AlnParams &AP,
\r
81 float SWFastNTB(const byte *A, unsigned LA, const byte *B, unsigned LB,
\r
82 const AlnParams &AP);
\r
84 void GlobalAlignBand(const byte *A, unsigned LA, const byte *B, unsigned LB,
\r
85 const AlnParams &AP, unsigned BandRadius, PathData &PD);
\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
91 bool GlobalAlign(const SeqData &Query, const SeqData &Target, string &Path);
\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
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
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
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
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
121 static inline void Max_xM(float &Score, float MM, float DM, float IM, byte &State)
\r
138 static inline void Max_xD(float &Score, float MD, float DD, byte &State)
\r
152 static inline void Max_xI(float &Score, float MI, float II, byte &State)
\r