X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=binaries%2Fsrc%2Ftcoffee%2Ft_coffee_source%2Futil_graph_maln.c;fp=binaries%2Fsrc%2Ftcoffee%2Ft_coffee_source%2Futil_graph_maln.c;h=03ef023d593401069e0242a8ae5e6988c25c811e;hb=d8e1d04583007816f5dc77595d322ba669075ae3;hp=0000000000000000000000000000000000000000;hpb=8140043fefd2101326b3e651e3b7e2d4ac806b99;p=jabaws.git diff --git a/binaries/src/tcoffee/t_coffee_source/util_graph_maln.c b/binaries/src/tcoffee/t_coffee_source/util_graph_maln.c new file mode 100644 index 0000000..03ef023 --- /dev/null +++ b/binaries/src/tcoffee/t_coffee_source/util_graph_maln.c @@ -0,0 +1,539 @@ +#include +#include +#include +#include +#include + +#include "io_lib_header.h" +#include "util_lib_header.h" +#include "define_header.h" +#include "dp_lib_header.h" +int check_link (CL_node ***G, int S1, int r1, int s2, int r2); +void light_nodes (CL_node *A, int va, CL_node*B, int vb, CL_node*C,int vc, char *s); +void print_graph (CL_node *G, Sequence *S); +Sequence *Seq; +CL_node *Start; +static int cycle; + + + +Alignment * add_constraint2aln ( Alignment *A, int s1, int r1, int s2, int r2) +{ + /*Note sCL_node ***G;1 and r1 must be numbered from 0 to n-1*/ + CL_node ***G; + + + G=aln2graph(A); + G=add_constraint2graph_aln (G,s1,r1, s2, r2); + A=graph2aln (A,G[0][0],aln2seq(A)); + vfree_graph (G[0][0]); + return A; +} +Alignment * graph_aln (Alignment *A, Constraint_list *iCL, Sequence *S) +{ + CL_node ***G; + int a,start; + CLIST_TYPE *entry=NULL; + Constraint_list *CL; + Seq=S; + HERE ("Function graph_aln is deprecated"); + return A; + +} + +void print_graph (CL_node *G, Sequence *S) +{ + Alignment *A=NULL; + + if (S==NULL) S=Seq; + A=seq2aln (Seq, A, 1); + A=graph2aln (A,G, Seq); + print_aln (A); +} + +Alignment* graph2aln (Alignment *A, CL_node *G, Sequence *S) +{ + int s, l, a; + CL_node *Gi; + + /*Rewind G*/ + while ( G->p)G=G->p; + while ( G->l)G=G->l; + + l=s=0; + Gi=G; + while (Gi){Gi=Gi->r;l++;} + Gi=G; + while (Gi){Gi=Gi->c;s++;} + + A=realloc_alignment (A, l+1); + + + l=0; + while (G) + { + Gi=G; + s=0; + while ( G!=NULL) + { + + if ( G->res==-1)A->seq_al[s][l]='-'; + else if ( G->res==-2)A->seq_al[s][l]='*'; + else if ( G->res==-3)A->seq_al[s][l]='#'; + else if (G->res>=0)A->seq_al[s][l]=S->seq[G->seq][G->res]; + + G=G->c; + s++; + } + G=Gi->r; + l++; + } + + + + for ( a=0;aseq_al[a][l]='\0'; + A->len_aln=strlen (A->seq_al[0]); + A->nseq=s; + + + return A; +} +CL_node ***aln2graph (Alignment *A) +{ + int a=0, b; + static CL_node ***galn; + CL_node *N, *iN, *pN; + int res; + + if ( !galn) + { + galn=calloc ( A->nseq, sizeof (CL_node**)); + for ( a=0; a< A->nseq; a++) + { + galn[a]=calloc (A->len_aln, sizeof (CL_node*)); + } + } + pN=iN=NULL; + N=declare_cl_nodes(-1, a); + + + for ( a=0; anseq; a++) + { + iN=N; + for (res=A->order[a][1], b=0; blen_aln; b++) + { + if (blen_aln-1) + { + N->r=declare_cl_nodes(-1, a); + (N->r)->l=N; + } + if ( pN) + { + N->p=pN; + pN->c=N; + } + + N->seq=A->order[a][0]; + N->res=(is_gap(A->seq_al[a][b]))?-1:res++; + + if (N->res!=-1)galn[a][res-1]=N; + if ( pN) + { + N->p=pN; + pN->c=N; + pN=pN->r; + } + N=N->r; + } + if ( anseq-1)iN->c=declare_cl_nodes(-1, a); + pN=iN; + N=iN->c; + } + + return galn; +} +CL_node ***add_constraint2graph_aln (CL_node ***G, int s1, int r1, int s2, int r2) +{ + CL_node *S, *E, *B; + int d; + + + S=G[s1][r1]; + E=G[s2][r2]; + + + d=get_node_distance (S,E); + if (d<0){B=S;S=E;E=B;} + d=(d<0)?-d:d; + + + insert_gap_columns (E,d); + shift_segment( S,d+1,d); + + return G; + +} + + +CL_node *shift_segment ( CL_node *S, int segL, int shiftL) +{ + int a; + CL_node *E, *G; + + + if ( !shiftL)return S; + + /*find segment coordinates*/ + for (E=S, a=1; a< segL; a++)E=E->r; + + /*Shift the gaps*/ + + G=swap_gap_in_graph (S, E); + for (a=1; a< shiftL; a++)swap_gap_in_graph (S, E); + + while (G!=E)G=remove_graph_gap_column (G); + remove_graph_gap_column (E); + + return G; +} + +int is_graph_gap_column(CL_node *S) +{ + while (S->p)S=S->p; + + while (S) + { + if (S->res>=0)return 0; + S=S->c; + } + return 1; +} +CL_node * remove_graph_gap_column (CL_node *S) +{ + CL_node *R,*L, *P, *RV; + + RV=S->r; + while (S->p) + { + + S=S->p; + } + + if ( !is_graph_gap_column (S))return RV; + + + + while (S) + { + + R=S->r; + L=S->l; + P=S->p; + + if (L)L->r=S->r; + if (R)R->l=S->l; + + P=S; + S=S->c; + vfree_cl_node (P); + } + return RV; +} + +CL_node * swap_gap_in_graph ( CL_node*S, CL_node *E) +{ + /*Moves gap AFTER End to BEFORE Start + SxxxE- + -xxxxx + straightens the links in between + */ + CL_node *G, *N, *iE, *iS, *SP, *SC, *SL; + + + /*Preserve the E/S values*/ + iE=E; + iS=S; + + + /*prepare the parent/child links first*/ + + SP=S->p; + SC=S->c; + SL=S->l; + + while ( S!=E->r) + { + N=S->r; + + S->p=N->p; + if (N->p)(S->p)->c=S; + + S->c=N->c; + if (N->c)(S->c)->p=S; + + S=S->r; + } + + E=iE; + S=iS; + + /*Remove the gap*/ + G=E->r; + if ( G->res>=0)fprintf ( stderr, "\nERROR: NOT a GAP"); + + E->r=G->r; + if (E->r)(E->r)->l=E; + + /*insert the gap*/ + + G->r=S; + S->l=G; + + G->l=SL; + if (SL)SL->r=G; + + + G->p=SP; + if (SP)SP->c=G; + + G->c=SC; + if (SC)SC->p=G; + + return G; + +} + +CL_node * declare_cl_nodes ( int len, int seq) +{ + static CL_node **N; + CL_node *IN; + static int Nlen; + int a; + + if (len==-1) + { + IN=calloc ( 1, sizeof (CL_node)); + IN->res=-1; + return IN; + } + + + + if ( len>Nlen) + { + free (N); + N=calloc (len, sizeof (CL_node*)); + } + + if ( len==0)return NULL; + + for (a=0; ares=-1; + (N[a])->seq=seq; + if (a!=0)(N[a])->l=N[a-1]; + if (a!=len-1)(N[a])->r=N[a+1]; + } + + (N[0])->l=N[len-1]; + (N[len-1])->r=N[0]; + + return N[0]; +} + +CL_node *insert_gap_columns (CL_node *S, int d) +{ + CL_node *Gs,*Ge, *pGs, *Gi, *Si; + int a; + + if ( d==0)return S; + + pGs=Gi=NULL; + Si=S; + while (S->p!=NULL)S=S->p; + + while (S!=NULL) + { + Gs=declare_cl_nodes(d, S->seq); + Ge=Gs->l; + + Ge->r=S->r; + if (Ge->r)(Ge->r)->l=Ge; + + Gs->l=S; + S->r=Gs; + + if (pGs) + { + Gi=Gs; + for (a=0; a< d; a++) + { + Gs->p=pGs; + pGs->c=Gs; + Gs=Gs->r; + pGs=pGs->r; + } + pGs=Gi; + } + else + { + pGs=Gs; + } + S=S->c; + } + return Si; +} + +int get_node_distance ( CL_node *S, CL_node *E) +{ + int distance=0; + CL_node *iS,*B; + int swap=1; + + /*project the two points onto one sequence*/ + if (S->seq>E->seq){B=S;S=E;E=B;swap*=-1;} + while (S->seq!=E->seq)S=S->c; + + /*Walk from E to S */ + iS=S; + while ( iS->res<0 && iS->r!=NULL){iS=iS->r;} + if (iS->res<0 || iS->res>E->res){B=S; S=E; E=B;swap*=-1;} + + while ( S!=E) + { + S=S->r; + distance+=swap; + } + return distance; +} + + + + + + + + + +int check_graph ( CL_node *S, char *string) +{ + CL_node *iS; + static int n; + int lr; + + if ( S==NULL)S=Start; + fprintf ( stderr, "\n\tGRAPH Check %s #%d\n",string, ++n); + while ( S->p!=NULL)S=S->p; + while ( S->l!=NULL)S=S->l; + while ( S) + { + iS=S; + lr=-1; + while (iS) + { + if (iS->l && (iS->l)->seq!=iS->seq){fprintf ( stderr, "\n\t\tSEq pb");myexit(EXIT_FAILURE);} + if (iS->free==1){fprintf ( stderr, "\n\t\tFree Node read");myexit(EXIT_FAILURE);} + if (iS->res>0) + { + if (lr!=-1 && iS->res-lr!=1){fprintf ( stderr, "\n\t\tERROR: lost residues");myexit (EXIT_FAILURE);} + lr=iS->res; + } + if ( iS->r && (iS->r)->l!=iS){fprintf ( stderr, "\n\t\tERROR: left != right: [%d %d][%d %d]", iS->seq, iS->res, (iS->l)->seq, (iS->r)->res);myexit (EXIT_FAILURE);} + if ( iS->p && (iS->p)->c!=iS){fprintf ( stderr, "\n\t\tERROR: parent != child: [%d %d][%d %d]", iS->seq, iS->res, (iS->p)->seq, (iS->p)->res);myexit (EXIT_FAILURE);} + if ( iS->c && (iS->c)->p!=iS){fprintf ( stderr, "\n\t\tERROR: parent != child: [%d %d][%d %d]", iS->seq, iS->res, (iS->c)->seq, (iS->c)->res);myexit (EXIT_FAILURE);} + iS=iS->r; + } + S=S->c; + } + return 1; +} + +CL_node * vfree_graph ( CL_node *S) +{ + CL_node *Si; + + while ( S->p!=NULL)S=S->p; + while ( S->l!=NULL)S=S->l; + + while ( S) + { + Si=S->c; + while ( S) + { + + S=S->r; + if (S)vfree_cl_node (S->l); + } + S=Si; + } + return S; + +} +CL_node *vfree_cl_node ( CL_node *N) +{ + if ( N->free==1)crash("freeing free block"); + N->free=1; + free (N); + return N; +} + + +void light_nodes (CL_node *A, int va, CL_node*B, int vb, CL_node*C,int vc, char *string ) +{ + int ta=0, tb=0, tc=0; + + fprintf ( stderr, "\nCycle %d\n LIGHT NODE: %s", cycle,string); + if ( A){ta=A->res; A->res=va;fprintf ( stderr, "\nA: seq %d res %d", A->seq, A->res);} + if ( B){tb=B->res; B->res=vb;fprintf ( stderr, "\nB: seq %d res %d", B->seq, B->res);} + if ( C){tc=C->res; C->res=vc;fprintf ( stderr, "\nC: seq %d res %d", C->seq, C->res);} + print_graph (A, 0); + if ( A){A->res=ta;} + if ( B){B->res=tb;} + if ( C){C->res=tc;} +} +int check_link (CL_node ***G, int s1, int r1, int s2, int r2) +{ + CL_node *S; + CL_node *E; + + S=G[s1][r1]; + E=G[s2][r2]; + while ( S->p)S=S->p; + while ( S) + { + S=S->c; + if ( S==E)return 1; + } + return 0; +} +/******************************COPYRIGHT NOTICE*******************************/ +/*© Centro de Regulacio Genomica */ +/*and */ +/*Cedric Notredame */ +/*Fri Feb 18 08:27:45 CET 2011 - Revision 596. */ +/*All rights reserved.*/ +/*This file is part of T-COFFEE.*/ +/**/ +/* T-COFFEE is free software; you can redistribute it and/or modify*/ +/* it under the terms of the GNU General Public License as published by*/ +/* the Free Software Foundation; either version 2 of the License, or*/ +/* (at your option) any later version.*/ +/**/ +/* T-COFFEE is distributed in the hope that it will be useful,*/ +/* but WITHOUT ANY WARRANTY; without even the implied warranty of*/ +/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the*/ +/* GNU General Public License for more details.*/ +/**/ +/* You should have received a copy of the GNU General Public License*/ +/* along with Foobar; if not, write to the Free Software*/ +/* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA*/ +/*............................................... |*/ +/* If you need some more information*/ +/* cedric.notredame@europe.com*/ +/*............................................... |*/ +/**/ +/**/ +/* */ +/******************************COPYRIGHT NOTICE*******************************/