A self contained C++ (or c) sequence alignement function

[Jared Roach]

This isn't quite what was wanted, but it comes *very* close 
and should be easily hackable.  I apologize for its slovenly 
adherence to basic programming elegance, but hey (!) it works.
	It is C code for the Macintosh, and furthermore it is 
written as an XFCN for HyperCard; I've included the whole code, 
but the dynamic alignmetn bit is easy to pick out.  Now, this 
code does *not* save the alignment - it just saves the score 
and the endpoint on each sequence.  If you want the alignment, 
it costs RAM, but it shouldn't be too difficult to hack this 
code to get it.  I just might do it myself. 

//  DynaCLip XFCN by Jared Roach  © June 1996
//  This program does dynamic local alignment of two 
sequences and saves the endpoint of the alignment
//  The intention is to use this for endclipping vector from 
the 5' end of sequence reads
//  The core C code was hacked from code by David Gordon to 
whom I owe a great debt
//  Max Robinson was instrumental in explaining basic (yeah 
right) C syntax to me
//  The XFCN shell was downloaded form the Web and is © 1992 
Mark Hanrek


//***********************************************************
****************************
//	 Hanrek XCMD Shell 1.2
//
//   ©1992 Mark Hanrek & The Information Workshop.  All 
Rights Reserved.
//
//	 Note: 	Do all your programming between the bold black 
lines below. 
//			Put additional functions you create into the 
"Support Functions" 
//			section below that.  Put function prototypes 
into ExampleXFCN.h.
//

/************************************************************
******* Includes ********/

#include <SetUpA4.h>
#include <HyperXCmd.h>
#include <SuperCard.h>
#include "StandardFunctions.h"


/************************************************************
******* Main Entry ******/

pascal void main( XCmdPtr paramPtr )	// No need to ever 
change any of this...
{
	RememberA0();
	SetUpA4();
	InitializeReturnInfo( paramPtr );
	ExternalHandler( paramPtr );
	RestoreA4();
}	


//¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥
¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥
//
//	DynaClipXFCN HyperTalk Syntax:
//
//	put 5 into gappenalty
//  put 2 into matchscore
//  put 1 into mismatchpenalty
//  
//  
//  put cd fld "Vector" into vector
//  put cd fld "Left-Clipped-Sequence" into seq
//  put the number of chars of vector into vectorlength
//  put the number of chars of seq into seqlength
//  if max (vectorlength,seqlength)>1499 then abort script
//  
//  put DynaClipXFCN( seqlength, vectorlength, seq, vector, 
gappenalty, matchscore, mismatchpenalty ) into cd fld 
"output"
//  
//

#include "DynaClipXFCN.h"

#define MAX( arg1, arg2 ) (( (arg1) > (arg2) ) ? (arg1) : 
(arg2))


void ExternalHandler( XCmdPtr paramPtr )
{
	short 	nGap;
	short 	nMatch;
	short 	nMismatch;
	
	short	i;
	
	short 	nBestScore = 0;
  	short 	nBestDown = 0;
  	short 	nBestAcross = 0;
  	short 	nScoreDiagonallyAbove;
  	short 	nToBeScoreDiagonallyAbove;
  	short 	nScoreByDiagonal;
  	short 	nAcross;
  	short 	nDown;
  	
	char 	pSeqDown[1500];
	char 	pSeqAcross[1500];
 	short 	nSeqDownLength;
 	short 	nSeqAcrossLength;
 	short 	pnBestDown;
 	short 	pnBestAcross;
 	short 	pnBestScore;
	short 	nScore[1500];
	
	for (i=0; i < 1500; ++i)
		nScore[i] = 0;
		
		
	ParamToShort( 0, &nSeqDownLength ); 			// 
the first parameter is "nSeqDownLength"
	ParamToShort( 1, &nSeqAcrossLength ); 			// 
the second parameter is "nSeqAcrossLength"
	ParamToCString( 2, pSeqDown );			// the third 
parameter is the "pSeqDown" string
	ParamToCString( 3, pSeqAcross );			// the 
third parameter is the "pSeqAcross" string
  	ParamToShort( 4, &nGap ); 			
	ParamToShort( 5, &nMatch ); 			
	ParamToShort( 6, &nMismatch ); 			
	
  
  for( nDown = 1; nDown <= nSeqDownLength; ++nDown ) {
    nToBeScoreDiagonallyAbove = nScore[0];

    /* case of first column */
    nScore[0] = nScore[0] - nGap;

    /* now handle case of other columns */
    for( nAcross = 1; nAcross <= nSeqAcrossLength; ++nAcross 
) {
      nScoreDiagonallyAbove = nToBeScoreDiagonallyAbove;
      nToBeScoreDiagonallyAbove = nScore[nAcross];
      if ( pSeqAcross[nAcross-1] == pSeqDown[nDown-1] )
        nScoreByDiagonal = nScoreDiagonallyAbove + nMatch;
      else
        nScoreByDiagonal = nScoreDiagonallyAbove - nMismatch;

      nScore[nAcross] = MAX( 0 , MAX( nScore[nAcross] - nGap, 
MAX( nScore[nAcross - 1] - nGap, nScoreByDiagonal)));


      if (nScore[nAcross] > nBestScore ) {
        nBestScore = nScore[nAcross];
        nBestAcross = nAcross;
        nBestDown = nDown;
      }
    } 
  } 

AppendReturnInfo( kResult, "|i nBestScore \r", nBestScore );
AppendReturnInfo( kResult, "|i nBestAcross \r", nBestAcross 
);
AppendReturnInfo( kResult, "|i nBestDown \r", nBestDown );

}