BitMagic-C++
xsample06.cpp

Use of sparse vector for compressed DNA strings (2 bits per bp) Construction of comparison functions on bit-transposed compressed containers, benchmarking.

See also
bm::sparse_vector
bm::sparse_vector_find_first_mismatch
/*
Copyright(c) 2002-2019 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/** \example xsample06.cpp
Use of sparse vector for compressed DNA strings (2 bits per bp)
Construction of comparison functions on bit-transposed compressed
containers, benchmarking.
\sa bm::sparse_vector
\sa bm::sparse_vector_find_first_mismatch
*/
/*! \file xsample06.cpp
\brief Example: Use of sparse vector for compressed DNA strings
*/
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include "bm.h"
#include "bmsparsevec.h"
// BitMagic utilities for debug and timings
#include "bmdbg.h"
#include "bmtimer.h"
using namespace std;
/// Translate DNA letter to integer code
/// Please note this function uses extended alphabet ATGC plus 'N' and '$'
/// Ns are used to indicate ambiguity and $ is part of Burrows-Wheeler transform
///
inline unsigned DNA2int(char DNA_bp)
{
switch (DNA_bp)
{
case 'A':
return 0; // 000
case 'T':
return 1; // 001
case 'G':
return 2; // 010
case 'C':
return 3; // 011
case 'N':
return 4; // 100
case '$':
return 5; // 101
default:
assert(0);
return 0;
}
}
/// Translate integer code to DNA letter
///
inline char int2DNA(unsigned code)
{
static char lut[] = { 'A', 'T', 'G', 'C', 'N', '$' };
if (code < 5)
return lut[code];
assert(0);
return 'N';
}
/// Print sparse vector
template<typename SV> void PrintSV(const SV& sv)
{
cout << "size() = " << sv.size() << " : ";
auto it = sv.begin(); auto it_end = sv.end();
for (; it != it_end; ++it)
{
auto v = *it;
char bp = int2DNA(v);
cout << bp;
}
cout << endl;
}
/// Test sparse vector against reference vector
/// (for QA purposes)
///
template<typename SV, typename VECT>
void TestSV(const SV& sv, const VECT& vect)
{
auto it = sv.begin(); auto it_end = sv.end();
auto itv = vect.begin(); auto itv_end = vect.end();
for (; it != it_end && itv != itv_end; ++it, ++itv)
{
auto v = *it;
char bp = int2DNA(v);
char bpv = *itv;
assert(bp == bpv);
if (bp != bpv)
{
cerr << "Error: reference vector mismatch!" << endl;
exit(1);
}
}
if (it != it_end || itv != itv_end)
{
cerr << "Error: reference size mismatch!" << endl;
exit(1);
}
}
typedef std::vector<char> vector_char_type;
typedef std::vector<std::pair<unsigned, unsigned> > vector_pairs_type;
/*
Lexicographical compare of two sparse vectors using bit-plane
mismatch search
*/
static
int compare_sv(const svector_u32& sv1, const svector_u32& sv2)
{
bool found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
if (found)
{
auto v1 = sv1[pos];
auto v2 = sv2[pos];
if (v1 < v2)
return -1;
return 1;
}
return 0; // EQ
}
/*
Lexicographical compare of two sparse vectors using
iterators. This variant is quite slow, because sparse vector iterators
are heavy classes doing reverse transformation on the fly
*/
static
int compare_sv_it(const svector_u32& sv1, const svector_u32& sv2)
{
for (svector_u32::size_type i = 0; i < sz; ++i, ++it1, ++it2)
{
auto v1 = *it1; auto v2 = *it2;
if (v1 == v2)
continue;
if (v1 < v2)
return -1;
return 1;
}
return 0;
}
/*
Utility function to generate random vector of DNA chars (4 letters)
*/
static
void generate_DNA_vector(svector_u32& sv, vector_char_type& vect, unsigned sz)
{
for (unsigned i = 0; i < sz; ++i)
{
unsigned code = rand() % 4; // generate code between 0 and 3
char bp = int2DNA(code);
assert(bp == 'A' || bp == 'T' || bp == 'G' || bp == 'C');
vect.push_back(bp);
bi = code;
}
bi.flush();
}
/*
Utility function to add symulated centromer (block of Ns in the middle)
*/
static
void add_centromer_Ns(svector_u32& sv, vector_char_type& vect, unsigned csz)
{
assert(csz);
assert(sz == svector_u32::size_type(vect.size()));
assert(csz < sz);
svector_u32::size_type half = sz / 2; // center position
svector_u32::size_type c_half = csz / 2;
svector_u32::size_type c_start = half - c_half; // simulated centromere start
svector_u32::size_type c_end = half + c_half; // simulated centromere end
// fill-in simulated centromere 'NNNNNN...NNNN'
for (svector_u32::size_type i = c_start; i < c_end; ++i)
{
vect[i] = 'N';
sv[i] = DNA2int('N'); // 4
}
}
/*
Generate large vectors to simulate human chr1
*/
static
{
const unsigned case_size = 200000000; // 200M bps
const unsigned centr_size = 7000000; // 7M centromere Ns
generate_DNA_vector(sv, vect, case_size);
add_centromer_Ns(sv, vect, centr_size);
sv.optimize(); // this will compress the sparse (N) plane
TestSV(sv, vect); // paranoiya check
}
/*
Generate benchmark set of mismatches
*/
static
const vector_char_type& vect,
unsigned m_count)
{
vect_m.resize(0);
if (!vect.size())
return;
vector_char_type::size_type sz = vect.size();
vector_char_type::size_type delta = sz / m_count;
for (vector_char_type::size_type i = 0; i < sz; i += delta)
{
vector_char_type::value_type v1 = vect[i];
unsigned code = rand() % 4;
vector_char_type::value_type v2 = int2DNA(code);
if (v2 == v1)
continue;
vect_m.push_back(vector_pairs_type::value_type(i, code));
} // for i
// add some extra with a distrubution skewed to the beginning
//
for (vector_char_type::size_type i = 1; i < sz / 4; i += (rand()%(1024 * 10)))
{
vector_char_type::value_type v1 = vect[i];
unsigned code = rand() % 4;
vector_char_type::value_type v2 = int2DNA(code);
if (v2 == v1)
continue;
vect_m.push_back(vector_pairs_type::value_type(i, code));
} // for i
}
// -------------------------------------------------------------------
const unsigned repeats = 20000;
/*
Mismatch search benchmark for bm::sparse_vector_find_first_mismatch
*/
static
void test_mismatch_search(const svector_u32& sv, const vector_pairs_type& vect_m)
{
svector_u32 sv1(sv); // copy sv
unsigned cnt = 0;
bm::chrono_taker tt1("1. SV mismatch", sz, &timing_map);
for (unsigned k = 0; k < sz; ++k)
{
unsigned i = vect_m[k].first;
svector_u32::value_type v2 = vect_m[k].second;
assert(v1 != v2);
sv1.set(i, v2); // change the copy vector
bool found = bm::sparse_vector_find_first_mismatch(sv, sv1, pos);
cnt += found;
assert(found);
assert(pos == i);
sv1.set(pos, v1); // restore old value
} // for
assert(cnt == vect_m.size());
}
/*
Mismatch search benchmark for std::vector::const_iterator
*/
static
const vector_pairs_type& vect_m)
{
vector_char_type vect1(vect);
unsigned sz = (unsigned)vect_m.size();
unsigned cnt = 0;
bm::chrono_taker tt1("2. STL iterator", sz, &timing_map);
for (unsigned k = 0; k < sz; ++k)
{
unsigned i = vect_m[k].first;
vector_char_type::value_type v1 = vect[i];
vector_char_type::value_type v2 = int2DNA(vect_m[k].second);
assert(v1 != v2);
vect1[i] = v2; // change the copy vector
// possible to use std::mismatch() here
bool found = false;
vector_char_type::size_type pos;
auto it = vect.begin(); auto it_end = vect.end();
auto it1 = vect1.begin();
for (; it != it_end; ++it, ++it1)
{
if (*it != *it1)
{
found = true;
pos = vector_char_type::size_type(it - vect.begin());
break;
}
} // for it
cnt += found;
assert(found);
assert(pos == i);
vect1[i] = v1; // restore old value
} // for
assert(cnt == vect_m.size());
}
/*
Mismatch search benchmark for std::vector using strncmp()
*/
static
void test_strcmp(const vector_char_type& vect, const vector_pairs_type& vect_m)
{
vector_char_type vect1(vect);
unsigned sz = (unsigned)vect_m.size();
unsigned cnt = 0;
bm::chrono_taker tt1("3. strcmp() test ", sz, &timing_map);
unsigned vs = unsigned(vect.size());
for (unsigned k = 0; k < sz; ++k)
{
unsigned i = vect_m[k].first;
vector_char_type::value_type v1 = vect[i];
assert(vect_m[k].second < 4);
vector_char_type::value_type v2 = int2DNA(vect_m[k].second);
assert(v1 != v2);
vect1[i] = v2; // change the copy vector
const char* s1 = vect.data();
const char* s2 = vect1.data();
int res = ::strncmp(s1, s2, vs);
cnt += bool(res);
assert(res);
vect1[i] = v1; // restore
} // for
assert(cnt == vect_m.size());
}
/*
Sparse vector compare benchmark
*/
static
void test_sv_cmp(const svector_u32& sv, const vector_pairs_type& vect_m)
{
svector_u32 sv1(sv);
unsigned sz = (unsigned)vect_m.size();
unsigned cnt = 0;
bm::chrono_taker tt1("4. sv compare", sz, &timing_map);
for (unsigned k = 0; k < sz; ++k)
{
unsigned i = vect_m[k].first;
svector_u32::value_type v2 = vect_m[k].second;
assert(v1 != v2);
sv1.set(i, v2); // change the copy vector
int res = compare_sv(sv, sv1);
assert(res != 0);
cnt += bool(res);
sv1.set(i, v1); // restore
} // for
assert(cnt == vect_m.size());
}
/*
Sparse vector compare benchmark using iterators (very slow)
*/
inline
void test_sv_cmp_it(const svector_u32& sv, const vector_pairs_type& vect_m)
{
svector_u32 sv1(sv);
unsigned sz = (unsigned)vect_m.size();
unsigned cnt = 0;
bm::chrono_taker tt1("4. sv-cmp-it()", sz, &timing_map);
for (unsigned k = 0; k < sz; ++k)
{
unsigned i = vect_m[k].first;
svector_u32::value_type v2 = vect_m[k].second;
assert(v1 != v2);
sv1.set(i, v2); // change the copy vector
int res = compare_sv_it(sv, sv1);
cnt += bool(res);
assert(res != 0);
sv1.set(i, v1); // restore
} // for
assert(cnt == vect_m.size());
}
// -------------------------------------------------------------------
int main(void)
{
try
{
// generate short DNA vector as STL vector and BitMagic
// bit-transposed container, print the results (as a demo)
// we don't have to re-load it every time,
// bit transposed container is serializable
{
const char* s = "ATGTCNNNNNTATA";
{
for (unsigned i = 0; s[i]; ++i)
{
bi = DNA2int(s[i]);
}
bi.flush();
}
sv.optimize(); // this will compress the sparse (N) plane
PrintSV(sv);
}
// run a battery of benchmarks for variants of mismatch searches
// and compare functions
{
vector_char_type dna_vect;
cout << "Generate benchmark test data." << endl;
generate_big_case(sv1, dna_vect);
generate_mismatches(vect_m, dna_vect, repeats);
cout << "generated mismatches=" << vect_m.size() << endl;
cout << "SV mismatch search test" << endl;
test_mismatch_search(sv1, vect_m);
cout << "STL interator mismatch test" << endl;
test_vect_mismatch_search(dna_vect, vect_m);
// test compare functions
//
cout << "strncmp() test" << endl;
test_strcmp(dna_vect, vect_m);
cout << "SV compare test" << endl;
test_sv_cmp(sv1, vect_m);
// really sow, not worth testing
//
#if 0
cout << "SV compare iterators test" << endl;
test_sv_cmp_it(sv1, vect_m);
#endif
}
std::cout << std::endl << "Performance:" << std::endl;
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
TestSV
void TestSV(const SV &sv, const VECT &vect)
Test sparse vector against reference vector (for QA purposes)
Definition: xsample06.cpp:108
test_vect_mismatch_search
static void test_vect_mismatch_search(const vector_char_type &vect, const vector_pairs_type &vect_m)
Definition: xsample06.cpp:321
bmsparsevec_algo.h
Algorithms for bm::sparse_vector.
bm::sparse_vector::optimize
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector plains
Definition: bmsparsevec.h:1750
bm::sparse_vector< unsigned, bm::bvector<> >::back_insert_iterator
friend back_insert_iterator
Definition: bmsparsevec.h:349
bm::sparse_vector< unsigned, bm::bvector<> >::const_iterator
friend const_iterator
Definition: bmsparsevec.h:348
bm::sparse_vector
sparse vector with runtime compression using bit transposition method
Definition: bmsparsevec.h:81
bm::chrono_taker
Utility class to collect performance measurements and statistics.
Definition: bmtimer.h:39
PrintSV
void PrintSV(const SV &sv)
Print sparse vector.
Definition: xsample06.cpp:91
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
compare_sv
static int compare_sv(const svector_u32 &sv1, const svector_u32 &sv2)
Definition: xsample06.cpp:141
bmsparsevec_serial.h
Serialization for sparse_vector<>
test_sv_cmp_it
void test_sv_cmp_it(const svector_u32 &sv, const vector_pairs_type &vect_m)
Definition: xsample06.cpp:432
add_centromer_Ns
static void add_centromer_Ns(svector_u32 &sv, vector_char_type &vect, unsigned csz)
Definition: xsample06.cpp:201
timing_map
bm::chrono_taker::duration_map_type timing_map
Definition: xsample06.cpp:280
bm::sparse_vector_find_first_mismatch
bool sparse_vector_find_first_mismatch(const SV &sv1, const SV &sv2, typename SV::size_type &midx, bm::null_support null_proc=bm::use_null)
Find first mismatch (element which is different) between two sparse vectors (uses linear scan in bit-...
Definition: bmsparsevec_algo.h:170
DNA2int
unsigned DNA2int(char DNA_bp)
Translate DNA letter to integer code Please note this function uses extended alphabet ATGC plus 'N' a...
Definition: xsample06.cpp:58
generate_DNA_vector
static void generate_DNA_vector(svector_u32 &sv, vector_char_type &vect, unsigned sz)
Definition: xsample06.cpp:183
test_mismatch_search
static void test_mismatch_search(const svector_u32 &sv, const vector_pairs_type &vect_m)
Definition: xsample06.cpp:288
bm::sparse_vector< unsigned, bm::bvector<> >::value_type
unsigned value_type
Definition: bmsparsevec.h:84
bm::chrono_taker::ct_time
@ ct_time
Definition: bmtimer.h:58
bmtimer.h
Timing utilities for benchmarking (internal)
bm::sparse_vector::size
size_type size() const BMNOEXCEPT
return size of the vector
Definition: bmsparsevec.h:644
bm::sparse_vector::begin
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
Definition: bmsparsevec.h:1922
test_strcmp
static void test_strcmp(const vector_char_type &vect, const vector_pairs_type &vect_m)
Definition: xsample06.cpp:367
generate_mismatches
static void generate_mismatches(vector_pairs_type &vect_m, const vector_char_type &vect, unsigned m_count)
Definition: xsample06.cpp:243
bm::chrono_taker::duration_map_type
std::map< std::string, statistics > duration_map_type
test name to duration map
Definition: bmtimer.h:65
bm::sparse_vector::get_back_inserter
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
Definition: bmsparsevec.h:506
int2DNA
char int2DNA(unsigned code)
Translate integer code to DNA letter.
Definition: xsample06.cpp:81
test_sv_cmp
static void test_sv_cmp(const svector_u32 &sv, const vector_pairs_type &vect_m)
Definition: xsample06.cpp:402
bm::chrono_taker::print_duration_map
static void print_duration_map(const duration_map_type &dmap, format fmt=ct_time)
Definition: bmtimer.h:127
main
int main(void)
Definition: xsample06.cpp:461
repeats
const unsigned repeats
Definition: xsample06.cpp:281
svector_u32
bm::sparse_vector< unsigned, bm::bvector<> > svector_u32
Definition: xsample06.cpp:132
generate_big_case
static void generate_big_case(svector_u32 &sv, vector_char_type &vect)
Definition: xsample06.cpp:226
vector_char_type
std::vector< char > vector_char_type
Definition: xsample06.cpp:133
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bm::sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition: bmsparsevec.h:1475
vector_pairs_type
std::vector< std::pair< unsigned, unsigned > > vector_pairs_type
Definition: xsample06.cpp:134
bm::sparse_vector< unsigned, bm::bvector<> >::size_type
bvector_type::size_type size_type
Definition: bmsparsevec.h:87
compare_sv_it
static int compare_sv_it(const svector_u32 &sv1, const svector_u32 &sv2)
Definition: xsample06.cpp:162