2
Copyright (C) 2009- The University of Notre Dame
3
This software is distributed under the GNU General Public License.
4
See the file COPYING for details.
14
#include "sequence_filter.h"
17
#define EVEN_MASK 0xCCCCCCCCCCCCCCCCULL
18
#define ODD_MASK 0x3333333333333333ULL
20
unsigned short short_masks[8] = { 65535, 16383, 4095, 1023, 255, 63, 15, 3 };
22
#define SHORT_MASK_8 65535
23
#define SHORT_MASK_7 16383
24
#define SHORT_MASK_6 4095
25
#define SHORT_MASK_5 1023
26
#define SHORT_MASK_4 255
27
#define SHORT_MASK_3 63
28
#define SHORT_MASK_2 15
29
#define SHORT_MASK_1 3
32
static mer_t k_mask = 0;
33
static int WINDOW_SIZE = 22;
34
static mer_t repeat_mask = 0;
36
#define MER_VALUE(mer) ( (mer & (EVEN_MASK & k_mask)) | ((~mer) & (ODD_MASK & k_mask)) )
38
struct mer_list_elem_s
43
struct mer_list_elem_s * next;
46
typedef struct mer_list_elem_s mer_list_element;
48
struct mer_hash_element_s
51
mer_list_element * mle;
53
struct mer_hash_element_s * next;
55
typedef struct mer_hash_element_s mer_hash_element;
57
struct cand_list_element_s
65
struct cand_list_element_s * next;
67
typedef struct cand_list_element_s cand_list_element;
69
/* These are globals referenced directly by sand_filter_mer_seq. */
70
/* This needs to be cleaned up. */
74
int rectangle_size = 1000;
75
unsigned long total_cand = 0;
77
static int MER_TABLE_BUCKETS = 5000011; //20000003;
78
static int CAND_TABLE_BUCKETS= 5000011; //20000003;
79
static struct cseq ** all_seqs = 0;
80
static cand_list_element ** candidates;
81
static mer_hash_element ** mer_table;
82
static struct itable * repeat_mer_table = 0;
83
static int num_seqs = 0;
85
static int start_x = 0;
87
static int start_y = 0;
91
#define in_range(x, s, e) ( ((s) <= (x)) && ((x) < (e)) )
93
void add_sequence_to_mer(mer_t mer, int i, char dir, short loc);
94
mer_hash_element * find_mer(mer_t mer);
95
void free_mer_table();
96
void free_mer_hash_element(mer_hash_element * mhe);
97
void free_mer_table();
98
void free_cand_table();
99
mer_list_element * create_mer_list_element(int seq_num, char dir, short loc);
100
mer_hash_element * get_mer_hash_element(mer_t mer);
101
void free_mer_list_element(mer_list_element * mle);
102
void mer_generate_cands(mer_hash_element * mhe);
103
void print_8mer(unsigned short mer);
105
mer_t make_mer(const char * str);
107
void add_candidate(int seq, int cand, char dir, mer_t mer, short loc1, short loc2);
108
void free_cand_list_element(cand_list_element * cle);
110
void find_all_kmers(int seq_num);
111
void find_minimizers(int seq_num);
112
minimizer get_minimizer(int seq_num, int window_start);
113
mer_t get_kmer(struct cseq *c, int i);
114
void print_16mer(mer_t mer16);
115
mer_t rev_comp_mer(mer_t mer);
117
void print_mhe(FILE * file, mer_hash_element * mhe);
119
void init_cand_table( int buckets )
122
CAND_TABLE_BUCKETS = buckets;
123
candidates = malloc(CAND_TABLE_BUCKETS * sizeof(cand_list_element *));
124
for (i=0; i < CAND_TABLE_BUCKETS; i++)
130
void init_mer_table( int buckets )
133
MER_TABLE_BUCKETS = buckets;
134
mer_table = malloc(MER_TABLE_BUCKETS * sizeof(mer_hash_element *));
135
for (i=0; i < MER_TABLE_BUCKETS; i++)
141
int load_seqs(FILE * input )
143
int seq_count = sequence_count(input);
145
all_seqs = malloc(seq_count*sizeof(struct cseq *));
148
while ((c=cseq_read(input))) {
149
all_seqs[num_seqs++] = c;
156
int load_seqs_two_files(FILE * f1, int * end1, FILE * f2, int * end2)
159
int count1 = sequence_count(f1);
160
int count2 = sequence_count(f2);
162
all_seqs = malloc((count1+count2)*sizeof(struct cseq *));
165
while((c = cseq_read(f1))) {
166
all_seqs[num_seqs++] = c;
171
while((c = cseq_read(f2))) {
172
all_seqs[num_seqs++] = c;
181
// Loads up a set of mers from a file and stores them.
182
// These mers cannot be treated as minimizers.
183
int init_repeat_mer_table(FILE * repeats, unsigned long buckets, int max_mer_repeat)
185
// Estimate the number of buckets here by dividing the file
189
unsigned long curr_pos = ftell(repeats);
190
fseek(repeats, 0, SEEK_END);
191
unsigned long end_pos = ftell(repeats);
192
buckets = (end_pos - curr_pos) / 25;
193
fseek(repeats, curr_pos, SEEK_SET);
197
int *count = malloc(sizeof(int));;
199
repeat_mer_table = itable_create(buckets);
200
if (k_mask == 0) set_k_mask();
202
while (fscanf(repeats, ">%d %s\n", count, str) == 2)
204
if (*count >= max_mer_repeat)
207
rev = rev_comp_mer(mer);
208
if (MER_VALUE(mer) < MER_VALUE(rev))
209
itable_insert(repeat_mer_table, mer, count);
211
itable_insert(repeat_mer_table, rev, count);
213
count = malloc(sizeof(int));
216
return itable_size(repeat_mer_table);
219
mer_t make_mer(const char * str)
223
int len = strlen(str);
224
for (i=0; i<len; i++)
226
mer = (mer << 2) | base_to_num(str[i]);
231
void rearrange_seqs_for_dist_framework()
235
struct cseq ** top = malloc(rectangle_size*(sizeof(struct cseq *)));
236
struct cseq ** bottom = malloc(rectangle_size*(sizeof(struct cseq*)));
238
for (i=0; i < num_seqs; i+=2)
240
top[i/2] = all_seqs[i];
241
bottom[i/2] = all_seqs[i+1];
243
for (i=0; i<rectangle_size; i++)
245
all_seqs[i] = top[i];
246
all_seqs[i+rectangle_size] = bottom[i];
253
int compare_cand(const void * pair1, const void * pair2)
256
// If c1.cand1 < c2.cand1, return a negative number, meaning less than.
257
// If c1.cand1 and c2.cand1 are equal, check the second one.
258
int diff = ((candidate_t *) pair1)->cand1 - ((candidate_t *) pair2)->cand1;
259
if (!diff) return ((candidate_t *) pair1)->cand2 - ((candidate_t *) pair2)->cand2;
263
int output_candidate_list( FILE * file, candidate_t * list, int total_output )
268
int total_printed = 0;
270
for (i=0; i<total_output; i++)
272
candidate_t pair = list[i];
273
fprintf(file, "%s\t%s\t%d\t%d\t%d\n", all_seqs[pair.cand1]->name, all_seqs[pair.cand2]->name, pair.dir, pair.loc1, (pair.dir == 1) ? pair.loc2 : all_seqs[pair.cand2]->num_bases - pair.loc2 - k);
276
return total_printed;
279
candidate_t * retrieve_candidates(int * total_cand_ret)
282
int total_output = 0;
284
cand_list_element * cle;
286
candidate_t * candidate_list = malloc(total_cand*sizeof(struct candidate_s));
288
for (curr_index = 0; curr_index < CAND_TABLE_BUCKETS; curr_index++)
290
cle = candidates[curr_index];
295
candidate_list[total_output].cand1 = cle->cand1;
296
candidate_list[total_output].cand2 = cle->cand2;
297
candidate_list[total_output].dir = cle->dir;
298
candidate_list[total_output].loc1 = cle->loc1;
299
candidate_list[total_output].loc2 = cle->loc2;
304
free_cand_list_element(candidates[curr_index]);
305
candidates[curr_index] = 0;
308
*total_cand_ret = total_output;
309
qsort(candidate_list, total_output, sizeof(struct candidate_s), compare_cand);
310
return candidate_list;
314
void generate_candidates()
318
mer_hash_element * mhe, *old_mhe;
320
for(curr_bucket = 0; curr_bucket < MER_TABLE_BUCKETS; curr_bucket++)
322
mhe = mer_table[curr_bucket];
325
mer_generate_cands(mhe);
330
mer_table[curr_bucket] = 0;
334
void mer_generate_cands(mer_hash_element * mhe)
338
mer_list_element *head, *curr;
347
add_candidate(head->seq_num, curr->seq_num, head->dir * curr->dir, mhe->mer, head->loc, curr->loc);
353
free_mer_list_element(mhe->mle);
357
void print_mer_table(FILE * file)
360
mer_hash_element * mhe, *old_mhe;
361
for (curr_bucket = 0; curr_bucket < MER_TABLE_BUCKETS; curr_bucket++)
363
mhe = mer_table[curr_bucket];
366
print_mhe(file, mhe);
373
void print_mhe(FILE * file, mer_hash_element * mhe)
377
mer_list_element *head, *curr;
386
translate_kmer(mhe->mer, mer_str, k);
387
fprintf(file, "%s\t%d\t%s\t%s\t%d\n", mer_str, mhe->count, all_seqs[head->seq_num]->name, all_seqs[curr->seq_num]->name, (int) (head->dir * curr->dir));
394
mer_t rev_comp_mer(mer_t mer)
398
for (i = 0; i < k; i++)
400
// Build new_mer by basically popping off the LSB of mer (mer >> 2)
401
// and pushing to the LSB of new_mer.
402
new_mer = new_mer << 2;
403
new_mer = new_mer | (mer & 3);
406
// Now it's reversed, so complement it, but mask it by k_mask so only the important bits get complemented.
407
return (~new_mer) & k_mask;
411
void find_all_kmers(int seq_num)
415
int end = all_seqs[seq_num]->num_bases - 15;
417
for (i = 0; i<end; i+=8)
419
mer16 = get_kmer(all_seqs[seq_num], i);
420
add_sequence_to_mer(mer16, seq_num, (char) 1, (short) i);
424
// Each time you move the window, you add a new kmer.
425
// Then do the following two things.
426
// 1. Check if the new kmer is less than the current minimizer.
427
// If so, set it as the new one.
428
// 2. Is the current absolute minimizer now outside the window?
429
// If so, check the window to find a NEW absolute minimizer, and add it.
430
void find_minimizers(int seq_num)
433
int end = all_seqs[seq_num]->num_bases - k + 1;
434
mer_t mer, rev, mer_val, rev_val;
436
minimizer window[WINDOW_SIZE];
438
int abs_min_index = 0;
442
memset(&abs_min,0,sizeof(abs_min));
443
abs_min.value = MINIMIZER_MAX;
446
// First, just populate the first window and get the first minimizer.
447
for (i = 0; i < WINDOW_SIZE; i++)
449
mer = get_kmer(all_seqs[seq_num], i);
450
rev = rev_comp_mer(mer);
451
mer_val = MER_VALUE(mer);
452
rev_val = MER_VALUE(rev);
454
if (mer_val < rev_val)
457
window[i].value = mer_val;
464
window[i].value = rev_val;
468
if (window[i].value < abs_min.value)
475
// Add the absolute minimizer for the first window.
476
add_sequence_to_mer(abs_min.mer, seq_num, abs_min.dir, abs_min.loc);
478
for (i = WINDOW_SIZE; i < end; i++)
480
index = i%WINDOW_SIZE;
482
// First, add the new k-mer to the window, evicting the k-mer that is
483
// no longer in the window
484
mer = get_kmer(all_seqs[seq_num], i);
485
rev = rev_comp_mer(mer);
486
mer_val = MER_VALUE(mer);
487
rev_val = MER_VALUE(rev);
489
if (mer_val < rev_val)
491
window[index].mer = mer;
492
window[index].value = mer_val;
493
window[index].dir = 1;
494
window[index].loc = i;
498
window[index].mer = rev;
499
window[index].value = rev_val;
500
window[index].dir = -1;
501
window[index].loc = i;
504
// Now, check if the new k-mer is better than the current absolute minimizer.
505
//if (window[index].value < abs_min.value)
506
if (window[index].value < abs_min.value)
508
// If so, set it as the new absolute minimizer and add this sequence to the mer table
509
abs_min = window[index];
510
abs_min_index = index;
511
add_sequence_to_mer(abs_min.mer, seq_num, abs_min.dir, abs_min.loc);
513
// Now, check if the current absolute minimizer is out of the window
514
// We just replaced index, so if abs_min_index == index, we just evicted
515
// the current minimizer.
516
else if (abs_min_index == index)
518
// Find the new minimizer
519
// If runtime starts to suffer I can implement something better than a linear search,
520
// but because WINDOW_SIZE is a small constant (around 20) it should be OK.
521
abs_min.value = MINIMIZER_MAX;
523
for (j = 0; j < WINDOW_SIZE; j++)
525
if (window[j].value < abs_min.value)
531
// Add the new current minimizer to the mer table.
532
add_sequence_to_mer(abs_min.mer, seq_num, abs_min.dir, abs_min.loc);
537
// Gets the next minimizer for this sequence. Returns 1 if it worked, 0 if we're at the end of the sequence.
538
int get_next_minimizer(int seq_num, minimizer * next_minimizer )
541
static int index = 0;
542
static minimizer * window = 0;
543
static minimizer abs_min = {0, ULONG_MAX, -1, 0};
544
static int abs_min_index = 0;
545
static int prev_seq_num = -1;
548
mer_t mer, rev, mer_val, rev_val;
550
// Re-initialize everything if the sequence we are using changes.
551
if (seq_num != prev_seq_num)
553
if (!window) window = malloc(WINDOW_SIZE*sizeof(minimizer));
557
abs_min.value = ULONG_MAX;
561
end = all_seqs[seq_num]->num_bases - k + 1;
562
prev_seq_num = seq_num;
565
// If we haven't populated the whole window yet, do so now.
569
for (i = 0; i < WINDOW_SIZE; i++)
571
// Get the current mer, its reverse complement, and its minimizer values.
572
mer = get_kmer(all_seqs[seq_num], i);
573
rev = rev_comp_mer(mer);
574
mer_val = MER_VALUE(mer);
575
rev_val = MER_VALUE(rev);
577
// Add them to the window.
579
if (mer_val < rev_val)
581
window[index].mer = mer;
582
window[index].value = mer_val;
583
window[index].dir = 1;
584
window[index].loc = i;
588
window[index].mer = rev;
589
window[index].value = rev_val;
590
window[index].dir = -1;
591
window[index].loc = i;
593
if (window[index].value < abs_min.value)
595
abs_min = window[index];
596
abs_min_index = index;
600
// Now, return the minimizer we found (it will be the first minimizer for the list)
601
*next_minimizer = abs_min;
606
// Otherwise, we can just continue on from the current position of i.
607
for ( ; i < end; i++)
609
index = i%WINDOW_SIZE;
611
// First, add the new k-mer to the window, evicting the k-mer that is
612
// no longer in the window
613
mer = get_kmer(all_seqs[seq_num], i);
614
rev = rev_comp_mer(mer);
615
mer_val = MER_VALUE(mer);
616
rev_val = MER_VALUE(rev);
618
if (mer_val < rev_val)
620
window[index].mer = mer;
621
window[index].value = mer_val;
622
window[index].dir = 1;
623
window[index].loc = i;
627
window[index].mer = rev;
628
window[index].value = rev_val;
629
window[index].dir = -1;
630
window[index].loc = i;
633
// Now, check if the new k-mer is better than the current absolute minimizer.
634
if (window[index].value < abs_min.value)
636
// If so, set it as the new absolute minimizer and add this sequence to the mer table
637
abs_min = window[index];
638
abs_min_index = index;
639
*next_minimizer = abs_min;
640
i++; // Increment i so we won't process this k-mer again.
643
// Now, check if the current absolute minimizer is out of the window
644
// We just replaced index, so if abs_min_index == index, we just evicted
645
// the current minimizer.
646
else if (abs_min_index == index)
648
// Find the new minimizer
649
// If runtime starts to suffer I can implement something better than a linear search,
650
// but because WINDOW_SIZE is a small constant (around 20) it should be OK.
652
abs_min.value = ULONG_MAX;
654
for (j = 0; j < WINDOW_SIZE; j++)
656
if (window[j].value < abs_min.value)
662
// Add the new current minimizer to the mer table.
663
*next_minimizer = abs_min;
664
i++; // Increment i so we won't process this k-mer again.
669
// We made it to the end of the sequence without finding a new minimizer, so we are done.
673
mer_t get_kmer(struct cseq *c, int curr)
675
// Which mer does this kmer start in?
676
int which_mer = curr/8;
677
int which_base = curr%8;
678
unsigned short curr_mer = 0;
683
// Start from the first base and push k bases.
684
while (bases_left > 0)
686
// We can fit the rest of this short inside mer, so do it.
687
if ((bases_left >= 8) || (bases_left > (8-which_base)))
689
// Mask out everything before which_base
690
curr_mer = c->data[which_mer] & short_masks[which_base];
692
// Push mer so that there is enough space for curr_mer
693
mer = mer << ( (8-which_base)*2 );
695
// Add curr_mer onto mer.
696
mer = mer | (mer_t) curr_mer;
698
bases_left -= (8 - which_base);
702
// Now we're down to the last few bases and we need to handle overflow.
705
// The bases in this short will be enough
707
// Make enough room for the rest of the bases
708
mer = mer << bases_left*2;
710
// Shift the curr mer to the end and mask it out.
711
curr_mer = c->data[which_mer];
713
int mercount = c->num_bases/8;
714
if (c->num_bases%8 > 0) { mercount++; }
716
if ((mercount-1) == which_mer) { curr_mer = curr_mer << ((8-(c->num_bases - (8*which_mer)))*2); }
717
curr_mer = (curr_mer >> ((8 - (bases_left+which_base))*2 )) & short_masks[8-bases_left];
719
// Now add it on to mer.
720
mer = mer | curr_mer;
728
void print_8mer(unsigned short mer)
734
str[i] = num_to_base((mer >> ((8-1)-i)*2) & 3);
741
void translate_kmer(mer_t mer, char * str, int length)
743
//print_mer(stderr, mer);
746
//int int_len = sizeof(mer_t)*8;
748
// 2 bits represent each base. So, to get the first base, we the
749
// two most significant bits. To get the second base, the two second
750
// most significant bits, etc. In other, we need to bit shift all but
751
// 2 (aka bitshift 14 to the right) when i = 0, bitshift 12 when i=1,
753
// We mask by 3 to make sure we only have the two numbers and nothing
754
// but 0's in the rest.
755
for (i=0; i<length; i++)
757
str[i] = num_to_base((mer >> ((length-1)-i)*2) & 3);
763
void add_sequence_to_mer(mer_t mer, int seq_num, char dir, short loc)
765
// Store the sequence and its reverse complement as the same key.
767
if (repeat_mer_table && itable_lookup(repeat_mer_table, mer)) return;
769
mer_list_element * mle, * new_mle;
771
// This will create it if it doesn't exist.
772
mer_hash_element * mhe = get_mer_hash_element(mer);
774
// Check that the list exists.
777
// If not, create it, increment the count and we're done.
778
new_mle = create_mer_list_element(seq_num, dir, loc);
784
// If a list does exist, add this sequence it.
788
// Because we add one sequence at a time, this will be at the front
789
// if it has ever had this mer before, so we don't add it twice.
790
if (mle->seq_num == seq_num) return;
792
new_mle = create_mer_list_element(seq_num, dir, loc);
799
mer_list_element * create_mer_list_element(int seq_num, char dir, short loc)
801
mer_list_element * new_mle = malloc(sizeof(*new_mle));
802
new_mle->seq_num = seq_num;
810
mer_hash_element * get_mer_hash_element(mer_t mer)
812
int bucket = mer % MER_TABLE_BUCKETS;
813
mer_hash_element * mhe;
815
// If there are no hash elements in this bucket
817
if (!mer_table[bucket])
819
mhe = malloc(sizeof(*mhe));
824
mer_table[bucket] = mhe;
830
// If this bucket is not empty, but does not contain this mer, add it.
832
mer_hash_element * new_mhe = malloc(sizeof(*new_mhe));
836
new_mhe->next = mer_table[bucket];
837
mer_table[bucket] = new_mhe;
844
mer_hash_element * find_mer(mer_t mer)
846
int bucket = mer % MER_TABLE_BUCKETS;
848
mer_hash_element * mhe = mer_table[bucket];
852
if (mhe->mer == mer) { return mhe; }
859
void free_mer_table()
863
for (; curr_mhe < MER_TABLE_BUCKETS; curr_mhe++)
865
free_mer_hash_element(mer_table[curr_mhe]);
869
void free_mer_hash_element(mer_hash_element * mhe)
873
free_mer_list_element(mhe->mle);
874
mer_hash_element * n = mhe->next;
876
free_mer_hash_element(n);
879
void free_mer_list_element(mer_list_element * mle)
883
mer_list_element * n = mle->next;
885
free_mer_list_element(n);
888
void set_k(int new_k)
894
void set_window_size(int new_size)
896
WINDOW_SIZE = new_size;
906
// Push it over two bits and or by binary 11
907
// This amounts to pushing two 1's onto the right side.
908
k_mask = (k_mask << 2) | 3;
912
void load_mer_table()
914
int curr_col, end_col, curr_row, end_row;
915
curr_col = curr_rect_x*rectangle_size;
916
end_col = curr_col+rectangle_size;
917
if (end_col > num_seqs) { end_col = num_seqs; }
919
curr_row = curr_rect_y*rectangle_size;
920
end_row = curr_row+rectangle_size;
921
if (end_row > num_seqs) { end_row = num_seqs; }
923
load_mer_table_subset(curr_col, end_col, curr_row, end_row, (curr_rect_x == curr_rect_y));
926
void load_mer_table_subset(int curr_col, int end_col, int curr_row, int end_row, int is_same_rect)
929
mer_t repeat_mask_rev;
931
if (k_mask == 0) { set_k_mask(); }
932
repeat_mask_rev = rev_comp_mer(repeat_mask);
933
if (MER_VALUE(repeat_mask_rev) < MER_VALUE(repeat_mask)) repeat_mask = repeat_mask_rev;
939
same_rect = is_same_rect;
941
// This is an imaginary matrix, but we're loading all the sequences
942
// on a given rectangle, defined by curr_rect_x, curr_rect_y and rectangle_size.
943
// Load the mers in each of these sequences, then we'll output any matches.
945
for ( ; curr_col < end_col; curr_col++ )
947
find_minimizers(curr_col);
950
// If we are on the diagonal, don't need to add both, because they are the same.
951
if (is_same_rect) { return; }
953
for ( ; curr_row < end_row; curr_row++ )
955
find_minimizers(curr_row);
959
cand_list_element * create_new_cle(int seq1, int seq2, int dir, int loc1, int loc2)
961
cand_list_element * new_cle = malloc(sizeof(*new_cle));
964
new_cle->cand1 = seq1;
965
new_cle->cand2 = seq2;
966
new_cle->loc1 = loc1;
967
new_cle->loc2 = loc2;
971
new_cle->cand2 = seq1;
972
new_cle->cand1 = seq2;
973
new_cle->loc2 = loc1;
974
new_cle->loc1 = loc2;
983
int should_compare_cands(int c1, int c2)
985
// If the two rectangles are equal, then we are intended to compare
986
// two from the same rectangle, so return 1.
987
if (same_rect) { return 1; }
989
// Otherwise, return false if they are in the same rectangle,
991
if (in_range(c1, start_x, end_x) && in_range(c2, start_x, end_x)) { return 0; }
992
if (in_range(c1, start_y, end_y) && in_range(c2, start_y, end_y)) { return 0; }
997
void add_candidate(int seq, int cand, char dir, mer_t min, short loc1, short loc2)
999
// Unless this is a diagonal, ones from the same block have already been compared.
1000
// If I don't do this step, then ones from the same block on the same axis
1001
// could get compared, because we don't really distinguish them.
1003
if (!should_compare_cands(seq, cand)) return;
1005
int index = (seq*cand*499);
1006
if (index < 0) { index *= -1; }
1007
index = index % CAND_TABLE_BUCKETS;
1009
cand_list_element * cle = candidates[index];
1010
// There are no candidate pairs in this bucket
1013
candidates[index] = create_new_cle(seq, cand, dir, loc1, loc2);
1019
// This bucket has candidate pairs, if ours is one of them just leave
1020
// because we've already printed it out.
1023
if ((cle->cand1 == seq) && (cle->cand2 == cand) && (cle->dir == dir))
1028
else if ((cle->cand2 == seq) && (cle->cand1 == cand) && (cle->dir == dir))
1036
// If we made it this far, we did not find this candidate pair, so add it.
1037
cand_list_element * new_cle = create_new_cle(seq, cand, dir, loc1, loc2);
1038
new_cle->next = candidates[index];
1039
candidates[index] = new_cle;
1045
void free_cand_table()
1049
for (i = 0; i < CAND_TABLE_BUCKETS; i++)
1051
free_cand_list_element(candidates[i]);
1056
void free_cand_list_element(cand_list_element * cle)
1060
cand_list_element * n = cle->next;
1062
free_cand_list_element(n);