source: trunk/GDE/SINA/builddir/src/unit_tests/kmer_test.cpp

Last change on this file was 19170, checked in by westram, 3 years ago
  • sina source
    • unpack + remove tarball
    • no longer ignore sina builddir.
File size: 15.3 KB
Line 
1/*
2  Copyright (c) 2006-2018 Elmar Pruesse <elmar.pruesse@ucdenver.edu>
3
4  This file is part of SINA.
5  SINA is free software: you can redistribute it and/or modify it under
6  the terms of the GNU General Public License as published by the Free
7  Software Foundation, either version 3 of the License, or (at your
8  option) any later version.
9
10  SINA is distributed in the hope that it will be useful, but WITHOUT ANY
11  WARRANTY; without even the implied warranty of MERCHANTABILITY or
12  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13  for more details.
14
15  You should have received a copy of the GNU General Public License
16  along with SINA.  If not, see <http://www.gnu.org/licenses/>.
17
18  Additional permission under GNU GPL version 3 section 7
19
20  If you modify SINA, or any covered work, by linking or combining it
21  with components of ARB (or a modified version of that software),
22  containing parts covered by the terms of the
23  ARB-public-library-license, the licensors of SINA grant you additional
24  permission to convey the resulting work. Corresponding Source for a
25  non-source form of such a combination shall include the source code
26  for the parts of ARB used as well as that of the covered work.
27*/
28
29#include "../kmer.h"
30
31#define BOOST_TEST_MODULE kmer_search
32
33#include <boost/test/unit_test.hpp>
34#include <boost/test/data/test_case.hpp>
35namespace bdata = boost::unit_test::data;
36
37#include <string>
38
39BOOST_AUTO_TEST_SUITE(kmer_test);
40
41using namespace sina;
42
43BOOST_AUTO_TEST_CASE(kmer_generator_test_bounds) {
44    BOOST_CHECK_THROW(kmer_generator kmer(0), std::runtime_error);
45    BOOST_CHECK_THROW(kmer_generator kmer(17), std::runtime_error);
46}
47
48
49// data for BOOST_DATA_TEST_CASE(kmer_generator_test...):
50
51const char test_sequence[] =
52    "AGCTN"
53    "AGCTAGCTN"
54    "AGCTAGCTAGCTN";
55
56const int test_sequence_len = std::extent<decltype(test_sequence)>::value - 1;
57
58const int try_k[] = {1,2,3,4,8};
59const int try_k_len = std::extent<decltype(try_k)>::value;
60
61const bool valid_k[try_k_len][test_sequence_len] = {
62    { // k = 1
63        true, true, true, true, false,
64        true, true, true, true,  true, true, true, true, false,
65        true, true, true, true,  true, true, true, true,  true, true, true, true, false
66    },
67    { // k = 2
68        false, true, true, true, false,
69        false, true, true, true,  true, true, true, true, false,
70        false, true, true, true,  true, true, true, true,  true, true, true, true, false
71    },
72    { // k = 3
73        false, false, true, true, false,
74        false, false, true, true,  true, true, true, true, false,
75        false, false, true, true,  true, true, true, true,  true, true, true, true, false
76    },
77    { // k = 4
78        false, false, false, true, false,
79        false, false, false, true,  true, true, true, true, false,
80        false, false, false, true,  true, true, true, true,  true, true, true, true, false
81    },
82    { // k = 8
83        false, false, false, false, false,
84        false, false, false, false,  false, false, false, true, false,
85        false, false, false, false,  false, false, false, true,  true, true, true, true, false
86    }
87};
88
89const bool first_k[try_k_len][test_sequence_len] = {
90    { // k = 1
91        true, true, true, true, false,
92        false, false, false, false,  false, false, false, false, false,
93        false, false, false, false,  false, false, false, false,  false, false, false, false, false
94    },
95    { // k = 2
96        false, true, true, true, false,
97        false, false, false, false,  true, false, false, false, false,
98        false, false, false, false,  false, false, false, false,  false, false, false, false, false
99    },
100    { // k = 3
101        false, false, true, true, false,
102        false, false, false, false,  true, true, false, false, false,
103        false, false, false, false,  false, false, false, false,  false, false, false, false, false
104    },
105    { // k = 4
106        false, false, false, true, false,
107        false, false, false, false,  true, true, true, false, false,
108        false, false, false, false,  false, false, false, false,  false, false, false, false, false
109    },
110    { // k = 8
111        false, false, false, false, false,
112        false, false, false, false,  false, false, false, true, false,
113        false, false, false, false,  false, false, false, false,  true, true, true, false, false
114    }
115};
116
117const unsigned int A = BASE_A;
118const unsigned int G = BASE_G;
119const unsigned int C = BASE_C;
120const unsigned int T = BASE_TU;
121
122const unsigned int kmers_k[try_k_len][test_sequence_len] = {
123    { // k = 1
124        A, G, C, T, 0,
125        A, G, C, T,  A, G, C, T, 0,
126        A, G, C, T,  A, G, C, T,  A, G, C, T, 0,
127    },
128    { // k = 2
129        0, A<<2|G, G<<2|C, C<<2|T, 0,
130        0, A<<2|G, G<<2|C, C<<2|T,
131        T<<2|A, A<<2|G, G<<2|C, C<<2|T, 0,
132        0, A<<2|G, G<<2|C, C<<2|T,
133        T<<2|A, A<<2|G, G<<2|C, C<<2|T,
134        T<<2|A, A<<2|G, G<<2|C, C<<2|T, 0
135    },
136    { // k = 3
137        0, 0, A<<4|G<<2|C, G<<4|C<<2|T, 0,
138        0, 0, A<<4|G<<2|C, G<<4|C<<2|T,
139        C<<4|T<<2|A, T<<4|A<<2|G, A<<4|G<<2|C, G<<4|C<<2|T, 0,
140        0, 0, A<<4|G<<2|C, G<<4|C<<2|T,
141        C<<4|T<<2|A, T<<4|A<<2|G, A<<4|G<<2|C, G<<4|C<<2|T,
142        C<<4|T<<2|A, T<<4|A<<2|G, A<<4|G<<2|C, G<<4|C<<2|T, 0
143    },
144    { // k = 4
145        0, 0, 0, A<<6|G<<4|C<<2|T, 0,
146        0, 0, 0, A<<6|G<<4|C<<2|T,
147        G<<6|C<<4|T<<2|A, C<<6|T<<4|A<<2|G, T<<6|A<<4|G<<2|C, A<<6|G<<4|C<<2|T, 0,
148        0, 0, 0, A<<6|G<<4|C<<2|T,
149        G<<6|C<<4|T<<2|A, C<<6|T<<4|A<<2|G, T<<6|A<<4|G<<2|C, A<<6|G<<4|C<<2|T,
150        G<<6|C<<4|T<<2|A, C<<6|T<<4|A<<2|G, T<<6|A<<4|G<<2|C, A<<6|G<<4|C<<2|T, 0
151    },
152    { // k = 8
153        0, 0, 0, 0, 0,
154        0, 0, 0, 0,
155        0, 0, 0, A<<14|G<<12|C<<10|T<<8|A<<6|G<<4|C<<2|T, 0,
156        0, 0, 0, 0,
157        0, 0, 0, A<<14|G<<12|C<<10|T<<8|A<<6|G<<4|C<<2|T,
158        G<<14|C<<12|T<<10|A<<8|G<<6|C<<4|T<<2|A,
159        C<<14|T<<12|A<<10|G<<8|C<<6|T<<4|A<<2|G,
160        T<<14|A<<12|G<<10|C<<8|T<<6|A<<4|G<<2|C,
161        A<<14|G<<12|C<<10|T<<8|A<<6|G<<4|C<<2|T, 0
162    }
163};
164
165BOOST_DATA_TEST_CASE(kmer_generator_test,
166                     bdata::xrange(try_k_len) ^ bdata::make(try_k),
167                     n, k
168    ) {
169    const auto& valid = valid_k[n];
170    const auto& kmers = kmers_k[n];
171
172    kmer_generator kmer(k);
173
174    for (int i = 0; i < test_sequence_len; ++i) {
175        kmer.push(test_sequence[i]);
176        BOOST_CHECK_EQUAL(kmer.good(), valid[i]);
177        BOOST_CHECK_MESSAGE(kmer.good() == valid[i], ""
178                            << " i=" << i
179                            << " kmer=" << kmer
180                            << " b=" << test_sequence[i]
181                            << " gc=" << kmer.get_good_count());
182        if (kmer.good()) {
183            BOOST_CHECK_EQUAL(kmer, kmers[i]);
184            BOOST_CHECK_MESSAGE(kmer == kmers[i], ""
185                                << " i=" << i
186                                << " b=" << test_sequence[i]
187                                << " kmer=" << kmer
188                                << " test_kmer=" << kmer_generator(k, kmers[i])
189                );
190        }
191    }
192}
193
194BOOST_DATA_TEST_CASE(kmer_iterable_generator_test,
195                     bdata::xrange(try_k_len) ^ bdata::make(try_k),
196                     n, k
197    ) {
198    const auto& valid = valid_k[n];
199    const auto& kmers = kmers_k[n];
200
201    int i = 0;
202    std::string test_string(test_sequence);
203    for (const auto& kmer : all_kmers(test_string, k)) {
204        while (not valid[i]) { ++i; }
205        BOOST_CHECK_EQUAL(kmer, kmers[i]);
206        BOOST_CHECK_MESSAGE(kmer == kmers[i], ""
207                            << " i=" << i
208                            << " b=" << test_sequence[i]
209                            << " kmer=" << kmer
210                            << " test_kmer=" << kmer_generator(k, kmers[i])
211            );
212        ++i;
213    }
214}
215
216BOOST_DATA_TEST_CASE(kmer_unique_generator_test,
217                     bdata::xrange(try_k_len) ^ bdata::make(try_k),
218                     n, k
219    ) {
220    const auto& valid = first_k[n];
221    const auto& kmers = kmers_k[n];
222
223    std::unordered_set<unsigned int> seen;
224
225    unique_kmer_generator kmer(seen, k);
226
227    for (int i = 0; i < test_sequence_len; ++i) {
228        kmer.push(test_sequence[i]);
229        BOOST_CHECK_EQUAL(kmer.good(), valid[i]);
230        BOOST_CHECK_MESSAGE(kmer.good() == valid[i], ""
231                            << " i=" << i
232                            << " kmer=" << kmer
233                            << " b=" << test_sequence[i]
234                            << " gc=" << kmer.get_good_count());
235        if (kmer.good()) {
236            BOOST_CHECK_EQUAL(kmer, kmers[i]);
237            BOOST_CHECK_MESSAGE(kmer == kmers[i], ""
238                                << " i=" << i
239                                << " b=" << test_sequence[i]
240                                << " kmer=" << kmer
241                                << " test_kmer=" << kmer_generator(k, kmers[i])
242                );
243        }
244    }
245}
246
247BOOST_DATA_TEST_CASE(kmer_iterable_unique_generator_test,
248                     bdata::xrange(try_k_len) ^ bdata::make(try_k),
249                     n, k
250    ) {
251    const auto& valid = first_k[n];
252    const auto& kmers = kmers_k[n];
253
254    int i = 0;
255    std::string test_string(test_sequence);
256    std::unordered_set<unsigned int> seen;
257    for (const auto& kmer : unique_kmers(test_string, seen, k)) {
258        while (not valid[i]) { ++i; }
259        BOOST_CHECK_EQUAL(kmer, kmers[i]);
260        BOOST_CHECK_MESSAGE(kmer == kmers[i], ""
261                            << " i=" << i
262                            << " b=" << test_sequence[i]
263                            << " kmer=" << kmer
264                            << " test_kmer=" << kmer_generator(k, kmers[i])
265            );
266        ++i;
267    }
268}
269
270
271// data for BOOST_DATA_TEST_CASE(prefix_kmer_generator_test,...):
272
273const int kmer_prefix_n = 2;
274const unsigned int kmer_prefix_lens[try_k_len][kmer_prefix_n] = {
275    { 1, 1 }, // k=1
276    { 1, 2 }, // k=2
277    { 2, 3 }, // k=3
278    { 2, 4 }, // k=4
279    { 2, 4 }, // k=8
280};
281
282const unsigned int kmer_prefixes[try_k_len][kmer_prefix_n] = {
283    { A, T }, // k=1
284    { A, G<<2|C }, // k=2
285    { G<<2|C, T<<4|A<<2|G }, // k=3
286    { C<<2|T, G<<6|C<<4|T<<2|A }, // k=4
287    { T<<2|A, A<<6|G<<4|C<<2|T } // k=8
288};
289
290const unsigned int kmer_prefix_counts[try_k_len][kmer_prefix_n] = {
291    { 6, 6 }, // k=1
292    { 6, 6 }, // k=2
293    { 6, 3 }, // k=3
294    { 3, 3 }, // k=4
295    { 1, 3 }, // k=8
296};
297
298const unsigned int kmer_unique_prefix_counts[try_k_len][kmer_prefix_n] = {
299    { 1, 1 }, // k=1
300    { 1, 1 }, // k=2
301    { 1, 1 }, // k=3
302    { 1, 1 }, // k=4
303    { 1, 1 }, // k=8
304};
305
306BOOST_DATA_TEST_CASE(prefix_kmer_generator_test,
307                     (bdata::xrange(try_k_len) ^ bdata::make(try_k)) *
308                     bdata::xrange(kmer_prefix_n),
309                     n, k, p
310    ) {
311    const auto& valid = valid_k[n];
312    const auto& kmers = kmers_k[n];
313    const auto& prefix_len = kmer_prefix_lens[n][p];
314    const auto& prefix = kmer_prefixes[n][p];
315    const auto& prefix_count = kmer_prefix_counts[n][p];
316
317    prefix_kmer_generator kmer(k, prefix_len, prefix);
318
319    unsigned int count = 0;
320    for (int i = 0; i < test_sequence_len; ++i) {
321        kmer.push(test_sequence[i]);
322        unsigned int current_prefix = kmers[i] >> (k-prefix_len)*2;
323        bool should_be_valid = valid[i] && current_prefix == prefix;
324        BOOST_CHECK_EQUAL(kmer.good(), should_be_valid);
325        BOOST_CHECK_MESSAGE(kmer.good() == should_be_valid, ""
326                            << " i=" << i
327                            << " kmer=" << kmer
328                            << " b=" << test_sequence[i]
329                            << " prefix_len=" << prefix_len
330                            << " prefix=" << kmer_generator(prefix_len,prefix)
331                            << " cur_prefix=" << kmer_generator(prefix_len,current_prefix)
332
333                            << " gc=" << kmer.get_good_count());
334        if (kmer.good()) {
335            BOOST_CHECK_EQUAL(kmer, kmers[i]);
336            BOOST_CHECK_MESSAGE(kmer == kmers[i], ""
337                                << " i=" << i
338                                << " b=" << test_sequence[i]
339                                << " kmer=" << kmer
340                                << " test_kmer=" << kmer_generator(k, kmers[i])
341                );
342            ++count;
343        }
344    }
345    BOOST_CHECK_EQUAL(count, prefix_count);
346}
347
348
349BOOST_DATA_TEST_CASE(kmer_iterable_prefix_generator_test,
350                     (bdata::xrange(try_k_len) ^ bdata::make(try_k)) *
351                     bdata::xrange(kmer_prefix_n),
352                     n, k, p
353    ) {
354    const auto& valid = valid_k[n];
355    const auto& kmers = kmers_k[n];
356    const auto& prefix_len = kmer_prefix_lens[n][p];
357    const auto& prefix = kmer_prefixes[n][p];
358    const auto& prefix_count = kmer_prefix_counts[n][p];
359
360    int i = 0;
361    unsigned int count = 0;
362    std::string test_string(test_sequence);
363    for (const auto& kmer : prefix_kmers(test_string, k, prefix_len, prefix)) {
364        bool should_be_valid = false;
365        unsigned int current_prefix;
366        do {
367            current_prefix = kmers[i] >> (k-prefix_len)*2;
368            should_be_valid = valid[i] && current_prefix == prefix;
369        } while (!should_be_valid && ++i);
370        BOOST_CHECK_EQUAL(kmer, kmers[i]);
371        BOOST_CHECK_MESSAGE(kmer == kmers[i], ""
372                            << " i=" << i
373                            << " b=" << test_sequence[i]
374                            << " kmer=" << kmer
375                            << " test_kmer=" << kmer_generator(k, kmers[i])
376                            << " b=" << test_sequence[i]
377                            << " prefix_len=" << prefix_len
378                            << " prefix=" << kmer_generator(prefix_len,prefix)
379                            << " cur_prefix=" << kmer_generator(prefix_len,current_prefix)
380            );
381        ++i;
382        ++count;
383    }
384    BOOST_CHECK_EQUAL(count, prefix_count);
385}
386
387
388BOOST_DATA_TEST_CASE(kmer_iterable_unique_prefix_generator_test,
389                     (bdata::xrange(try_k_len) ^ bdata::make(try_k)) *
390                     bdata::xrange(kmer_prefix_n),
391                     n, k, p
392    ) {
393    const auto& valid = first_k[n];
394    const auto& kmers = kmers_k[n];
395    const auto& prefix_len = kmer_prefix_lens[n][p];
396    const auto& prefix = kmer_prefixes[n][p];
397    const auto& prefix_count = kmer_unique_prefix_counts[n][p];
398
399    int i = 0;
400    unsigned int count = 0;
401    std::unordered_set<unsigned int> seen;
402
403    std::string test_string(test_sequence);
404    for (const auto& kmer : unique_prefix_kmers(test_string, seen, k, prefix_len, prefix)) {
405        bool should_be_valid = false;
406        unsigned int current_prefix;
407        do {
408            current_prefix = kmers[i] >> (k-prefix_len)*2;
409            should_be_valid = valid[i] && current_prefix == prefix;
410        } while (!should_be_valid && ++i);
411        BOOST_CHECK_EQUAL(kmer, kmers[i]);
412        BOOST_CHECK_MESSAGE(kmer == kmers[i], ""
413                            << " i=" << i
414                            << " b=" << test_sequence[i]
415                            << " kmer=" << kmer
416                            << " test_kmer=" << kmer_generator(k, kmers[i])
417                            << " b=" << test_sequence[i]
418                            << " prefix_len=" << prefix_len
419                            << " prefix=" << kmer_generator(prefix_len,prefix)
420                            << " cur_prefix=" << kmer_generator(prefix_len,current_prefix)
421            );
422        ++i;
423        ++count;
424    }
425    BOOST_CHECK_EQUAL(count, prefix_count);
426}
427
428BOOST_AUTO_TEST_SUITE_END(); // kmer_test
429
430
431/*
432  Local Variables:
433  mode:c++
434  c-file-style:"stroustrup"
435  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
436  indent-tabs-mode:nil
437  fill-column:99
438  End:
439*/
440// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
Note: See TracBrowser for help on using the repository browser.