inc/fuzzyFind.h File Reference

#include "dnautil.h"
#include "localmem.h"
#include "aliType.h"
#include "memgfx.h"

Include dependency graph for fuzzyFind.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	ffAli
Defines
#define	ffIntronMaxDefault   750000
Functions
void	setFfIntronMax (int value)
void	setFfExtendThroughN (boolean val)
void	ffFreeAli (struct ffAli **pAli)
int	ffOneIntronOrientation (struct ffAli *left, struct ffAli *right)
int	ffIntronOrientation (struct ffAli *ali)
int	ffScoreIntron (DNA a, DNA b, DNA y, DNA z, int orientation)
ffAli *	ffRightmost (struct ffAli *ff)
ffAli *	ffMakeRightLinks (struct ffAli *rightMost)
void	ffCountGoodEnds (struct ffAli *aliList)
int	ffAliCount (struct ffAli *d)
ffAli *	ffAliFromSym (int symCount, char *nSym, char *hSym, struct lm *lm, char *nStart, char *hStart)
int	ffScoreMatch (DNA *a, DNA *b, int size)
int	ffScoreCdna (struct ffAli *ali)
int	ffScore (struct ffAli *ali, enum ffStringency stringency)
int	ffScoreProtein (struct ffAli *ali, enum ffStringency stringency)
int	ffScoreSomething (struct ffAli *ali, enum ffStringency stringency, boolean isProt)
int	ffScoreSomeAlis (struct ffAli *ali, int count, enum ffStringency stringency)
int	ffCalcGapPenalty (int hGap, int nGap, enum ffStringency stringency)
int	ffCalcCdnaGapPenalty (int hGap, int nGap)
int	ffGapPenalty (struct ffAli *ali, struct ffAli *right, enum ffStringency stringency)
int	ffCdnaGapPenalty (struct ffAli *ali, struct ffAli *right)
boolean	ffSlideIntrons (struct ffAli *ali)
boolean	ffSlideOrientedIntrons (struct ffAli *ali, int orient)
ffAli *	ffRemoveEmptyAlis (struct ffAli *ali, boolean doFree)
ffAli *	ffMergeHayOverlaps (struct ffAli *ali)
ffAli *	ffMergeNeedleAlis (struct ffAli *ali, boolean doFree)
void	ffExpandExactRight (struct ffAli *ali, DNA *needleEnd, DNA *hayEnd)
void	ffExpandExactLeft (struct ffAli *ali, DNA *needleStart, DNA *hayStart)
ffAli *	ffMergeClose (struct ffAli *aliList, DNA *needleStart, DNA *hayStart)
void	ffAliSort (struct ffAli **pList, int(*compare)(const void *elem1, const void *elem2))
void	ffCat (struct ffAli **pA, struct ffAli **pB)
int	ffCmpHitsHayFirst (const void *va, const void *vb)
int	ffCmpHitsNeedleFirst (const void *va, const void *vb)
ffAli *	ffFind (DNA *needleStart, DNA *needleEnd, DNA *hayStart, DNA *hayEnd, enum ffStringency stringency)
boolean	ffFindEitherStrand (DNA *needle, DNA *haystack, enum ffStringency stringency, struct ffAli **pAli, boolean *pRcNeedle)
boolean	ffFindEitherStrandN (DNA *needle, int needleSize, DNA *haystack, int haySize, enum ffStringency stringency, struct ffAli **pAli, boolean *pRcNeedle)
boolean	ffFindAndScore (DNA *needle, int needleSize, DNA *haystack, int haySize, enum ffStringency stringency, struct ffAli **pAli, boolean *pRcNeedle, int *pScore)
int	ffShAliPart (FILE *f, struct ffAli *aliList, char *needleName, DNA *needle, int needleSize, int needleNumOffset, char *haystackName, DNA *haystack, int haySize, int hayNumOffset, int blockMaxGap, boolean rcNeedle, boolean rcHaystack, boolean showJumpTable, boolean showNeedle, boolean showHaystack, boolean showSideBySide, boolean upcMatch, int cdsS, int cdsE, int hayPartS, int hayPartE)
int	ffShAli (FILE *f, struct ffAli *aliList, char *needleName, DNA *needle, int needleSize, int needleNumOffset, char *haystackName, DNA *haystack, int haySize, int hayNumOffset, int blockMaxGap, boolean rcNeedle)
void	ffShowAli (struct ffAli *aliList, char *needleName, DNA *needle, int needleNumOffset, char *haystackName, DNA *haystack, int hayNumOffset, boolean rcNeedle)
Variables
int	ffIntronMax

---

Define Documentation

#define ffIntronMaxDefault   750000

Definition at line 65 of file fuzzyFind.h.

Referenced by main(), ssStitch(), and usage().

---

Function Documentation

int ffAliCount

(

struct ffAli *

d

)

Definition at line 119 of file ffAli.c.

References ffAli::right.

Referenced by jiggleSmallExons(), pslFromFakeFfAli(), savePslx(), ssFindBest(), ssGraphMake(), and trimFlakyEnds().

{
int acc = 0;
while (d != NULL)
    {
    ++acc;
    d = d->right;
    }
return acc;
}

Here is the caller graph for this function:

struct ffAli* ffAliFromSym	(	int	symCount,
		char *	nSym,
		char *	hSym,
		struct lm *	lm,
		char *	nStart,
		char *	hStart
	)			[read]

Definition at line 131 of file ffAli.c.

References AllocVar, ffMakeRightLinks(), lm, lmAllocVar, and ffAli::nEnd.

Referenced by bandExtFf(), and smoothOneGap().

{
struct ffAli *ffList = NULL, *ff = NULL;
char n, h;
int i;

for (i=0; i<=symCount; ++i)
    {
    boolean isGap;
    n = nSym[i];
    h = hSym[i];
    isGap = (n == '-' || n == 0 || h == '-' || h == 0);
    if (isGap)
        {
        if (ff != NULL)
            {
            ff->nEnd = nStart;
            ff->hEnd = hStart;
            ff->left = ffList;
            ffList = ff;
            ff = NULL;
            }
        }
    else
        {
        if (ff == NULL)
            {
            if (lm != NULL)
                {
                lmAllocVar(lm, ff);
                }
            else
                {
                AllocVar(ff);
                }
            ff->nStart = nStart;
            ff->hStart = hStart;
            }
        }
    if (n != '-')
        {
        ++nStart;
        }
    if (h != '-')
        {
        ++hStart;
        }
    }
ffList = ffMakeRightLinks(ffList);
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ffAliSort	(	struct ffAli **	pList,
		int(*)(const void *elem1, const void *elem2)	compare
	)

Definition at line 39 of file ffAliHelp.c.

References ffMakeRightLinks(), ffAli::right, slReverse(), and slSort().

Referenced by ssStitch(), and weaveAli().

{
/* Get head of list and handle easy special empty case. */
struct ffAli *r = *pList;
if (r == NULL) return;

/* Since first pointer is "left", in order to reuse slSort, have
 * to jump through some minor hoops. First go to right end of list,
 * then sort it. */
while (r->right) r = r->right;
slSort(&r, compare);

/* We're sorted, but our right links are all broken.  Fix this. */
slReverse(&r);
r = ffMakeRightLinks(r);
*pList = r;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffCalcCdnaGapPenalty	(	int	hGap,
		int	nGap
	)

Definition at line 38 of file ffScore.c.

References digitsBaseTwo(), and ffIntronMax.

Referenced by ffCalcGapPenalty(), ffCdnaGapPenalty(), and smoothOneGap().

{
int acc = 2;
if (hGap > 400000)      /* Discourage really long introns. */
    {
    acc += (hGap - 400000)/3000;
    if (hGap > ffIntronMax)
        acc += (hGap - ffIntronMax)/2000;
    }
if (hGap < 0)   /* Discourage jumping back in haystack. */
    {
    hGap = -8*hGap;
    if (hGap > 48)
        hGap = (hGap*hGap);
    }
if (nGap < 0)   /* Jumping back in needle gets rid of previous alignment. */
    {
    acc += -nGap;
    nGap = 0;
    }
acc += digitsBaseTwo(hGap)/2;
if (nGap != 0)
    {
    acc += digitsBaseTwo(nGap);
    }
else
    {
    if (hGap > 30)
        acc -= 1;
    }
return acc;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffCalcGapPenalty	(	int	hGap,
		int	nGap,
		enum ffStringency	stringency
	)

Definition at line 115 of file ffScore.c.

References calcLooseGap(), calcTightGap(), errAbort(), ffCalcCdnaGapPenalty(), ffCdna, ffLoose, and ffTight.

Referenced by ffGapPenalty(), scoreAli(), ssGapCost(), ssGraphMake(), and trimGapPenalty().

{
switch (stringency)
    {
    case ffCdna:
        return ffCalcCdnaGapPenalty(hGap, nGap);
    case ffTight:
        return calcTightGap(hGap,nGap);
    case ffLoose:
        return calcLooseGap(hGap,nGap);
    default:
        errAbort("Unknown stringency type %d", stringency);
        return 0;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ffCat	(	struct ffAli **	pA,
		struct ffAli **	pB
	)

Definition at line 11 of file ffAliHelp.c.

References ffAli::left, and ffAli::right.

Referenced by bandExtAfter(), bandExtBefore(), cutAtBigIntrons(), findFromSmallerSeeds(), mergeProtoGenes(), scanForSmallerExons(), scanForTinyInternal(), and ssStitch().

{
struct ffAli *a = *pA;
struct ffAli *b = *pB;

/* If list to add is empty our job is real easy. */
if (b == NULL)
    return;

/* If list to add into is empty, then just switch in the
 * second list. */
if (a == NULL)
    {
    *pA = *pB;
    *pB = NULL;
    return;
    }

/* Neither list empty.  Find rightmost element of first list
 * and cross-link it with leftmost element of second list. */
while (a->right != NULL) a = a->right;
b->left = a;
a->right = b;
*pB = NULL;
}

Here is the caller graph for this function:

int ffCdnaGapPenalty	(	struct ffAli *	ali,
		struct ffAli *	right
	)

Definition at line 133 of file ffScore.c.

References ffCalcCdnaGapPenalty(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ffAli::nStart, and ffAli::right.

Referenced by reconsiderAlignedGaps().

{
int hGap = right->hStart - left->hEnd;
int nGap = right->nStart - left->nEnd;
return ffCalcCdnaGapPenalty(hGap, nGap);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffCmpHitsHayFirst	(	const void *	va,
		const void *	vb
	)

Definition at line 58 of file ffAliHelp.c.

References ffAli::hStart, and ffAli::nStart.

Referenced by weaveAli().

{
const struct ffAli *a = *((struct ffAli **)va);
const struct ffAli *b = *((struct ffAli **)vb);
int diff;
if ((diff = a->hStart - b->hStart) != 0)
    return diff;
return a->nStart - b->nStart;
}

Here is the caller graph for this function:

int ffCmpHitsNeedleFirst	(	const void *	va,
		const void *	vb
	)

Definition at line 70 of file ffAliHelp.c.

References ffAli::hStart, and ffAli::nStart.

Referenced by ssStitch().

{
const struct ffAli *a = *((struct ffAli **)va);
const struct ffAli *b = *((struct ffAli **)vb);
int diff;
if ((diff = a->nStart - b->nStart) != 0)
    return diff;
return a->hStart - b->hStart;
}

Here is the caller graph for this function:

void ffCountGoodEnds

(

struct ffAli *

aliList

)

Definition at line 108 of file ffAli.c.

References countGoodEnd(), countGoodStart(), ffAli::endGood, ffAli::right, and ffAli::startGood.

Referenced by ffFind(), and pslToFfAli().

{
struct ffAli *ali;
for (ali = aliList; ali != NULL; ali = ali->right)
    {
    ali->startGood = countGoodStart(ali);
    ali->endGood = countGoodEnd(ali);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ffExpandExactLeft	(	struct ffAli *	ali,
		DNA *	needleStart,
		DNA *	hayStart
	)

Definition at line 99 of file ffAliHelp.c.

References ffAli::hStart, and ffAli::nStart.

Referenced by addExtraHits(), findAliBetween(), and rwFindTilesBetween().

{
DNA *nStart = ali->nStart-1;
DNA *hStart = ali->hStart-1;
while (nStart >= needleStart && hStart >= hayStart)
    {
    if (*nStart != *hStart)
        break;
    nStart -= 1;
    hStart -= 1;
    }
ali->nStart = nStart + 1;
ali->hStart = hStart + 1;
return;
}

Here is the caller graph for this function:

void ffExpandExactRight	(	struct ffAli *	ali,
		DNA *	needleEnd,
		DNA *	hayEnd
	)

Definition at line 82 of file ffAliHelp.c.

References ffAli::hEnd, and ffAli::nEnd.

Referenced by addExtraHits(), findAliBetween(), and rwFindTilesBetween().

{
DNA *nEnd = ali->nEnd;
DNA *hEnd = ali->hEnd;
while (nEnd < needleEnd && hEnd < hayEnd)
    {
    if (*nEnd != *hEnd)
        break;
    nEnd += 1;
    hEnd += 1;
    }
ali->nEnd = nEnd;
ali->hEnd = hEnd;
return;
}

Here is the caller graph for this function:

struct ffAli* ffFind	(	DNA *	needleStart,
		DNA *	needleEnd,
		DNA *	hayStart,
		DNA *	hayEnd,
		enum ffStringency	stringency
	)			[read]

Definition at line 1428 of file fuzzyFind.c.

References dnaUtilOpen(), ffAbort(), ffCountGoodEnds(), ffMemCleanup(), ffMemInit(), ffRecover, findBestAli(), popAbortHandler(), pushAbortHandler(), and saveAliToPermanentMem().

Referenced by alignComponents(), ffFindAndScore(), smallMiddleExons(), and ssFindBundles().

{
struct ffAli *bestAli;
int status;

assert(needleStart <= needleEnd);
assert(hayStart <= hayEnd);

ffMemInit();
dnaUtilOpen();


/* Set up error recovery. */
status = setjmp(ffRecover);
if (status == 0)    /* Always true except after long jump. */
    {
    pushAbortHandler(ffAbort);
    bestAli = findBestAli(needleStart, needleEnd, hayStart, hayEnd, stringency);
    ffCountGoodEnds(bestAli);
    bestAli = saveAliToPermanentMem(bestAli);
    }
else    /* They long jumped here because of an error. */
    {
    bestAli = NULL;
    }
popAbortHandler();
ffMemCleanup();
return bestAli;
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean ffFindAndScore	(	DNA *	needle,
		int	needleSize,
		DNA *	haystack,
		int	haySize,
		enum ffStringency	stringency,
		struct ffAli **	pAli,
		boolean *	pRcNeedle,
		int *	pScore
	)

Definition at line 1460 of file fuzzyFind.c.

References FALSE, ffFind(), ffFreeAli(), ffScore(), reverseComplement(), and TRUE.

Referenced by ffFindEitherStrandN().

{
int fScore, rScore;
struct ffAli *fAli, *rAli;

/* Get forward alignment and score it. */
fAli = ffFind(needle, needle+needleSize, haystack, haystack+haySize, stringency);
fScore = ffScore(fAli,stringency);

/* Get reverse alignment and score it. */
reverseComplement(needle, needleSize);
rAli = ffFind(needle, needle+needleSize, haystack, haystack+haySize, stringency);
rScore = ffScore(rAli,stringency);
reverseComplement(needle, needleSize);

/* If no good alignment on either strand return FALSE. */
if (fAli == NULL && rAli == NULL)
    {
    *pAli = NULL;
    return FALSE;
    }

/* Return TRUE with best alignment.  Free the other one. */
if (fScore > rScore)
    {
    *pAli = fAli;
    *pRcNeedle = FALSE;
    if (pScore != NULL)
        *pScore = fScore;
    ffFreeAli(&rAli);
    }   
else
    {
    *pAli = rAli;
    *pRcNeedle = TRUE;
    if (pScore != NULL)
        *pScore = rScore;
    ffFreeAli(&fAli);
    }
return TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean ffFindEitherStrand	(	DNA *	needle,
		DNA *	haystack,
		enum ffStringency	stringency,
		struct ffAli **	pAli,
		boolean *	pRcNeedle
	)

Definition at line 1514 of file fuzzyFind.c.

References ffFindEitherStrandN().

{
return ffFindEitherStrandN(needle, strlen(needle), haystack, strlen(haystack),
stringency, pAli, pRcNeedle);
}

Here is the call graph for this function:

boolean ffFindEitherStrandN	(	DNA *	needle,
		int	needleSize,
		DNA *	haystack,
		int	haySize,
		enum ffStringency	stringency,
		struct ffAli **	pAli,
		boolean *	pRcNeedle
	)

Definition at line 1506 of file fuzzyFind.c.

References ffFindAndScore().

Referenced by ffFindEitherStrand().

{
return ffFindAndScore(needle, needleSize, haystack, haySize, stringency, pAli, pRcNeedle, NULL);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ffFreeAli

(

struct ffAli **

pAli

)

Definition at line 14 of file ffAli.c.

References ffAli::right, and slFreeList().

Referenced by ffFindAndScore(), forceMonotonic(), ssFfItemFree(), and ssStitch().

{
struct ffAli *ali = *pAli;
if (ali != NULL)
    {
    while (ali->right)
        ali = ali->right;
    slFreeList(&ali);
    }
*pAli = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffGapPenalty	(	struct ffAli *	ali,
		struct ffAli *	right,
		enum ffStringency	stringency
	)

Definition at line 141 of file ffScore.c.

References ffCalcGapPenalty(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ffAli::nStart, and ffAli::right.

Referenced by ffScoreSomeAlis(), and ffScoreSomething().

{
int hGap = right->hStart - left->hEnd;
int nGap = right->nStart - left->nEnd;
return ffCalcGapPenalty(hGap, nGap, stringency);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffIntronOrientation

(

struct ffAli *

ali

)

Definition at line 36 of file ffAli.c.

References ffAli::hEnd, intronOrientation(), ffAli::left, and ffAli::right.

Referenced by ffSlideIntrons(), jiggleSmallExons(), recursiveWeave(), refineSpliceSites(), and trimFlakyEnds().

{
struct ffAli *left = ali, *right;
int orient = 0;

if (left != NULL)
    {
    while((right = left->right) != NULL)
        {
        orient += intronOrientation(left->hEnd, right->hStart);
        left = right;
        }
    }
return orient;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct ffAli* ffMakeRightLinks

(

struct ffAli *

rightMost

)

[read]

Definition at line 62 of file ffAli.c.

References ffAli::left, and ffAli::right.

Referenced by ffAliFromSym(), ffAliSort(), gfRangesToFfItem(), lumpHits(), pslToFakeFfAli(), pslToFfAli(), rwFindTilesBetween(), scanIndexForSmallExons(), and ssFindBestBig().

{
struct ffAli *ff, *last = NULL;

for (ff = rightMost; ff != NULL; ff = ff->left)
    {
    ff->right = last;
    last = ff;
    }
return last;
}

Here is the caller graph for this function:

struct ffAli* ffMergeClose	(	struct ffAli *	aliList,
		DNA *	needleStart,
		DNA *	hayStart
	)			[read]

Definition at line 116 of file ffAliHelp.c.

References ffRemoveEmptyAlis(), ffAli::hEnd, ffAli::hStart, max, min, ffAli::nEnd, ffAli::nStart, ffAli::right, and TRUE.

Referenced by ssStitch().

{
struct ffAli *mid, *ali;
int closeEnough = -3;

if (aliList == NULL)
    return NULL;
for (mid = aliList->right; mid != NULL; mid = mid->right)
    {
    for (ali = aliList; ali != mid; ali = ali->right)
        {
        char *nStart, *nEnd;
        int nOverlap;
        nStart = max(ali->nStart, mid->nStart);
        nEnd = min(ali->nEnd, mid->nStart);
        nOverlap = nEnd - nStart;
        /* Overlap or perfectly abut in needle, and needle/hay
         * offset the same. */
        if (nOverlap >= closeEnough)
            {
            int aliDiag = (ali->nStart - needleStart) - (ali->hStart - hayStart);
            int midDiag = (mid->nStart - needleStart) - (mid->hStart - hayStart);
            if (aliDiag == midDiag)
                {
                /* Make mid encompass both, and make ali empty. */
                mid->nStart = min(ali->nStart, mid->nStart);
                mid->nEnd = max(ali->nEnd, mid->nEnd);
                mid->hStart = min(ali->hStart, mid->hStart);
                mid->hEnd = max(ali->hEnd, mid->hEnd);
                ali->hStart = ali->hEnd = mid->hStart;
                ali->nEnd = ali->nStart = mid->nStart;;
                }
            }
        }
    }
aliList = ffRemoveEmptyAlis(aliList, TRUE);
return aliList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct ffAli* ffMergeHayOverlaps

(

struct ffAli *

ali

)

[read]

Definition at line 330 of file ffAliHelp.c.

References ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ffAli::nStart, and ffAli::right.

Referenced by findBestAli(), and ssStitch().

{
struct ffAli *a = NULL;
struct ffAli *leftA = NULL;

if (ali == NULL)
    return NULL;
a = ali;
for (;;)
    {
    int nOverlap;
    int hOverlap;
    int aSize;

    /* Advance to next ali */
    leftA = a;
    a = a->right;
    if (a == NULL)
        break;

    nOverlap = leftA->nEnd - a->nStart;
    hOverlap = leftA->hEnd - a->hStart;
    aSize = a->nEnd - a->nStart;
    if (hOverlap > 0 && hOverlap < aSize && nOverlap <= 0)
        {
        a->hStart += hOverlap;
        a->nStart += hOverlap;
        }
    }
return ali;
}

Here is the caller graph for this function:

struct ffAli* ffMergeNeedleAlis	(	struct ffAli *	ali,
		boolean	doFree
	)			[read]

Definition at line 365 of file ffAliHelp.c.

References freeMem(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ffAli::nStart, and ffAli::right.

Referenced by findBestAli(), smoothSmallGaps(), and ssStitch().

{
struct ffAli *a = NULL;
struct ffAli *leftA = NULL;
struct ffAli *rightA;

if (ali == NULL)
    return NULL;
rightA = ali;
for (;;)
    {
    /* Advance to next ali */
    leftA = a;
    a = rightA;
    if (a == NULL)
        break;
    rightA = a->right;
    

    /* See if can merge current alignment into left one. */
    if (leftA != NULL)
        {
        int overlap = leftA->nEnd - a->nStart;

        /* Deal with overlaps in needle */
        if (overlap > 0)
            {
            /* See if left encompasses current segment. */
            if (leftA->nStart <= a->nStart && leftA->nEnd >= a->nEnd)
                {
                /* Eliminate current segment. */
                leftA->right = rightA;
                if (rightA != NULL)
                    rightA->left = leftA;
                if (doFree) freeMem(a);
                a = leftA;
                }
            else
                {
                /* Remove overlapping area from current segment, leave
                 * it in left segment. */
                a->hStart += overlap;
                a->nStart += overlap;
                }
            }
        else if (overlap == 0 && leftA->hEnd == a->hStart)
            {
            /* Remove current segment from list. */
            leftA->right = rightA;
            if (rightA != NULL)
                rightA->left = leftA;
            /* Fold data from current segment into left segment */
            leftA->nEnd = a->nEnd;
            leftA->hEnd = a->hEnd;
            if (doFree) freeMem(a); 
            a = leftA;
            }
        }
    }
return ali;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffOneIntronOrientation	(	struct ffAli *	left,
		struct ffAli *	right
	)

Definition at line 27 of file ffAli.c.

References ffAli::hEnd, ffAli::hStart, intronOrientation(), ffAli::left, ffAli::nEnd, ffAli::nStart, and ffAli::right.

{
if (left->nEnd != right->nStart)
    return 0;
return intronOrientation(left->hEnd, right->hStart);
}

Here is the call graph for this function:

struct ffAli* ffRemoveEmptyAlis	(	struct ffAli *	ali,
		boolean	doFree
	)			[read]

Definition at line 284 of file ffAliHelp.c.

References freeMem(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ffAli::nStart, and ffAli::right.

Referenced by ffMergeClose(), findBestAli(), refineSmallExons(), refineSpliceSites(), and ssStitch().

{
struct ffAli *leftAli;
struct ffAli *startAli;
struct ffAli *rightAli;

/* Figure out left most non-empty ali. */
while (ali->left)
    ali = ali->left;
while (ali)
    {
    /* If current ali is empty, chuck it out. */
    if (ali->nEnd <= ali->nStart || ali->hEnd <= ali->hStart)
        {
        struct ffAli *empty = ali;
        ali = ali->right;
        if (doFree) freeMem(empty);
        }
    else
        break;
    }
ali->left = NULL;

/* Get rid of empty middle alis. */
startAli = leftAli = ali;
ali = ali->right;
while (ali)
    {
    rightAli = ali->right;
    if (ali->nEnd <= ali->nStart || ali->hEnd <= ali->hStart)
        {
        leftAli->right = rightAli;
        if (rightAli != NULL)
            rightAli->left = leftAli;
        if (doFree) freeMem(ali);
        }
    else
        {
        leftAli = ali;
        }
    ali = rightAli;
    }
return startAli;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct ffAli* ffRightmost

(

struct ffAli *

ff

)

[read]

Definition at line 54 of file ffAli.c.

References ffAli::right.

Referenced by savePslx(), smallMiddleExons(), smoothOneGap(), and trimFlakyEnds().

{
while (ff->right != NULL)
    ff = ff->right;
return ff;
}

Here is the caller graph for this function:

int ffScore	(	struct ffAli *	ali,
		enum ffStringency	stringency
	)

Definition at line 195 of file ffScore.c.

References FALSE, and ffScoreSomething().

Referenced by cutAtBigIntrons(), ffFindAndScore(), and ffScoreCdna().

{
return ffScoreSomething(ali, stringency, FALSE);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffScoreCdna

(

struct ffAli *

ali

)

Definition at line 201 of file ffScore.c.

References ffCdna, and ffScore().

{
return ffScore(ali, ffCdna);
}

Here is the call graph for this function:

int ffScoreIntron	(	DNA	a,
		DNA	b,
		DNA	y,
		DNA	z,
		int	orientation
	)

Definition at line 160 of file ffAliHelp.c.

Referenced by slideIntron(), and trimGapPenalty().

{
int score = 0;
int revScore = 0;

if (orientation >= 0)
    {
    if (a == 'g' || a == 'G') ++score;
    if (b == 't' || b == 'T') ++score;
    if (y == 'a' || y == 'A') ++score;
    if (z == 'g' || z == 'G') ++score;
    }

if (orientation <= 0)
    {
    if (a == 'c' || a == 'C') ++revScore;
    if (b == 't' || b == 'T') ++revScore;
    if (y == 'a' || y == 'A') ++revScore;
    if (z == 'c' || z == 'C') ++revScore;
    }

return score > revScore ? score : revScore;
}

Here is the caller graph for this function:

int ffScoreMatch	(	DNA *	a,
		DNA *	b,
		int	size
	)

Definition at line 17 of file ffScore.c.

Referenced by trimFlakyEnds().

{
int i;
int score = 0;
for (i=0; i<size; ++i)
    {
    DNA aa = a[i];
    DNA bb = b[i];
    if (aa == 'n' || bb == 'n')
        continue;
    if (aa == bb)
        ++score;
    else
        score -= 1;
    }
return score;
}

Here is the caller graph for this function:

int ffScoreProtein	(	struct ffAli *	ali,
		enum ffStringency	stringency
	)

Definition at line 208 of file ffScore.c.

References ffScoreSomething(), and TRUE.

{
return ffScoreSomething(ali, stringency, TRUE);
}

Here is the call graph for this function:

int ffScoreSomeAlis	(	struct ffAli *	ali,
		int	count,
		enum ffStringency	stringency
	)

Definition at line 149 of file ffScore.c.

References dnaScoreMatch(), ffGapPenalty(), ffAli::hEnd, ffAli::hStart, ffAli::nStart, and ffAli::right.

{
int score = 0;
int oneScore;

while (--count >= 0)
    {
    int len = ali->hEnd - ali->hStart;
    struct ffAli *right = ali->right;
    oneScore = dnaScoreMatch(ali->hStart, ali->nStart, len);
    score += oneScore;
    if (count > 0)  /* Calculate gap penalty */
        score -= ffGapPenalty(ali, right,stringency);
    ali = right;
    }
return score;
}

Here is the call graph for this function:

int ffScoreSomething	(	struct ffAli *	ali,
		enum ffStringency	stringency,
		boolean	isProt
	)

Definition at line 168 of file ffScore.c.

References aaScoreMatch(), dnaScoreMatch(), ffGapPenalty(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nStart, and ffAli::right.

Referenced by ffScore(), and ffScoreProtein().

{
int score = 0;
int oneScore;
int (*scoreMatch)(char *a, char *b, int size);

if (ali == NULL)
    return -0x7FFFFFFF;
scoreMatch = (isProt ? aaScoreMatch : dnaScoreMatch );
while (ali->left != NULL) ali = ali->left;
while (ali != NULL)
    {
    int len = ali->hEnd - ali->hStart;
    struct ffAli *right = ali->right;
    oneScore = scoreMatch(ali->hStart, ali->nStart, len);
    score += oneScore;
    if (right)  /* Calculate gap penalty */
        {
        score -= ffGapPenalty(ali, right, stringency);
        }
    ali = right;
    }
return score;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffShAli	(	FILE *	f,
		struct ffAli *	aliList,
		char *	needleName,
		DNA *	needle,
		int	needleSize,
		int	needleNumOffset,
		char *	haystackName,
		DNA *	haystack,
		int	haySize,
		int	hayNumOffset,
		int	blockMaxGap,
		boolean	rcNeedle
	)

Definition at line 368 of file fuzzyShow.c.

References FALSE, ffShAliPart(), and TRUE.

Referenced by ffShowAli().

{
return ffShAliPart(f, aliList, needleName, needle, needleSize, needleNumOffset,
    haystackName, haystack, haySize, hayNumOffset, blockMaxGap, rcNeedle, FALSE,
    TRUE, TRUE, TRUE, TRUE, FALSE, 0, 0, 0, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int ffShAliPart	(	FILE *	f,
		struct ffAli *	aliList,
		char *	needleName,
		DNA *	needle,
		int	needleSize,
		int	needleNumOffset,
		char *	haystackName,
		DNA *	haystack,
		int	haySize,
		int	hayNumOffset,
		int	blockMaxGap,
		boolean	rcNeedle,
		boolean	rcHaystack,
		boolean	showJumpTable,
		boolean	showNeedle,
		boolean	showHaystack,
		boolean	showSideBySide,
		boolean	upcMatch,
		int	cdsS,
		int	cdsE,
		int	hayPartS,
		int	hayPartE
	)

Definition at line 82 of file fuzzyShow.c.

References FALSE, ffAli::hEnd, ffAli::hStart, ffAli::left, needMem(), ffAli::nEnd, ffAli::nStart, ffAli::right, and TRUE.

Referenced by ffShAli().

{
long i;
struct ffAli *ali;
struct ffAli *lastAli;
struct ffAli *leftAli = aliList;
struct ffAli *rightAli = aliList;
int charsInLine;
struct baf baf;
int maxSize = (needleSize > haySize ? needleSize : haySize);
char *colorFlags = needMem(maxSize);
int anchorCount = 0;
boolean restrictToWindow = FALSE;
int hayOffStart = 0, hayOffEnd = haySize;
int hayPaddedOffStart = 0, hayPaddedOffEnd = haySize;
int hayExtremity = rcHaystack ? (hayNumOffset + haySize) : hayNumOffset;
int nPartS=0, nPartE=0;

if (aliList != NULL)
    {
    while (leftAli->left != NULL) leftAli = leftAli->left;
    while (rightAli->right != NULL) rightAli = rightAli->right;
    }

/* If we are only showing part of the alignment, translate haystack window
 * coords to needle window coords and haystack-offset window coords: */
if (hayPartS > (hayNumOffset + (leftAli->hStart - haystack)) ||
    (hayPartE > 0 && hayPartE < (hayNumOffset + (rightAli->hEnd - haystack))))
    {
    DNA *haystackPartS;
    DNA *haystackPartE;
    restrictToWindow = TRUE;
    if (rcHaystack)
        {
        haystackPartS = haystack + (haySize - (hayPartE - hayNumOffset));
        haystackPartE = haystack + (haySize - (hayPartS - hayNumOffset));
        }
    else
        {
        haystackPartS = haystack + hayPartS - hayNumOffset;
        haystackPartE = haystack + hayPartE - hayNumOffset;
        }
    boolean foundStart = FALSE;
    hayOffStart = haystackPartS - haystack;
    hayOffEnd = haystackPartE - haystack;
    for (ali = leftAli;  ali != NULL;  ali = ali->right)
        {
        if (haystackPartS < ali->hEnd && !foundStart)
            {
            int offset = haystackPartS - ali->hStart;
            if (offset < 0)
                offset = 0;
            nPartS = offset + ali->nStart - needle;
            hayOffStart = offset + ali->hStart - haystack;
            foundStart = TRUE;
            }
        if (haystackPartE > ali->hStart)
            {
            if (haystackPartE > ali->hEnd)
                {
                nPartE = ali->nEnd - needle;
                hayOffEnd = ali->hEnd - haystack;
                }
            else
                {
                nPartE = haystackPartE - ali->hStart + ali->nStart - needle;
                hayOffEnd = haystackPartE - haystack;
                }
            }
        }
    hayPaddedOffStart = max(0, (hayOffStart - 100));
    hayPaddedOffEnd = min(haySize, (hayOffEnd + 100));
    if (rcHaystack)
        hayExtremity = hayNumOffset + haySize - hayPaddedOffStart;
    else
        hayExtremity = hayNumOffset + hayPaddedOffEnd;
    }

if (showJumpTable)
    {
    fputs("<CENTER><P><TABLE BORDER=1 WIDTH=\"97%\"><TR>", f);
    fputs("<TD WIDTH=\"23%\"><P ALIGN=CENTER><A HREF=\"#cDNA\">cDNA Sequence</A></TD>", f);
    if (restrictToWindow)
        fputs("<TD WIDTH=\"23%\"><P ALIGN=CENTER><A HREF=\"#cDNAStart\">cDNA Sequence in window</A></TD>", f);
    fputs("<TD WIDTH=\"27%\"><P ALIGN=\"CENTER\"><A HREF=\"#genomic\">Genomic Sequence</A></TD>", f);
    fputs("<TD WIDTH=\"29%\"><P ALIGN=\"CENTER\"><A HREF=\"#1\">cDNA in Genomic</A></TD>", f);
    fputs("<TD WIDTH=\"21%\"><P ALIGN=\"CENTER\"><A HREF=\"#ali\">Side by Side</A></TD>", f);
    fputs("</TR></TABLE>\n", f);
    }
if (cdsE > 0) 
    {
    fprintf(f, "Matching bases in coding regions of cDNA and genomic sequences are colored blue%s. ", 
            (upcMatch ? " and capitalized" : ""));
    fprintf(f, "Matching bases in UTR regions of cDNA and genomic sequences are colored red%s. ", 
            (upcMatch ? " and capitalized" : ""));
    fputs("Light blue (coding) or orange (UTR) bases mark the boundaries of gaps in either sequence "
          "(often splice sites).\n", f);
    } 
else 
    {
    fprintf(f, "Matching bases in cDNA and genomic sequences are colored blue%s. ", 
            (upcMatch ? " and capitalized" : ""));
    fputs("Light blue bases mark the boundaries of gaps in either sequence "
          "(often splice sites).\n", f);
    } 
if (showNeedle && restrictToWindow)
    fputs("Bases that were in the selected browser region are shown in bold "
          "and underlined, "
          "and only the alignment for these bases is displayed in the "
          "Genomic and Side by Side sections.\n", f);

if (showJumpTable)
    fputs("</P></CENTER>\n", f);
htmHorizontalLine(f);

fprintf(f, "<H4><A NAME=cDNA></A>cDNA %s%s</H4>\n", needleName, (rcNeedle ? " (reverse complemented)" : ""));

/* NOTE: if rcHaystack, hayNumOffset changes here into the end, not start! */
if (rcHaystack) 
    hayNumOffset += haySize;

if (rcNeedle)
    reverseComplement(needle, needleSize);

if (showNeedle)
    {
    ffShNeedle(f, needle, needleSize, needleNumOffset, colorFlags,
               aliList, upcMatch, cdsS, cdsE,
               restrictToWindow, nPartS, nPartE);
    }

if (showHaystack)
    {
    struct cfm *cfm = cfmNew(10, 50, TRUE, rcHaystack, f, hayExtremity);
    char *h = cloneMem(haystack, haySize);
    char *accentFlags = needMem(haySize);
    zeroBytes(accentFlags, haySize);
    fprintf(f, "<H4><A NAME=genomic></A>Genomic %s %s:</H4>\n", 
        haystackName,
        (rcHaystack ? "(reverse strand)" : ""));
    fprintf(f, "<TT><PRE>\n");
    zeroBytes(colorFlags, haySize);
    for (ali = leftAli; ali != NULL; ali = ali->right)
        {
        boolean utr = FALSE;
        int i;
        int off = ali->hStart-haystack;
        int count = ali->hEnd - ali->hStart;
        int offn = ali->nStart-needle;
        if ((cdsE > 0) && ((cdsS-offn-1) > 0)) 
            utr = TRUE;
        for (i=0; i<count; ++i)
            {
            if (!utr && (i > (cdsE-offn-1)) && (cdsE > 0))
                utr = TRUE;
            if (utr && (i == (cdsS-offn)))
                utr = FALSE;
            if (toupper(ali->hStart[i]) == toupper(ali->nStart[i]))
                {
                if (utr)
                    colorFlags[off+i] = ((i == 0 || i == count-1) ? socOrange : socRed);
                else
                    colorFlags[off+i] = ((i == 0 || i == count-1) ? socBrightBlue : socBlue);
                if (upcMatch)
                    h[off+i] = toupper(h[off+i]);
                }
            if (restrictToWindow && off+i >= hayOffStart && off+i < hayOffEnd)
                accentFlags[off+i] = TRUE;
            }
        }
    ali = leftAli;
    lastAli = NULL;
    while (ali && (ali->hEnd - haystack) <= hayPaddedOffStart)
        ali = ali->right;
    for (i = hayPaddedOffStart; i < hayPaddedOffEnd; ++i)
        {
        /* Put down "anchor" on first match position in haystack
         * so user can hop here with a click on the needle. */
        if (ali != NULL &&  i == ali->hStart - haystack)
            {
            if (lastAli == NULL || ali->hStart - lastAli->hEnd > blockMaxGap)
                {
                fprintf(f, "<A NAME=%d></A>", ++anchorCount);
                }
            lastAli = ali;
            ali = ali->right;
            }
        cfmOutExt(cfm, h[i], seqOutColorLookup[(int)colorFlags[i]],
                  accentFlags[i], accentFlags[i], FALSE);
        }
    cfmFree(&cfm);
    freeMem(h);
    fprintf(f, "</TT></PRE>\n");
    htmHorizontalLine(f);
    }

if (showSideBySide)
    {
    fprintf(f, "<H4><A NAME=ali></A>Side by Side Alignment</H4>\n");
    fprintf(f, "<TT><PRE>\n");
    lastAli = NULL;
    charsInLine = 0;
    bafInit(&baf, needle, needleNumOffset, FALSE, 
        haystack, hayNumOffset, rcHaystack, f, 50, FALSE);
    for (ali=leftAli; ali!=NULL; ali = ali->right)
        {
        boolean doBreak = TRUE;
        int aliLen;
        int i;

        if ((ali->hEnd - haystack) <= hayOffStart ||
            (ali->hStart - haystack) >= hayOffEnd)
            continue;

        /* Decide whether to put in a line break and/or blank characters */
        if (lastAli != NULL)
            {
            int nSkip = ali->nStart - lastAli->nEnd;
            int hSkip = ali->hStart - lastAli->hEnd;
            if (nSkip > 0 && nSkip <= blockMaxGap && hSkip == 0)
                {
                for (i=0; i<nSkip; ++i)
                    bafOut(&baf, lastAli->nEnd[i],'.');
                doBreak = FALSE; 
                }
            else if (hSkip > 0 && hSkip <= blockMaxGap && nSkip == 0)
                {
                for (i=0; i<hSkip; ++i)
                    bafOut(&baf, '.', lastAli->hEnd[i]);
                doBreak = FALSE;
                }
            else if (hSkip == nSkip && hSkip <= blockMaxGap)
                {
                for (i=0; i<hSkip; ++i)
                    bafOut(&baf, lastAli->nEnd[i], lastAli->hEnd[i]);
                doBreak = FALSE;
                }
            }
        else
            {
            doBreak = FALSE;
            }
        if (doBreak)
            bafFlushLine(&baf);
        int offset = max(0, (hayOffStart - (ali->hStart - haystack)));
        int nStart = offset + ali->nStart - needle;
        int hStart = offset + ali->hStart - haystack;
        bafSetPos(&baf, nStart, hStart);
        if (doBreak || lastAli == NULL)
            bafStartLine(&baf);
        aliLen = ali->nEnd - ali->nStart;
        for (i=0; i<aliLen; ++i)
            {
            int hayOff = i + (ali->hStart - haystack);
            if (hayOff < hayOffStart)
                continue;
            if (hayOff >= hayOffEnd)
                break;
            bafOut(&baf, ali->nStart[i], ali->hStart[i]);
            }
        lastAli = ali;
        }
    if (leftAli != NULL)
        bafFlushLine(&baf);
    fprintf(f, "</TT></PRE>\n");
    fprintf(f, "<EM>*Aligned Blocks with gaps &lt;= %d bases are merged for "
            "this display when only one sequence has a gap, or when gaps in "
            "both sequences are of the same size.</EM>\n", blockMaxGap);
    }
if (rcNeedle)
    reverseComplement(needle, needleSize);
return anchorCount;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ffShowAli	(	struct ffAli *	aliList,
		char *	needleName,
		DNA *	needle,
		int	needleNumOffset,
		char *	haystackName,
		DNA *	haystack,
		int	hayNumOffset,
		boolean	rcNeedle
	)

Definition at line 380 of file fuzzyShow.c.

References ffShAli().

{
ffShAli(stdout, aliList, needleName, needle, strlen(needle), needleNumOffset,
    haystackName, haystack, strlen(haystack), hayNumOffset, 8, rcNeedle);
}

Here is the call graph for this function:

boolean ffSlideIntrons

(

struct ffAli *

ali

)

Definition at line 276 of file ffAliHelp.c.

References ffIntronOrientation(), and ffSlideOrientedIntrons().

Referenced by findBestAli(), jiggleSmallExons(), and ssStitch().

{
int orient = ffIntronOrientation(ali);
return ffSlideOrientedIntrons(ali, orient);
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean ffSlideOrientedIntrons	(	struct ffAli *	ali,
		int	orient
	)

Definition at line 259 of file ffAliHelp.c.

References FALSE, ffAli::left, ffAli::right, slideIntron(), and TRUE.

Referenced by ffSlideIntrons(), and refineSpliceSites().

{
struct ffAli *left = ali, *right;
boolean slid = FALSE;
if (left == NULL)
    return FALSE;
while((right = left->right) != NULL)
    {
    if (slideIntron(left, right, orient))
        slid = TRUE;
    left = right;
    }
return slid;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void setFfExtendThroughN

(

boolean

val

)

Definition at line 605 of file fuzzyFind.c.

References extendThroughN.

Referenced by main().

{
extendThroughN = val;
}

Here is the caller graph for this function:

void setFfIntronMax

(

int

value

)

Definition at line 12 of file ffScore.c.

References ffIntronMax.

Referenced by main().

{
ffIntronMax = value;
}

Here is the caller graph for this function:

---

Variable Documentation

int ffIntronMax

Definition at line 10 of file ffScore.c.

Referenced by ffCalcCdnaGapPenalty(), ffSeedExtInMem(), gfAlignSomeClumps(), gfAlignStrand(), gfAlignTrans(), gfAlignTransTrans(), gfFindAlignAaTrans(), scanIndexForSmallExons(), seedResolvePower(), setFfIntronMax(), and ssStitch().

---