-
Notifications
You must be signed in to change notification settings - Fork 193
/
index.hpp
268 lines (226 loc) · 11.1 KB
/
index.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
#ifndef INDEX_H
#define INDEX_H
#include <iostream>
#include <exception>
#include <sstream>
#include <climits>
#include "rocksdb/db.h"
#include "rocksdb/env.h"
#include "rocksdb/options.h"
#include "rocksdb/write_batch.h"
#include "rocksdb/memtablerep.h"
#include "rocksdb/statistics.h"
#include "rocksdb/cache.h"
#include "rocksdb/slice_transform.h"
#include "rocksdb/table.h"
#include "rocksdb/filter_policy.h"
#include "pb2json.h"
#include "vg.hpp"
#include "hash_map.hpp"
namespace vg {
#ifdef __APPLE__
#include <machine/endian.h>
#include <libkern/OSByteOrder.h>
#define htobe16(x) OSSwapHostToBigInt16(x)
#define htole16(x) OSSwapHostToLittleInt16(x)
#define be16toh(x) OSSwapBigToHostInt16(x)
#define le16toh(x) OSSwapLittleToHostInt16(x)
#define htobe32(x) OSSwapHostToBigInt32(x)
#define htole32(x) OSSwapHostToLittleInt32(x)
#define be32toh(x) OSSwapBigToHostInt32(x)
#define le32toh(x) OSSwapLittleToHostInt32(x)
#define htobe64(x) OSSwapHostToBigInt64(x)
#define htole64(x) OSSwapHostToLittleInt64(x)
#define be64toh(x) OSSwapBigToHostInt64(x)
#define le64toh(x) OSSwapLittleToHostInt64(x)
#endif
/*
Cache our variant graph in a database (rocksdb-backed) which enables us to quickly:
1) obtain specific nodes and edges from a large graph
2) search nodes and edges by kmers that they contain or overlap them
3) index the kmers of the graph
4) store paths and determine the relative locations of nodes and edges in them
Each of these functions uses a different subset of the namespace. Our key format is:
+=\x00 is our 'start' separator
-=\xff is our 'end' separator --- this makes it easy to do range queries
ids are stored as raw int64_t
// key // value
--------------------------------------------------------------
+m+metadata_key value // various information about the table
+g+node_id node [vg::Node]
+g+from_id+f+to_id edge [vg::Edge]
+g+to_id+t+from_id null // already stored under from_id+to_id, but this provides reverse index
+g+node_id+p+path_id+pos mapping [vg::Mapping]
+k+kmer+node_id position of kmer in node [int32_t]
+p+path_id+pos+node_id mapping [vg::Mapping]
+s+node_id+offset mapping [vg::Mapping] // mapping-only "side" against one node
+a+node_id+offset alignment [vg::Alignment]
*/
class Index {
public:
Index(void);
Index(string& name);
~Index(void);
rocksdb::Options GetOptions(void);
void open(const std::string& dir, bool read_only = false);
void open_read_only(string& dir);
void open_for_write(string& dir);
void open_for_bulk_load(string& dir);
void reset_options(void);
void flush(void);
void compact(void);
void close(void);
string name;
char start_sep;
char end_sep;
int threads;
rocksdb::DB* db;
bool is_open;
rocksdb::Options db_options;
rocksdb::WriteOptions write_options;
rocksdb::ColumnFamilyOptions column_family_options;
bool bulk_load;
bool mem_env;
size_t block_cache_size;
void load_graph(VG& graph);
void dump(std::ostream& out);
void for_all(std::function<void(string&, string&)> lambda);
void for_range(string& key_start, string& key_end,
std::function<void(string&, string&)> lambda);
void put_node(const Node* node);
void put_edge(const Edge* edge);
void batch_node(const Node* node, rocksdb::WriteBatch& batch);
void batch_edge(const Edge* edge, rocksdb::WriteBatch& batch);
void put_kmer(const string& kmer,
const int64_t id,
const int32_t pos);
void batch_kmer(const string& kmer,
const int64_t id,
const int32_t pos,
rocksdb::WriteBatch& batch);
void put_metadata(const string& tag, const string& data);
void put_node_path(int64_t node_id, int64_t path_id, int64_t path_pos, const Mapping& mapping);
void put_path_position(int64_t path_id, int64_t path_pos, int64_t node_id, const Mapping& mapping);
void put_mapping(const Mapping& mapping);
void put_alignment(const Alignment& alignment);
rocksdb::Status get_node(int64_t id, Node& node);
rocksdb::Status get_edge(int64_t from, int64_t to, Edge& edge);
rocksdb::Status get_metadata(const string& key, string& data);
int get_node_path(int64_t node_id, int64_t path_id, int64_t& path_pos, Mapping& mapping);
void get_mappings(int64_t node_id, vector<Mapping>& mappings);
void get_alignments(int64_t node_id, vector<Alignment>& alignments);
// obtain the key corresponding to each entity
const string key_for_node(int64_t id);
const string key_for_edge_from_to(int64_t from, int64_t to);
const string key_for_edge_to_from(int64_t to, int64_t from);
const string key_prefix_for_edges_from_node(int64_t from);
const string key_prefix_for_edges_to_node(int64_t to);
const string key_for_kmer(const string& kmer, int64_t id);
const string key_prefix_for_kmer(const string& kmer);
const string key_for_metadata(const string& tag);
const string key_for_path_position(int64_t path_id, int64_t path_pos, int64_t node_id);
const string key_for_node_path_position(int64_t node_id, int64_t path_id, int64_t path_pos);
const string key_prefix_for_node_path(int64_t node_id, int64_t path_id);
const string key_for_mapping_prefix(int64_t node_id);
const string key_for_mapping(const Mapping& mapping);
const string key_for_alignment_prefix(int64_t node_id);
const string key_for_alignment(const Alignment& alignment);
// deserialize a key/value pair
void parse_node(const string& key, const string& value, int64_t& id, Node& node);
void parse_edge(const string& key, const string& value, char& type, int64_t& id1, int64_t& id2, Edge& edge);
void parse_kmer(const string& key, const string& value, string& kmer, int64_t& id, int32_t& pos);
void parse_node_path(const string& key, const string& value,
int64_t& node_id, int64_t& path_id, int64_t& path_pos, Mapping& mapping);
void parse_path_position(const string& key, const string& value,
int64_t& path_id, int64_t& path_pos, int64_t& node_id, Mapping& mapping);
void parse_mapping(const string& key, const string& value, int64_t& node_id, string& hash, Mapping& mapping);
void parse_alignment(const string& key, const string& value, int64_t& node_id, string& hash, Alignment& alignment);
// for dumping graph state/ inspection
string entry_to_string(const string& key, const string& value);
string graph_entry_to_string(const string& key, const string& value);
string kmer_entry_to_string(const string& key, const string& value);
string position_entry_to_string(const string& key, const string& value);
string metadata_entry_to_string(const string& key, const string& value);
string node_path_to_string(const string& key, const string& value);
string path_position_to_string(const string& key, const string& value);
string mapping_entry_to_string(const string& key, const string& value);
string alignment_entry_to_string(const string& key, const string& value);
// accessors, traversal, context
void get_context(int64_t id, VG& graph);
void expand_context(VG& graph, int steps);
void get_range(int64_t from_id, int64_t to_id, VG& graph);
void for_graph_range(int64_t from_id, int64_t to_id, function<void(string&, string&)> lambda);
void get_connected_nodes(VG& graph);
void get_edges_of(int64_t id, vector<Edge>& edges);
void get_edges_from(int64_t from, vector<Edge>& edges);
void get_edges_to(int64_t to, vector<Edge>& edges);
void get_path(VG& graph, const string& name, int64_t start, int64_t end);
void node_path_position(int64_t id, string& path_name, int64_t& position, int64_t& offset);
pair<list<int64_t>, int64_t> get_nearest_node_prev_path_member(int64_t node_id, int64_t path_id, int64_t& path_pos, int max_steps = 4);
pair<list<int64_t>, int64_t> get_nearest_node_next_path_member(int64_t node_id, int64_t path_id, int64_t& path_pos, int max_steps = 4);
bool get_node_path_relative_position(int64_t node_id, int64_t path_id,
list<int64_t>& path_prev, int64_t& prev_pos,
list<int64_t>& path_next, int64_t& next_pos);
Mapping path_relative_mapping(int64_t node_id, int64_t path_id,
list<int64_t>& path_prev, int64_t& prev_pos,
list<int64_t>& path_next, int64_t& next_pos);
bool surject_alignment(const Alignment& source,
set<string>& path_names,
Alignment& surjection,
string& path_name,
int64_t& path_pos,
int window = 5);
void path_layout(map<string, pair<int64_t, int64_t> >& layout,
map<string, int64_t>& lengths);
int64_t path_first_node(int64_t path_id);
int64_t path_last_node(int64_t path_id, int64_t& path_length);
// kmers
void get_kmer_subgraph(const string& kmer, VG& graph);
uint64_t approx_size_of_kmer_matches(const string& kmer);
void approx_sizes_of_kmer_matches(const vector<string>& kmers, vector<uint64_t>& sizes);
void for_kmer_range(const string& kmer, function<void(string&, string&)> lambda);
void get_kmer_positions(const string& kmer, map<int64_t, vector<int32_t> >& positions);
void get_kmer_positions(const string& kmer, map<string, vector<pair<int64_t, int32_t> > >& positions);
void prune_kmers(int max_kb_on_disk);
void remember_kmer_size(int size);
set<int> stored_kmer_sizes(void);
void store_batch(map<string, string>& items);
//void store_positions(VG& graph, std::map<long, Node*>& node_path, std::map<long, Edge*>& edge_path);
// once we have indexed the kmers, we can get the nodes and edges matching
void kmer_matches(std::string& kmer, std::set<int64_t>& node_ids, std::set<int64_t>& edge_ids);
// paths
int64_t get_max_path_id(void);
void put_max_path_id(int64_t id);
int64_t new_path_id(const string& name);
string path_name_prefix(const string& name);
string path_id_prefix(int64_t id);
void put_path_id_to_name(int64_t id, const string& name);
void put_path_name_to_id(int64_t id, const string& name);
string get_path_name(int64_t id);
int64_t get_path_id(const string& name);
void load_paths(VG& graph);
void store_paths(VG& graph); // of graph
void store_path(VG& graph, Path& path); // path of graph
map<string, int64_t> paths_by_id(void);
// alignments and mappings
void for_each_mapping(function<void(const Mapping&)> lambda);
void for_each_alignment(function<void(const Alignment&)> lambda);
// what table is the key in
char graph_key_type(string& key);
};
class indexOpenException: public exception
{
virtual const char* what() const throw()
{
return "unable to open variant graph index";
}
};
class keyNotFoundException: public exception
{
virtual const char* what() const throw()
{
return "unable to find key in index";
}
};
}
#endif