Debian Codegraph @

libkmer/existDB-create-from-fasta.C

raw
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <errno.h>
5 #include "existDB.H"
6 #include "bio++.H"
7 #include "seqCache.H"
8 #include "seqStream.H"
9 #include "merStream.H"
10
11 bool
12 existDB::createFromFastA(char const *filename,
13 uint32 merSize,
14 uint32 flags) {
15
16 bool beVerbose = false;
17 bool rebuilding = false;
18
19 _hashTable = 0L;
20 _buckets = 0L;
21 _counts = 0L;
22
23 _merSizeInBases = merSize;
24
25 _searchForDupe = true;
26
27 if ((flags & existDBcompressHash) ||
28 (flags & existDBcompressBuckets) ||
29 (flags & existDBcompressCounts))
30 fprintf(stderr, "existDB::createFromSequence: compression not supported.\n"), exit(1);
31
32 // This (at =22) eats up 16MB, and should allow a lot of mers at big sizes. Unfortunately, we
33 // know nothing about how man mers are going to be in the input.
34 //
35 // Setting this too high drastically reduces performance, suspected because of cache misses.
36 // Setting this too low will also reduce performance, by increasing the search time in a bucket.
37 //
38 uint32 tblBits = logBaseTwo64(sizeOfFile(filename));
39
40 rebuild:
41 _shift1 = 2 * _merSizeInBases - tblBits;
42 _shift2 = _shift1 / 2;
43 _mask1 = uint64MASK(tblBits);
44 _mask2 = uint64MASK(_shift1);
45
46 _hshWidth = uint32ZERO;
47 _chkWidth = 2 * merSize - tblBits;
48 _cntWidth = 16;
49
50 uint64 tableSizeInEntries = uint64ONE << tblBits;
51 uint64 numberOfMers = uint64ZERO;
52 uint64 *countingTable = new uint64 [tableSizeInEntries + 1];
53
54 for (uint64 i=tableSizeInEntries+1; i--; )
55 countingTable[i] = 0;
56
57 _isCanonical = flags & existDBcanonical;
58 _isForward = flags & existDBforward;
59
60 assert(_isCanonical + _isForward == 1);
61
62 ////////////////////////////////////////////////////////////////////////////////
63 //
64 // 1) Count bucket sizes
65 //
66 merStream *M = new merStream(new kMerBuilder(_merSizeInBases),
67 new seqStream(filename),
68 true, true);
69
70 while (M->nextMer()) {
71 if (_isForward) {
72 countingTable[ HASH(M->theFMer()) ]++;
73 numberOfMers++;
74 }
75
76 if (_isCanonical) {
77 countingTable[ HASH(M->theCMer()) ]++;
78 numberOfMers++;
79 }
80 }
81
82 delete M;
83
84 #ifdef STATS
85 uint64 dist[32] = {0};
86 uint64 maxcnt = 0;
87 for (uint64 i=tableSizeInEntries+1; i--; ) {
88 if (countingTable[i] > maxcnt)
89 maxcnt = countingTable[i];
90
91 if (countingTable[i] < 32)
92 dist[countingTable[i]]++;
93 }
94
95 for(uint64 i=0; i<32; i++)
96 fprintf(stderr, "existDB::usage[%2d] = %d\n", i, dist[i]);
97 fprintf(stderr, "existDB::maxcnt = %d\n", maxcnt);
98 #endif
99
100
101 ////////////////////////////////////////////////////////////////////////////////
102 //
103 // Determine how many bits we need to hold the value
104 // numberOfMers.....then....
105 //
106 // This is numberOfMers+1 because we need to store the
107 // first position after the last mer. That is, if there are two
108 // mers, we will store that the first mer is at position 0, the
109 // second mer is at position 1, and the end of the second mer is at
110 // position 2.
111 //
112 if (_compressedHash) {
113 _hshWidth = 1;
114 while ((numberOfMers+1) > (uint64ONE << _hshWidth))
115 _hshWidth++;
116 }
117
118
119 ////////////////////////////////////////////////////////////////////////////////
120 //
121 // 2) Allocate a hash table and some mer storage buckets.
122 //
123 _hashTableWords = tableSizeInEntries + 2;
124 if (_compressedHash)
125 _hashTableWords = _hashTableWords * _hshWidth / 64 + 1;
126
127 _bucketsWords = numberOfMers + 2;
128 if (_compressedBucket)
129 _bucketsWords = _bucketsWords * _chkWidth / 64 + 1;
130
131 _countsWords = numberOfMers + 2;
132 if (_compressedCounts)
133 _countsWords = _countsWords * _cntWidth / 64 + 1;
134
135 if (beVerbose) {
136 fprintf(stderr, "existDB::createFromFastA()-- hashTable is "uint64FMT"MB\n", _hashTableWords >> 17);
137 fprintf(stderr, "existDB::createFromFastA()-- buckets is "uint64FMT"MB\n", _bucketsWords >> 17);
138 if (flags & existDBcounts)
139 fprintf(stderr, "existDB::createFromFastA()-- counts is "uint64FMT"MB\n", _countsWords >> 17);
140 }
141
142 _hashTable = new uint64 [_hashTableWords];
143 _buckets = new uint64 [_bucketsWords];
144 _countsWords = (flags & existDBcounts) ? _countsWords : 0;
145 _counts = (flags & existDBcounts) ? new uint64 [_countsWords] : 0L;
146
147 // These aren't strictly needed. _buckets is cleared as it is initialied. _hashTable
148 // is also cleared as it is initialized, but in the _compressedHash case, the last
149 // few words might be uninitialized. They're unused.
150 //
151 //memset(_hashTable, 0, sizeof(uint64) * _hashTableWords);
152 //memset(_buckets, 0, sizeof(uint64) * _bucketsWords); // buckets is cleared as it is built
153 //memset(_counts, 0, sizeof(uint64) * _countsWords);
154
155 _hashTable[_hashTableWords-1] = 0;
156 _hashTable[_hashTableWords-2] = 0;
157 _hashTable[_hashTableWords-3] = 0;
158 _hashTable[_hashTableWords-4] = 0;
159
160 ////////////////////////////////////////////////////////////////////////////////
161 //
162 // Make the hash table point to the start of the bucket, and reset
163 // the counting table -- we're going to use it to fill the buckets.
164 //
165 uint64 tmpPosition = 0;
166 uint64 begPosition = 0;
167 uint64 ptr = 0;
168
169 if (_compressedHash) {
170 for (uint64 i=0; i<tableSizeInEntries; i++) {
171 tmpPosition = countingTable[i];
172 countingTable[i] = begPosition;
173
174 setDecodedValue(_hashTable, ptr, _hshWidth, begPosition);
175 ptr += _hshWidth;
176
177 begPosition += tmpPosition;
178 }
179
180 setDecodedValue(_hashTable, ptr, _hshWidth, begPosition);
181 } else {
182 for (uint64 i=0; i<tableSizeInEntries; i++) {
183 tmpPosition = countingTable[i];
184 countingTable[i] = begPosition;
185
186 _hashTable[i] = begPosition;
187
188 begPosition += tmpPosition;
189 }
190
191 // Set the last position in the hash, but we don't care about
192 // the temporary counting table.
193 //
194 _hashTable[tableSizeInEntries] = begPosition;
195 }
196
197
198
199
200 ////////////////////////////////////////////////////////////////////////////////
201 //
202 // 3) Build list of mers, placed into buckets
203 //
204 M = new merStream(new kMerBuilder(_merSizeInBases),
205 new seqStream(filename),
206 true, true);
207
208 while (M->nextMer()) {
209 if (_isForward)
210 insertMer(HASH(M->theFMer()), CHECK(M->theFMer()), 1, countingTable);
211
212 if (_isCanonical)
213 insertMer(HASH(M->theCMer()), CHECK(M->theCMer()), 1, countingTable);
214 }
215
216 delete M;
217
218 // Compress out the gaps we have from redundant kmers.
219
220 uint64 pos = 0;
221 uint64 frm = 0;
222 uint64 len = 0;
223
224 for (uint64 i=0; i<tableSizeInEntries; i++) {
225 frm = _hashTable[i];
226 len = countingTable[i] - _hashTable[i];
227
228 _hashTable[i] = pos;
229
230 for (uint64 j=0; j<len; j++) {
231 if (_counts)
232 _counts[pos] = _counts[frm];
233
234 _buckets[pos++] = _buckets[frm++];
235 }
236 }
237
238 if (beVerbose)
239 fprintf(stderr, "Compressed from "uint64FMT" to "uint64FMT" ("uint64FMT" bits)\n",
240 _hashTable[tableSizeInEntries], pos, logBaseTwo64(pos));
241
242 while (pos < _bucketsWords)
243 _buckets[pos++] = 0;
244
245 _hashTable[tableSizeInEntries] = pos;
246
247 // All done. Delete temporary stuff
248 //
249 delete [] countingTable;
250
251 // But if we horribly screwed up the estimate of tblBits, reset and recompute
252
253 if ((logBaseTwo64(pos) < tblBits) &&
254 (rebuilding == false)) {
255 rebuilding = true;
256
257 delete [] _hashTable;
258 delete [] _buckets;
259 delete [] _counts;
260
261 _hashTable = 0L;
262 _buckets = 0L;
263 _counts = 0L;
264
265 tblBits = logBaseTwo64(pos);
266
267 goto rebuild;
268 }
269
270 return(true);
271 }