|
NCBI Home IEB Home C Toolkit docs C++ Toolkit source browser C Toolkit source browser (2) |
NCBI C Toolkit Cross ReferenceC/api/blocks.c |
source navigation diff markup identifier search freetext search file search |
1 /* $Id: blocks.c,v 6.3 1999/11/26 15:42:23 vakatov Exp $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information (NCBI)
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government do not place any restriction on its use or reproduction.
13 * We would, however, appreciate having the NCBI and the author cited in
14 * any work or product based on this material
15 *
16 * Although all reasonable efforts have been taken to ensure the accuracy
17 * and reliability of the software and data, the NLM and the U.S.
18 * Government do not and cannot warrant the performance or results that
19 * may be obtained by using this software or data. The NLM and the U.S.
20 * Government disclaim all warranties, express or implied, including
21 * warranties of performance, merchantability or fitness for any particular
22 * purpose.
23 *
24 * ===========================================================================
25 *
26 * File Name: blocks.c
27 *
28 * Author: Sarah Wheelan
29 *
30 * Version Creation Date: 5/99
31 *
32 * $Revision: 6.3 $
33 *
34 * File Description: Indexed SeqAlign Functions
35 *
36 * Modifications:
37 * --------------------------------------------------------------------------
38 * $Log: blocks.c,v $
39 * Revision 6.3 1999/11/26 15:42:23 vakatov
40 * Fixed for the C++ and/or MSVC DLL compilation
41 *
42 * Revision 6.2 1999/08/27 14:54:03 durand
43 * fix memory leaks in PopSet Viewer
44 *
45 * Revision 6.1 1999/07/06 19:49:14 kans
46 * initial public checkin
47 *
48 * Revision 1.22 1999/07/02 13:20:42 wheelan
49 * fixed more Blockify bugs
50 *
51 * Revision 1.21 1999/07/01 20:57:15 wheelan
52 * fixed minus strand problems by adding CalcMinusBounds, FlipSequence, and PropagateStrandInfo; also adds PatricksSABlock structure printing function; also lots of changes in SAMergeBlocks to correctly manage minus strands
53 *
54 * Revision 1.20 1999/06/29 16:09:57 wheelan
55 * fixed bugs in Blockify; forced SplitBlocks to correctly set strand
56 *
57 * Revision 1.19 1999/06/25 20:56:11 wheelan
58 * fixed major bug in IndexBlocks, fixed a few problems in Blockify
59 *
60 * Revision 1.18 1999/06/24 20:44:36 wheelan
61 * added IndexNewBlocks to correctly index SABlocks made from DenseDiags
62 *
63 * Revision 1.17 1999/06/24 11:37:00 wheelan
64 * fixed Blockify to set visible to 1
65 *
66 * Revision 1.16 1999/06/23 16:52:34 wheelan
67 * removed some unused variables
68 *
69 * Revision 1.15 1999/06/21 12:08:13 wheelan
70 * added SeqAlignListMergeAll, debugged SAMerge and SquishBlocks
71 *
72 * Revision 1.14 1999/06/11 19:15:49 wheelan
73 * Fixed bugs in SAMergeBlocks, and modified IndexBlocks to propagate the SeqId across each bioseq (cannot write to dense-seg structure if no SeqId for every segment of first block)
74 *
75 * Revision 1.13 1999/06/11 18:01:50 wheelan
76 * Changed seqalign type to 255 in DeBlockify, since type = 0 does not work with
77 salsa
78 *
79 * Revision 1.11 1999/06/09 21:18:38 wheelan
80 * Modified Blockify to work for dense-diags. Fixed bugs in IndexBlocks, TeenyBlock, and SASplitBlock.
81 *
82 * Revision 1.10 1999/05/29 00:09:15 lewisg
83 * new editing functions
84 *
85 * Revision 1.9 1999/05/24 23:10:50 lewisg
86 * more initialization for AddEmptyBlocks
87 *
88 *
89 * ==========================================================================
90 */
91
92
93 #include <blocks.h>
94 #include <ncbi.h>
95 #include <math.h>
96
97 static void FlipSequence(SegmentPtr segp, Int4 len);
98 static void CalcMinusBounds(SegmentPtr segp, SegmentPtr PNTR segp_storage);
99
100
101 /*******************************************************************************
102
103 Function : blk_PrintSABP()
104
105 Purpose : display an indexed seqalign as a matrix (debug purpose only)
106
107 Parameters : sabp;header of the indexed seqalign
108
109 Return value : -
110
111 *******************************************************************************/
112 NLM_EXTERN void blk_PrintSABP(SABlockPtr sabp)
113 {
114 FILE *hFile;
115 SABlockPtr sabp2; /*used to scan "SeqALign" Index blocks*/
116 SegmentPtr segp,segp2; /*used to scan each Bsp segment in a block*/
117
118 hFile=fopen("zsabp.txt","w");
119 sabp2=sabp;
120 /*write the align coord*/
121 while (sabp2){
122 fprintf(hFile,"{%4i}[%7i..%7i]",sabp2->SegID,sabp2->from,sabp2->to);
123 sabp2=sabp2->next;
124 if (sabp2) fprintf(hFile,"<-->");
125 }
126 fprintf(hFile,"\n");
127 sabp2=sabp;
128 while (sabp2){
129 fprintf(hFile,"============================");
130 sabp2=sabp2->next;
131 }
132 segp=sabp->segp_head;
133 fprintf(hFile,"\n\n");
134 /*write the SABP : line by line, bsp by bsp*/
135 while(segp){/*bsp loop*/
136 segp2=segp;
137 while(segp2){/*segment loop for one bsp; from-to*/
138 fprintf(hFile,"(%4i)[%7i..%7i]",segp2->BspID,segp2->from,segp2->to);
139 segp2=segp2->bsp_next;
140 if (segp2) fprintf(hFile,"<-->");
141 }
142 segp2=segp;
143 fprintf(hFile,"\n");
144 while(segp2){/*segment loop for one bsp; gap strand*/
145 fprintf(hFile," (%c) (%c) (%c) ",
146 (segp2->gap>0 ? '-':'a' ),
147 (segp2->strand!=Seq_strand_minus ? '+':'-' ),
148 (segp2->visible>0 ? '1':'0' ));
149 segp2=segp2->bsp_next;
150 }
151 segp2=segp;
152 fprintf(hFile,"\n");
153 while (segp2){
154 fprintf(hFile,"----------------------------");
155 segp2=segp2->next;
156 }
157 fprintf(hFile,"\n");
158 segp=segp->next;
159 }
160 fprintf(hFile,"\n\n");
161 fclose(hFile);
162 }
163
164 /******************************************************************
165 * Blockify converts a seqalign to the SABlock structure. It
166 * does all the necessary memory allocation, so the structure
167 * will need to be freed with CleanupBlocks once it's no longer
168 * used. The top-level coordinates (in the SABlocks) refer to
169 * the alignment coordinates, starting from zero, and the
170 * coordinates in each chain of Segments refer to bioseq
171 * coordinates, also starting from zero. Gaps are coded by the
172 * last real residue before the gap (e.g. for aaacct----ttt
173 * the gap has segp->from = segp->to = 5, which is the coordinate
174 * of the 't' before the gap). Therefore, segp->gap MUST be
175 * set to something other than zero to signify that this is a
176 * gap and not a one-residue block.
177 *******************************************************************/
178
179 NLM_EXTERN SABlockPtr Blockify(SeqAlignPtr sap)
180 {
181 Boolean added;
182 Int4 bioseq;
183 Int4 block;
184 Int4 counter;
185 DenseDiagPtr ddp;
186 DenseSegPtr dsp;
187 SABlockPtr head_sabp;
188 Int4 i;
189 Int2 index;
190 Int4 master_from;
191 Int4 master_to;
192 SABlockPtr prev_sabp;
193 SABlockPtr sabp;
194 SABlockPtr sabp_new;
195 SegmentPtr segp;
196 SegmentPtr segp_head;
197 SegmentPtr segp_prev;
198 SegmentPtr segp_storage;
199 SegmentPtr segp_temp;
200 SegmentPtr segp_temp2;
201 SegmentPtr segp_temp3;
202 Int4 shift;
203 SeqIdPtr sip;
204 SeqLocPtr slp;
205 StdSegPtr ssp;
206
207 bioseq = block = 1;
208 if (sap->segtype == 1)
209 {
210 ddp = (DenseDiagPtr)sap->segs;
211 if (ddp == NULL)
212 return NULL;
213 if (ddp->dim != 2)
214 {
215 ErrPostEx(SEV_WARNING,0,0,"Need pairwise alignment as input\n");
216 return NULL;
217 }
218 head_sabp = NULL;
219 segp_storage = segp_temp = NULL;
220 segp_storage = (SegmentPtr)MemNew(sizeof(Segment));
221 segp_temp = (SegmentPtr)MemNew(sizeof(Segment));
222 segp_storage->next = segp_temp;
223 segp_storage->sip = SeqIdDup(ddp->id);
224 segp_temp->sip = SeqIdDup(ddp->id->next);
225 segp_storage->from = ddp->starts[0];
226 segp_storage->to = segp_storage->from + ddp->len - 1;
227 segp_storage->link = TRUE;
228 segp_storage->visible = 1;
229 segp_temp->link = TRUE;
230 segp_temp->from = ddp->starts[1];
231 segp_temp->to = segp_temp->from + ddp->len - 1;
232 segp_temp->prev = segp_storage;
233 segp_temp->visible = 1;
234 head_sabp = sabp = (SABlockPtr)MemNew(sizeof(SABlock));
235 sabp->segp_head = segp_storage;
236 sabp->aligned = TRUE;
237 sabp->from = ddp->starts[0];
238 sabp->to = ddp->starts[0] + ddp->len - 1;
239 sabp->visible = 1;
240 if (ddp->strands)
241 {
242 if (ddp->strands[0] == Seq_strand_minus)
243 {
244 segp_storage->strand = Seq_strand_plus;
245 if (ddp->strands[1] != Seq_strand_minus)
246 segp_temp->strand = Seq_strand_minus;
247 else
248 segp_temp->strand = Seq_strand_plus;
249 } else
250 {
251 segp_storage->strand = ddp->strands[0];
252 segp_temp->strand = ddp->strands[1];
253 }
254 } else
255 {
256 segp_storage->strand = segp_temp->strand = Seq_strand_unknown;
257 }
258 counter = 1;
259 ddp = ddp->next;
260 while (ddp)
261 {
262 if (ddp->dim != 2)
263 {
264 ErrPostEx(SEV_WARNING,0,0,"Need pairwise alignment as input\n");
265 return NULL;
266 }
267 while (!SeqIdComp(segp_storage->sip, ddp->id))
268 {
269 ddp = ddp->next;
270 }
271 if (ddp->strands)
272 {
273 if (ddp->strands[0] == Seq_strand_minus)
274 {
275 ddp->strands[0] = Seq_strand_plus;
276 if (ddp->strands[1] == Seq_strand_minus)
277 ddp->strands[1] = Seq_strand_plus;
278 else
279 ddp->strands[1] = Seq_strand_minus;
280 }
281 }
282 segp_storage->next->sip = SeqIdDup(ddp->id->next);
283 head_sabp = AddEmptySegments(head_sabp);
284 counter += 1;
285 sabp = head_sabp;
286 added = FALSE;
287 while (!added)
288 {
289 if (ddp->starts[0] + ddp->len - 1 < sabp->from)
290 {
291 sabp_new = (SABlockPtr)MemNew(sizeof(SABlock));
292 sabp_new->from = ddp->starts[0];
293 sabp_new->to = ddp->starts[0] + ddp->len - 1;
294 sabp_new->aligned = TRUE;
295 sabp_new->next = sabp;
296 sabp_new->visible = 1;
297 if (sabp->prev)
298 {
299 sabp_new->prev = sabp->prev;
300 sabp->prev->next = sabp_new;
301 sabp->prev = sabp_new;
302 } else
303 {
304 head_sabp->prev = sabp_new;
305 head_sabp = sabp_new;
306 }
307 segp_head = NULL;
308 for (i = 0; i<= counter; i++)
309 {
310 segp_temp = (SegmentPtr)MemNew(sizeof(Segment));
311 if (segp_head)
312 {
313 segp_temp->prev = segp_prev;
314 segp_prev->next = segp_temp;
315 segp_prev = segp_temp;
316 segp_temp->visible = 1;
317 segp_temp->gap = 2;
318 } else
319 {
320 segp_head = segp_prev = segp_temp;
321 segp_temp->from = sabp_new->from;
322 segp_temp->to = sabp_new->to;
323 segp_temp->sip = segp_storage->sip;
324 segp_temp->link = TRUE;
325 segp_temp->visible = 1;
326 }
327 }
328 segp_temp->from = ddp->starts[1];
329 segp_temp->to = ddp->starts[1] + ddp->len - 1;
330 segp_temp->sip = segp_storage->next->sip;
331 segp_temp->gap = 0;
332 segp_temp->link = TRUE;
333 segp_temp->visible = 1;
334 if (ddp->strands)
335 {
336 segp_head->strand = ddp->strands[0];
337 segp_temp->strand = ddp->strands[1];
338 } else
339 {
340 segp_head->strand = segp_temp->strand = Seq_strand_unknown;
341 }
342 sabp_new->segp_head = segp_head;
343 ddp = ddp->next;
344 added = TRUE;
345 } else if (ddp->starts[0] < sabp->from)
346 {
347 sabp_new = (SABlockPtr)MemNew(sizeof(SABlock));
348 sabp_new->next = sabp;
349 sabp_new->aligned = TRUE;
350 sabp_new->from = ddp->starts[0];
351 sabp_new->to = sabp->from - 1;
352 sabp_new->visible = 1;
353 if (sabp->prev)
354 {
355 sabp_new->prev = sabp->prev;
356 sabp->prev->next = sabp_new;
357 sabp->prev = sabp_new;
358 } else
359 {
360 sabp->prev = sabp_new;
361 head_sabp = sabp_new;
362 }
363 segp_head = NULL;
364 for (i = 0; i<= counter; i++)
365 {
366 segp_temp = (SegmentPtr)MemNew(sizeof(Segment));
367 if (segp_head)
368 {
369 segp_temp->prev = segp_prev;
370 segp_prev->next = segp_temp;
371 segp_prev = segp_temp;
372 segp_temp->gap = 2;
373 segp_temp->visible = 1;
374 } else
375 {
376 segp_head = segp_prev = segp_temp;
377 segp_temp->from = sabp_new->from;
378 segp_temp->to = sabp_new->to;
379 segp_temp->sip = segp_storage->sip;
380 segp_temp->link = TRUE;
381 segp_temp->visible = 1;
382 }
383 }
384 shift = sabp_new->to - sabp_new->from;
385 segp_temp->from = ddp->starts[1];
386 segp_temp->to = ddp->starts[1] + shift;
387 segp_temp->gap = 0;
388 segp_temp->sip = segp_storage->next->sip;
389 segp_temp->link = TRUE;
390 segp_temp->visible = 1;
391 if (ddp->strands)
392 {
393 segp_head->strand = ddp->strands[0];
394 segp_temp->strand = ddp->strands[1];
395 } else
396 {
397 segp_head->strand = segp_temp->strand = Seq_strand_unknown;
398 }
399 sabp_new->segp_head = segp_head;
400 ddp->starts[0] += (shift+1);
401 ddp->starts[1] += (shift+1);
402 ddp->len -= (shift+1);
403 } else if (ddp->starts[0] == sabp->from)
404 {
405 if (ddp->starts[0] + ddp->len - 1 > sabp->to)
406 {
407 segp_temp = sabp->segp_head;
408 shift = sabp->to - sabp->from;
409 for (i = 0; i< counter; i++)
410 {
411 segp_temp = segp_temp->next;
412 }
413 segp_temp->from = ddp->starts[1];
414 segp_temp->to = ddp->starts[1] + shift;
415 segp_temp->gap = 0;
416 segp_temp->sip = segp_storage->next->sip;
417 segp_temp->link = TRUE;
418 segp_temp->visible = 1;
419 if (ddp->strands)
420 {
421 segp_temp->strand = ddp->strands[1];
422 } else
423 {
424 segp_temp->strand = Seq_strand_unknown;
425 }
426 ddp->starts[0] = ddp->starts[0] + shift + 1;
427 ddp->starts[1] = ddp->starts[1] + shift + 1;
428 ddp->len = ddp->len - shift - 1;
429 sabp = sabp->next;
430 } else if (ddp->starts[0] + ddp->len - 1 == sabp->to)
431 {
432 segp_temp = sabp->segp_head;
433 for (i=0; i<counter; i++)
434 {
435 segp_temp = segp_temp->next;
436 }
437 segp_temp->from = ddp->starts[1];
438 segp_temp->to = ddp->starts[1] + ddp->len - 1;
439 segp_temp->gap = 0;
440 segp_temp->sip = segp_storage->next->sip;
441 segp_temp->link = TRUE;
442 segp_temp->visible = 1;
443 if (ddp->strands)
444 {
445 segp_temp->strand = ddp->strands[1];
446 } else
447 {
448 segp_temp->strand = Seq_strand_unknown;
449 }
450 ddp = ddp->next;
451 added = TRUE;
452 } else
453 {
454 sabp = SASplitBlock(sabp, (ddp->starts[0] + ddp->len));
455 segp_temp = sabp->segp_head;
456 for (i = 0; i<counter; i++)
457 {
458 segp_temp = segp_temp->next;
459 }
460 segp_temp->from = ddp->starts[1];
461 segp_temp->to = ddp->starts[1] + ddp->len - 1;
462 segp_temp->gap = 0;
463 segp_temp->sip = segp_storage->next->sip;
464 segp_temp->link = TRUE;
465 segp_temp->visible = 1;
466 if (ddp->strands)
467 {
468 segp_temp->strand = ddp->strands[1];
469 } else
470 {
471 segp_temp->strand = Seq_strand_unknown;
472 }
473 ddp = ddp->next;
474 added = TRUE;
475 }
476 } else if (ddp->starts[0] > sabp->from && ddp->starts[0] <= sabp->to)
477 {
478 sabp = SASplitBlock(sabp, ddp->starts[0]);
479 sabp = sabp->next;
480 } else
481 {
482 sabp = sabp->next;
483 }
484 if (!sabp && !added)
485 {
486 sabp = head_sabp;
487 while (sabp->next)
488 {
489 sabp = sabp->next;
490 }
491 sabp_new = (SABlockPtr)MemNew(sizeof(SABlock));
492 sabp_new->from = ddp->starts[0];
493 sabp_new->to = ddp->starts[0] + ddp->len - 1;
494 sabp_new->aligned = TRUE;
495 sabp_new->prev = sabp;
496 sabp_new->visible = 1;
497 sabp->next = sabp_new;
498 segp_head = NULL;
499 for (i = 0; i<= counter; i++)
500 {
501 segp_temp = (SegmentPtr)MemNew(sizeof(Segment));
502 if (segp_head)
503 {
504 segp_prev->next = segp_temp;
505 segp_temp->prev = segp_prev;
506 segp_prev = segp_temp;
507 segp_temp->gap = 2;
508 segp_temp->visible = 1;
509 } else
510 {
511 segp_head = segp_prev = segp_temp;
512 segp_temp->from = ddp->starts[0];
513 segp_temp->to = ddp->starts[0] + ddp->len - 1;
514 segp_temp->sip = segp_storage->sip;
515 segp_temp->link = TRUE;
516 segp_temp->visible = 1;
517 }
518 }
519 segp_temp->from = ddp->starts[1];
520 segp_temp->to = ddp->starts[1] + ddp->len - 1;
521 segp_temp->gap = 0;
522 segp_temp->sip = segp_storage->next->sip;
523 segp_temp->link = TRUE;
524 segp_temp->visible = 1;
525 if (ddp->strands)
526 {
527 segp_head->strand = ddp->strands[0];
528 segp_temp->strand = ddp->strands[1];
529 } else
530 {
531 segp_head->strand = segp_temp->strand = Seq_strand_unknown;
532 }
533 sabp_new->segp_head = segp_head;
534 ddp = ddp->next;
535 added = TRUE;
536 }
537 }
538 }
539 head_sabp = FillInUnaligned(head_sabp);
540 head_sabp = IndexNewBlocks(head_sabp);
541 segp_temp = head_sabp->segp_head;
542 segp_temp3 = (SegmentPtr)MemNew(sizeof(Segment));
543 while (segp_temp)
544 {
545 if (segp_temp->strand == Seq_strand_unknown)
546 {
547 segp_temp = PropagateStrandInfo(segp_temp);
548 }
549 if (segp_temp->strand == Seq_strand_minus)
550 {
551 CalcMinusBounds(segp_temp, &segp_temp3);
552 FlipSequence(segp_temp, (segp_temp3->to + segp_temp3->from));
553 }
554 segp_temp = segp_temp->next;
555 }
556 MemFree(segp_temp3);
557 return head_sabp;
558 } else if (sap->segtype == 2) /*DENSE-SEG*/
559 {
560 dsp = sap->segs;
561 if (!dsp)
562 return NULL;
563 if (dsp->strands)
564 {
565 if (dsp->strands[0] == Seq_strand_minus)
566 {
567 sap = SeqAlignListReverseStrand(sap);
568 dsp = sap->segs;
569 if (!dsp)
570 return NULL;
571 }
572 }
573 index = 0;
574 head_sabp = NULL;
575 master_from = master_to = 0;
576 segp_storage = segp_temp = NULL;
577 while (index < dsp->numseg)
578 {
579 if (index == 0)
580 {
581 for (counter = 0; counter < dsp->dim; counter++)
582 {
583 segp_temp = (SegmentPtr)MemNew(sizeof(Segment));
584 if (segp_storage)
585 {
586 segp_temp2->next = segp_temp;
587 segp_temp2 = segp_temp;
588 } else
589 {
590 segp_storage = segp_temp2 = segp_temp;
591 }
592 segp_temp->to = -1;
593 }
594 }
595 master_from = master_to + 1;
596 master_to += dsp->lens[index];
597 sabp = (SABlockPtr)MemNew(sizeof(SABlock));
598 if (!head_sabp)
599 {
600 head_sabp = sabp;
601 prev_sabp = sabp;
602 sabp->prev = NULL;
603 } else
604 {
605 prev_sabp->next = sabp;
606 sabp->prev = prev_sabp;
607 prev_sabp = sabp;
608 }
609 sabp->from = master_from-1;/*switch to zero-based values*/
610 sabp->to = master_to-1;
611 sabp->visible = 1;
612 sabp->next = NULL;
613 /* lyg: initialize the RegionID to correspond to alignment */
614 sabp->RegionID = block;
615 /* lyg: indicate that the block is aligned */
616 sabp->aligned = TRUE;
617 sabp->SegID=block++;
618 segp_head = NULL;
619 sip=dsp->ids;
620 segp_temp = segp_storage;
621 for (i = 0; i< dsp->dim; i++,sip=sip->next)
622 {
623 segp = (SegmentPtr)MemNew(sizeof(Segment));
624 if (!segp_head)
625 {
626 segp_head = segp;
627 segp_prev = segp;
628 } else
629 {
630 segp_prev->next = segp;
631 segp->prev = segp_prev;
632 segp_prev = segp;
633 }
634 if (dsp->starts[(dsp->dim*index) + i] == -1)
635 {
636 segp->gap = 1;
637 segp->from = segp->to = segp_temp->to;
638 segp->strand = Seq_strand_unknown;
639 } else
640 {
641 segp->gap = 0;
642 segp->from = dsp->starts[dsp->dim*index + i];
643 segp->to = segp->from + dsp->lens[index]-1;
644 segp_temp->to += dsp->lens[index];
645 if(dsp->strands)
646 segp->strand = dsp->strands[dsp->dim*index + i];
647 else
648 segp->strand = Seq_strand_plus;
649 }
650 segp->link=TRUE;
651 segp->visible = 1;
652 segp->move = FALSE; /* lyg: no pending move */
653 if (index == 0) segp->sip=SeqIdDup(sip);
654 segp->BspID=bioseq++;
655 segp_temp = segp_temp->next;
656 }
657 sabp->segp_head = segp_head;
658 index += 1;
659 bioseq=1;
660 }
661 segp_temp = segp_storage;
662 while(segp_temp)
663 {
664 segp_temp2 = segp_temp->next;
665 MemFree(segp_temp);
666 segp_temp = segp_temp2;
667 }
668 head_sabp = IndexBlocks(head_sabp);
669 return head_sabp;
670 } else if (sap->segtype == 3) /*STD-SEG*/
671 {
672 ssp = sap->segs;
673 if (!ssp)
674 return NULL;
675 head_sabp = NULL;
676 while (ssp)
677 {
678 sabp = (SABlockPtr)MemNew(sizeof(SABlock));
679 sabp->visible = 1;
680 if (head_sabp)
681 {
682 prev_sabp->next = sabp;
683 sabp->prev = prev_sabp;
684 } else
685 {
686 prev_sabp = head_sabp = sabp;
687 }
688 slp = ssp->loc;
689 segp_head = NULL;
690 while (slp)
691 {
692 segp = (SegmentPtr)MemNew(sizeof(Segment));
693 if (segp_head)
694 {
695 segp_prev->next = segp;
696 segp->prev = segp_prev;
697 } else
698 {
699 segp_prev = segp_head = segp;
700 }
701 segp->visible = 1;
702 segp->from = SeqLocStart(slp);
703 segp->to = SeqLocStop(slp);
704 segp->sip = SeqIdDup(SeqLocId(slp));
705 slp = slp->next;
706 }
707 sabp->segp_head = segp_head;
708 ssp = ssp->next;
709 }
710 return head_sabp;
711 } else
712 {
713 return NULL;
714 }
715 }
716
717 /************************************************************
718 * DeBlockify converts the SABlock structure to a SeqAlign
719 * of segtype dense-seg. For the structures that were
720 * originally diags, each diag ends up as a new "sequence" in
721 * the alignment, with gaps on either side to fill out the
722 * alignment. DeBlockify does not free the SABlock structure.
723 ************************************************************/
724
725 NLM_EXTERN SeqAlignPtr DeBlockify(SABlockPtr sabp)
726 {
727 Int4 count_blocks;
728 Int4 count_segments;
729 DenseSegPtr dsp;
730 Int4 i;
731 SABlockPtr sabp_head;
732 SeqAlignPtr sap;
733 SegmentPtr segp;
734 SeqIdPtr sip;
735
736 if (!sabp)
737 return NULL;
738 sap = SeqAlignNew();
739 dsp = DenseSegNew();
740 if (!dsp)
741 return NULL;
742 sabp_head = sabp;
743 count_blocks = count_segments = 0;
744 while (sabp)
745 {
746 count_blocks++;
747 sabp = sabp->next;
748 }
749 sabp = sabp_head;
750 segp = sabp->segp_head;
751 while (segp)
752 {
753 count_segments++;
754 segp = segp->next;
755 }
756 sap->segs = (Pointer)dsp;
757 sap->type = 255;
758 sap->segtype = 2;
759 sap->dim = count_segments;
760 dsp->dim = count_segments;
761 dsp->numseg = count_blocks;
762 dsp->lens = (Int4Ptr)MemNew((size_t)((count_blocks+2)*sizeof(Int4)));
763 dsp->strands = (Uint1Ptr)MemNew((size_t)((count_segments*count_blocks+4)*sizeof(Uint1)));
764 dsp->starts = (Int4Ptr)MemNew((size_t)((count_segments*count_blocks+4)*sizeof(Int4)));
765 sip = GetSeqIdList(sabp);
766 dsp->ids = sip;
767 sabp = sabp_head;
768 count_segments = count_blocks = 0;
769 i = 0;
770 while (sabp)
771 {
772 count_blocks++;
773 dsp->lens[count_blocks-1] = sabp->to - sabp->from;
774 segp = sabp->segp_head;
775 while (segp)
776 {
777 dsp->strands[i] = segp->strand;
778 if (segp->gap != 0)
779 {
780 dsp->starts[i] = -1;
781 } else
782 {
783 dsp->starts[i] = segp->from;
784 }
785 segp = segp->next;
786 i++;
787 }
788 sabp = sabp->next;
789 }
790 sap->segs = dsp;
791 return sap;
792 }
793
794 NLM_EXTERN SeqAlignPtr SeqAlignListMergeAll(SeqAnnotPtr sap)
795 {
796 SABlockPtr sabp;
797 SABlockPtr sabp_next;
798 SeqAlignPtr salp;
799
800 if (!sap)
801 return NULL;
802 salp = (SeqAlignPtr)sap->data;
803 if (!salp->next)
804 return salp;
805 sabp = sabp_next = NULL;
806 while (salp)
807 {
808 if (sabp)
809 {
810 sabp_next = Blockify(salp);
811 sabp = SAMergeBlocks(sabp, sabp_next);
812 } else
813 {
814 sabp = Blockify(salp);
815 sabp_next = Blockify(salp->next);
816 sabp = SAMergeBlocks(sabp, sabp_next);
817 salp = salp->next;
818 }
819 salp = salp->next;
820 }
821 salp = DeBlockify(sabp);
822 return salp;
823 }
824
825 NLM_EXTERN SeqIdPtr GetSeqIdList(SABlockPtr sabp)
826 {
827 SegmentPtr segp;
828 SeqIdPtr sip;
829 SeqIdPtr sip_head;
830 SeqIdPtr sip_tmp;
831
832 segp = sabp->segp_head;
833 sip_head = NULL;
834 while (segp)
835 {
836 sip = (SeqIdPtr)MemNew(sizeof(SeqId));
837 if (segp->sip)
838 sip = SeqIdDup(segp->sip);
839 if (sip_head)
840 {
841 sip_tmp->next = sip;
842 sip_tmp = sip;
843 } else
844 {
845 sip_head = sip_tmp = sip;
846 }
847 segp = segp->next;
848 }
849 return sip_head;
850 }
851
852 /************************************************************
853 * CleanupBlocks just frees all the memory associated with
854 * the given SABlock structure, including all the memory
855 * for all associated segment structures.
856 ************************************************************/
857
858 NLM_EXTERN void CleanupBlocks(SABlockPtr sabp)
859 {
860 Boolean done;
861 SegmentPtr segp;
862 SABlockPtr sabp2;
863
864 sabp2 = sabp;
865 done = FALSE;
866 while (sabp)
867 {
868 while (sabp->segp_head)
869 {
870 segp = sabp->segp_head;
871 sabp->segp_head = segp->next;
872 segp->prev = NULL;
873 if (!done && segp->sip){
874 segp->sip=SeqIdFree(segp->sip);
875 }
876 MemFree(segp);
877 segp = sabp->segp_head;
878 }
879 sabp = sabp->next;
880 done = TRUE;
881 }
882 while (sabp2)
883 {
884 sabp = sabp2->next;
885 sabp2->prev = NULL;
886 MemFree(sabp2);
887 sabp2 = sabp;
888 }
889 return;
890 }
891
892 /***************************************************************
893 * IndexBlocks takes an assembled SABlock structure and
894 * recalculates the SegID and BspID for each block. It also
895 * recalculates the alignment coordinates by taking the length
896 * of the first non-gap sequence in each block as the length
897 * of the block (is there a better way to do this?). The
898 * function uses several Segment structures to store the
899 * coordinates of the alignment and of each bioseq. This way,
900 * the gaps in the bioseqs can also be numbered (they are not
901 * always numbered by the SAMergeBlocks function). IndexBlocks
902 * also creates the "horizontal" bsp_prev and bsp_next links
903 * across each bioseq in the alignment.
904 *
905 * lyg: please do not reindex RegionID
906 *
907 ****************************************************************/
908
909 NLM_EXTERN SABlockPtr IndexBlocks(SABlockPtr sabp)
910 {
911 Int4 bioseq;
912 Int4 block;
913 Boolean found;
914 SABlockPtr head;
915 SegmentPtr segp;
916 SegmentPtr segp_align;
917 SegmentPtr segp_curr;
918 SegmentPtr segp_prev;
919 SegmentPtr segp_storage;
920
921 if (!sabp)
922 {
923 return NULL;
924 }
925 block = 1;
926 head = sabp;
927 segp_align = (SegmentPtr)MemNew(sizeof(Segment));
928 segp_align->to = segp_align->to = -1;
929 segp_curr = segp_storage = NULL;
930 while (sabp)
931 {
932 sabp->SegID = block;
933 block++;
934 segp = sabp->segp_head;
935 if (!segp)
936 {
937 if (sabp->prev)
938 sabp->prev->next = sabp->next;
939 if (sabp->next)
940 sabp->next->prev = sabp->prev;
941 MemFree(sabp);
942 block--;
943 }
944 bioseq = 1;
945 found = FALSE;
946 segp_curr = segp_storage;
947 while (segp)
948 {
949 if (block == 2)
950 {
951 segp_curr = (SegmentPtr)MemNew(sizeof(Segment));
952 if (segp_storage)
953 {
954 segp_prev->next = segp_curr;
955 segp_prev = segp_curr;
956 } else
957 {
958 segp_storage = segp_prev = segp_curr;
959 }
960 segp_curr->bsp_prev = segp;
961 } else
962 {
963 segp->bsp_prev = segp_curr->bsp_prev;
964 segp_curr->bsp_prev = segp;
965 segp->bsp_prev->bsp_next = segp;
966 }
967 if (segp->gap != 0)
968 {
969 if (segp->gap == 1)
970 segp->from = segp->to = segp_curr->to;
971 } else
972 {
973 segp_curr->to = segp->to;
974 if (!found)
975 {
976 segp_align->from = segp_align->to + 1;
977 segp_align->to = segp_align->from + (segp->to - segp->from);
978 found = TRUE;
979 }
980 }
981 segp->BspID = bioseq;
982 segp = segp->next;
983 bioseq++;
984 if (block > 2)
985 {
986 segp_curr = segp_curr->next;
987 }
988 }
989 sabp->from = segp_align->from;
990 sabp->to = segp_align->to;
991 sabp = sabp->next;
992 }
993 MemFree(segp_align);
994 segp_curr = segp_storage;
995 while (segp_curr)
996 {
997 segp_curr = segp_storage->next;
998 segp_storage->bsp_prev = segp_storage->bsp_next = NULL;
999 MemFree(segp_storage);
1000 segp_storage = segp_curr;
1001 }
1002 segp_storage = head->segp_head;
1003 segp_curr = segp_storage;
1004 while (segp_curr)
1005 {
1006 if (!segp_curr->sip)
1007 {
1008 segp_align = segp_curr;
1009 while (segp_align->sip == NULL)
1010 {
1011 segp_align = segp_align->bsp_next;
1012 }
1013 segp_curr->sip = segp_align->sip;
1014 }
1015 segp_align = segp_curr->bsp_next;
1016 while (segp_align)
1017 {
1018 segp_align->sip = segp_curr->sip;
1019 segp_align = segp_align->bsp_next;
1020 }
1021 segp_curr = segp_curr->next;
1022 }
1023 return head;
1024 }
1025
1026 NLM_EXTERN SegmentPtr PropagateStrandInfo(SegmentPtr segp)
1027 {
1028 Boolean done;
1029 SegmentPtr segp_head;
1030 SegmentPtr segp_temp;
1031 Uint1 strand;
1032
1033 segp_head = segp;
1034 done = FALSE;
1035 strand = Seq_strand_unknown;
1036 while (!done && segp)
1037 {
1038 if (segp->strand != Seq_strand_unknown)
1039 {
1040 strand = segp->strand;
1041 done = TRUE;
1042 }
1043 segp = segp->bsp_next;
1044 }
1045 if (strand != Seq_strand_unknown)
1046 {
1047 segp_temp = segp_head;
1048 while (segp_temp)
1049 {
1050 segp_temp->strand = strand;
1051 segp_temp = segp_temp->bsp_next;
1052 }
1053 }
1054 return segp_head;
1055 }
1056
1057
1058 /***********************************************************
1059 * IndexNewBlocks does the same thing as IndexBlocks, but
1060 * for new structures created from DenseDiags, it sets all
1061 * the flags to visible, as Blockify does not traverse all
1062 * the segments to be able to do this.
1063 ***********************************************************/
1064
1065 NLM_EXTERN SABlockPtr IndexNewBlocks(SABlockPtr sabp)
1066 {
1067 Int4 bioseq;
1068 Int4 block;
1069 Boolean found;
1070 SABlockPtr head;
1071 SegmentPtr segp;
1072 SegmentPtr segp_align;
1073 SegmentPtr segp_curr;
1074 SegmentPtr segp_prev;
1075 SegmentPtr segp_storage;
1076
1077 if (!sabp)
1078 {
1079 return NULL;
1080 }
1081 block = 1;
1082 head = sabp;
1083 segp_align = (SegmentPtr)MemNew(sizeof(Segment));
1084 segp_align->to = segp_align->to = -1;
1085 segp_curr = segp_storage = NULL;
1086 while (sabp)
1087 {
1088 sabp->SegID = block;
1089 block++;
1090 segp = sabp->segp_head;
1091 if (!segp)
1092 {
1093 if (sabp->prev)
1094 sabp->prev->next = sabp->next;
1095 if (sabp->next)
1096 sabp->next->prev = sabp->prev;
1097 MemFree(sabp);
1098 block--;
1099 }
1100 bioseq = 1;
1101 found = FALSE;
1102 segp_curr = segp_storage;
1103 while (segp)
1104 {
1105 if (block == 2)
1106 {
1107 segp_curr = (SegmentPtr)MemNew(sizeof(Segment));
1108 if (segp_storage)
1109 {
1110 segp_prev->next = segp_curr;
1111 segp_prev = segp_curr;
1112 } else
1113 {
1114 segp_storage = segp_prev = segp_curr;
1115 }
1116 segp_curr->bsp_prev = segp;
1117 } else
1118 {
1119 segp->bsp_prev = segp_curr->bsp_prev;
1120 segp_curr->bsp_prev = segp;
1121 segp->bsp_prev->bsp_next = segp;
1122 }
1123 if (segp->gap != 0)
1124 {
1125 if (segp->gap == 1)
1126 segp->from = segp->to = segp_curr->to;
1127 else if (segp->gap == 2)
1128 segp->from = segp->to = 0;
1129 } else
1130 {
1131 segp_curr->to = segp->to;
1132 if (!found)
1133 {
1134 segp_align->from = segp_align->to + 1;
1135 segp_align->to = segp_align->from + (segp->to - segp->from);
1136 found = TRUE;
1137 }
1138 }
1139 segp->BspID = bioseq;
1140 segp->visible = 1;
1141 segp = segp->next;
1142 bioseq++;
1143 if (block > 2)
1144 {
1145 segp_curr = segp_curr->next;
1146 }
1147 }
1148 sabp->from = segp_align->from;
1149 sabp->to = segp_align->to;
1150 sabp = sabp->next;
1151 }
1152 MemFree(segp_align);
1153 segp_curr = segp_storage;
1154 while (segp_curr)
1155 {
1156 segp_curr = segp_storage->next;
1157 segp_storage->bsp_prev = segp_storage->bsp_next = NULL;
1158 MemFree(segp_storage);
1159 segp_storage = segp_curr;
1160 }
1161 segp_storage = head->segp_head;
1162 segp_curr = segp_storage;
1163 while (segp_curr)
1164 {
1165 if (!segp_curr->sip)
1166 {
1167 segp_align = segp_curr;
1168 while (segp_align->sip == NULL)
1169 {
1170 segp_align = segp_align->bsp_next;
1171 }
1172 segp_curr->sip = segp_align->sip;
1173 }
1174 segp_align = segp_curr->bsp_next;
1175 while (segp_align)
1176 {
1177 segp_align->sip = segp_curr->sip;
1178 segp_align = segp_align->bsp_next;
1179 }
1180 segp_curr = segp_curr->next;
1181 }
1182 return head;
1183 }
1184
1185
1186 /******************************************************************
1187 * This function returns either the total length of the alignment
1188 * (in alignment coordinates), or the number of sequences involved
1189 * in the alignment, or the number of blocks in the alignment, or
1190 * all three, depending on whether any of length, numbioseqs or
1191 * numblocks are NULL. If the Int4Ptr validate is not NULL, the
1192 * function also goes through the segments for each block to make
1193 * sure that each block has the same number of segments, in the
1194 * same order. If this is not the case, *validate is set to the
1195 * SegID of the first block that contains a mistake. If the
1196 * alignment is valid, *validate will be zero.
1197 ******************************************************************/
1198
1199 NLM_EXTERN void GetBlockInfo(SABlockPtr sabp, Int4Ptr length, Int4Ptr numbioseqs, Int4Ptr numblocks, Int4Ptr validate)
1200 {
1201 Int4 blocks;
1202 Int4 count;
1203 SegmentPtr segp;
1204 ValNodePtr vnp;
1205 ValNodePtr vnp_head;
1206
1207 if (!sabp)
1208 {
1209 return;
1210 }
1211 segp = sabp->segp_head;
1212 vnp = vnp_head = NULL;
1213 if (numbioseqs)
1214 {
1215 *numbioseqs = 0;
1216 while (segp)
1217 {
1218 *numbioseqs += 1;
1219 if (validate)
1220 {
1221 vnp = ValNodeAdd(&vnp_head);
1222 vnp->data.intvalue = segp->BspID;
1223 }
1224 segp = segp->next;
1225 }
1226 }
1227 if (length || numblocks || validate)
1228 {
1229 if (length)
1230 *length = 0;
1231 blocks = 0;
1232 if (validate)
1233 {
1234 *validate = 0;
1235 }
1236 while (sabp)
1237 {
1238 if (length)
1239 *length += (sabp->to - sabp->from + 1);
1240 blocks += 1;
1241 if (validate)
1242 {
1243 vnp = vnp_head;
1244 segp = sabp->segp_head;
1245 count = 0;
1246 while (segp)
1247 {
1248 count += 1;
1249 if (segp->BspID != vnp->data.intvalue)
1250 {
1251 *validate = blocks;
1252 ValNodeFree(vnp_head);
1253 return;
1254 }
1255 vnp = vnp->next;
1256 segp = segp->next;
1257 }
1258 if (count != *numbioseqs)
1259 {
1260 *validate = blocks;
1261 ValNodeFree(vnp_head);
1262 return;
1263 }
1264 }
1265 sabp = sabp->next;
1266 }
1267 if (numblocks)
1268 *numblocks = blocks;
1269 }
1270 ValNodeFree(vnp_head);
1271 return;
1272 }
1273
1274
1275 /******************************************************************
1276 * SAMergeBlocks first finds the first sequence in the first
1277 * alignment that is also in the second alignment, and then merges
1278 * the two alignments using that sequence as a guide. It is
1279 * fairly conservative with memory allocation -- when possible
1280 * it just modifies existing SABlocks and links them together. The
1281 * structure that is returned has the same AlignID as the first
1282 * alignment passed to the function.
1283 * SAMergeBlocks calls GetBlockOrientation to figure out how the
1284 * relationships between the shared sequences in each set of blocks,
1285 * and then uses this information to merge and split the blocks
1286 * as needed. Note that the shared sequence is removed from the
1287 * second set of blocks, so it shouldn't appear twice in the final
1288 * alignment.
1289 *******************************************************************/
1290
1291 NLM_EXTERN SABlockPtr SAMergeBlocks (SABlockPtr sabp1, SABlockPtr sabp2)
1292 {
1293 Int4 c;
1294 Boolean done;
1295 Int4 i;
1296 Int4 index1;
1297 Int4 index2;
1298 SABlockPtr merged;
1299 SABlockPtr merged_head;
1300 Boolean minus1;
1301 Boolean minus2;
1302 SegmentPtr minus_head1;
1303 SegmentPtr minus_head2;
1304 SegmentPtr minus_prev;
1305 SegmentPtr minus_tmp;
1306 Int4 orient;
1307 SABlockPtr new_sabp1;
1308 SABlockPtr new_sabp2;
1309 Int4 num_bioseqs1;
1310 Int4 num_bioseqs2;
1311 SegmentPtr prev;
1312 SABlockPtr prev_sabp;
1313 SegmentPtr segp1;
1314 SegmentPtr segp2;
1315 Int4 shift;
1316 Int4 thisalign;
1317 SegmentPtr tmp_curr;
1318 SegmentPtr tmp_head;
1319 SegmentPtr tmp1;
1320 SegmentPtr tmp2;
1321 SegmentPtr tmp3;
1322
1323 if (!sabp1 || !sabp2)
1324 {
1325 if (!sabp1)
1326 {
1327 if (!sabp2)
1328 {
1329 return NULL;
1330 } else
1331 {
1332 return sabp2;
1333 }
1334 } else if (!sabp2)
1335 {
1336 return sabp1;
1337 }
1338 }
1339 thisalign = sabp1->AlignID;
1340 segp1 = sabp1->segp_head;
1341 /* Find the bioseqs in common -- this just finds the first bioseq */
1342 /* in the first alignment that matches a bioseq in the second */
1343 /* alignment -- change later to specify which common bioseq to use?*/
1344 index1 = 0;
1345 index2 = 0;
1346 done = FALSE;
1347 while (segp1 && !done)
1348 {
1349 segp2 = sabp1->segp_head;
1350 while (segp2 && !done)
1351 {
1352 if (SeqIdComp(segp1->sip, segp2->sip))
1353 {
1354 index1 = segp1->BspID;
1355 index2 = segp2->BspID;
1356 done = TRUE;
1357 }
1358 segp2 = segp2->next;
1359 }
1360 segp1 = segp1->next;
1361 }
1362 if (index1 == 0 || index2 == 0)
1363 {
1364 return NULL;
1365 }
1366 GetBlockInfo(sabp1, NULL, &num_bioseqs1, NULL, &num_bioseqs2);
1367 GetBlockInfo(sabp2, NULL, &num_bioseqs2, NULL, NULL);
1368 if (num_bioseqs1 == 0 || num_bioseqs2 == 0)
1369 {
1370 return NULL;
1371 }
1372 segp1 = sabp1->segp_head;
1373 segp2 = sabp2->segp_head;
1374 i = 0;
1375 minus_head1 = minus_head2 = FALSE;
1376 while (segp1)
1377 {
1378 i++;
1379 minus_tmp = (SegmentPtr)MemNew(sizeof(Segment));
1380 if (minus_head1)
1381 {
1382 minus_prev->next = minus_tmp;
1383 minus_prev = minus_tmp;
1384 } else
1385 {
1386 minus_head1 = minus_prev = minus_tmp;
1387 }
1388 if (segp1->strand == Seq_strand_minus)
1389 {
1390 if (i == index1)
1391 return sabp1;
1392 CalcMinusBounds(segp1, &minus_tmp);
1393 FlipSequence(segp1, (minus_tmp->to + minus_tmp->from));
1394 minus_tmp->strand = Seq_strand_minus;
1395 minus1 = TRUE;
1396 }
1397 segp1 = segp1->next;
1398 }
1399 i = 0;
1400 while (segp2)
1401 {
1402 i++;
1403 minus_tmp = (SegmentPtr)MemNew(sizeof(Segment));
1404 if (minus_head2)
1405 {
1406 minus_prev->next = minus_tmp;
1407 minus_prev = minus_tmp;
1408 } else
1409 {
1410 minus_head2 = minus_prev = minus_tmp;
1411 }
1412 if (segp2->strand == Seq_strand_minus)
1413 {
1414 if (i == index2)
1415 return sabp1;
1416 CalcMinusBounds(segp2, &minus_tmp);
1417 FlipSequence(segp2, (minus_tmp->from + minus_tmp->to));
1418 minus_tmp->strand = Seq_strand_minus;
1419 minus2 = TRUE;
1420 }
1421 segp2 = segp2->next;
1422 }
1423 segp1 = sabp1->segp_head;
1424 segp2 = sabp2->segp_head;
1425 merged = merged_head = NULL;
1426 done = FALSE;
1427 while (!done)
1428 {
1429 orient = GetBlockOrientation(&shift, segp1, segp2, index1, index2);
1430 if (orient == -2)
1431 {
1432 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
1433 new_sabp1->AlignID = thisalign;
1434 if (merged_head)
1435 {
1436 merged->next = new_sabp1;
1437 new_sabp1->prev = merged;
1438 merged = new_sabp1;
1439 } else
1440 {
1441 merged = merged_head = new_sabp1;
1442 merged->prev = NULL;
1443 }
1444 tmp1 = sabp1->segp_head;
1445 tmp_head = NULL;
1446 for (i = 1; i<=num_bioseqs1; i++)
1447 {
1448 tmp2 = (SegmentPtr)MemNew(sizeof(Segment));
1449 if (tmp_head)
1450 {
1451 tmp_curr->next = tmp2;
1452 tmp2->prev = tmp_curr;
1453 tmp_curr = tmp2;
1454 } else
1455 {
1456 tmp_head = tmp_curr = tmp2;
1457 }
1458 tmp2->from = tmp1->from;
1459 tmp2->to = tmp2->from + shift;
1460 tmp2->sip = tmp1->sip;
1461 tmp1 = tmp1->next;
1462 }
1463 tmp2 = sabp2->segp_head;
1464 for (i = 1; i<=num_bioseqs2; i++)
1465 {
1466 if (i!=index2)
1467 {
1468 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
1469 tmp_curr->next = tmp1;
1470 tmp1->prev = tmp_curr;
1471 tmp_curr = tmp1;
1472 tmp1->from = tmp1->to = tmp2->from -1;
1473 tmp1->sip = tmp2->sip;
1474 }
1475 tmp2 = tmp2->next;
1476 }
1477 new_sabp1->segp_head = tmp_head;
1478 new_sabp1->next = sabp2;
1479 new_sabp2 = sabp2->next;
1480 sabp2->next = NULL;
1481 sabp2->prev = merged;
1482 merged = sabp2;
1483 sabp2->AlignID = thisalign;
1484 tmp1 = sabp1->segp_head;
1485 for (i = 1; i<=num_bioseqs1; i++)
1486 {
1487 tmp2 = (SegmentPtr)MemNew(sizeof(Segment));
1488 if (i>1)
1489 {
1490 tmp2->prev = tmp_curr;
1491 tmp_curr->next = tmp2;
1492 } else
1493 {
1494 tmp_head = tmp_curr = tmp2;
1495 }
1496 tmp_curr = tmp2;
1497 tmp2->from = tmp2->to = -1;
1498 tmp2->gap = 1;
1499 tmp2->sip = tmp1->sip;
1500 tmp1->from += shift+1;
1501 tmp1 = tmp1->next;
1502 }
1503 tmp1 = segp2;
1504 for (i=1; i<=num_bioseqs2; i++)
1505 {
1506 if (i!=index2)
1507 {
1508 tmp_curr->next = tmp1;
1509 tmp1->prev = tmp_curr;
1510 tmp_curr = tmp1;
1511 tmp1 = tmp1->next;
1512 } else
1513 {
1514 tmp3 = tmp1->next;
1515 tmp1->next = tmp1->prev = NULL;
1516 MemFree(tmp1);
1517 tmp1 = tmp3;
1518 }
1519 }
1520 merged->segp_head = tmp_head;
1521 if (sabp1)
1522 segp1 = sabp1->segp_head;
1523 sabp2 = sabp2->next;
1524 if (sabp2)
1525 segp2 = sabp2->segp_head;
1526 } else if (orient == -1)
1527 {
1528 new_sabp2 = (SABlockPtr)MemNew(sizeof(SABlock));
1529 new_sabp2->AlignID = thisalign;
1530 if (merged_head)
1531 {
1532 merged->next = new_sabp2;
1533 new_sabp2->prev = merged;
1534 merged = new_sabp2;
1535 } else
1536 {
1537 merged = merged_head = new_sabp2;
1538 merged->prev = NULL;
1539 }
1540 tmp1 = segp1;
1541 for (i=1; i<=num_bioseqs1; i++)
1542 {
1543 tmp2 = (SegmentPtr)MemNew(sizeof(Segment));
1544 if (i == 1)
1545 {
1546 tmp_head = tmp_curr = tmp2;
1547 } else
1548 {
1549 tmp_curr->next = tmp2;
1550 tmp2->prev = tmp_curr;
1551 tmp_curr = tmp2;
1552 }
1553 tmp2->from = tmp2->to = -1;
1554 tmp2->gap = 1;
1555 tmp2->sip = tmp1->sip;
1556 }
1557 tmp1 = segp2;
1558 for (i=1; i<=num_bioseqs2; i++)
1559 {
1560 if (i!=index2)
1561 {
1562 tmp2 = (SegmentPtr)MemNew(sizeof(Segment));
1563 tmp_curr->next = tmp2;
1564 tmp2->prev = tmp_curr;
1565 tmp_curr=tmp2;
1566 tmp2->from = tmp1->from;
1567 tmp2->to = tmp2->from + shift;
1568 tmp1->from += (shift+1);
1569 }
1570 tmp1 = tmp1->next;
1571 }
1572 merged->segp_head = tmp_head;
1573 merged->next = sabp1;
1574 merged = sabp1;
1575 tmp_curr = merged->segp_head;
1576 for (i=1; i<num_bioseqs1; i++)
1577 {
1578 tmp_curr = tmp_curr->next;
1579 }
1580 tmp2 = segp2;
1581 for (i=1; i<=num_bioseqs2; i++)
1582 {
1583 if (i!=index2)
1584 {
1585 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
1586 tmp_curr->next = tmp1;
1587 tmp1->prev = tmp_curr;
1588 tmp_curr = tmp1;
1589 tmp1->from = tmp1->to = tmp2->from-1;
1590 tmp1->sip = tmp2->sip;
1591 }
1592 tmp2 = tmp2->next;
1593 }
1594 sabp1 = sabp1->next;
1595 if (sabp1)
1596 segp1 = sabp1->segp_head;
1597 } else if (orient == 1)
1598 {
1599 if (shift > 0)
1600 {
1601 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
1602 new_sabp1->AlignID = thisalign;
1603 }
1604 if (merged_head)
1605 {
1606 prev_sabp = merged;
1607 merged->next = sabp1;
1608 merged = merged->next;
1609 merged->prev = prev_sabp;
1610 } else
1611 {
1612 merged = merged_head = sabp1;
1613 merged->prev = NULL;
1614 }
1615 new_sabp2 = sabp1->next;
1616 tmp1 = merged->segp_head;
1617 for (i = 1; i<num_bioseqs1; i++)
1618 {
1619 tmp1 = tmp1->next;
1620 }
1621 for (i = 1; i<=num_bioseqs2; i++)
1622 {
1623 if (i!= index2)
1624 {
1625 prev = tmp1;
1626 tmp1->next = (SegmentPtr)MemNew(sizeof(Segment));
1627 tmp1 = tmp1->next;
1628 tmp1->from = tmp1->to = -1;
1629 tmp1->gap = 1;
1630 tmp1->sip = segp2->sip;
1631 tmp1->prev = prev;
1632 }
1633 segp2 = segp2->next;
1634 }
1635 if (shift > 0)
1636 {
1637 merged->next = new_sabp1;
1638 new_sabp1->prev = merged;
1639 merged = new_sabp1;
1640 segp1 = merged->prev->segp_head;
1641 tmp_head = NULL;
1642 i = 0;
1643 while (segp1)
1644 {
1645 i++;
1646 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
1647 if (tmp_head)
1648 {
1649 prev->next = tmp1;
1650 tmp1->prev = prev;
1651 prev = tmp1;
1652 } else
1653 {
1654 tmp_head = prev = tmp1;
1655 }
1656 if (i == index1)
1657 {
1658 tmp1->from = segp1->to+1;
1659 tmp1->to = tmp1->from + shift - 1;
1660 tmp1->gap = 0;
1661 tmp1->sip = segp1->sip;
1662 } else
1663 {
1664 tmp1->from = tmp1->to = segp1->to;
1665 tmp1->gap = 1;
1666 tmp1->sip = segp1->sip;
1667 }
1668 segp1 = segp1->next;
1669 }
1670 new_sabp1->segp_head = tmp_head;
1671 }
1672 sabp1 = new_sabp2;
1673 if (sabp1)
1674 segp1 = sabp1->segp_head;
1675 if (sabp2)
1676 segp2 = sabp2->segp_head;
1677 } else if (orient == 2)
1678 {
1679 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
1680 new_sabp1->AlignID = thisalign;
1681 new_sabp1->from = sabp1->from;
1682 new_sabp1->to = sabp1->from + shift - 1;
1683 tmp_head = NULL;
1684 tmp2 = sabp1->segp_head;
1685 for (i = 1; i<=num_bioseqs1; i++)
1686 {
1687 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
1688 if (tmp_head)
1689 {
1690 prev->next = tmp1;
1691 tmp1->prev = prev;
1692 prev = tmp1;
1693 } else
1694 {
1695 tmp_head = prev = tmp1;
1696 }
1697 tmp1->from = tmp2->from;
1698 tmp1->to = tmp1->from + shift - 1;
1699 tmp1->sip = tmp2->sip;
1700 tmp2 = tmp2->next;
1701 }
1702 tmp2 = sabp2->segp_head;
1703 for (i = 1; i<=num_bioseqs2; i++)
1704 {
1705 if (i != index2)
1706 {
1707 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
1708 prev->next = tmp1;
1709 tmp1->prev = prev;
1710 prev = tmp1;
1711 tmp1->from = tmp2->from-1;
1712 tmp1->to = tmp1->from;
1713 tmp1->sip = tmp2->sip;
1714 tmp1->gap = 1;
1715 }
1716 tmp2 = tmp2->next;
1717 }
1718 new_sabp1->segp_head = tmp_head;
1719 if (merged_head)
1720 {
1721 prev_sabp = merged;
1722 merged->next = new_sabp1;
1723 merged = merged->next;
1724 merged->prev = prev_sabp;
1725 } else
1726 {
1727 merged = merged_head = new_sabp1;
1728 merged->prev = NULL;
1729 }
1730 tmp1 = sabp1->segp_head;
1731 for (i = 1; i<num_bioseqs1; i++)
1732 {
1733 tmp1->from = tmp1->from + shift;
1734 tmp1 = tmp1->next;
1735 }
1736 tmp1->from = tmp1->from + shift;
1737 sabp1->prev = NULL;
1738 merged->next = NULL;
1739 segp1 = tmp1;
1740 if (sabp2)
1741 segp2 = sabp2->segp_head;
1742 } else if (orient == 3)
1743 {
1744 if (shift == 0)
1745 {
1746 if (merged_head && (sabp1 != merged))
1747 {
1748 merged->next = sabp1;
1749 sabp1->prev = merged;
1750 merged = sabp1;
1751 } else
1752 {
1753 merged = merged_head = sabp1;
1754 merged->prev = NULL;
1755 }
1756 tmp1 = sabp1->segp_head;
1757 for (i = 1; i< num_bioseqs1; i++)
1758 {
1759 tmp1 = tmp1->next;
1760 }
1761 tmp2 = sabp2->segp_head;
1762 for (i = 1; i<=num_bioseqs2; i++)
1763 {
1764 if (i!= index2)
1765 {
1766 tmp1->next = tmp2;
1767 tmp2->prev = tmp1;
1768 tmp1 = tmp1->next;
1769 tmp2 = tmp2->next;
1770 } else
1771 {
1772 tmp3 = tmp2->next;
1773 tmp2->next = tmp2->prev = NULL;
1774 MemFree(tmp2);
1775 tmp2 = tmp3;
1776 }
1777 }
1778 sabp1 = sabp1->next;
1779 if (sabp1)
1780 segp1 = sabp1->segp_head;
1781 sabp2->segp_head = NULL;
1782 new_sabp2 = sabp2->next;
1783 sabp2->prev = sabp2->next = NULL;
1784 MemFree(sabp2);
1785 sabp2 = new_sabp2;
1786 if (sabp2)
1787 segp2 = sabp2->segp_head;
1788 } else if (shift > 0)
1789 {
1790 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
1791 new_sabp1->AlignID = thisalign;
1792 if (merged_head)
1793 {
1794 merged->next = new_sabp1;
1795 new_sabp1->prev = merged;
1796 merged = new_sabp1;
1797 } else
1798 {
1799 merged = merged_head = new_sabp1;
1800 merged->prev = NULL;
1801 }
1802 tmp1 = sabp1->segp_head;
1803 tmp_head = NULL;
1804 for (i = 1; i<=num_bioseqs1; i++)
1805 {
1806 tmp2 = (SegmentPtr)MemNew(sizeof(Segment));
1807 if (tmp_head)
1808 {
1809 tmp_curr->next = tmp2;
1810 tmp2->prev = tmp_curr;
1811 tmp_curr = tmp2;
1812 } else
1813 {
1814 tmp_head = tmp_curr = tmp2;
1815 }
1816 tmp2->sip = tmp1->sip;
1817 tmp2->from = tmp1->from;
1818 tmp2->gap = tmp1->gap;
1819 if (tmp1->gap == 0)
1820 {
1821 tmp2->to = tmp1->to - shift;
1822 tmp1->from = tmp1->to - shift + 1;
1823 } else
1824 {
1825 tmp2->to = tmp2->from;
1826 }
1827 tmp1 = tmp1->next;
1828 }
1829 tmp2 = sabp2->segp_head;
1830 for (i = 1; i<=num_bioseqs2; i++)
1831 {
1832 if (i!=index2)
1833 {
1834 tmp_curr->next = tmp2;
1835 tmp2->prev = tmp_curr;
1836 tmp2->next = NULL;
1837 tmp_curr = tmp2;
1838 tmp2 = tmp2->next;
1839 } else
1840 {
1841 tmp3 = tmp2->next;
1842 tmp2->next = tmp2->prev = NULL;
1843 MemFree(tmp2);
1844 tmp2 = tmp3;
1845 }
1846 }
1847 tmp_curr->next = NULL;
1848 new_sabp1->segp_head = tmp_head;
1849 new_sabp2 = sabp2->next;
1850 sabp2->next = sabp2->prev = NULL;
1851 MemFree(sabp2);
1852 sabp2 = new_sabp2;
1853 if (sabp2)
1854 segp2 = sabp2->segp_head;
1855 if (sabp1)
1856 segp1 = sabp1->segp_head;
1857 } else if (shift < 0)
1858 {
1859 if (merged_head && (sabp1!=merged))
1860 {
1861 merged->next = sabp1;
1862 sabp1->prev = merged;
1863 merged = sabp1;
1864 } else
1865 {
1866 merged = merged_head = sabp1;
1867 merged->prev = NULL;
1868 }
1869 tmp1 = sabp1->segp_head;
1870 for (i = 1; i<=num_bioseqs1; i++)
1871 {
1872 tmp_head= tmp1;
1873 tmp1 = tmp1->next;
1874 }
1875 tmp2 = sabp2->segp_head;
1876 for (i = 1; i<=num_bioseqs2; i++)
1877 {
1878 if (i != index2)
1879 {
1880 tmp_curr = (SegmentPtr)MemNew(sizeof(Segment));
1881 tmp_curr->prev = tmp_head;
1882 tmp_head->next = tmp_curr;
1883 tmp_head = tmp_curr;
1884 tmp_curr->from = tmp2->from;
1885 if (tmp2->gap == 0)
1886 {
1887 tmp_curr->to = tmp2->to + shift;
1888 } else
1889 {
1890 tmp_curr->to = tmp_curr->from;
1891 tmp_curr->gap = tmp2->gap;
1892 }
1893 tmp_curr->sip = tmp2->sip;
1894 }
1895 if (tmp2->gap == 0)
1896 tmp2->from = tmp2->to + shift + 1;
1897 tmp2 = tmp2->next;
1898 }
1899 if (sabp2)
1900 segp2 = sabp2->segp_head;
1901 sabp1 = sabp1->next;
1902 if (sabp1)
1903 segp1 = sabp1->segp_head;
1904 }
1905 } else if (orient == 4)
1906 {
1907 if(merged_head)
1908 {
1909 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
1910 new_sabp1->AlignID = thisalign;
1911 merged->next = new_sabp1;
1912 new_sabp1->prev = merged;
1913 } else
1914 {
1915 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
1916 new_sabp1->AlignID = thisalign;
1917 merged_head = merged = new_sabp1;
1918 merged->prev = NULL;
1919 }
1920 tmp1 = sabp1->segp_head;
1921 tmp_head = NULL;
1922 for (i = 1; i<=num_bioseqs1; i++)
1923 {
1924 tmp2 = (SegmentPtr)MemNew(sizeof(Segment));
1925 if (tmp_head)
1926 {
1927 tmp_curr->next = tmp2;
1928 tmp2->prev = tmp_curr;
1929 tmp_curr = tmp2;
1930 } else
1931 {
1932 tmp_head = tmp_curr = tmp2;
1933 }
1934 tmp2->from = tmp1->from;
1935 if (tmp1->gap == 0)
1936 {
1937 tmp2->to = tmp2->from + shift - 1;
1938 tmp1->from = tmp1->from + shift;
1939 }
1940 tmp2->sip = tmp1->sip;
1941 tmp1 = tmp1->next;
1942 }
1943 tmp2 = sabp2->segp_head;
1944 for (i = 1; i<=num_bioseqs2; i++)
1945 {
1946 if (i!=index2)
1947 {
1948 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
1949 tmp_curr->next = tmp1;
1950 tmp1->prev = tmp_curr;
1951 tmp1->from = tmp1->to = -1;
1952 tmp1->gap = 1;
1953 tmp1->sip = tmp2->sip;
1954 }
1955 tmp2 = tmp2->next;
1956 }
1957 tmp1->next = NULL;
1958 if (sabp1)
1959 segp1 = sabp1->segp_head;
1960 if (sabp2)
1961 segp2 = sabp2->segp_head;
1962 } else if (orient == 5 || orient == 6)
1963 {
1964 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
1965 new_sabp1->AlignID = thisalign;
1966 if (merged_head)
1967 {
1968 merged->next = new_sabp1;
1969 new_sabp1->prev = merged;
1970 merged = new_sabp1;
1971 } else
1972 {
1973 merged = merged_head = new_sabp1;
1974 merged->prev = NULL;
1975 }
1976 tmp2 = sabp1->segp_head;
1977 tmp_head = NULL;
1978 for (i = 1; i<=num_bioseqs1; i++)
1979 {
1980 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
1981 if (tmp_head)
1982 {
1983 tmp_curr->next = tmp1;
1984 tmp1->prev = tmp_curr;
1985 tmp_curr = tmp1;
1986 } else
1987 {
1988 tmp_curr = tmp_head = tmp1;
1989 }
1990 tmp1->from = tmp2->from - 1;
1991 tmp1->to = tmp2->from - 1;
1992 tmp1->gap = 1;
1993 tmp1->sip = tmp2->sip;
1994 tmp2 = tmp2->next;
1995 }
1996 tmp2 = segp2;
1997 for (i = 1; i<=num_bioseqs2; i++)
1998 {
1999 if (i!=index2)
2000 {
2001 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
2002 tmp1->prev = tmp_curr;
2003 tmp_curr->next = tmp1;
2004 tmp_curr = tmp1;
2005 tmp1->from = tmp2->from;
2006 tmp1->to = tmp2->from + shift - 1;
2007 }
2008 tmp2->from += shift;
2009 tmp2 = tmp2->next;
2010 }
2011 if (sabp1)
2012 segp1 = sabp1->segp_head;
2013 if (sabp2)
2014 segp2 = sabp2->segp_head;
2015 } else if (orient == 7)
2016 {
2017 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
2018 new_sabp1->AlignID = thisalign;
2019 if (merged_head)
2020 {
2021 merged->next = new_sabp1;
2022 new_sabp1->prev = merged;
2023 merged = new_sabp1;
2024 } else
2025 {
2026 merged = merged_head = new_sabp1;
2027 merged->prev = NULL;
2028 }
2029 tmp2 = sabp1->segp_head;
2030 tmp_head = NULL;
2031 for (i = 1; i<=num_bioseqs1; i++)
2032 {
2033 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
2034 if (tmp_head)
2035 {
2036 tmp_curr->next = tmp1;
2037 tmp1->prev = tmp_curr;
2038 tmp_curr = tmp1;
2039 } else
2040 {
2041 tmp_curr = tmp_head = tmp1;
2042 }
2043 if (i == index1)
2044 {
2045 prev = sabp2->segp_head;
2046 for (c = 1; c<=num_bioseqs2; c++)
2047 {
2048 if (c==index2)
2049 {
2050 tmp1->from = prev->from;
2051 tmp1->to = prev->to;
2052 tmp1->gap = 0;
2053 }
2054 prev = prev->next;
2055 }
2056 } else
2057 {
2058 tmp1->from = -1;
2059 tmp1->to = -1;
2060 tmp1->gap = 1;
2061 }
2062 tmp1->sip = tmp2->sip;
2063 tmp2 = tmp2->next;
2064 }
2065 tmp2 = segp2;
2066 for (i = 1; i<=num_bioseqs2; i++)
2067 {
2068 if (i!=index2)
2069 {
2070 tmp_curr->next = tmp2;
2071 tmp2->prev = tmp_curr;
2072 tmp_curr = tmp2;
2073 tmp2 = tmp2->next;
2074 } else
2075 {
2076 tmp3 = tmp2;
2077 tmp2 = tmp2->next;
2078 tmp3->next = tmp3->prev = NULL;
2079 MemFree(tmp3);
2080 }
2081 }
2082 new_sabp1->segp_head = tmp_head;
2083 sabp2->segp_head = NULL;
2084 new_sabp2 = sabp2->next;
2085 sabp2->next = sabp2->prev = NULL;
2086 MemFree(sabp2);
2087 sabp2 = new_sabp2;
2088 if (shift > 0)
2089 {
2090 new_sabp1 = (SABlockPtr)MemNew(sizeof(SABlock));
2091 tmp_head = NULL;
2092 tmp1 = merged->segp_head;
2093 i = 0;
2094 while (tmp1)
2095 {
2096 i++;
2097 tmp_curr = (SegmentPtr)MemNew(sizeof(Segment));
2098 if (tmp_head)
2099 {
2100 prev->next = tmp_curr;
2101 tmp_curr->prev = prev;
2102 prev = tmp_curr;
2103 } else
2104 {
2105 tmp_head = prev = tmp_curr;
2106 }
2107 if (i == index1)
2108 {
2109 tmp_curr->from = tmp1->to + 1;
2110 tmp_curr->to = tmp_curr->from + shift - 1;
2111 tmp_curr->gap = 0;
2112 } else
2113 {
2114 tmp_curr->from = tmp_curr->to = tmp1->to;
2115 tmp_curr->gap = 1;
2116 }
2117 tmp_curr->sip = tmp1->sip;
2118 tmp1 = tmp1->next;
2119 }
2120 new_sabp1->segp_head = tmp_head;
2121 new_sabp1->prev = merged;
2122 merged->next = new_sabp1;
2123 merged = new_sabp1;
2124 }
2125 if (sabp1)
2126 segp1 = sabp1->segp_head;
2127 if (sabp2)
2128 segp2 = sabp2->segp_head;
2129 }
2130 if (sabp1 == NULL)
2131 {
2132 new_sabp2 = NULL;
2133 if (sabp2)
2134 new_sabp2 = sabp2;
2135 while (sabp2)
2136 {
2137 segp1 = merged->segp_head;
2138 for (i = 1; i<=num_bioseqs1; i++)
2139 {
2140 tmp1 = (SegmentPtr)MemNew(sizeof(Segment));
2141 if (i == 1)
2142 {
2143 tmp2 = sabp2->segp_head;
2144 sabp2->segp_head = tmp1;
2145 tmp_curr = tmp1;
2146 } else
2147 {
2148 tmp_curr->next = tmp1;
2149 tmp1->prev = tmp_curr;
2150 tmp_curr = tmp1;
2151 }
2152 tmp1->from = tmp1->to = segp1->from + 1;
2153 tmp1->gap = 1;
2154 tmp1->sip = segp1->sip;
2155 segp1 = segp1->next;
2156 }
2157 for (i = 1; i<=num_bioseqs2; i++)
2158 {
2159 if (i!=index2)
2160 {
2161 tmp_curr->next = tmp2;
2162 tmp2->prev = tmp_curr;
2163 tmp_curr = tmp2;
2164 }
2165 tmp2 = tmp2->next;
2166 }
2167 sabp2 = sabp2->next;
2168 }
2169 if (new_sabp2)
2170 {
2171 merged->next = new_sabp2;
2172 new_sabp2->prev = merged;
2173 merged = new_sabp2;
2174 }
2175 done = TRUE;
2176 } else if (sabp2 == NULL)
2177 {
2178 new_sabp1 = sabp1;
2179 while (sabp1)
2180 {
2181 tmp2 = merged->prev->segp_head;
2182 tmp1 = sabp1->segp_head;
2183 for (i = 1; i<num_bioseqs1; i++)
2184 {
2185 tmp1 = tmp1->next;
2186 tmp2 = tmp2->next;
2187 }
2188 tmp2 = tmp2->next;
2189 for (i = 1; i<=num_bioseqs2; i++)
2190 {
2191 if (i != index2)
2192 {
2193 tmp_curr = (SegmentPtr)MemNew(sizeof(Segment));
2194 tmp1->next = tmp_curr;
2195 tmp_curr->prev = tmp1;
2196 tmp1 = tmp_curr;
2197 tmp1->from = tmp1->to = tmp2->to;
2198 tmp1->gap = 1;
2199 tmp1->sip = tmp2->sip;
2200 tmp2 = tmp2->next;
2201 }
2202 }
2203 sabp1 = sabp1->next;
2204 }
2205 merged->next = new_sabp1;
2206 new_sabp1->prev = merged;
2207 while (merged->next)
2208 merged = merged->next;
2209 done = TRUE;
2210 }
2211 }
2212 if (!done)
2213 merged->next = NULL;
2214 merged_head = IndexBlocks(merged_head); /* fix IndexBlocks to number gaps */
2215 merged_head = SquishBlocks(merged_head);
2216 i = 0;
2217 if (minus1)
2218 {
2219 segp1 = merged_head->segp_head;
2220 minus_tmp = minus_head1;
2221 while (minus_tmp)
2222 {
2223 i++;
2224 if (minus_tmp->strand == Seq_strand_minus && i!= index1)
2225 {
2226 FlipSequence(segp1, (minus_tmp->to + minus_tmp->from));
2227 }
2228 segp1 = segp1->next;
2229 minus_tmp = minus_tmp->next;
2230 }
2231 }
2232 i = 0;
2233 if (minus2)
2234 {
2235 minus_tmp = minus_head2;
2236 while (minus_tmp)
2237 {
2238 i++;
2239 if (i == index2)
2240 minus_tmp = minus_tmp->next;
2241 if (minus_tmp->strand == Seq_strand_minus)
2242 {
2243 FlipSequence(segp1, (minus_tmp->to + minus_tmp->from));
2244 }
2245 segp1 = segp1->next;
2246 minus_tmp = minus_tmp->next;
2247 }
2248 }
2249 merged = merged_head;
2250 while (merged->next)
2251 merged = merged->next;
2252 return merged_head;
2253 }
2254
2255
2256 NLM_EXTERN Int4 GetBlockOrientation(Int4Ptr shift, SegmentPtr segp1, SegmentPtr segp2, Int4 index1, Int4 index2)
2257 {
2258 Int4 i;
2259 Int4 orient;
2260
2261 for (i = 1; i < index1; i++)
2262 {
2263 segp1 = segp1->next;
2264 }
2265 for (i = 1; i < index2; i++)
2266 {
2267 segp2 = segp2->next;
2268 }
2269 if (segp1->gap != 0)
2270 {
2271 if (segp2->gap == 0)
2272 {
2273 if (segp1->from <= segp2->from)
2274 {
2275 *shift = 0;
2276 orient = 1;
2277 }
2278 else if (segp2->from < segp1->from && segp2->to > segp1->from)
2279 /* ..... */
2280 /* _________ */
2281 {
2282 *shift = segp1->from - segp2->from;
2283 orient = -1;
2284 } else if (segp2->to <= segp1->from)
2285 /* .... */
2286 /* ______ */
2287 {
2288 *shift = 0;
2289 orient = 7;
2290 }
2291 } else
2292 {
2293 if (segp1->from == segp2->from)
2294 {
2295 *shift = 0;
2296 orient = 3;
2297 } else if (segp1->from > segp2->from)
2298 {
2299 *shift = 0;
2300 orient = 7;
2301 } else
2302 {
2303 *shift = 0;
2304 orient = 1;
2305 }
2306 }
2307 } else if (segp2->gap != 0)
2308 {
2309 if (segp1->from < segp2->from && segp1->to > segp2->from)
2310 /* ---------- */
2311 /* ...... */
2312 {
2313 *shift = segp2->from - segp1->from;
2314 orient = -2;
2315 } else if (segp1->from >= segp2->from)
2316 /* --------*/
2317 /* .... */
2318 {
2319 *shift = 0;
2320 orient = 7;
2321 } else if (segp1->to < segp2->from)
2322 /* ------- */
2323 /* ..... */
2324 {
2325 *shift = 0;
2326 orient = 1;
2327 }
2328 } else if (segp1->from < segp2->from && segp1->to < segp2->from)
2329 /* --------- */
2330 /* _________*/
2331 {
2332 if (segp1->bsp_next)
2333 {
2334 if (segp1->bsp_next->from > segp1->to+1)
2335 {
2336 *shift = MIN((segp2->from - segp1->to - 1), (segp1->bsp_next->from-segp1->to));
2337 } else
2338 {
2339 *shift = 0;
2340 }
2341 } else
2342 {
2343 *shift = segp2->from - segp1->to;
2344 }
2345 orient = 1;
2346 } else if (segp1->from < segp2->from && segp1->to < segp2->to)
2347 /* ------------ */
2348 /* ____________*/
2349 {
2350 *shift = segp2->from - segp1->from;
2351 orient = 2;
2352 } else if (segp1->from == segp2->from)
2353 /* ---------- or ------- */
2354 /* ______ */ /* ___________ */
2355 {
2356 *shift = segp1->to - segp2->to;
2357 orient = 3;
2358 } else if (segp1->from < segp2->from)
2359 /* --------------- */
2360 /* ______ */
2361 {
2362 *shift = segp2->from - segp1->from;
2363 orient = 4;
2364 } else if (segp1->from > segp2->from && segp1->to < segp2->to)
2365 /* ------- */
2366 /* ______________ */
2367 {
2368 *shift = segp1->from - segp2->from;
2369 orient = 5;
2370 } else if (segp1->from > segp2->from && segp1->from <= segp2->to)
2371 /* ----------*/
2372 /* __________ */
2373 {
2374 *shift = segp1->from - segp2->from;
2375 orient = 6;
2376 } else if (segp1->from > segp2->to)
2377 /* ---------*/
2378 /*______ */
2379 {
2380 *shift = segp1->from - segp2->to - 1;
2381 orient = 7;
2382 }
2383 return orient;
2384 }
2385
2386 NLM_EXTERN SABlockPtr SARemoveSequence(Int4 BspID, SeqIdPtr sip, SABlockPtr sabp)
2387 {
2388 SABlockPtr sabp_head;
2389 SegmentPtr segp;
2390
2391 sabp_head = sabp;
2392 if (BspID)
2393 {
2394 while (sabp)
2395 {
2396 segp = sabp->segp_head;
2397 while (segp)
2398 {
2399 if (segp->BspID == BspID)
2400 {
2401 if (segp->prev == NULL)
2402 {
2403 sabp->segp_head = segp->next;
2404 segp->next = NULL;
2405 MemFree(segp);
2406 } else
2407 {
2408 segp->prev->next = segp->next;
2409 if (segp->next)
2410 segp->next->prev = segp->prev;
2411 segp->prev = segp->next = NULL;
2412 MemFree(segp);
2413 }
2414 }
2415 segp = segp->next;
2416 }
2417 sabp = sabp->next;
2418 }
2419 sabp_head = SquishBlocks(sabp_head);
2420 } else if (sip)
2421 {
2422 while (sabp)
2423 {
2424 segp = sabp->segp_head;
2425 while (segp)
2426 {
2427 if (SeqIdComp(sip, segp->sip))
2428 {
2429 if (segp->prev == NULL)
2430 {
2431 sabp->segp_head = segp->next;
2432 segp->next = NULL;
2433 MemFree(segp);
2434 } else
2435 {
2436 segp->prev->next = segp->next;
2437 if (segp->next)
2438 segp->next->prev = segp->prev;
2439 segp->prev = segp->next = NULL;
2440 MemFree(segp);
2441 }
2442 }
2443 segp = segp->next;
2444 }
2445 sabp = sabp->next;
2446 }
2447 sabp_head = SquishBlocks(sabp_head);
2448 }
2449 return sabp_head;
2450 }
2451
2452
2453 /*******************************************************************
2454 * SquishBlocks looks through an SABlock structure and merges
2455 * together adjacent series of Segments if the Segments, looking
2456 * pairwise, have the same pattern, e.g.
2457 * ... ..... (gap) ........
2458 * ___ _____ (sequence) ________
2459 * ___ _____ (sequence) -> ________
2460 * ... ..... (gap) ........
2461 *
2462 * The function also removes an SABlock if all its segments consist
2463 * only of gaps.
2464 * Note that the SABlock structure must be regular; that is, every
2465 * SABlock must have the same number of segments, in the same order,
2466 * or things will get strangely truncated.
2467 ********************************************************************/
2468
2469 NLM_EXTERN SABlockPtr SquishBlocks(SABlockPtr sabp)
2470 {
2471 Boolean all_gap1;
2472 Boolean all_gap2;
2473 Boolean merge;
2474 SABlockPtr sabp_head;
2475 SABlockPtr sabp_next;
2476 SABlockPtr sabp_tmp;
2477 SegmentPtr segp1;
2478 SegmentPtr segp2;
2479
2480 sabp_head = sabp;
2481 while (sabp)
2482 {
2483 sabp_next = sabp->next;
2484 if (!sabp_next)
2485 sabp = sabp->next;
2486 else
2487 {
2488 segp1 = sabp->segp_head;
2489 segp2 = sabp_next->segp_head;
2490 merge = all_gap1 = all_gap2 = TRUE;
2491 while (segp1 && segp2)
2492 {
2493 if (segp1->gap == 0 && segp2->gap != 0)
2494 {
2495 all_gap1 = FALSE;
2496 merge = FALSE;
2497 } else if (segp1->gap != 0 && segp2->gap == 0)
2498 {
2499 all_gap2 = FALSE;
2500 merge = FALSE;
2501 } else if (segp1->gap == 0 && segp2->gap == 0)
2502 {
2503 all_gap1 = FALSE;
2504 all_gap2 = FALSE;
2505 }
2506 segp1 = segp1->next;
2507 segp2 = segp2->next;
2508 }
2509 if (merge)
2510 {
2511 if (all_gap1)
2512 {
2513 if (sabp->prev)
2514 {
2515 sabp->prev->next = sabp_next->next;
2516 if (sabp_next->next)
2517 sabp_next->next->prev = sabp->prev;
2518 sabp_tmp = sabp_next->next;
2519 sabp->prev = sabp->next = NULL;
2520 sabp_next->prev = sabp_next->next = NULL;
2521 CleanupBlocks(sabp);
2522 CleanupBlocks(sabp_next);
2523 sabp = sabp_tmp;
2524 } else
2525 {
2526 sabp_head = sabp_next->next;
2527 sabp->next = NULL;
2528 if (sabp_next->next)
2529 sabp_next->next->prev = NULL;
2530 sabp_next->prev = sabp_next->next = NULL;
2531 CleanupBlocks(sabp);
2532 CleanupBlocks(sabp_next);
2533 sabp = sabp_head;
2534 }
2535 } else
2536 {
2537 segp1 = sabp->segp_head;
2538 segp2 = sabp_next->segp_head;
2539 while (segp1 && segp2)
2540 {
2541 segp1->to = segp2->to;
2542 segp1 = segp1->next;
2543 segp2 = segp2->next;
2544 }
2545 sabp_tmp = sabp_next->next;
2546 sabp->next = sabp_next->next;
2547 if (sabp_next->next)
2548 sabp_next->next->prev = sabp;
2549 sabp_next->prev = sabp_next->next = NULL;
2550 CleanupBlocks(sabp_next);
2551 if (sabp_tmp)
2552 sabp_tmp->prev = sabp;
2553 }
2554 } else if (all_gap1)
2555 {
2556 if (sabp->prev)
2557 {
2558 sabp->prev->next = sabp->next;
2559 sabp_tmp = sabp->next;
2560 sabp->prev = sabp->next = NULL;
2561 CleanupBlocks(sabp);
2562 sabp = sabp_tmp;
2563 } else
2564 {
2565 sabp_head = sabp->next;
2566 sabp->prev = sabp->next = NULL;
2567 CleanupBlocks(sabp);
2568 sabp = sabp_head;
2569 }
2570 } else if (all_gap2)
2571 {
2572 sabp->next = sabp_next->next;
2573 if (sabp_next->next)
2574 sabp_next->next->prev = sabp;
2575 sabp_next->prev = sabp_next->next = NULL;
2576 CleanupBlocks(sabp_next);
2577 } else
2578 {
2579 sabp = sabp->next;
2580 }
2581 }
2582 all_gap1 = TRUE;
2583 if (sabp)
2584 {
2585 segp1 = sabp->segp_head;
2586 while (segp1 && all_gap1)
2587 {
2588 if (segp1->gap == 0)
2589 all_gap1 = FALSE;
2590 segp1 = segp1->next;
2591 }
2592 if (all_gap1)
2593 {
2594 if (sabp->prev)
2595 sabp->prev->next = sabp->next;
2596 if (sabp->next)
2597 sabp->next->prev = sabp->prev;
2598 sabp->prev = sabp->next = NULL;
2599 CleanupBlocks(sabp);
2600 }
2601 }
2602 }
2603 sabp_head = IndexBlocks(sabp_head);
2604 return sabp_head;
2605 }
2606
2607
2608 /***************************************************************
2609 * RearrangeSegments puts any BspID into any position. If the
2610 * position given is greater than the number of bioseqs, or if the
2611 * BspID is already in that position, or if the BspID is not
2612 * found in the structure, the function gives back the SABlock
2613 * structure unchanged.
2614 ****************************************************************/
2615
2616 NLM_EXTERN SABlockPtr RearrangeSegments (Int4 BspID, SABlockPtr sabp, Int4 position)
2617 {
2618 Int4 counter;
2619 Boolean found;
2620 SABlockPtr sabp_head;
2621 SegmentPtr segp;
2622 SegmentPtr segp_target;
2623
2624 sabp_head = sabp;
2625 while (sabp)
2626 {
2627 counter = 0;
2628 segp = sabp->segp_head;
2629 found = FALSE;
2630 while (segp && !found)
2631 {
2632 counter += 1;
2633 if (BspID == segp->BspID)
2634 {
2635 if (counter == position)
2636 return sabp_head;
2637 segp_target = segp;
2638 if (segp_target->next)
2639 {
2640 if (segp->prev)
2641 {
2642 segp_target->next->prev = segp->prev;
2643 segp->prev->next = segp_target->next;
2644 } else
2645 {
2646 sabp->segp_head = segp_target->next;
2647 segp_target->next->prev = NULL;
2648 }
2649 } else
2650 {
2651 if (segp->prev)
2652 {
2653 segp->prev->next = NULL;
2654 } else
2655 {
2656 return sabp_head;
2657 }
2658 }
2659 segp_target->next = segp_target->prev = NULL;
2660 found = TRUE;
2661 }
2662 segp = segp->next;
2663 }
2664 if (!found)
2665 return sabp_head;
2666 segp = sabp->segp_head;
2667 found = FALSE;
2668 counter = 0;
2669 while (segp && !found)
2670 {
2671 counter += 1;
2672 if (counter == position)
2673 {
2674 segp_target->next = segp;
2675 if (segp->prev)
2676 {
2677 segp_target->prev = segp->prev;
2678 segp->prev->next = segp_target;
2679 segp->prev = segp_target;
2680 } else
2681 {
2682 sabp->segp_head = segp_target;
2683 segp_target->prev = NULL;
2684 segp_target->next = segp;
2685 segp->prev = segp_target;
2686 }
2687 found = TRUE;
2688 }
2689 segp = segp->next;
2690 }
2691 if (!found)
2692 return sabp_head;
2693 sabp = sabp->next;
2694 }
2695 return sabp_head;
2696 }
2697
2698 static void FlipSequence(SegmentPtr segp, Int4 len)
2699 {
2700 Int4 temp;
2701 SegmentPtr segp_tmp;
2702
2703 segp_tmp = segp;
2704 while (segp_tmp)
2705 {
2706 if (segp_tmp->gap!=2)
2707 {
2708 temp = segp_tmp->to;
2709 segp_tmp->to = len - segp_tmp->from;
2710 segp_tmp->from = len - temp;
2711 /* if (segp_tmp->strand == Seq_strand_minus)
2712 segp_tmp->strand = Seq_strand_plus;
2713 else
2714 segp_tmp->strand = Seq_strand_minus; */
2715 }
2716 segp_tmp = segp_tmp->bsp_next;
2717 }
2718 return;
2719 }
2720
2721 static void CalcMinusBounds(SegmentPtr segp, SegmentPtr PNTR segp_storage)
2722 {
2723 SegmentPtr segp_tmp;
2724
2725 segp_tmp = segp;
2726 (*segp_storage)->from = (*segp_storage)->to = -3;
2727 while (segp_tmp)
2728 {
2729 if (segp_tmp->gap == 0)
2730 {
2731 if ((*segp_storage)->from < -1)
2732 {
2733 (*segp_storage)->from = segp_tmp->from;
2734 }
2735 (*segp_storage)->to = segp_tmp->to;
2736 }
2737 segp_tmp = segp_tmp->bsp_next;
2738 }
2739 return;
2740 }
2741
2742 /***************************************************************
2743 * SASplitBlock takes the input block and splits it:
2744 * agaaacttttccgctccacc
2745 * 7 9 26
2746 *
2747 * if from = 10, the function will return a pointer to a block
2748 * containing the alignment from 7 to 9, whose 'next' pointer
2749 * will point to a block containing the alignment from 10 to 26.
2750 * The function copies the RegionID of the parent block into
2751 * both of the new blocks, and it does not try to renumber the
2752 * SegIDs or to horizontally link the new segments; therefore,
2753 * IndexBlocks must be called after using this function. If
2754 * from is the same as the first residue of the block, or if
2755 * from is greater than the last residue in the block, nothing
2756 * happens.
2757 ***************************************************************/
2758
2759 NLM_EXTERN SABlockPtr SASplitBlock (SABlockPtr sabp, Int4 from)
2760 {
2761 SABlockPtr sabp_head;
2762 SABlockPtr sabp_new;
2763 SegmentPtr segp1;
2764 SegmentPtr segp2;
2765 SegmentPtr segp2_prev;
2766 Int4 shift;
2767
2768 sabp_head = sabp;
2769 if (from > sabp->from && from <= sabp->to)
2770 {
2771 sabp_new = (SABlockPtr)MemNew(sizeof(SABlock));
2772 sabp_new->from = from;
2773 sabp_new->to = sabp->to;
2774 sabp->to = from-1;
2775 shift = sabp->to - sabp->from;
2776 sabp_new->next = sabp->next;
2777 if (sabp_new->next)
2778 {
2779 sabp_new->next->prev = sabp_new;
2780 }
2781 sabp->next = sabp_new;
2782 sabp_new->prev = sabp;
2783 sabp_new->AlignID = sabp->AlignID;
2784 sabp_new->RegionID = sabp->RegionID;
2785 sabp_new->visible = sabp->visible;
2786 /* lyg: preserve align state */
2787 sabp_new->aligned = sabp->aligned;
2788 segp1 = sabp->segp_head;
2789 sabp_new->segp_head = NULL;
2790 while (segp1)
2791 {
2792 segp2 = (SegmentPtr)MemNew(sizeof(Segment));
2793 if (sabp_new->segp_head)
2794 {
2795 segp2_prev->next = segp2;
2796 segp2->prev = segp2_prev;
2797 segp2_prev = segp2;
2798 } else
2799 {
2800 sabp_new->segp_head = segp2_prev = segp2;
2801 }
2802 if (segp1->gap != 0)
2803 {
2804 segp2->gap = segp1->gap;
2805 segp2->from = segp2->to = segp1->to;
2806 segp2->sip = segp1->sip;
2807 segp2->visible = segp1->visible;
2808 } else
2809 {
2810 segp2->from = segp1->from + shift + 1;
2811 segp2->to = segp1->to;
2812 segp1->to = segp1->from + shift;
2813 segp2->sip = segp1->sip;
2814 segp2->visible = segp1->visible;
2815 }
2816 segp2->link = segp1->link;
2817 segp2->strand = segp1->strand;
2818 segp1 = segp1->next;
2819 }
2820 }
2821 return sabp_head;
2822 }
2823
2824
2825 /****************************************************************
2826 * TeenyBlock makes 1-residue blocks beginning at the alignment
2827 * coordinate "from" and ending with the alignment coordinate
2828 * "to" (inclusive). It calls SASplitBlock recursively to
2829 * create the little blocks. If from > to, the function makes the
2830 * entire alignment into 1-residue blocks starting at from. If
2831 * from and to are both 0, the function splits the whole alignment.
2832 * If from and to are not included in the alignment coordinates,
2833 * the function does nothing.
2834 ****************************************************************/
2835
2836 NLM_EXTERN SABlockPtr TeenyBlock (SABlockPtr sabp, Int4 from, Int4 to)
2837 {
2838 SABlockPtr sabp_head;
2839 SABlockPtr sabp_prev;
2840
2841 sabp_head = sabp;
2842 if (!sabp)
2843 return NULL;
2844 if(from <= to) {
2845 while (from > sabp->to){
2846 sabp = sabp->next;
2847 if (!sabp)
2848 return sabp_head;
2849 }
2850 if (to < sabp->to)
2851 sabp = SASplitBlock(sabp, to+1);
2852 }
2853 while (to >= sabp->to || from > to || to == 0)
2854 {
2855 while (from <= sabp->to && sabp)
2856 {
2857 sabp_prev = sabp->prev;
2858 sabp = SASplitBlock(sabp, from);
2859 if (sabp_prev)
2860 {
2861 sabp_prev->next = sabp;
2862 sabp->prev = sabp_prev;
2863 } else
2864 {
2865 sabp_head = sabp;
2866 }
2867 sabp = sabp->next;
2868 from += 1;
2869 }
2870 from++; /* lyg don't need to split existing split */
2871 sabp = sabp->next;
2872 if(sabp == NULL) break;
2873 if (to < sabp->to)
2874 {
2875 sabp = SASplitBlock(sabp, to+1);
2876 }
2877 }
2878 sabp_head = IndexBlocks(sabp_head);
2879 return sabp_head;
2880 }
2881
2882
2883 /**********************************************************************
2884 * AddEmptyBlocks adds n blocks to the beginning and/or to the end of
2885 * the given SABlock structure. The blocks consist of the same number
2886 * of segments, with seqids, and BspIDs all set as expected, as
2887 * the rest of the blocks, but the 'from' and 'to' numbers are all left
2888 * as zero. The segments are horizontally linked in correct order. The
2889 * entire structure is not reindexed, though, so any blocks added at
2890 * the beginning may have SegIDs of zero or negative values.
2891 **********************************************************************/
2892
2893 NLM_EXTERN SABlockPtr AddEmptyBlocks(SABlockPtr sabp, Int4 n, Boolean beginning, Boolean end)
2894 {
2895 Int4 count;
2896 Int4 i;
2897 Int4 j;
2898 SABlockPtr sabp_head;
2899 SABlockPtr sabp_new;
2900 SABlockPtr sabp_newhead;
2901 SABlockPtr sabp_tmp;
2902 SegmentPtr segp;
2903 SegmentPtr segp_head;
2904 SegmentPtr segp_orig;
2905 SegmentPtr segp_prev;
2906 SegmentPtr segp_storage;
2907 SegmentPtr segp_tmp;
2908
2909 if (!sabp)
2910 return NULL;
2911 sabp_head = sabp;
2912 GetBlockInfo(sabp, NULL, &count, NULL, NULL);
2913 if (!count)
2914 return NULL;
2915 if (beginning)
2916 {
2917 segp = segp_head = NULL;
2918 segp_storage = NULL;
2919 sabp_tmp = sabp_newhead = NULL;
2920 for (i=1; i<=n; i++)
2921 {
2922 sabp_new = (SABlockPtr)MemNew(sizeof(SABlock));
2923 if (sabp_newhead)
2924 {
2925 sabp_tmp->prev = sabp_new;
2926 sabp_new->next = sabp_tmp;
2927 sabp_tmp = sabp_new;
2928 sabp_new->SegID = sabp_new->next->SegID - 1;
2929 } else
2930 {
2931 sabp_tmp = sabp_newhead = sabp_new;
2932 sabp_new->SegID = sabp->SegID - 1;
2933 }
2934 sabp_new->AlignID = sabp->AlignID;
2935 /* begin lyg */
2936 sabp_new->RegionID = sabp->RegionID;
2937 sabp_new->aligned = sabp->aligned;
2938 sabp_new->from = sabp_new->to = sabp->from - 1;
2939 /* end lyg */
2940 segp_tmp = segp_storage;
2941 segp_orig = sabp->segp_head;
2942 segp_head = NULL;
2943 for (j=1; j<=count; j++)
2944 {
2945 segp = (SegmentPtr)MemNew(sizeof(Segment));
2946 if (segp_head)
2947 {
2948 segp_prev->next = segp;
2949 segp->prev = segp_prev;
2950 segp_prev = segp;
2951 } else
2952 {
2953 segp_prev = segp_head = segp;
2954 }
2955 if (i > 1)
2956 {
2957 segp->BspID = segp_tmp->BspID;
2958 /* begin lyg */
2959 segp->gap = 1; /* make single gaps */
2960 segp->from = segp->to = segp_tmp->from;
2961 segp->strand = segp_tmp->strand;
2962 segp->move = 0;
2963 segp->link = 0;
2964 /* end lyg */
2965 segp->sip = segp_tmp->sip;
2966 segp->bsp_next = segp_tmp;
2967 segp_tmp->bsp_prev = segp;
2968 segp_tmp = segp_tmp->next;
2969 } else
2970 {
2971 if (segp_storage)
2972 {
2973 segp_tmp->next = segp;
2974 segp_tmp = segp_tmp->next;
2975 } else
2976 {
2977 segp_storage = segp_tmp = segp;
2978 }
2979 segp->BspID = segp_orig->BspID;
2980 /* begin lyg */
2981 segp->gap = 1; /* make single gaps */
2982 segp->from = segp->to = segp_orig->from;
2983 segp->strand = segp_orig->strand;
2984 segp->move = 0;
2985 segp->link = 0;
2986 /* end lyg */
2987 segp->sip = segp_orig->sip;
2988 segp->bsp_next = segp_orig;
2989 segp_orig->bsp_prev = segp;
2990 segp_orig = segp_orig->next;
2991 }
2992 }
2993 segp_storage = segp_head;
2994 sabp_tmp->segp_head = segp_head;
2995 }
2996 sabp_newhead->next = sabp_head;
2997 sabp_head->prev = sabp_newhead;
2998 while (sabp_newhead)
2999 {
3000 sabp_head = sabp_newhead;
3001 sabp_newhead = sabp_newhead->prev;
3002 }
3003 }
3004 if (end)
3005 {
3006 segp = segp_head = NULL;
3007 segp_storage = NULL;
3008 sabp_tmp = sabp_newhead = NULL;
3009 while (sabp->next)
3010 {
3011 sabp = sabp->next;
3012 }
3013 for (i=1; i<=n; i++)
3014 {
3015 sabp_new = (SABlockPtr)MemNew(sizeof(SABlock));
3016 if (sabp_newhead)
3017 {
3018 sabp_tmp->next = sabp_new;
3019 sabp_new->prev = sabp_tmp;
3020 sabp_tmp = sabp_new;
3021 sabp_new->SegID = sabp_new->prev->SegID + 1;
3022 } else
3023 {
3024 sabp_tmp = sabp_newhead = sabp_new;
3025 sabp_new->SegID = sabp->SegID + 1;
3026 }
3027 sabp_new->AlignID = sabp->AlignID;
3028 /* begin lyg */
3029 sabp_new->RegionID = sabp->RegionID;
3030 sabp_new->aligned = sabp->aligned;
3031 sabp_new->from = sabp_new->to = sabp->to + 1;
3032 /* end lyg */
3033 segp_tmp = segp_storage;
3034 segp_orig = sabp->segp_head;
3035 segp_head = NULL;
3036 for (j=1; j<=count; j++)
3037 {
3038 segp = (SegmentPtr)MemNew(sizeof(Segment));
3039 if (segp_head)
3040 {
3041 segp_prev->next = segp;
3042 segp->prev = segp_prev;
3043 segp_prev = segp;
3044 } else
3045 {
3046 segp_prev = segp_head = segp;
3047 }
3048 if (i > 1)
3049 {
3050 segp->BspID = segp_tmp->BspID;
3051 /* begin lyg */
3052 segp->gap = 1; /* make single gaps */
3053 segp->from = segp->to = segp_tmp->to;
3054 segp->strand = segp_tmp->strand;
3055 segp->move = 0;
3056 segp->link = 0;
3057 /* end lyg */
3058 segp->sip = segp_tmp->sip;
3059 segp->bsp_prev = segp_tmp;
3060 segp_tmp->bsp_next = segp;
3061 segp_tmp = segp_tmp->next;
3062 } else
3063 {
3064 if (segp_storage)
3065 {
3066 segp_tmp->next = segp;
3067 segp_tmp = segp_tmp->next;
3068 } else
3069 {
3070 segp_storage = segp_tmp = segp;
3071 }
3072 segp->BspID = segp_orig->BspID;
3073 /* begin lyg */
3074 segp->gap = 1; /* make single gaps */
3075 segp->from = segp->to = segp_orig->to;
3076 segp->strand = segp_orig->strand;
3077 segp->move = 0;
3078 segp->link = 0;
3079 /* end lyg */
3080 segp->sip = segp_tmp->sip;
3081 segp->bsp_prev = segp_orig;
3082 segp_orig->bsp_next = segp;
3083 segp_orig = segp_orig->next;
3084 }
3085 }
3086 segp_storage = segp_head;
3087 sabp_tmp->segp_head = segp_head;
3088 }
3089 sabp->next = sabp_newhead;
3090 sabp_newhead->prev = sabp;
3091 }
3092 return sabp_head;
3093 }
3094
3095 /****************************************************************
3096 * AddEmptySegments adds an empty segment structure onto
3097 * the end of the segment list for each SABlock. The newly
3098 * added segment is uninitialized, except that the gap value is
3099 * set to 2.
3100 ****************************************************************/
3101
3102 NLM_EXTERN SABlockPtr AddEmptySegments(SABlockPtr sabp)
3103 {
3104 SABlockPtr sabp_head;
3105 SegmentPtr segp;
3106 SegmentPtr segp_temp;
3107
3108 if (!sabp)
3109 return NULL;
3110 sabp_head = sabp;
3111 while (sabp)
3112 {
3113 segp = sabp->segp_head;
3114 while (segp->next)
3115 {
3116 segp = segp->next;
3117 }
3118 segp_temp = (SegmentPtr)MemNew(sizeof(Segment));
3119 segp_temp->prev = segp;
3120 segp->next = segp_temp;
3121 segp_temp->gap = 2;
3122 sabp = sabp->next;
3123 }
3124 return sabp_head;
3125 }
3126
3127 /**********************************************************
3128 * FillInUnaligned is a helper function for Blockify for
3129 * Dense-diags. If there are any blocks missing from
3130 * the master sequence (the first sequence, also the
3131 * alignment coordinates), the function allocates those
3132 * blocks and their segments, and fills in the information
3133 * for the first segment, leaving the others blank except
3134 * for filling in gap = 2 in each. The function does not
3135 * add blocks to the beginning or end of the alignment,
3136 * so the alignment may not start at position 0 of the
3137 * master and it may not end at the end of the master.
3138 * Use other functions to fill in the "complete"
3139 * alignment. This function also switches the alignment
3140 * coordinates to zero-based values.
3141 **********************************************************/
3142
3143 NLM_EXTERN SABlockPtr FillInUnaligned(SABlockPtr sabp)
3144 {
3145 Int4 c;
3146 Int4 i;
3147 SABlockPtr sabp_head;
3148 SABlockPtr sabp_new;
3149 SABlockPtr sabp_prev;
3150 SegmentPtr segp;
3151 SegmentPtr segp_head;
3152 SegmentPtr segp_prev;
3153 SeqIdPtr sip;
3154
3155 if (!sabp)
3156 return NULL;
3157 sabp_head = sabp_prev = sabp;
3158 segp = sabp->segp_head;
3159 sip = segp->sip;
3160 i = 0;
3161 while (segp)
3162 {
3163 i += 1;
3164 segp = segp->next;
3165 }
3166 sabp->from -= 1;
3167 sabp->to -= 1;
3168 sabp = sabp->next;
3169 while (sabp)
3170 {
3171 sabp->from -= 1;
3172 sabp->to -= 1;
3173 if (sabp->from > sabp_prev->to + 1)
3174 {
3175 sabp_new = (SABlockPtr)MemNew(sizeof(SABlock));
3176 sabp_new->prev = sabp_prev;
3177 sabp_new->next = sabp;
3178 sabp->prev = sabp_new;
3179 sabp_prev->next = sabp_new;
3180 sabp_new->from = sabp_prev->to + 1;
3181 sabp_new->to = sabp->from - 1;
3182 sabp_new->aligned = FALSE;
3183 sabp_new->visible = 1;
3184 segp_head = NULL;
3185 for (c = 0; c < i; c++)
3186 {
3187 segp = (SegmentPtr)MemNew(sizeof(Segment));
3188 segp->visible = 1;
3189 if (segp_head)
3190 {
3191 segp->prev = segp_prev;
3192 segp_prev->next = segp;
3193 segp_prev = segp;
3194 segp->from = segp->to = 0;
3195 segp->gap = 2;
3196 } else
3197 {
3198 segp_head = segp_prev = segp;
3199 segp->from = sabp_new->from+1;
3200 segp->to = sabp_new->to+1;
3201 segp->sip = sip;
3202 }
3203 }
3204 sabp_new->segp_head = segp_head;
3205 }
3206 sabp_prev = sabp;
3207 sabp = sabp->next;
3208 }
3209 return sabp_head;
3210 }
3211
3212 /*****************************************************************************
3213 *
3214 * For a given column, return a pointer to the block that contains the
3215 * position. Returns NULL if a containing block is not found.
3216 *
3217 *****************************************************************************/
3218
3219 NLM_EXTERN SABlock * SAReturnBlock(SABlock *sabpHead, Int4 lColumn)
3220 {
3221 SABlock *sabp;
3222
3223 if(sabpHead == NULL) {
3224 ErrPostEx(SEV_ERROR, 0, 0, "Invalid call on SAReturnBlock");
3225 return NULL;
3226 }
3227
3228 for(sabp = sabpHead; sabp != NULL; sabp = sabp->next)
3229 if(lColumn >= sabp->from && lColumn <= sabp->to) break;
3230 return sabp;
3231 }
3232
3233 /*****************************************************************************
3234 *
3235 * For a given position, return a pointer to the Segment that contains the
3236 * position. Returns NULL if a containing Segment is not found. Note that
3237 * the lRow argument is position, not BspID.
3238 *
3239 *****************************************************************************/
3240
3241 NLM_EXTERN Segment * SAReturnSegment(SABlock *sabpHead, Int4 lColumn, Int4 lRow)
3242 {
3243 SABlock *sabp;
3244 Int4 i;
3245 Segment *segp;
3246
3247 if(sabpHead == NULL) {
3248 ErrPostEx(SEV_ERROR, 0, 0, "Invalid call on SAReturnSegment");
3249 return NULL;
3250 }
3251
3252 sabp = SAReturnBlock(sabpHead, lColumn);
3253 if(sabp == NULL) return NULL;
3254
3255 for(i = 0, segp = sabp->segp_head; segp != NULL && i < lRow;
3256 i++, segp = segp->next) continue;
3257
3258 return segp;
3259 }
3260
3261 /*****************************************************************************
3262 *
3263 * Generic Segment traversal function with callback
3264 *
3265 *****************************************************************************/
3266
3267 NLM_EXTERN Int4 SATraverse(SABlock *sabpHead, pfnSAFunction pFunction, void *pData)
3268 {
3269 Segment *segp;
3270 SABlock *sabp;
3271
3272 if(sabpHead == NULL) {
3273 ErrPostEx(SEV_ERROR, 0, 0, "Invalid call on SATraverse");
3274 return 0;
3275 }
3276
3277 for(sabp = sabpHead; sabp != NULL; sabp = sabp->next)
3278 for(segp = sabp->segp_head; segp != NULL; segp = segp->next)
3279 (*pFunction)(segp, pData);
3280
3281 return 1;
3282 }
3283
3284 /*****************************************************************************
3285 *
3286 * Traverser to clear the move bit
3287 *
3288 *****************************************************************************/
3289
3290 NLM_EXTERN void SAClearMove(Segment *pSegment, void *pData)
3291 {
3292 if(pSegment == NULL) return;
3293 pSegment->move = FALSE;
3294 }
3295
3296
3297 /*****************************************************************************
3298 *
3299 * Generic SABlock traversal function with callback
3300 *
3301 *****************************************************************************/
3302
3303 NLM_EXTERN Int4 SATraverseBlock(SABlock *sabpHead, pfnSABlockFunction pFunction,
3304 void * pData)
3305 {
3306 SABlock *sabp;
3307
3308 if(sabpHead == NULL) {
3309 ErrPostEx(SEV_ERROR, 0, 0, "Invalid call on SABlockTraverse");
3310 return 0;
3311 }
3312
3313 for(sabp = sabpHead; sabp != NULL; sabp = sabp->next)
3314 (*pFunction)(sabp, pData);
3315
3316 return 1;
3317 }
3318
3319 /*****************************************************************************
3320 *
3321 * Traverser to find the highest valued RegionID
3322 *
3323 *****************************************************************************/
3324
3325 NLM_EXTERN void SARegionBounds(SABlock *sabp, void *pData)
3326 {
3327 if(sabp == NULL) return;
3328 if(sabp->RegionID > *(Int4 *)pData) *(Int4 *)pData = sabp->RegionID;
3329 }
3330 |
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more information. |