Debian Codegraph @

statistic_functions.h

raw
1 /* BaitFisher (version 1.2.8) a program for designing DNA target enrichment baits
2 * BaitFilter (version 1.0.6) a program for selecting optimal bait regions
3 * Copyright 2013-2017 by Christoph Mayer
4 *
5 * This source file is part of the BaitFisher-package.
6 *
7 * This program is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with BaitFisher. If not, see <http://www.gnu.org/licenses/>.
19 *
20 *
21 * For any enquiries send an Email to Christoph Mayer
22 * [email protected]
23 *
24 * When publishing work that is based on the results please cite:
25 * Mayer et al. 2016: BaitFisher: A software package for multi-species target DNA enrichment probe design
26 *
27 */
28 #ifndef STATISTIC_FUNCTIONS_H
29 #define STATISTIC_FUNCTIONS_H
30
31 #include <iostream>
32 #include <vector>
33 #include <map>
34 #include <cmath>
35 #include <cctype>
36 #include <iterator>
37 #include <cstdlib>
38 #include <algorithm>
39 #include <climits>
40
41 #define EPSS 0.00000000001;
42
43
44 #define macro_min(x,y) ((x)<(y) ? (x) : (y))
45 #define macro_max(x,y) ((x)>(y) ? (x) : (y))
46 #define macro_mean_double(x,y) (((x)+(y))/2.0)
47
48
49 template<typename T>
50 size_t vec_mean_sd(const std::vector<T> &vec,
51 double &mean, double &sd)
52 {
53 size_t i, n=vec.size();
54 double sum_x = 0;
55 double sum_xx = 0;
56
57 if (n==0)
58 return 0;
59
60 for (i=0; i<n; ++i)
61 {
62 sum_x += (double)vec[i];
63 sum_xx += (double)vec[i]*vec[i];
64 }
65 if (n!=0)
66 mean = sum_x/(double)n;
67 else
68 mean = 0;
69 if (n>1)
70 sd = sqrt( (sum_xx-sum_x*mean)/(double)(n-1.0) );
71 else
72 sd = 0;
73 if (sd < 0.000001)
74 sd = 0;
75 return n;
76 }
77
78 template<typename T>
79 size_t vec_mean_sd(const std::vector<T> &vec,
80 double &mean, double &sd,
81 T &sum, T &sum_of_squares)
82 {
83 size_t i, n=vec.size();
84 T sum_x = 0;
85 T sum_xx = 0;
86 T elem;
87
88 if (n==0)
89 return 0;
90
91 for (i=0; i<n; ++i)
92 {
93 elem = vec[i];
94 sum_x += elem;
95 sum_xx += elem*elem;
96 }
97 mean = (double)sum_x/(double)n;
98 if (n>1)
99 sd = sqrt( (sum_xx-sum_x*mean)/(double)(n-1.0) );
100 else
101 sd = 0;
102 if (sd < 0.000001)
103 sd = 0;
104
105 sum = sum_x;
106 sum_of_squares = sum_xx;
107
108 return n;
109 }
110
111 // Coordinates conventions:
112 // The first coordinate is the index of the first element in the range as 0 based index.
113 // The second coordinate is the index of the last element in the range as 0 based index.
114 template<typename T>
115 void median_range(std::vector<T> &vec, size_t f, size_t l, double &median, size_t &index, bool &is_datum)
116 {
117 size_t s = f+l; // This is not the length or size of the range. It is the sum of the indices.
118 size_t m = s/2; // This is the index of the mid of the range
119
120 // In order to see that the following code is correct one should look at the following examples:
121 // vec: 0,1,2, Range: 0 to 2, which is the full vector. => s=2, m=1 which is the correct mid of the range. s is even so index=m=1, median is vec[m]=vec[1].
122 // vec: 0,1,2,3 Range: 1 to 3, => s=4, m=2, median = vec[2], index = 2
123 // vec: 0,1,2,3 Range: 3 to 3, => s=6, m=3, median = vec[3], index = 3
124 // vec: 0,1,2,3 Range: 0 to 3, => s=3, m=1, s is odd so median = (vec[1]+vec[2])/2, index = 1
125 // vec: 0,1,2,4,4 Range 1 to 4, => s=5, m=2, s is odd so median = (vec[2]+vec[3])/2, index = 2
126 // vec: 0,1,2,4,4 Range 2 to 4, => s=6, m=3, median = vec[3], index = 3
127 // vec: 0,1,2,4,4 Range 1 to 3, => s=4, m=2, median = vec[2], index = 2
128
129 // The following code simply relies on the fact that:
130 // (i) m is obviously the middle of the range, or left of the middle if the number of elements is even.
131 // (ii) s is even if the range has an odd number of elements and vice versa.
132
133 if (s%2 == 0)
134 {
135 median = vec[m];
136 index = m;
137 is_datum = true;
138 }
139 else
140 {
141 median = (vec[m]+vec[m+1])/2;
142 index = m;
143 is_datum = false;
144 }
145 }
146
147 // Method 2 routines:
148
149 // Prerequisite: Type T must be a type for which it makes sense to multiply it with a double to obtain a double.
150 // Compute quartiles:
151 // second quartile=median
152 // Q1 and Q3 are medians of the first part and second part, where the first and second part are obtained by dividing the data at the median.
153 template<typename T>
154 size_t vec_median_quartile_sort_method2(std::vector<T> &vec, double &Q1, double &Q2, double &Q3)
155 {
156 size_t n=vec.size();
157 size_t index, dummy;
158 bool is_datum;
159
160 std::sort(vec.begin(), vec.end());
161
162 median_range(vec, 0, n-1, Q2, index, is_datum);
163
164 if (is_datum)
165 {
166 median_range(vec, 0, index, Q1, dummy, is_datum);
167 median_range(vec, index, n-1, Q3, dummy, is_datum);
168 }
169 else
170 {
171 median_range(vec, 0, index, Q1, dummy, is_datum);
172 median_range(vec, index+1, n-1, Q3, dummy, is_datum);
173 }
174 return n;
175 }
176
177 template<typename T>
178 size_t vec_median_quartile_method2(std::vector<T> vec, double &Q1, double &Q2, double &Q3)
179 {
180 return vec_median_quartile_sort_method2(vec, Q1, Q2, Q3);
181 }
182
183 //
184 // Computes outlier bounds for a vector.
185 // Side effect: vec gets sorted. More efficient than copying the vector.
186 template<typename T>
187 size_t vec_median_quartile_outlier_bounds_sort_method2(std::vector<T> &vec, double &Q1, double &Q2, double &Q3, double &O_lower, double &O_upper)
188 {
189 int res = vec_median_quartile_sort_method2(vec, Q1, Q2, Q3);
190 double IQR = Q3 - Q1;
191
192 O_lower = Q1 - 1.5 * IQR;
193 O_upper = Q3 + 1.5 * IQR;
194
195 return res;
196 }
197
198 // Computes outlier bounds for a vector.
199 // Same vec_median_quartile_outlier_bounds_sort but without sorting the vector. Slighly slower, since the vector has to be copied.
200 template<typename T>
201 size_t vec_median_quartile_outlier_bounds_method2(std::vector<T> vec, double &Q1, double &Q2, double &Q3, double &O_lower, double &O_upper)
202 {
203 int res = vec_median_quartile_sort_method2(vec, Q1, Q2, Q3);
204 double IQR = Q3 - Q1;
205
206 O_lower = Q1 - 1.5 * IQR;
207 O_upper = Q3 + 1.5 * IQR;
208
209 return res;
210 }
211
212 template<typename T>
213 void vec_mark_outlier_mehod2(std::vector<T> &vec, std::vector<bool> &outlier)
214 {
215 outlier.clear();
216
217 double Q1, Q2, Q3, O_lower, O_upper;
218 vec_median_quartile_outlier_bounds_method2(vec, Q1, Q2, Q3, O_lower, O_upper);
219
220 unsigned i, N = vec.size();
221 outlier.reserve(N);
222 for (i=0; i<N; ++i)
223 {
224 if (vec[i] < O_lower || vec[i] > O_upper)
225 outlier.push_back(true);
226 else
227 outlier.push_back(false);
228 }
229 std::cout << "Qi: " << Q1 << " " << Q2 << " " << Q3 << std::endl;
230 std::cout << "Bounds: " << O_lower << " " << O_upper << std::endl;
231 }
232
233 // Method 3 routines:
234
235 // Prerequisite: Type T must be a type for which it makes sense to multiply it with a double to obtain a double.
236 // Compute quartiles: Averages of values at certain indices.
237 //
238 template<typename T>
239 size_t vec_median_quartile_sort_method3(std::vector<T> &vec, double &Q1, double &Q2, double &Q3)
240 {
241 size_t n=vec.size();
242 size_t m = n/4;
243 size_t r = n%4;
244
245 std::sort(vec.begin(), vec.end());
246
247 if (n==0)
248 return 0;
249
250 if (n==1)
251 {
252 Q1 = vec[0];
253 Q2 = vec[0];
254 Q3 = vec[0];
255 return 1;
256 }
257
258 if (r == 0)
259 {
260 Q1 = 0.5*vec[ m-1] + 0.5*vec[ m];
261 Q2 = 0.5*vec[2*m-1] + 0.5*vec[2*m];
262 Q3 = 0.5*vec[3*m-1] + 0.5*vec[3*m];
263 }
264 else if (r == 1)
265 {
266 // std::cerr << "m: " << m << std::endl;
267
268 Q1 = 0.25*vec[ m-1] + 0.75*vec[ m];
269 Q2 = vec[2*m];
270 Q3 = 0.75*vec[ 3*m] + 0.25*vec[3*m+1];
271 }
272 else if (r == 2)
273 {
274 // std::cerr << "m: " << m << std::endl;
275
276 Q1 = vec[m];
277 Q2 = 0.50*vec[2*m] + 0.50*vec[2*m+1];
278 Q3 = vec[3*m+1];
279 }
280 else // if (r == 3)
281 {
282 // std::cerr << "m: " << m << std::endl;
283
284 Q1 = 0.75*vec[ m] + 0.25*vec[ m+1];
285 Q2 = vec[2*m+1];
286 Q3 = 0.25*vec[3*m+1] + 0.75*vec[3*m+2];
287 }
288 return n;
289 }
290
291 template<typename T>
292 size_t vec_median_quartile_method3(std::vector<T> vec, double &Q1, double &Q2, double &Q3)
293 {
294 return vec_median_quartile_sort_method3(vec, Q1, Q2, Q3);
295 }
296
297 // Computes outlier bounds for a vector.
298 // Side effect: vec gets sorted. More efficient than copying the vector.
299 template<typename T>
300 size_t vec_median_quartile_outlier_bounds_sort_method3(std::vector<T> &vec, double &Q1, double &Q2, double &Q3, double &O_lower, double &O_upper)
301 {
302 int res = vec_median_quartile_sort_method3(vec, Q1, Q2, Q3);
303 double IQR = Q3 - Q1;
304
305 O_lower = Q1 - 1.5 * IQR;
306 O_upper = Q3 + 1.5 * IQR;
307
308 return res;
309 }
310
311 // Computes outlier bounds for a vector.
312 // Same vec_median_quartile_outlier_bounds_sort but without sorting the vector. Slighly slower, since the vector has to be copied.
313 template<typename T>
314 size_t vec_median_quartile_outlier_bounds_method3(std::vector<T> vec, double &Q1, double &Q2, double &Q3, double &O_lower, double &O_upper)
315 {
316 int res = vec_median_quartile_sort_method3(vec, Q1, Q2, Q3);
317 double IQR = Q3 - Q1;
318
319 O_lower = Q1 - 1.5 * IQR;
320 O_upper = Q3 + 1.5 * IQR;
321
322 return res;
323 }
324
325 template<typename T>
326 void vec_mark_outlier_mehod3(std::vector<T> &vec, std::vector<bool> &outlier)
327 {
328 outlier.clear();
329
330 double Q1, Q2, Q3, O_lower, O_upper;
331 vec_median_quartile_outlier_bounds_method3(vec, Q1, Q2, Q3, O_lower, O_upper);
332
333 unsigned i, N = vec.size();
334 outlier.reserve(N);
335 for (i=0; i<N; ++i)
336 {
337 if (vec[i] < O_lower || vec[i] > O_upper)
338 outlier.push_back(true);
339 else
340 outlier.push_back(false);
341 }
342 std::cout << "Qi: " << Q1 << " " << Q2 << " " << Q3 << std::endl;
343 std::cout << "Bounds: " << O_lower << " " << O_upper << std::endl;
344 }
345
346 template<typename T>
347 size_t vec_min_max(const std::vector<T> &vec, T &min, T &max)
348 {
349 size_t i, n=vec.size();
350
351 if (n==0)
352 return 0;
353
354 max = min = vec[0];
355
356 for (i=0; i<n; ++i)
357 {
358 if (vec[i] < min)
359 min = vec[i];
360
361 if (vec[i] > max)
362 max = vec[i];
363 }
364 return n;
365 }
366
367
368 // Determines the mean and sd for a range.
369 template <typename T>
370 size_t range_mean_sd(T it_beg,
371 T it_end,
372 double &mean, double &sd)
373 {
374 double sum_x = 0;
375 double sum_xx = 0;
376 size_t n=0;
377
378 if (it_beg == it_end)
379 {
380 return 0;
381 }
382
383 while (it_end != it_beg)
384 {
385 sum_x += (double)*it_beg;
386 sum_xx += (double)*it_beg* *it_beg;
387 ++it_beg;
388 ++n;
389 }
390 mean = sum_x/(double)n;
391 if (n>1)
392 sd = sqrt( (sum_xx-sum_x*mean)/(double)(n-1.0) );
393 else // if (n==1)
394 sd = 0;
395 if (sd < 0.000001)
396 sd = 0;
397 return n;
398 }
399
400
401 template<typename T>
402 size_t range_min_max(T it_beg,
403 T it_end,
404 double &min, double &max)
405 {
406 size_t n=0;
407
408 if (it_beg == it_end)
409 return 0;
410
411 max = min = *it_beg;
412
413 while (it_end != it_beg)
414 {
415 if (*it_beg< min)
416 min = *it_beg;
417
418 if (*it_beg > max)
419 max = *it_beg;
420 ++n;
421 ++it_beg;
422 }
423 return n;
424 }
425
426 template <typename T>
427 void vec_sum_sum_squares(std::vector<T> v, T& sum, T&sum_squares)
428 {
429 sum=0;
430 sum_squares=0;
431
432 unsigned i, n=v.size();
433
434 for (i=0; i<n; ++i)
435 {
436 sum += v[i];
437 sum_squares += v[i]*v[i];
438 }
439 }
440
441 // More functions: Single result as return value, using pointers to specify ranges.
442 template <typename T>
443 T minimum(T*b, T*e)
444 {
445 T m;
446 if (b>=e)
447 return INT_MIN;
448 m = *b;
449 ++b;
450 while (b!=e)
451 {
452 if (*b < m)
453 {
454 m = *b;
455 }
456 ++b;
457 }
458 return m;
459 }
460
461 template <typename T>
462 T maximum(T*b, T*e)
463 {
464 T m;
465 if (b>=e)
466 return INT_MIN;
467 m = *b;
468 ++b;
469 while (b!=e)
470 {
471 if (*b > m)
472 {
473 m = *b;
474 }
475 ++b;
476 }
477 return m;
478 }
479
480
481
482
483
484 #endif