Context Navigation

← Previous Revision
Next Revision →
Blame
Revision Log

source: tags/initial/NALIGNER/ali_aligner.hxx

Visit:

Last change on this file was 2, checked in by oldcode, 25 years ago
Initial revision
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 11.1 KB

Line
1
2
3	#ifndef _ALI_ALIGNER_INC_
4	#define _ALI_ALIGNER_INC_
5
6	#include <malloc.h>
7
8	#include "ali_solution.hxx"
9	#include "ali_tstack.hxx"
10	#include "ali_tlist.hxx"
11	#include "ali_tarray.hxx"
12	#include "ali_profile.hxx"
13	#include "ali_pathmap.hxx"
14
15	#define ALI_ALIGNER_INS 1
16	#define ALI_ALIGNER_SUB 2
17	#define ALI_ALIGNER_DEL 3
18	#define ALI_ALIGNER_MULTI_FLAG 4
19
20	struct ALI_ALIGNER_CONTEXT {
21	long max_number_of_maps;
22	};
23
24	/*
25	* Structure of a cell of the distance matrix
26	*/
27	struct ali_aligner_cell {
28	float d1, d2, d3;
29	ALI_TARRAY<ali_pathmap_up_pointer> *starts;
30
31	ali_aligner_cell(void) {
32	d1 = d2 = d3 = 0.0;
33	starts = 0;
34	}
35
36	void print(void) {
37	printf("%4.2f %4.2f %4.2f %8p",d1,d2,d3,starts);
38	}
39	};
40
41	/*
42	* Structure of a column of the distance matrix
43	*/
44	struct ali_aligner_column {
45	unsigned long column_length;
46	//ali_aligner_cell (*cells)[];
47	ali_aligner_cell **cells;
48
49	ali_aligner_column(unsigned long length) {
50	column_length = length;
51	cells = (ali_aligner_cell**) calloc((unsigned int) column_length, sizeof(ali_aligner_cell));
52	//cells = (ali_aligner_cell (*) [0]) calloc((unsigned int) column_length, sizeof(ali_aligner_cell));
53	//cells = (ali_aligner_cell (*) [1]) calloc((unsigned int) column_length, sizeof(ali_aligner_cell));
54	if (cells == 0)
55	ali_fatal_error("Out of memory");
56	}
57	~ali_aligner_column(void) {
58	if (cells)
59	free((char *) cells);
60	}
61
62	void print(void) {
63	unsigned int i;
64	for (i = 0; i < column_length; i++) {
65	printf("%2d: ",i);
66	(*cells)[i].print();
67	printf("\n");
68	}
69	}
70	};
71
72	/*
73	* Structure of a LONG deletion (multi gap) in the distance matrix
74	*/
75	struct ali_aligner_dellist_elem {
76	unsigned long start;
77	float costs;
78	unsigned char operation;
79
80	ali_aligner_dellist_elem(unsigned long s = 0, float c = 0.0,
81	unsigned char op = 0) {
82	start = s;
83	costs = c;
84	operation = op;
85	}
86
87	void print(void) {
88	printf("(%3ld %4.2f %2d)",start,costs,operation);
89	}
90	};
91
92	/*
93	* Structure of the list of LONG deletions in the distance matrix
94	*/
95	struct ali_aligner_dellist {
96	ALI_PROFILE *profile;
97	ALI_TLIST<ali_aligner_dellist_elem *> list_of_dels;
98
99	ali_aligner_dellist(ALI_PROFILE *p) {
100	profile = p;
101	}
102	~ali_aligner_dellist(void) {
103	ali_aligner_dellist_elem * elem;
104	if (!list_of_dels.is_empty()) {
105	elem = list_of_dels.first();
106	while (list_of_dels.is_next()) {
107	delete elem;
108	elem = list_of_dels.next();
109	}
110	delete elem;
111	}
112	}
113
114	void print(void) {
115	printf("DEL_LIST: ");
116	if (!list_of_dels.is_empty()) {
117	list_of_dels.first()->print();
118	while (list_of_dels.is_next()) {
119	printf(", ");
120	list_of_dels.next()->print();
121	}
122	}
123	printf("\n");
124	}
125	void print_cont(unsigned long position) {
126	ali_aligner_dellist_elem *elem;
127	if (!list_of_dels.is_empty()) {
128	elem = list_of_dels.first();
129	while (list_of_dels.is_next()) {
130	elem->print();
131	printf("\t %f\n",profile->gap_percent(elem->start,position));
132	elem = list_of_dels.next();
133	}
134	elem->print();
135	printf("\t %f\n",profile->gap_percent(elem->start,position));
136	}
137	}
138	unsigned long length(void) {
139	return list_of_dels.cardinality();
140	}
141	void make_empty(void) {
142	ali_aligner_dellist_elem *elem;
143	if (!list_of_dels.is_empty()) {
144	elem = list_of_dels.first();
145	while (list_of_dels.is_next()) {
146	delete elem;
147	elem = list_of_dels.next();
148	}
149	delete elem;
150	}
151	list_of_dels.make_empty();
152	}
153	void insert(unsigned long start, float costs, unsigned char operation) {
154	ali_aligner_dellist_elem *new_elem;
155
156	new_elem = new ali_aligner_dellist_elem(start,costs,operation);
157	list_of_dels.append_end(new_elem);
158	}
159	float update(unsigned long position);
160	ALI_TARRAY<ali_pathmap_up_pointer> *starts(float costs,
161	unsigned long y_offset);
162	void optimize(unsigned long position);
163	};
164
165
166	/*
167	* Structure of the virtual cell at the left buttom
168	*/
169	struct ali_aligner_last_cell {
170	ALI_PROFILE *profile;
171	float d1, d2, d3;
172	ALI_TLIST<ali_pathmap_up_pointer> left_starts;
173	ALI_TLIST<ali_pathmap_up_pointer> up_starts;
174
175	ali_aligner_last_cell(ALI_PROFILE *prof) {
176	profile = prof;
177	d1 = d2 = d3 = -1.0;
178	}
179
180	void insert_left(unsigned long start, unsigned char operation, float costs) {
181	ali_pathmap_up_pointer left;
182	if (costs < d3 \|\| d3 == -1.0) {
183	left_starts.make_empty();
184	d3 = costs;
185	}
186	if (costs == d3) {
187	left.start = start;
188	left.operation = operation;
189	left_starts.append_end(left);
190	}
191	}
192	void insert_up(unsigned long start, unsigned char operation, float costs) {
193	ali_pathmap_up_pointer up;
194	if (costs < d1 \|\| d1 == -1.0) {
195	up_starts.make_empty();
196	d1 = costs;
197	}
198	if (costs == d1) {
199	up.start = start;
200	up.operation = operation;
201	up_starts.append_end(up);
202	}
203	}
204	void update_border(unsigned long start_x, unsigned long end_x,
205	unsigned long start_y, unsigned long end_y)
206	{
207	float cost;
208
209	cost = profile->w_del_multi(start_y, end_y) +
210	profile->w_ins_multi(start_x, end_x);
211
212	insert_left(0, ALI_UP, cost);
213	insert_up(0, ALI_LEFT, cost);
214	}
215	void update_left(ali_aligner_cell *akt_cell, unsigned long akt_pos,
216	unsigned long start_x, unsigned long end_x) {
217	float min;
218	unsigned char operation = 0;
219
220	min = (akt_cell->d1 < akt_cell->d2) ? akt_cell->d1 : akt_cell->d2;
221	if (akt_cell->d1 == min)
222	operation \|= ALI_UP;
223	if (akt_cell->d2 == min)
224	operation \|= ALI_DIAG;
225
226	insert_left(akt_pos, operation,
227	min + profile->w_ins_multi_cheap(start_x + akt_pos, end_x));
228	}
229	void update_up(ali_aligner_cell *akt_cell, unsigned long akt_pos,
230	unsigned long start_y, unsigned long end_y) {
231	float min;
232	unsigned char operation = 0;
233
234	min = (akt_cell->d3 < akt_cell->d2) ? akt_cell->d3 : akt_cell->d2;
235	if (akt_cell->d3 == min)
236	operation \|= ALI_LEFT;
237	if (akt_cell->d2 == min)
238	operation \|= ALI_DIAG;
239
240	insert_up(akt_pos,operation,
241	min + profile->w_del_multi_cheap(start_y + akt_pos, end_y));
242	}
243	void update_up(ali_aligner_column *akt_col,
244	unsigned long start_y, unsigned long end_y) {
245	unsigned long cell;
246
247	/*
248	* Value for start := start + 1 (because of -1)
249	*/
250
251	for (cell = 0; cell < akt_col->column_length - 1; cell++)
252	update_up(&(*akt_col->cells)[cell], cell + 1, start_y, end_y);
253
254	d2 = (*akt_col->cells)[akt_col->column_length - 1].d2;
255	}
256
257	void print(void) {
258	ali_pathmap_up_pointer elem;
259	printf("d1 = %f, d2 = %f, d3 = %f\n",d1,d2,d3);
260	printf("left starts = ");
261	if (!left_starts.is_empty()) {
262	elem = left_starts.first();
263	printf("<(%ld %d)",(long)elem.start,elem.operation);
264	while (left_starts.is_next()) {
265	elem = left_starts.next();
266	printf(", (%ld %d)",(long)elem.start,elem.operation);
267	}
268	printf(">\n");
269	}
270	else {
271	printf("empty\n");
272	}
273	printf("up starts = ");
274	if (!up_starts.is_empty()) {
275	elem = up_starts.first();
276	printf("<(%ld %d)",elem.start,elem.operation);
277	while (up_starts.is_next()) {
278	elem = up_starts.next();
279	printf(", (%ld %d)",(long)elem.start,elem.operation);
280	}
281	printf(">\n");
282	}
283	else {
284	printf("empty\n");
285	}
286	}
287	};
288
289
290	/*
291	* Structure for collecting all possible solution
292	*/
293	struct ali_aligner_result {
294	ALI_TLIST<ALI_MAP > map_list;
295
296	ali_aligner_result(void) {
297	map_list = new ALI_TLIST<ALI_MAP *>;
298	}
299	~ali_aligner_result(void) {
300	if (map_list) {
301	clear();
302	delete map_list;
303	}
304	}
305
306	void insert(ALI_MAP *in_map) {
307	map_list->append_end(in_map);
308	}
309	void clear(void) {
310	if (!map_list->is_empty()) {
311	delete map_list->first();
312	while (map_list->is_next())
313	delete map_list->next();
314	}
315	}
316	};
317
318
319	/*
320	* Class of the extended aligner
321	*/
322	class ALI_ALIGNER {
323	ALI_PROFILE *profile;
324	ALI_PATHMAP *path_map[3];
325	ali_aligner_last_cell *last_cell;
326
327	ali_aligner_result result;
328	unsigned long result_counter;
329	unsigned long start_x, end_x, start_y, end_y;
330
331	float minimum2(float a, float b);
332	float minimum3(float a, float b, float c);
333
334	void calculate_first_column_first_cell(
335	ali_aligner_cell akt_cell, ali_aligner_dellist del_list);
336	void calculate_first_column_second_cell(
337	ali_aligner_cell up_cell, ali_aligner_cell akt_cell,
338	ali_aligner_dellist *del_list);
339	void calculate_first_column_cell(
340	ali_aligner_cell up_cell, ali_aligner_cell akt_cell,
341	unsigned long pos_y, ali_aligner_dellist *del_list);
342	void calculate_first_column(ali_aligner_column *akt_col,
343	ali_aligner_dellist *del_list);
344
345	void calculate_second_column_first_cell(
346	ali_aligner_cell left_cell, ali_aligner_cell akt_cell,
347	ali_aligner_dellist *del_list);
348	void calculate_second_column_second_cell(
349	ali_aligner_cell diag_cell, ali_aligner_cell left_cell,
350	ali_aligner_cell up_cell, ali_aligner_cell akt_cell,
351	ali_aligner_dellist *del_list);
352	void calculate_second_column_cell(
353	ali_aligner_cell diag_cell, ali_aligner_cell left_cell,
354	ali_aligner_cell up_cell, ali_aligner_cell akt_cell,
355	unsigned long pos_y, ali_aligner_dellist *del_list);
356	void calculate_second_column(ali_aligner_column *prev_col,
357	ali_aligner_column *akt_col,
358	ali_aligner_dellist *del_list);
359
360	void calculate_first_cell(
361	ali_aligner_cell left_cell, ali_aligner_cell akt_cell,
362	unsigned long pos_x, ali_aligner_dellist *del_list);
363	void calculate_second_cell(
364	ali_aligner_cell diag_cell, ali_aligner_cell left_cell,
365	ali_aligner_cell up_cell, ali_aligner_cell akt_cell,
366	unsigned long pos_x, ali_aligner_dellist *del_list);
367	void calculate_cell(ali_aligner_cell diag_cell, ali_aligner_cell left_cell,
368	ali_aligner_cell up_cell, ali_aligner_cell akt_cell,
369	unsigned long pos_x, unsigned long pos_y,
370	ali_aligner_dellist *del_list);
371	void calculate_column(ali_aligner_column *prev_col,
372	ali_aligner_column *akt_col,
373	unsigned long pos_x,
374	ali_aligner_dellist *del_list);
375
376	void calculate_matrix(void);
377
378	void generate_result(ALI_TSTACK<unsigned char> *stack);
379	void mapper_pre(ALI_TSTACK<unsigned char> *stack,
380	unsigned long pos_x, unsigned long pos_y,
381	unsigned char operation,
382	int random_mapping_flag = 0);
383	void mapper_post(ALI_TSTACK<unsigned char> *stack,
384	unsigned long pos_x, unsigned long pos_y);
385	void mapper_pre_random_up(
386	ALI_TSTACK<unsigned char> *stack,
387	ALI_TLIST<ali_pathmap_up_pointer> *list);
388	void mapper_pre_random_left(
389	ALI_TSTACK<unsigned char> *stack,
390	ALI_TLIST<ali_pathmap_up_pointer> *list);
391	void mapper_random(ALI_TSTACK<unsigned char> *stack, int plane,
392	unsigned long pos_x, unsigned long pos_y);
393	void mapper(ALI_TSTACK<unsigned char> *stack, int plane,
394	unsigned long pos_x, unsigned long pos_y);
395	void make_map_random(ALI_TSTACK<unsigned char> *stack);
396	void make_map_systematic(ALI_TSTACK<unsigned char> *stack);
397	void make_map(void);
398
399	unsigned long number_of_solutions();
400
401	public:
402	ALI_ALIGNER(ALI_ALIGNER_CONTEXT context, ALI_PROFILE profile,
403	unsigned long start_x, unsigned long end_x,
404	unsigned long start_y, unsigned long end_y);
405	ALI_TLIST<ALI_MAP > solutions(void) {
406	ALI_TLIST<ALI_MAP > ret = result.map_list;
407	result.map_list = 0;
408	return ret;
409	}
410	};
411
412
413
414	#endif
415

Note: See TracBrowser for help on using the repository browser.

Download in other formats: