Branch data Line data Source code
1 : : // $Id: SmithWaterman.h 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #ifndef smith_waterman_h
6 : : #define smith_waterman_h
7 : :
8 : : #include "BroString.h"
9 : : #include <map>
10 : : using namespace std;
11 : :
12 : : // BroSubstrings are essentially BroStrings, augmented with indexing
13 : : // information required for the Smith-Waterman algorithm. Each substring
14 : : // can be marked as being a common substring of arbitrarily many strings,
15 : : // for each of which we store where the substring starts.
16 : : //
17 : : //
18 : 0 : class BroSubstring : public BroString {
19 : :
20 : : public:
21 : : typedef vector<BroSubstring*> Vec;
22 : : typedef Vec::iterator VecIt;
23 : : typedef Vec::const_iterator VecCIt;
24 : :
25 : : // An alignment to another string.
26 : : //
27 : 0 : struct BSSAlign {
28 : :
29 : 0 : BSSAlign(const BroString* string, int index)
30 : 0 : { this->string = string; this->index = index; }
31 : :
32 : : // The other string
33 : : //
34 : : const BroString* string;
35 : :
36 : : // Offset in the string that substring
37 : : // starts at, counting from 0.
38 : : //
39 : : int index;
40 : : };
41 : :
42 : : typedef vector<BSSAlign> BSSAlignVec;
43 : : typedef BSSAlignVec::iterator BSSAlignVecIt;
44 : : typedef BSSAlignVec::const_iterator BSSAlignVecCIt;
45 : :
46 : 0 : BroSubstring(const string& string)
47 : 0 : : BroString(string), _new(false) { }
48 : :
49 : 0 : BroSubstring(const BroString& string)
50 : 0 : : BroString(string), _new(false) { }
51 : :
52 : : BroSubstring(const BroSubstring& bst);
53 : :
54 : : const BroSubstring& operator=(const BroSubstring& bst);
55 : :
56 : : // Returns true if this string completely covers the given one.
57 : : // "Covering" means that the substring must be at least as long
58 : : // as the one compared to, and completely covers the range occupied
59 : : // by the given one.
60 : : //
61 : : bool DoesCover(const BroSubstring* bst) const;
62 : :
63 : : void AddAlignment(const BroString* string, int index);
64 : 0 : const BSSAlignVec& GetAlignments() const { return _aligns; }
65 : 0 : unsigned int GetNumAlignments() const { return _aligns.size(); }
66 : :
67 : : void SetNum(int num) { _num = num; }
68 : : int GetNum() const { return _num; }
69 : :
70 : 0 : void MarkNewAlignment(bool mark) { _new = mark; }
71 : 0 : bool IsNewAlignment() { return _new; }
72 : :
73 : : // Helper methods for vectors:
74 : : //
75 : : static VectorVal* VecToPolicy(Vec* vec);
76 : : static Vec* VecFromPolicy(VectorVal* vec);
77 : : static char* VecToString(Vec* vec);
78 : : static BroString::IdxVec* GetOffsetsVec(const Vec* vec,
79 : : unsigned int index);
80 : :
81 : : private:
82 : : typedef map<string, void*> DataMap;
83 : : typedef DataMap::iterator DataMapIt;
84 : :
85 : : BroSubstring();
86 : :
87 : : // The alignments registered for this substring.
88 : : BSSAlignVec _aligns;
89 : :
90 : : // Every substring can have a numerical label.
91 : : int _num;
92 : :
93 : : // True if this node marks the start of a new alignment.
94 : : bool _new;
95 : : };
96 : :
97 : : // A comparison class that sorts BroSubstrings according to the string
98 : : // offset value of the nth input string, where "nth" starts from 0.
99 : : //
100 : : class BroSubstringCmp {
101 : : public:
102 : 0 : BroSubstringCmp(unsigned int index) { _index = index; }
103 : : bool operator()(const BroSubstring* bst1, const BroSubstring* bst2) const;
104 : :
105 : : private:
106 : : unsigned int _index;
107 : : };
108 : :
109 : : // Smith-Waterman Implementation
110 : : // ---------------------------------------------------------------------
111 : : //
112 : :
113 : : // We support two modes of operation: finding a single optimal alignment,
114 : : // and repeated alignments.
115 : : //
116 : : enum SWVariant {
117 : : SW_SINGLE = 0, // return a single, optimum alignment
118 : : SW_MULTIPLE = 1, // find repeated, non-overlapping alignments
119 : : };
120 : :
121 : : // Parameters for Smith-Waterman are stored in this simple record.
122 : : //
123 : : struct SWParams {
124 : 0 : SWParams(unsigned int min_toklen = 3, SWVariant sw_variant = SW_SINGLE)
125 : : {
126 : 0 : _min_toklen = min_toklen;
127 : 0 : _sw_variant = sw_variant;
128 : 0 : }
129 : :
130 : : // The minimum string size to report. For example, min_toklen = 2
131 : : // won't report any common single-letter subsequences.
132 : : unsigned int _min_toklen;
133 : :
134 : : SWVariant _sw_variant;
135 : : };
136 : :
137 : :
138 : : // The smith_waterman() algorithm finds the longest common subsequence(s)
139 : : // of two strings, also known as the best local alignment. A subsequence
140 : : // is a sequence of common substrings.
141 : : //
142 : : // s1: first input string
143 : : // s2: second input string
144 : : // params: Smith-Waterman parameters.
145 : : //
146 : : // Subsequences of a string are any strings based on the original one
147 : : // with individual characters left out. Note that this is different
148 : : // from the longest common substring problem.
149 : : //
150 : : // The function returns a vector consisting of all substrings comprising
151 : : // the subsequence. With each string you also get the indices of both
152 : : // input strings where the string occurs. On error, or if no common
153 : : // subsequence exists, an empty vector is returned.
154 : : //
155 : : extern BroSubstring::Vec* smith_waterman(const BroString* s1,
156 : : const BroString* s2,
157 : : SWParams& params);
158 : :
159 : : #endif
|
