/* Program based on CGR  to compare forward strands of two sequences. Here the 'i'th position of 
   SequenceA  is compared with the 'j'th position of SequenceB.  Then the no. of similar nucleotides
   previous to the (i,j)'th positions are found out including i and j.
   The program uses anchored-alignment method. Using FCGR, similar n-mers of both sequences are found
   out first and then the algorithm runs on similar parts only.  This saves us a big computational cost.
   No mismatch is allowed.
   */

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
 
#define N 256            //N= 2^n, as which 'n-mer' is desired as anchor
#define M 300            //No. of repeats allowed for a pattern. If repeats>M then whole of SequenceB
			 // is compared for that particular pattern 
#define mnm 10           //The threshold(minimum) length for a segment


//***Global Variables***
long double cgrA[2][200000]={'\0'},cgrB[2][200000]={'\0'};   //Array size should be greater than
							     //sequence length
int ctrB[N][N][M]={'\0'};   //FCGR and positions of patterns (for SequenceB only)    

//***Main function***
int main()           
{
 char s1[300],s;
 FILE *fr,*fw,*fw1;
 long double x,y,d,max(long double,long double),width;
 long length[3]={'\0'},l,i,j=0,Kmx[M][3]={'\0'},approx(long,long),k=0;
 int i1,j1,k1,i2,i_temp=0,j_temp=0,rep1,rep2,got_in=0,c,kctr[N][N]={'\0'},ctr,temp,line=0;
 time_t t1,t2;
 float K,Ki_max=0;

 fr=fopen("sequences.txt","r");
//The input sequences should be in fasta format and both should be pasted one after the other in the 
//input file "sequences.txt".  A '>' should be added after the last line in the second sequence
 fw=fopen("result.txt","w");              //Text file for graph of the alignments
 fw1=fopen("to_chain.txt","w");           //Text file for chain.c's input

 time(&t1);
 width=(double)1000.0/N;                          //width of a single CGR square.

 //Reading the sequence and converting to position-FCGR...
 while(fgets(s1,299,fr)!=NULL)
 {
 for(i=0;i<strlen(s1);i++)          //Reading line by line, s1 is one line
  {
  if(s1[i]=='>')                    //For recognising next sequence
     {
     length[k]=j;
     printf("\nReading seq %d\n",k);
     k++;
     x=500.0;
     y=500.0;
     }
  if(s1[i]=='A'||s1[i]=='a'||s1[i]=='T'||s1[i]=='t'||s1[i]=='G'||s1[i]=='g'||s1[i]=='C'||s1[i]=='c')
     {
      s=s1[i];
      j++;

      if(s=='C'||s=='c')
       {
       x=x/2;
       y=(y+1000.0)/2;
       }
      if(s=='G'||s=='g')
       {
       x=(x+1000.0)/2;
       y=(y+1000.0)/2;
       }
     if(s=='T'||s=='t')
       {
       x=(x+1000.0)/2;
       y=y/2.0;
       }
     if(s=='A'||s=='a')
       {
       x=x/2.0;
       y=y/2.0;
       }              
     if(k==1)             //if SequenceA
       {
       cgrA[0][j-1]=x;                                   //x co-ordinate
       cgrA[1][j-1]=y; 					 //y co-ordinate
       } 
     if(k==2)             //if SequenceB 
       {
       cgrB[0][j-1-length[k-1]]=x;
       cgrB[1][j-1-length[k-1]]=y;
       
       //Position CGR...  (for SequenceB only)
       if((float)x/width-(int)x/width!=0 || (float)y/width-(int)y/width!=0)
             {
             i1=(int)x/width;
             j1=N-1-(int)y/width;

                     if(kctr[i1][j1]<M-1)
                       {
                       ctrB[i1][j1][kctr[i1][j1]]=j-1-length[k-1];
                       kctr[i1][j1]++;
                       }
                      else if(kctr[i1][j1]==M-1)
                       {
                       printf("Repeat is greater. i1 =%d\tj1=%d\n",i1,j1);  
                       ctrB[i1][j1][kctr[i1][j1]]=-1;
 		       }
             }  
       }                    //if(k==2) over!!
           
     }
   }
 }                          //while loop (reading the sequences) over!!
 l=j;                       //Combined length
 fprintf(fw1,"%ld\t%ld\t0\n",length[1],length[2]-length[1]);  //'0' stands for fowd. strand comparison


//*******************************
//****Computing CGR distance*****
//*******************************
 for(i=length[1]-1;i>0;i--)       //reading from right to left in SequenceA...
   {
   Ki_max=0;
   ctr=0;

   //Finding the CGR square of the current point...
   if((float)cgrA[0][i]/width-(int)cgrA[0][i]/width!=0 || (float)cgrA[1][i]/width-(int)cgrA[1][i]/width!=0)
             {
             i_temp=(int)cgrA[0][i]/width;
             j_temp=N-1-(int)cgrA[1][i]/width;
             }

   for(i1=0;i1<M-1;i1++)
     {
     if(ctrB[i_temp][j_temp][i1]==0)     //If there is no point in the corresponding square in SequenceB      
       break;
     
     j=ctrB[i_temp][j_temp][i1];         //Position of the pattern in SequenceB
    
     check_it1a:
     K=0;
     k=approx(i,j);                       //Find maximum possible length of the alignment
     if(k<mnm)                            
        continue;  			  //If length is less than threshold, then ignore

     //Checking whether closeness in CGR implies sequence similarity to that extent..and finding real K..
     rep2=0;
     check_it1:
     if(i-k+rep2<0||j-k+rep2<0)
        {
        rep2++;
        goto check_it1; 
        }
     if(pow(0.5,k-rep2)*max(cgrA[0][i-k+rep2]-cgrB[0][j-k+rep2],cgrA[1][i-k+rep2]-cgrB[1][j-k+rep2])-(1e-10)<=max(cgrA[0][i]-cgrB[0][j],cgrA[1][i]-cgrB[1][j]) && max(cgrA[0][i]-cgrB[0][j],cgrA[1][i]-cgrB[1][j])<=pow(0.5,k-rep2)*max(cgrA[0][i-k+rep2]-cgrB[0][j-k+rep2],cgrA[1][i-k+rep2]-cgrB[1][j-k+rep2])+(1e-10))
        {
        rep1=k-rep2;
        }  
     else if(rep2<k)
        {
        rep2++;
        goto check_it1;
        }
       
     K=k-rep2;
        
     if(K>mnm)
         {
          printf("%d\t\t%d-%d\t\t%d-%d\n",(long int)K,i-(long int)K,i,j-(long int)K,j);
          fprintf(fw,"%d\t%d\n%d\t%d\n\n",i-(long int)K,j-(long int)K,i,j); 
          Kmx[ctr][0]=K;              
          Kmx[ctr][1]=i;                   //Storing values for finding largest K
	  Kmx[ctr][2]=j;
          ctr++;
          if(K>Ki_max)
             Ki_max=K;     
          }

     if(got_in==1)
          goto check_it3;
     }                                      //Checking position-FCGR of SequenceB, over !!


    //If 'repeats' are present more than the allowed(i.e. M)....
    if(ctrB[i_temp][j_temp][M-1]==-1)
      {
      for(j=ctrB[i_temp][j_temp][M-2];j<length[2]-length[1];j++) //Considering each j > 'the latest 
                                                                 //position-FCGR
          {
          if(max(cgrA[0][i]-cgrB[0][j],cgrA[1][i]-cgrB[1][j])<pow(.5,mnm)*1000)
              { 
              check_it4:
              k=approx(i,j);
              if(k<mnm)
                continue;
            
	      //Checking whether closeness in CGR implies sequence similarity to that extent..
              K=0;
              rep2=0;
              got_in=1;
              goto check_it1;
              check_it3:
              got_in=0;
              }
          }       

      }        //'if more repeats are there, over !! 

    //Printing the segments with largest length
    for(temp=0;temp<ctr;temp++)
      {
       if(Kmx[temp][0]==Ki_max)
          {
          fprintf(fw1,"%d\t%d\t%d\t%d\t%d\n",(long int)Kmx[temp][0],Kmx[temp][1]-(long int)Kmx[temp][0],Kmx[temp][1],Kmx[temp][2]-(long int)Kmx[temp][0],Kmx[temp][2]);
  	  line++;
 	  }
      }
    i=i-Ki_max;
   }            //SequenceA over !!


 time(&t2);

 printf("Combined length = %ld\n",l);
 printf("No. of lines in 'to_chain.txt' is %d\n",line);
 printf("SeqA-length = %ld\tSeqB-length = %ld\n",length[1],length[2]-length[1]);
 printf("Computation time = %d s\n",(int)t2-t1);

 
 fclose(fr);
 fclose(fw);
 fclose(fw1);
} 



//************************
//    'max' function           (Finding bigger(absolute value) of two numbers)
//************************
long double max(long double a,long double b)
   {
   long double big;  
   if(fabs(a)>=fabs(b))
       big=fabs(a);
   else
       big=fabs(b);
   return(big);
   }



//*********************************
//       'approx' function          (Computing maximum value of 'k' from dij)
//********************************
long approx(long ia, long ja)
 {
 long ka;
 long double da,max();

 if(max(cgrA[0][ia]-cgrB[0][ja],cgrA[1][ia]-cgrB[1][ja])>0)
     {
     da=(long double)log(max(cgrA[0][ia]-cgrB[0][ja],cgrA[1][ia]-cgrB[1][ja]))-log(1000);
     ka=(int)da/log(0.5);
     }
 else                  //if dij=0 then both should be same from beginning..
     {
     if(ia<=ja)
        ka=ia;
     else ka=ja;
     if(ka>60)          //max precision of long double variable
        {
         ka=60;
         while(max(cgrA[0][ia-ka]-cgrB[0][ja-ka],cgrA[1][ia-ka]-cgrB[1][ja-ka])==0 && ia-ka>60 && ja-ka>60)
            {
            ka=ka+60;
            }
         if(max(cgrA[0][ia-ka]-cgrB[0][ja-ka],cgrA[1][ia-ka]-cgrB[1][ja-ka])>0)
            {
            da=(long double)log(max(cgrA[0][ia-ka]-cgrB[0][ja-ka],cgrA[1][ia-ka]-cgrB[1][ja-ka]))-log(1000);
            ka=ka+(int)da/log(0.5);
            }
         if(max(cgrA[0][ia-ka]-cgrB[0][ja-ka],cgrA[1][ia-ka]-cgrB[1][ja-ka])==0 && (ia-ka<=60||ja-ka<=60))
            {
             ka=ia;
             if(ia>ja)
                ka=ja;
             }
          }
       }

     return(ka);
 }