0
|
1 #define QF_LAMBDA 0.275
|
|
2 #define QF_KARLIN 0.333
|
|
3
|
|
4
|
|
5
|
|
6 typedef struct {
|
|
7 uint64_t id; //The thread id
|
|
8 SeqInfo * database; //Database sequence and lengths
|
|
9 SeqInfo * query; //Query sequence and lengths
|
|
10 uint64_t from; //Starting READ to compute alignments from
|
|
11 uint64_t to; //End READ to compute alignments from
|
|
12 AVLContainer * container_a; //Container to hold the multidimensional array
|
|
13 AVLContainer * container_b; //Container to hold the multidimensional array
|
|
14 AVLContainer * container_c; //Container to hold the multidimensional array
|
|
15 AVLContainer * container_d; //Container to hold the multidimensional array
|
|
16 uint64_t * contained_reads;
|
|
17 uint64_t * base_coordinates;
|
|
18 uint64_t accepted_query_reads; //Number of reads that have a fragment with evalue less than specified
|
|
19 long double min_e_value; //Minimum evalue to accept read
|
|
20 long double min_coverage; //Minimum coverage percentage to accept read
|
|
21 long double min_identity; //Minimum identity percentage to accept read
|
|
22 long double window; //Percentage of window that will be explored (+-)
|
|
23 FILE * out; //File to write alignments out
|
|
24 int igap;
|
|
25 int egap;
|
|
26 uint64_t * hits; // To work in hits mode only
|
|
27 struct positioned_cell * mc;
|
|
28 struct cell ** table;
|
|
29 char * reconstruct_X;
|
|
30 char * reconstruct_Y;
|
|
31 char * writing_buffer_alignment;
|
|
32 unsigned char * my_x;
|
|
33 unsigned char * my_y;
|
|
34 Head * queue_head; //To tell where the queue starts after modifications
|
|
35 pthread_mutex_t * lock;
|
|
36 unsigned char full_comp; // Tells whether read reporting should stop at first match or keep reporting
|
|
37 unsigned char * markers; // To tell which sequences were already used
|
|
38 } HashTableArgs;
|
|
39
|
|
40
|
|
41
|
|
42 /*
|
|
43 Nucleotides matching function
|
|
44 */
|
|
45 int64_t compare_letters(unsigned char a, unsigned char b);
|
|
46
|
|
47 /**
|
|
48 * Initialize the memory pool to later retrieve individual memory addresses for llpos
|
|
49 *
|
|
50 */
|
|
51 void init_mem_pool_llpos(Mempool_l * mp);
|
|
52
|
|
53 /**
|
|
54 * Get a new memory address from the pool mp for a type llpos
|
|
55 *
|
|
56 */
|
|
57 llpos * getNewLocationllpos(Mempool_l * mp, uint64_t * n_pools_used);
|
|
58
|
|
59 /*
|
|
60 Load input database using 4 threads
|
|
61 */
|
|
62 void * load_input(void * a);
|
|
63 /*
|
|
64 Compute alignments by thread given a hash table argument
|
|
65 */
|
|
66 void * computeAlignmentsByThread(void * a);
|
|
67
|
|
68
|
|
69 /*
|
|
70 Performs NW and backtracking to recover alignment
|
|
71 */
|
|
72 void build_alignment(char * reconstruct_X, char * reconstruct_Y, uint64_t curr_db_seq, uint64_t curr_read, HashTableArgs * hta, unsigned char * my_x, unsigned char * my_y, struct cell ** table, struct positioned_cell * mc, char * writing_buffer_alignment, BasicAlignment * ba, uint64_t xlen, uint64_t ylen, int64_t * cell_path_y, long double * window);
|
|
73
|
|
74 /*
|
|
75 Compute the alignment and evalue of a given hit
|
|
76 The positions pos_database and pos_query refer to the last match in the hit
|
|
77 */
|
|
78 void alignmentFromQuickHits(SeqInfo * database, SeqInfo * query, uint64_t pos_database, uint64_t pos_query, uint64_t curr_read, uint64_t curr_db_seq, Quickfrag * qf, uint64_t offset_db_reads, uint64_t offset_db_coordinates);
|
|
79
|
|
80 /*
|
|
81 Computes the cell path for the y points given incremental x
|
|
82 Only add +- window size to each to know which path to go through
|
|
83 */
|
|
84 void calculate_y_cell_path(Point p0, Point p1, Point p2, Point p3, int64_t * cell_path_y);
|
|
85 /*
|
|
86 Calculates NW table with two rows and stores a cellpath of scores, identities, gaps and starting and ending positions
|
|
87 */
|
|
88 struct best_cell NW(unsigned char * X, uint64_t Xstart, uint64_t Xend, unsigned char * Y, uint64_t Ystart, uint64_t Yend, int64_t iGap, int64_t eGap, struct cell ** table, struct positioned_cell * mc, int show, int64_t * cell_path_y, long double * window, uint64_t * curr_window_size);
|
|
89
|
|
90 /*
|
|
91 Computes the alignment given a NW table
|
|
92 */
|
|
93 void backtrackingNW(unsigned char * X, uint64_t Xstart, uint64_t Xend, unsigned char * Y, uint64_t Ystart, uint64_t Yend, struct cell ** table, char * rec_X, char * rec_Y, struct best_cell * bc, uint64_t * ret_head_x, uint64_t * ret_head_y, BasicAlignment * ba, int64_t * cell_path_y, uint64_t window_size);
|
|
94
|
|
95 /*
|
|
96 Get memory for a new AVL tree node
|
|
97 */
|
|
98 AVLTree * getNewLocationAVLTree(Mempool_AVL * mp, uint64_t * n_pools_used, uint64_t key);
|
|
99
|
|
100 /*
|
|
101 Initialize a memory pool for AVL trees
|
|
102 */
|
|
103 void init_mem_pool_AVL(Mempool_AVL * mp);
|
|
104
|
|
105 /*
|
|
106 Right rotate an AVL tree to make it balanced
|
|
107 */
|
|
108 AVLTree * right_rotate(AVLTree * y);
|
|
109
|
|
110 /*
|
|
111 Left rotate an AVL tree to make it balanced
|
|
112 */
|
|
113 AVLTree * left_rotate(AVLTree * x);
|
|
114
|
|
115
|
|
116 /*
|
|
117 Find a key in an AVL tree
|
|
118 */
|
|
119 AVLTree * find_AVLTree(AVLTree * node, uint64_t key);
|
|
120
|
|
121 /*
|
|
122 Find a key in an AVL tree but return its hit list
|
|
123 */
|
|
124 llpos * find_AVLTree_llpos(AVLTree * node, uint64_t key);
|
|
125
|
|
126 /*
|
|
127 Insert node in AVL tree
|
|
128 */
|
|
129 AVLTree * insert_AVLTree(AVLTree * node, uint64_t key, Mempool_AVL * mp, uint64_t * n_pools_used, uint64_t pos, Mempool_l * mp_l, uint64_t * n_pools_used_l, uint64_t s_id);
|
|
130
|
|
131 /*
|
|
132 Traverse AVL tree in pre order
|
|
133 */
|
|
134 void pre_order(AVLTree * root);
|
|
135
|
|
136
|