jkOwnLib/fuzzyFind.c File Reference

#include "common.h"
#include "dnautil.h"
#include "localmem.h"
#include "errabort.h"
#include "fuzzyFind.h"
#include "obscure.h"

Include dependency graph for fuzzyFind.c:

Go to the source code of this file.

Data Structures
struct	protoGene
Functions
void	dumpFf (struct ffAli *left, DNA *needle, DNA *hay)
static void	ffAbort ()
static void	ffMemInit ()
static void	ffMemCleanup ()
static void *	ffNeedMem (size_t size)
static void	makeFreqTable (DNA *dna, int dnaSize, double freq[4])
static double	oligoProb (DNA *oligo, int size, double freq[4])
static boolean	findImprobableOligo (DNA *needle, int needleLength, double maxProb, double freq[4], DNA **rOligo, int *rOligoLength, double *rOligoProb)
static boolean	hasRepeat (DNA *oligo, int oligoLen)
static boolean	ffFindGoodOligo (DNA *needle, int needleLength, double maxProb, double freq[4], DNA **rOligo, int *rOligoLength, double *rOligoProb)
static boolean	leftNextMatch (struct ffAli *ali, DNA *ns, DNA *ne, DNA *hs, DNA *he, int gapPenalty, int maxSkip)
static boolean	rightNextMatch (struct ffAli *ali, DNA *ns, DNA *ne, DNA *hs, DNA *he, int gapPenalty, int maxSkip)
static boolean	expandRight (struct ffAli *ali, DNA *needleStart, DNA *needleEnd, DNA *hayStart, DNA *hayEnd, int numSkips, int gapPenalty, int maxSkip)
static boolean	expandLeft (struct ffAli *ali, DNA *needleStart, DNA *needleEnd, DNA *hayStart, DNA *hayEnd, int numSkips, int gapPenalty, int maxSkip)
static boolean	exactFind (DNA *needle, int nSize, DNA *hay, int hSize, int *hOffset)
static struct ffAli *	reconsiderAlignedGaps (struct ffAli *ali)
static struct ffAli *	trimAlis (struct ffAli *aliList)
void	setFfExtendThroughN (boolean val)
boolean	expandThroughNRight (struct ffAli *ali, DNA *needleStart, DNA *needleEnd, DNA *hayStart, DNA *hayEnd)
boolean	expandThroughNLeft (struct ffAli *ali, DNA *needleStart, DNA *needleEnd, DNA *hayStart, DNA *hayEnd)
static struct ffAli *	expandAlis (struct ffAli *ali, DNA *nStart, DNA *nEnd, DNA *hStart, DNA *hEnd, int gapPenalty, int maxSkip)
DNA *	matchInMem (DNA *ns, DNA *ne, DNA *hs, DNA *he)
ffAli *	findAliBetween (DNA *tile, int tileSize, DNA *ns, DNA *ne, DNA *hs, DNA *he)
double	evalExactAli (struct ffAli *ali, DNA *ns, DNA *ne, DNA *hs, DNA *he, int numTiles, double freq[4])
void	ffUnlink (struct ffAli **pList, struct ffAli *el)
void	unlinkAli (struct ffAli **pList, struct ffAli *ali)
int	cmpProtoSize (const void *va, const void *vb)
int	cmpProtoNeedle (const void *va, const void *vb)
int	cmpProtoScore (const void *va, const void *vb)
boolean	canAdd (struct protoGene *a, struct protoGene *b)
boolean	bestMerger (struct protoGene *list, enum ffStringency stringency, DNA *ns, DNA *hs, struct protoGene **retA, struct protoGene **retB)
void	mergeProtoGenes (struct protoGene **pList, struct protoGene *a, struct protoGene *b)
void	lumpProtoGenes (struct protoGene **pList, DNA *ns, DNA *hs, enum ffStringency stringency)
protoGene *	lumpHits (struct ffAli **pHitList, DNA *ns, DNA *hs)
void	thinProtoList (struct protoGene **pList, int maxToTake)
static struct ffAli *	weaveAli (struct ffAli *hitList, DNA *ns, DNA *ne, DNA *hs, DNA *he, double freq[4], int *rBestVal, enum ffStringency stringency)
static struct ffAli *	rwFindTilesBetween (DNA *ns, DNA *ne, DNA *hs, DNA *he, enum ffStringency stringency, double probMax)
static struct ffAli *	exactAli (DNA *ns, DNA *ne, DNA *hs, DNA *he)
static struct ffAli *	recursiveWeave (DNA *ns, DNA *ne, DNA *hs, DNA *he, enum ffStringency stringency, double probMax, int level, int orientation)
static struct ffAli *	findWovenTiles (DNA *ns, DNA *ne, DNA *hs, DNA *he, enum ffStringency stringency)
static struct ffAli *	findBestAli (DNA *ns, DNA *ne, DNA *hs, DNA *he, enum ffStringency stringency)
static struct ffAli *	saveAliToPermanentMem (struct ffAli *volatileAli)
ffAli *	ffFind (DNA *needleStart, DNA *needleEnd, DNA *hayStart, DNA *hayEnd, enum ffStringency stringency)
boolean	ffFindAndScore (DNA *needle, int needleSize, DNA *haystack, int haySize, enum ffStringency stringency, struct ffAli **pAli, boolean *pRcNeedle, int *pScore)
boolean	ffFindEitherStrandN (DNA *needle, int needleSize, DNA *haystack, int haySize, enum ffStringency stringency, struct ffAli **pAli, boolean *pRcNeedle)
boolean	ffFindEitherStrand (DNA *needle, DNA *haystack, enum ffStringency stringency, struct ffAli **pAli, boolean *pRcNeedle)
Variables
static char const	rcsid [] = "$Id: fuzzyFind.c,v 1.17 2006/05/09 01:05:55 markd Exp $"
static jmp_buf	ffRecover
static struct lm *	ffMemPool = NULL
static int	extendThroughN
static double	rwFreq [4]
static boolean	rwIsCdna
static boolean	rwCheckGoodEnough

---

Function Documentation

boolean bestMerger	(	struct protoGene *	list,
		enum ffStringency	stringency,
		DNA *	ns,
		DNA *	hs,
		struct protoGene **	retA,
		struct protoGene **	retB
	)

Definition at line 934 of file fuzzyFind.c.

References canAdd(), FALSE, ffCdna, protoGene::hEnd, protoGene::hStart, protoGene::nEnd, protoGene::nStart, and protoGene::right.

Referenced by lumpProtoGenes().

{
int bestScore = -0x7fffffff;
int score;
struct protoGene *bestA = NULL, *bestB = NULL;
struct protoGene *a, *b;
boolean isCdna = (stringency == ffCdna);

if (list == NULL)
    return FALSE;

for (a = list; a != NULL; a = a->right)
    {
    for (b = a->right; b != NULL; b = b->right)
        {
        if (canAdd(a,b))
            {
            int hGap = b->hStart - a->hEnd;
            int nGap = b->nStart - a->nEnd;
            if (hGap < 0)
                {
                hGap = -8*hGap;
                if (!isCdna || hGap < 32)
                    hGap = (hGap*hGap);
                }
            if (nGap < 0)
                nGap = -8*nGap;
            score = -hGap - nGap*nGap;
            if (score > bestScore)
                {
                bestA = a;
                bestB = b;
                bestScore = score;
                }
            }
        }
    }
*retA = bestA;
*retB = bestB;
return bestA != NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean canAdd	(	struct protoGene *	a,
		struct protoGene *	b
	)

Definition at line 906 of file fuzzyFind.c.

References FALSE, ffAli::hEnd, protoGene::hEnd, protoGene::hits, ffAli::hStart, protoGene::hStart, ffAli::nEnd, protoGene::nEnd, ffAli::nStart, protoGene::nStart, ffAli::right, and TRUE.

Referenced by bestMerger().

{
struct ffAli *pa;
DNA *bnEnd = b->nEnd;
DNA *bnStart = b->nStart;
DNA *bhEnd = b->hEnd;
DNA *bhStart = b->hStart;
int bSize = bnEnd - bnStart;
int maxOverlap;
for (pa = a->hits; pa != NULL; pa = pa->right)
    {
    int aSize = pa->nEnd - pa->nStart;
    DNA *start = (bnStart > pa->nStart ? bnStart : pa->nStart);
    DNA *end = (bnEnd < pa->nEnd ? bnEnd : pa->nEnd);
    maxOverlap = (aSize < bSize ? aSize : bSize) / 4;
    if (maxOverlap < 2) maxOverlap = 2;
    if (end - start >= maxOverlap)
       return FALSE;
    start = (bhStart > pa->hStart ? bhStart : pa->hStart);
    end = (bhEnd < pa->hEnd ? bhEnd : pa->hEnd);
    if (end - start >= maxOverlap)
        return FALSE;
    }
return TRUE;
}

Here is the caller graph for this function:

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

Definition at line 890 of file fuzzyFind.c.

References protoGene::nStart.

{
const struct protoGene *a = *((struct protoGene **)va);
const struct protoGene *b = *((struct protoGene **)vb);
return (a->nStart - b->nStart);
}

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

Definition at line 898 of file fuzzyFind.c.

References protoGene::score.

Referenced by thinProtoList().

{
const struct protoGene *a = *((struct protoGene **)va);
const struct protoGene *b = *((struct protoGene **)vb);
return (b->score - a->score);
}

Here is the caller graph for this function:

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

Definition at line 879 of file fuzzyFind.c.

References protoGene::nEnd, and protoGene::nStart.

{
const struct protoGene *a = *((struct protoGene **)va);
const struct protoGene *b = *((struct protoGene **)vb);
int aSize, bSize;
aSize = a->nEnd - a->nStart;
bSize = b->nEnd - b->nStart;
return (bSize - aSize);
}

void dumpFf	(	struct ffAli *	left,
		DNA *	needle,
		DNA *	hay
	)

Definition at line 81 of file supStitch.c.

Referenced by dumpBuns().

{
struct ffAli *ff;
for (ff = left; ff != NULL; ff = ff->right)
    {
    printf("(%ld - %ld)[%ld-%ld] ", (long)(ff->hStart-hay), (long)(ff->hEnd-hay),
        (long)(ff->nStart - needle), (long)(ff->nEnd - needle));
    }
printf("\n");
}

Here is the caller graph for this function:

double evalExactAli	(	struct ffAli *	ali,
		DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		int	numTiles,
		double	freq[4]
	)

Definition at line 831 of file fuzzyFind.c.

References ffAli::nEnd, ffAli::nStart, oligoProb(), and ffAli::right.

Referenced by rwFindTilesBetween().

{
int haySize = he-hs;
double prob = 1.0;
double allPossibles = haySize*numTiles;

for (;ali != NULL;ali=ali->right)
    {
    double p = oligoProb(ali->nStart, ali->nEnd - ali->nStart, freq) * allPossibles;
    if (p < 1.0)
        prob *= p;
    }
return prob;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* exactAli	(	DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he
	)			[static, read]

Definition at line 1236 of file fuzzyFind.c.

References exactFind(), and ffNeedMem().

Referenced by recursiveWeave().

{
int exactOffset;
if (exactFind(ns, ne-ns, hs, he-hs, &exactOffset))
    {
    struct ffAli *ali = ffNeedMem(sizeof(*ali));
    ali->nStart = ns;
    ali->nEnd = ne;
    ali->hStart = hs + exactOffset;
    ali->hEnd = ali->hStart + (ne - ns);
    if (ali->hEnd > he)
        ali->hEnd = he;
    return ali;
    }
else
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean exactFind	(	DNA *	needle,
		int	nSize,
		DNA *	hay,
		int	hSize,
		int *	hOffset
	)			[static]

Definition at line 498 of file fuzzyFind.c.

References FALSE, and TRUE.

Referenced by exactAli().

{
DNA firstC = needle[0];
DNA *restOfNeedle = needle+1;
int i;
int endIx = hSize - nSize;
int restSize = nSize-1;

for (i = 0; i<=endIx; ++i)
    {
    if (firstC == hay[i])
        {
        if (memcmp(restOfNeedle, hay+i+1, restSize) == 0)
            {
            *hOffset = i;
            return TRUE;
            }
        }
    }
*hOffset = -1;
return FALSE;
}

Here is the caller graph for this function:

static struct ffAli* expandAlis	(	struct ffAli *	ali,
		DNA *	nStart,
		DNA *	nEnd,
		DNA *	hStart,
		DNA *	hEnd,
		int	gapPenalty,
		int	maxSkip
	)			[static, read]

Definition at line 669 of file fuzzyFind.c.

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

Referenced by findBestAli().

{
struct ffAli *a, *left, *right;
DNA *ns, *ne, *hs, *he;
boolean expanded = TRUE;

while (expanded)
    {
    expanded = FALSE;
    /* Loop through expanding three times. */
    /* First just expand through N's that don't require an insertion/deletion. */
    for (a = ali; a != NULL; a = a->right)
        {
        if ((left = a->left) != NULL)
            {
            ns = left->nEnd;
            hs = left->hEnd;
            }
        else
            {
            ns = nStart;
            hs = hStart;
            }
        if ((right = a->right) != NULL)
            {
            ne = right->nStart;
            he = right->hStart;
            }
        else
            {
            ne = nEnd;
            he = hEnd;
            }
        expanded |= expandThroughNLeft(a, ns, ne, hs, he);
        expanded |= expandThroughNRight(a, ns, ne, hs, he);
        }
    /* Second do other expansion that doesn't require an insertion/deletion. */
    for (a = ali; a != NULL; a = a->right)
        {
        if ((left = a->left) != NULL)
            {
            ns = left->nEnd;
            hs = left->hEnd;
            }
        else
            {
            ns = nStart;
            hs = hStart;
            }
        if ((right = a->right) != NULL)
            {
            ne = right->nStart;
            he = right->hStart;
            }
        else
            {
            ne = nEnd;
            he = hEnd;
            }
        expanded |= expandLeft(a, ns, ne, hs, he, 0, gapPenalty, maxSkip);
        expanded |= expandRight(a, ns, ne, hs, he, 0, gapPenalty, maxSkip);
        }
    /* Finally do insertion/deletion. */
    for (a = ali; a != NULL; a = a->right)
        {
        if ((left = a->left) != NULL)
            {
            ns = left->nEnd;
            hs = left->hEnd;
            }
        else
            {
            ns = nStart;
            hs = hStart;
            }
        if ((right = a->right) != NULL)
            {
            ne = right->nStart;
            he = right->hStart;
            }
        else
            {
            ne = nEnd;
            he = hEnd;
            }
        expanded |= expandLeft(a, ns, ne, hs, he, 1, gapPenalty, maxSkip);
        expanded |= expandRight(a, ns, ne, hs, he, 1, gapPenalty, maxSkip);
        }
    while (ali->left)
        ali = ali->left;
    }
return ali;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean expandLeft	(	struct ffAli *	ali,
		DNA *	needleStart,
		DNA *	needleEnd,
		DNA *	hayStart,
		DNA *	hayEnd,
		int	numSkips,
		int	gapPenalty,
		int	maxSkip
	)			[static]

Definition at line 355 of file fuzzyFind.c.

References dnaScoreMatch(), expandRight(), ffNeedMem(), ffAli::hStart, ffAli::left, leftNextMatch(), ffAli::nStart, and ffAli::right.

Referenced by expandRight().

{
DNA *ns = ali->nStart;
DNA *hs = ali->hStart;
int score;
DNA *oldNs = ns;

for (;;)
    {
    while (ns > needleStart && hs > hayStart && ns[-1] == hs[-1])
        {
        --hs;
        --ns;
        }
    if (ns <= needleStart || hs <= hayStart)
        {
        ali->nStart = ns;
        ali->hStart = hs;
        return ns != oldNs;
        }
    /* Find fuzzy score to the left. */
        {
        int windowSize = 5;
        int nSize = ns-needleStart;
        int hSize = hs-hayStart;
        if (windowSize > nSize) windowSize = nSize;
        if (windowSize > hSize) windowSize = hSize;
        if (windowSize > 0)
            score = dnaScoreMatch(ns-windowSize, hs-windowSize, windowSize); 
        else
            score = -1;

        if (score >= windowSize-2)
            {
            hs -= windowSize;
            ns -= windowSize;
            }
        else if (--numSkips >= 0)
            {
            struct ffAli *newAli = ffNeedMem(sizeof(*newAli));
            ali->nStart = ns;
            ali->hStart = hs;
            if (ns - needleStart < 3 || 
                !leftNextMatch(newAli, needleStart, ns, hayStart, hs, gapPenalty, maxSkip))
                {
                return ns != oldNs; /* We did our best... */
                }
            newAli->right = ali;
            newAli->left = ali->left;
            if (ali->left)
                ali->left->right = newAli;
            ali->left = newAli;
            ali = newAli;
            expandRight(ali, needleStart, ns, hayStart, hs, 0, gapPenalty, maxSkip);
            ns = ali->nStart;
            hs = ali->hStart;
            }
        else
            {
            ali->nStart = ns;
            ali->hStart = hs;
            return ns != oldNs;
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean expandRight	(	struct ffAli *	ali,
		DNA *	needleStart,
		DNA *	needleEnd,
		DNA *	hayStart,
		DNA *	hayEnd,
		int	numSkips,
		int	gapPenalty,
		int	maxSkip
	)			[static]

Definition at line 425 of file fuzzyFind.c.

References dnaScoreMatch(), expandLeft(), ffNeedMem(), ffAli::hEnd, ffAli::left, ffAli::nEnd, ffAli::right, and rightNextMatch().

Referenced by expandLeft().

{
int score;
DNA *ne = ali->nEnd;
DNA *he = ali->hEnd;
DNA *oldNe = ne;

for (;;)
    {
    /* Expand as far to the right as you can keeping perfect match */
    while (ne < needleEnd && he < hayEnd && *ne == *he)
        {
        ++he;
        ++ne;
        }

    /* Check to see if have come to the end. */
    if (ne >= needleEnd || he >= hayEnd)
        {
        ali->nEnd = ne;
        ali->hEnd = he;
        return oldNe != ne;
        }

    /* Find fuzzy score to the right. */
        {
        int windowSize = 5;
        int nSize = needleEnd-ne;
        int hSize = hayEnd - he;
        if (windowSize > nSize) windowSize = nSize;
        if (windowSize > hSize) windowSize = hSize;
        if (windowSize > 0)
            score = dnaScoreMatch(ne, he, windowSize); 
        else
            score = -1;

        if (score >= windowSize-2)
            {
            he += windowSize;
            ne += windowSize;
            }
        else if (--numSkips >= 0)
            {
            struct ffAli *newAli = ffNeedMem(sizeof(*newAli));
            ali->nEnd = ne;
            ali->hEnd = he;
            if (needleEnd - ne < 3 || 
                !rightNextMatch(newAli, ne, needleEnd, he, hayEnd, gapPenalty, maxSkip))
                {
                return oldNe != ne; /* We did our best... */
                }
            newAli->left = ali;
            newAli->right = ali->right;
            if (ali->right)
                ali->right->left = newAli;
            ali->right = newAli;
            ali = newAli;
            expandLeft(ali, ne, needleEnd, he, hayEnd, 0, gapPenalty, maxSkip);
            ne = ali->nEnd;
            he = ali->hEnd;
            }
        else 
            {
            ali->nEnd = ne;
            ali->hEnd = he;
            return oldNe != ne;
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

boolean expandThroughNLeft	(	struct ffAli *	ali,
		DNA *	needleStart,
		DNA *	needleEnd,
		DNA *	hayStart,
		DNA *	hayEnd
	)

Definition at line 641 of file fuzzyFind.c.

References extendThroughN, FALSE, ffAli::hStart, ffAli::nStart, and TRUE.

Referenced by expandAlis().

{
DNA *nStart = ali->nStart-1;
DNA *hStart = ali->hStart-1;
DNA n,h;
boolean expanded = FALSE;
while (nStart >= needleStart && hStart >= hayStart)
    {
    n = *nStart;
    h = *hStart;
    if ((n == h) ||
        (n == 'n' && (extendThroughN || nStart - 3 < needleStart || nStart[-1] != 'n' || nStart[-2] != 'n' || nStart[-3] != 'n')) ||
        (h == 'n' && (extendThroughN || hStart - 3 < hayStart || hStart[-1] != 'n' || hStart[-2] != 'n' || hStart[-3] != 'n')))
        {
        nStart -= 1;
        hStart -= 1;
        expanded = TRUE;
        }
    else
        break;
    }
ali->nStart = nStart + 1;
ali->hStart = hStart + 1;
return expanded;
}

Here is the caller graph for this function:

boolean expandThroughNRight	(	struct ffAli *	ali,
		DNA *	needleStart,
		DNA *	needleEnd,
		DNA *	hayStart,
		DNA *	hayEnd
	)

Definition at line 611 of file fuzzyFind.c.

References extendThroughN, FALSE, ffAli::hEnd, ffAli::nEnd, and TRUE.

Referenced by expandAlis().

{
DNA *nEnd = ali->nEnd;
DNA *hEnd = ali->hEnd;
DNA n,h;
boolean expanded = FALSE;
while (nEnd < needleEnd && hEnd < hayEnd)
    {
    n = *nEnd;
    h = *hEnd;
    if ((n == h) || 
        (n == 'n' && 
        (extendThroughN || nEnd + 3 >= needleEnd || nEnd[1] != 'n' || nEnd[2] != 'n' || nEnd[3] != 'n')) ||
        (h == 'n' && 
        (extendThroughN || hEnd + 3 >= hayEnd || hEnd[1] != 'n' || hEnd[2] != 'n' || hEnd[3] != 'n')))
        {
        nEnd += 1;
        hEnd += 1;
        expanded = TRUE;
        }
    else
        break;
    }
ali->nEnd = nEnd;
ali->hEnd = hEnd;
return expanded;
}

Here is the caller graph for this function:

static void ffAbort

(

)

[static]

Definition at line 77 of file fuzzyFind.c.

References ffRecover.

Referenced by ffFind(), and saveAliToPermanentMem().

{
longjmp(ffRecover, -1);
}

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:

static boolean ffFindGoodOligo	(	DNA *	needle,
		int	needleLength,
		double	maxProb,
		double	freq[4],
		DNA **	rOligo,
		int *	rOligoLength,
		double *	rOligoProb
	)			[static]

Definition at line 219 of file fuzzyFind.c.

References FALSE, findImprobableOligo(), hasRepeat(), and TRUE.

Referenced by rwFindTilesBetween().

{
int oligoLen;
DNA *oligo;

/* Loop around until you get one that doesn't repeat. */
for (;;)
    {
    if (!findImprobableOligo(needle, needleLength, maxProb, freq, rOligo, rOligoLength, rOligoProb))
        return FALSE;
    oligoLen = *rOligoLength;
    oligo = *rOligo;
    if (hasRepeat(oligo, oligoLen))
        {
        DNA *newNeedle = oligo+oligoLen;
        int newSize = needleLength - (newNeedle-needle);
        if (newSize <= 0)
            return FALSE;
        needle = newNeedle;
        needleLength = newSize;
        }
    else
        return TRUE;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void ffMemCleanup

(

)

[static]

Definition at line 91 of file fuzzyFind.c.

References ffMemPool, and lmCleanup().

Referenced by ffFind().

{
lmCleanup(&ffMemPool);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void ffMemInit

(

)

[static]

Definition at line 85 of file fuzzyFind.c.

References ffMemPool, and lmInit().

Referenced by ffFind().

{
ffMemPool = lmInit(2048);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void* ffNeedMem

(

size_t

size

)

[static]

Definition at line 97 of file fuzzyFind.c.

References ffMemPool, and lmAlloc().

Referenced by exactAli(), expandLeft(), expandRight(), findAliBetween(), lumpHits(), and rwFindTilesBetween().

{
return lmAlloc(ffMemPool, size);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ffUnlink	(	struct ffAli **	pList,
		struct ffAli *	el
	)

Definition at line 847 of file fuzzyFind.c.

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

Referenced by mergeProtoGenes(), and unlinkAli().

{
struct ffAli *list = *pList;
struct ffAli *right = el->right;
struct ffAli *left = el->left;

if (el == list)    /* If first element need to update list. */
    *pList = right;
if (right != NULL)
    right->left = left;
if (left != NULL)
    left->right = right;
el->left = el->right = NULL;
}

Here is the caller graph for this function:

struct ffAli* findAliBetween	(	DNA *	tile,
		int	tileSize,
		DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he
	)			[read]

Definition at line 783 of file fuzzyFind.c.

References ffExpandExactLeft(), ffExpandExactRight(), ffNeedMem(), and matchInMem().

{
DNA *match;
DNA *tileEnd = tile + tileSize;
int tries = 0;
for (;;)
    {
    if ((match = matchInMem(tile, tileEnd, hs, he)) == NULL)
        return NULL;
    if (matchInMem(tile, tileEnd, match+1, he) == NULL)
        {
        /* Got exactly one match, whoopie! */
        struct ffAli *ali = ffNeedMem(sizeof(*ali));
        ali->nStart = tile;
        ali->nEnd = tileEnd;
        ali->hStart = match;
        ali->hEnd = match + (tileEnd-tile);
        ffExpandExactLeft(ali, ns, hs);
        ffExpandExactRight(ali, ne, he);
        return ali;
        }

    /* Got more than one match.  Expand tile to make it more specific.
     * In general first add base to start, then base to beginning.  If
     * at beginning or end already are constrained.  If already spanning
     * full needle, can't expand, so you're done. */
    if (tile <= ns)
        {
        if (tileEnd >= ne)
            return NULL;
        ++tileEnd;
        }
    else if (tile >= tileEnd)
        {
        --tile;
        }
    else if (tries & 1)
        {
        ++tileEnd;
        }
    else
        {
        --tile;
        }    
    ++tries;
    }    
}

Here is the call graph for this function:

static struct ffAli* findBestAli	(	DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		enum ffStringency	stringency
	)			[static, read]

Definition at line 1364 of file fuzzyFind.c.

References expandAlis(), FALSE, ffCdna, ffMergeHayOverlaps(), ffMergeNeedleAlis(), ffRemoveEmptyAlis(), ffSlideIntrons(), findWovenTiles(), nextPowerOfFour(), reconsiderAlignedGaps(), and trimAlis().

Referenced by ffFind().

{
static int iniExpGapPen[] = {0 /* (exact) */, 4 /* cDna */, 4 /* tight */, 4 /* loose */};
static int addExpGapPen[] = {0 /* (exact) */, 3 /* cDna */, 3 /* tight */, 3 /* loose */};
static int midTileMinSize[] ={0 /*(exact) */,12 /* cDNA */, 12 /* tight */, 4 /* loose */};

struct ffAli *bestAli;
int matchSize;

matchSize = nextPowerOfFour(he-hs)+1;
if (matchSize < midTileMinSize[stringency])
    matchSize = midTileMinSize[stringency];

bestAli = findWovenTiles(ns, ne, hs, he, stringency);
if (bestAli == NULL)
    return NULL;

bestAli = ffMergeNeedleAlis(bestAli, FALSE);
bestAli = expandAlis(bestAli,ns,ne,hs,he,iniExpGapPen[stringency], 1);
bestAli = ffMergeNeedleAlis(bestAli, FALSE);
bestAli = expandAlis(bestAli,ns,ne,hs,he,addExpGapPen[stringency], 2*matchSize);
bestAli = trimAlis(bestAli);
bestAli = ffMergeNeedleAlis(bestAli, FALSE);
bestAli = ffMergeHayOverlaps(bestAli);
bestAli = reconsiderAlignedGaps(bestAli);
bestAli = ffRemoveEmptyAlis(bestAli, FALSE);
bestAli = ffMergeNeedleAlis(bestAli, FALSE);
if (stringency == ffCdna)
    ffSlideIntrons(bestAli);
bestAli = ffRemoveEmptyAlis(bestAli, FALSE);
return bestAli;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean findImprobableOligo	(	DNA *	needle,
		int	needleLength,
		double	maxProb,
		double	freq[4],
		DNA **	rOligo,
		int *	rOligoLength,
		double *	rOligoProb
	)			[static]

Definition at line 130 of file fuzzyFind.c.

References FALSE, ntVal, and TRUE.

Referenced by ffFindGoodOligo().

{
int i;
double totalProb = 1.0;
int base;
int startIx = 0;

for (i=0;i<needleLength;++i)
    {
    if ((base = ntVal[(int)needle[i]]) < 0)
        {
        totalProb = 1.0;
        startIx = i+1;
        }
    else
        {
        if ((totalProb *= freq[base]) <= maxProb)
            {
            *rOligo = needle+startIx;
            *rOligoLength = i-startIx+1;
            *rOligoProb = totalProb;
            return TRUE;
            }
        }
    }
return FALSE;
}

Here is the caller graph for this function:

static struct ffAli* findWovenTiles	(	DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		enum ffStringency	stringency
	)			[static, read]

Definition at line 1342 of file fuzzyFind.c.

References ffCdna, ffTight, makeFreqTable(), and recursiveWeave().

Referenced by findBestAli().

{
struct ffAli *bestAli;
int haySize = he - hs;
int needleSize = ne - ns;
static double tileStrinProbMult[] = { 0.0001, 0.0005, 0.0005, 0.5, };
                                    /* exact  cDNA        tight    loose */
if (needleSize < 2 || haySize < 2)  /* Be serious man! */
    return NULL;

/* Set up rwVariables - essentially locals except that they don't change over the course
 * of the recursion. */
makeFreqTable(hs, haySize, rwFreq);
rwIsCdna = (stringency == ffCdna);
rwCheckGoodEnough = (stringency == ffTight || stringency == ffCdna);

bestAli = recursiveWeave(ns, ne, hs, he, stringency, tileStrinProbMult[stringency], 1, 0);

return bestAli;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean hasRepeat	(	DNA *	oligo,
		int	oligoLen
	)			[static]

Definition at line 162 of file fuzzyFind.c.

References FALSE, and TRUE.

Referenced by ffFindGoodOligo().

{
int mod;
int i;
DNA b;
boolean gotRepeat;
int repSize;
int maxRep = (oligoLen+1)/2;

b = oligo[0];
gotRepeat = TRUE;
for (i=1; i<oligoLen; ++i)
    {
    if (oligo[i] != b)
        {
        gotRepeat = FALSE;
        break;
        }
    }
if (gotRepeat)
    return TRUE;

gotRepeat = TRUE;
for (i=2; i<oligoLen; ++i)
    {
    if (oligo[i&1] != oligo[i])
        {
        gotRepeat = FALSE;
        break;
        }
    }
if (gotRepeat)
    return TRUE;

for (repSize = 3; repSize <= maxRep; ++repSize)
    {
    mod = 0;
    gotRepeat = TRUE;
    for (i=repSize; i<oligoLen; ++i)
        {
        if (oligo[mod] != oligo[i])
            {
            gotRepeat = FALSE;
            break;
            }
        if (++mod == repSize)
            mod = 0;
        }
    if (gotRepeat)
        return TRUE;
    }
return gotRepeat;
}

Here is the caller graph for this function:

static boolean leftNextMatch	(	struct ffAli *	ali,
		DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		int	gapPenalty,
		int	maxSkip
	)			[static]

Definition at line 248 of file fuzzyFind.c.

References digitsBaseTwo(), FALSE, ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ffAli::nStart, and TRUE.

Referenced by expandLeft().

{
int haySize = he - hs;
int needleSize = ne - ns;
int diagSize = haySize + needleSize;
int matchSize;
int i;

/* We take care of bigger skips on the "tile" level. */
if (diagSize > maxSkip)
    diagSize = maxSkip;
/* Scan diagonally... */
/*
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6
*/
for (i=1; i<=diagSize; ++i)
    {
    int hOff = i;
    int nOff = 0;
    int hDiff = hOff - haySize;
    matchSize = gapPenalty + digitsBaseTwo(i);
    if (hDiff > 0)
        {
        nOff += hDiff;
        hOff -= hDiff;
        }
    for (;hOff >= 0; --hOff, ++nOff)
        {
        int needleLeft = needleSize - nOff;
        int hayLeft = haySize - hOff;
        if (matchSize > needleLeft) break;
        if (matchSize > hayLeft) continue;
        if (ne[-nOff-1] == he[-hOff-1] && memcmp(ne-nOff-matchSize, he-hOff-matchSize, matchSize) == 0)
            {
            ali->nStart = ne - nOff - matchSize;
            ali->nEnd = ne - nOff;
            ali->hStart = he - hOff - matchSize;
            ali->hEnd = he- hOff;
            return TRUE;
            }
        }
    }
return FALSE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct protoGene* lumpHits	(	struct ffAli **	pHitList,
		DNA *	ns,
		DNA *	hs
	)			[read]

Definition at line 1005 of file fuzzyFind.c.

References ffMakeRightLinks(), ffNeedMem(), ffAli::hEnd, protoGene::hEnd, protoGene::hits, ffAli::hStart, protoGene::hStart, ffAli::left, protoGene::left, ffAli::nEnd, protoGene::nEnd, ffAli::nStart, protoGene::nStart, protoGene::right, ffAli::right, and unlinkAli().

{
struct protoGene proto;
struct protoGene *retProto;
struct ffAli *ali, *nextAli;
int dif, lastDif;
int lumpCount = 1;

if ((ali = *pHitList) == NULL)
    return NULL;

/* Move first hit onto our crude exon. */
nextAli = ali->right;
proto.left = proto.right = NULL;
unlinkAli(pHitList, ali);
proto.hits = ali;
proto.hStart = ali->hStart;
proto.hEnd = ali->hEnd;
proto.nStart = ali->nStart;
proto.nEnd = ali->nEnd;
lastDif = ali->hStart - ali->nStart;

/* Go through rest of list and put others that are close to
 * on the same diagonal onto this exon. */
while ((ali = nextAli) != NULL)
    {
    nextAli = ali->right;
    dif = ali->hStart - ali->nStart;
    if (lastDif - 2 <= dif && dif <= lastDif + 2)
        {
        lastDif = dif;
        unlinkAli(pHitList, ali);
        ali->left = proto.hits;
        proto.hits = ali;
        proto.hEnd = ali->hEnd;
        proto.nEnd = ali->nEnd;
        ++lumpCount;
        }
    }
proto.hits = ffMakeRightLinks(proto.hits);
retProto = ffNeedMem(sizeof(*retProto));
memcpy(retProto, &proto, sizeof(*retProto));
return retProto;
}

Here is the call graph for this function:

void lumpProtoGenes	(	struct protoGene **	pList,
		DNA *	ns,
		DNA *	hs,
		enum ffStringency	stringency
	)

Definition at line 993 of file fuzzyFind.c.

References bestMerger(), and mergeProtoGenes().

{
struct protoGene *a, *b;

while (bestMerger(*pList, stringency, ns, hs, &a, &b))
    {
    mergeProtoGenes(pList, a, b);
    }
}

Here is the call graph for this function:

static void makeFreqTable	(	DNA *	dna,
		int	dnaSize,
		double	freq[4]
	)			[static]

Definition at line 103 of file fuzzyFind.c.

References dnaBaseHistogram().

Referenced by findWovenTiles().

{
int histo[4];
double total;
int i;

dnaBaseHistogram(dna, dnaSize, histo);
total = histo[0] + histo[1] + histo[2] + histo[3];
if (total == 0) total = 1;
for (i=0; i<4; ++i)
    freq[i] = (double)histo[i] / total;
}

Here is the call graph for this function:

Here is the caller graph for this function:

DNA* matchInMem	(	DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he
	)

Definition at line 767 of file fuzzyFind.c.

Referenced by findAliBetween(), and rwFindTilesBetween().

{
int nLen = ne - ns;
DNA c = *ns++;
he -= nLen;
nLen -= 1;
while (hs < he)
    {   
    if (*hs++ == c && memcmp(ns, hs, nLen) == 0)
        {
        return hs-1;
        }
    }
return NULL;
}

Here is the caller graph for this function:

void mergeProtoGenes	(	struct protoGene **	pList,
		struct protoGene *	a,
		struct protoGene *	b
	)

Definition at line 978 of file fuzzyFind.c.

References ffCat(), ffUnlink(), ffAli::hEnd, protoGene::hEnd, protoGene::hits, ffAli::hStart, protoGene::hStart, ffAli::nEnd, protoGene::nEnd, ffAli::nStart, and protoGene::nStart.

Referenced by lumpProtoGenes().

{
ffUnlink((struct ffAli**)pList, (struct ffAli *)b);
ffCat(&a->hits, &b->hits);
if (a->hStart > b->hStart)
    a->hStart = b->hStart;
if (a->nStart > b->nStart)
    a->nStart = b->nStart;
if (a->hEnd < b->hEnd)
    a->hEnd = b->hEnd;
if (a->nEnd < b->nEnd)
    a->nEnd = b->nEnd;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static double oligoProb	(	DNA *	oligo,
		int	size,
		double	freq[4]
	)			[static]

Definition at line 116 of file fuzzyFind.c.

References ntVal.

Referenced by evalExactAli().

{
double prob = 1.0;
int i;
int baseVal;

for (i=0; i<size; ++i)
    {
    if ((baseVal = ntVal[(int)oligo[i]]) >= 0)
        prob *= freq[baseVal];
    }
return prob;
}

Here is the caller graph for this function:

static struct ffAli* reconsiderAlignedGaps

(

struct ffAli *

ali

)

[static, read]

Definition at line 541 of file fuzzyFind.c.

References dnaScoreMatch(), ffCdnaGapPenalty(), ffAli::hEnd, ffAli::hStart, ffAli::left, matchScore, ffAli::nEnd, ffAli::nStart, and ffAli::right.

Referenced by findBestAli().

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

if (ali == NULL)
    return NULL;
a = ali;
for (;;)
    {
    int gapSize;

    /* Advance to next ali */
    left = a;
    a = a->right;
    if (a == NULL)
        break;
    gapSize = a->nStart - left->nEnd;
    if (gapSize == a->hStart - left->hEnd)
        {
        int gapScore;
        int matchScore;
        gapScore = -ffCdnaGapPenalty(left, a);
        matchScore = dnaScoreMatch(left->nEnd, left->hEnd, gapSize);
        if (matchScore > gapScore)
            {
            /* Make current cover left. RemoveEmpty will take
             * care of empty shell of left later. */
            a->hStart = left->hEnd = left->hStart;
            a->nStart = left->nEnd = left->nStart;
            }
        }
    }
return ali;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* recursiveWeave	(	DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		enum ffStringency	stringency,
		double	probMax,
		int	level,
		int	orientation
	)			[static, read]

Definition at line 1255 of file fuzzyFind.c.

References exactAli(), ffExact, ffIntronOrientation(), ffAli::hEnd, ffAli::left, ffAli::nEnd, ffAli::right, and rwFindTilesBetween().

Referenced by findWovenTiles().

{
struct ffAli *left = NULL, *right = NULL, *aliList;

if ((left = exactAli(ns, ne, hs, he)) != NULL)
    return left;
if (stringency == ffExact)
    return NULL;

aliList = rwFindTilesBetween(ns, ne, hs, he, stringency, probMax);
if (aliList != NULL)
    {
    DNA *lne, *rns, *lhe, *rhs;
    int ndif, hdif;
    right = aliList;
    if (orientation == 0)
        orientation = ffIntronOrientation(aliList);
    for (;;)
        {
        /* Figure out the end points to recurse to. */
        if (left != NULL)
            {
            lne = left->nEnd;
            lhe = left->hEnd;
            }
        else
            {
            lne = ns;
            lhe = hs;
            }
        if (right != NULL)
            {
            rns = right->nStart;
            rhs = right->hStart;
            }
        else
            {
            rns = ne;
            rhs = he;
            }
        ndif = rns-lne;
        hdif = rhs-lhe;
        /* If a big enough gap left recurse. */
        if (ndif >= 5 && hdif >= 5)
            {
            struct ffAli *newLeft = NULL, *newRight;

            newLeft = recursiveWeave(lne, rns, lhe, rhs, stringency, probMax*2, level+1, 
                orientation);
            if (newLeft != NULL)
                {
                /* Insert new tiles between left and right. */
                
                /* Find right end of tile set. */
                newRight = newLeft;
                while (newRight->right != NULL)
                    newRight = newRight->right;
                
                
                if (left != NULL)
                    {
                    left->right = newLeft;
                    newLeft->left = left;
                    }
                else
                    {
                    aliList = newLeft;
                    }
                if (right != NULL)
                    {
                    right->left = newRight;
                    newRight->right = right;
                    }
                }
            }
        if ((left = right) == NULL)
            break;
        right = right->right;
        }
    }
return aliList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean rightNextMatch	(	struct ffAli *	ali,
		DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		int	gapPenalty,
		int	maxSkip
	)			[static]

Definition at line 300 of file fuzzyFind.c.

References digitsBaseTwo(), FALSE, ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ffAli::nStart, and TRUE.

Referenced by expandRight().

{
int haySize = he - hs;
int needleSize = ne - ns;
int diagSize = haySize + needleSize;
int matchSize;
int i;

/* We take care of bigger skips on the "tile" level. */
if (diagSize > maxSkip)
    diagSize = maxSkip;
/* Scan diagonally... */
/*
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6
*/
for (i=1; i<=diagSize; ++i)
    {
    int hOff = i;
    int nOff = 0;
    int hDiff = hOff - haySize;
    matchSize = gapPenalty + digitsBaseTwo(i);
    if (hDiff > 0)
        {
        nOff += hDiff;
        hOff -= hDiff;
        }
    for (;hOff >= 0; --hOff, ++nOff)
        {
        int needleLeft = needleSize - nOff;
        int hayLeft = haySize - hOff;
        if (matchSize > needleLeft) break;
        if (matchSize > hayLeft) continue;
        if (ns[nOff] == hs[hOff] && memcmp(ns+nOff, hs+hOff, matchSize) == 0)
            {
            ali->nStart = ns + nOff;
            ali->nEnd = ns + nOff + matchSize;
            ali->hStart = hs + hOff;
            ali->hEnd = hs + hOff + matchSize;
            return TRUE;
            }
        }
    }
return FALSE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* rwFindTilesBetween	(	DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		enum ffStringency	stringency,
		double	probMax
	)			[static, read]

Definition at line 1159 of file fuzzyFind.c.

References evalExactAli(), FALSE, ffExpandExactLeft(), ffExpandExactRight(), ffFindGoodOligo(), ffMakeRightLinks(), ffNeedMem(), matchInMem(), nextPowerOfFour(), ffAli::right, tileSize, and weaveAli().

Referenced by recursiveWeave().

{
int searchOffset;
int endTileOffset;
int haySize = he - hs;
int needleSize = ne - ns;
int numTiles = 0;
int bestWeaveVal;
int tileIx;
struct ffAli *hitList = NULL;
struct ffAli *bestAli;
struct ffAli *ali;
int possibleTiles;
double tileProbOne;

possibleTiles = (haySize - nextPowerOfFour(needleSize));
if (possibleTiles < 1) possibleTiles = 1;
tileProbOne = probMax/possibleTiles;

searchOffset = 0;
endTileOffset = 0;
tileIx = 0;
for (;;)
    {
    DNA *tile;
    int tileSize;
    double tileProb;
    DNA *h = hs;

    searchOffset = endTileOffset;
    if (!ffFindGoodOligo(ns+searchOffset, needleSize-searchOffset, tileProbOne,
        rwFreq, &tile, &tileSize, &tileProb))
        {
        break;
        }
    /* Find all parts that match the tile. */
    for (;;)
        {
        if ((h = matchInMem(tile, tile+tileSize, h, he)) == NULL)
            break;
        ali = ffNeedMem(sizeof(*ali));
        ali->hStart = h;
        ali->hEnd = ali->hStart + tileSize;
        ali->nStart = tile;
        ali->nEnd = tile + tileSize;
        ali->left = hitList;
        hitList = ali;
        h += tileSize;
        } 
    endTileOffset = tile + tileSize - ns;
    ++numTiles;
    }
if (hitList == NULL)
    return NULL;

hitList = ffMakeRightLinks(hitList);
for (ali = hitList; ali != NULL; ali = ali->right)
    {
    ffExpandExactLeft(ali, ns, hs);
    ffExpandExactRight(ali, ne, he);
    }
bestAli = weaveAli(hitList, ns, ne, hs, he, rwFreq, &bestWeaveVal, stringency);
if (rwCheckGoodEnough)
    {
    double prob;
    prob = evalExactAli(bestAli, ns, ne, hs, he, numTiles, rwFreq);
    if (prob > 0.1)
        return NULL;
    rwCheckGoodEnough = FALSE;
    }

return bestAli;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* saveAliToPermanentMem

(

struct ffAli *

volatileAli

)

[static, read]

Definition at line 1398 of file fuzzyFind.c.

References ffAbort(), ffAli::left, needMem(), ffAli::right, and slFreeList().

Referenced by ffFind().

{
struct ffAli *leftList = NULL;
struct ffAli *newAli, *ali;
struct ffAli *rightList = NULL;

/* Allocate memory, copy contents and set left pointer. */
for (ali = volatileAli; ali != NULL; ali = ali->right)
    {
    newAli = needMem(sizeof(*newAli));
    if (newAli == NULL)
        {
        slFreeList(leftList);
        ffAbort();
        }
    memcpy(newAli, ali, sizeof(*newAli));
    newAli->left = leftList;
    leftList = newAli;
    }

/* Set right pointer. */
for (ali = leftList; ali != NULL; ali = ali->left)
    {
    ali->right = rightList;
    rightList = ali;
    }
return rightList;
}

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 thinProtoList	(	struct protoGene **	pList,
		int	maxToTake
	)

Definition at line 1080 of file fuzzyFind.c.

References cmpProtoScore(), and slSort().

{
struct protoGene *newList = NULL, *pg, *next;
int i;

slSort(pList, cmpProtoScore);
for (pg=*pList, i=0; pg != NULL && i < maxToTake; pg = next, ++i)
    {
    next = pg->left;
    pg->left = newList;
    newList = pg;
    }
*pList = newList;
}

Here is the call graph for this function:

static struct ffAli* trimAlis

(

struct ffAli *

aliList

)

[static, read]

Definition at line 580 of file fuzzyFind.c.

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

Referenced by findBestAli().

{
struct ffAli *ali;
int trimCount = 0;
for (ali = aliList; ali != NULL; ali = ali->right)
    {
    while (ali->nStart[0] != ali->hStart[0] && ali->nStart < ali->nEnd)
        {
        ali->nStart += 1;
        ali->hStart += 1;
        ++trimCount;
        }
    while (ali->nEnd[-1] != ali->hEnd[-1] && ali->nEnd > ali->nStart)
        {
        ali->nEnd -= 1;
        ali->hEnd -= 1;
        ++trimCount;
        }
    }
return aliList;
}

Here is the caller graph for this function:

void unlinkAli	(	struct ffAli **	pList,
		struct ffAli *	ali
	)

Definition at line 864 of file fuzzyFind.c.

References ffUnlink().

Referenced by lumpHits(), and weaveAli().

{
ffUnlink(pList, ali);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* weaveAli	(	struct ffAli *	hitList,
		DNA *	ns,
		DNA *	ne,
		DNA *	hs,
		DNA *	he,
		double	freq[4],
		int *	rBestVal,
		enum ffStringency	stringency
	)			[static, read]

Definition at line 1097 of file fuzzyFind.c.

References ffAliSort(), ffCmpHitsHayFirst(), ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ffAli::nStart, ffAli::right, and unlinkAli().

Referenced by rwFindTilesBetween().

{
struct ffAli *ali, *lastAli;
struct protoGene *proto, *protoList = NULL;
int protoCount = 0;

/* Sort initial hits and remove duplicates. */
ffAliSort(&hitList, ffCmpHitsHayFirst);
ali = hitList;
for (;;)
    {
    lastAli = ali;
    if ((ali = ali->right) == NULL)
        break;
    if (ali->hStart == lastAli->hStart && ali->hEnd == lastAli->hEnd
       && ali->nStart == lastAli->nStart && ali->nEnd == lastAli->nEnd)
       {
       unlinkAli(&hitList, lastAli);
       }
    }

/* Lump together things which look to be separated only by small
 * amounts of noise. */
while ((proto = lumpHits(&hitList, ns, hs)) != NULL)
    {
    proto->left = protoList;
    protoList = proto;
    ++protoCount;
    }
if (protoCount > 200)
    {
    thinProtoList(&protoList, 200);
    }
protoList = (struct protoGene *)ffMakeRightLinks((struct ffAli*)protoList);


/* Lump together any other ones that can, starting with ones
 * that go together best. */
ffAliSort((struct ffAli**)(void*)&protoList, cmpProtoNeedle);
lumpProtoGenes(&protoList, ns, hs, stringency );
for (proto = protoList; proto != NULL; proto = proto->right)
    {
    ffAliSort((struct ffAli**)&proto->hits, ffCmpHitsNeedleFirst);
/*    removeThrowbackHits(proto); */
    proto->score = ffScore(proto->hits,stringency);
    }

/* Sort by score and return the best. */
ffAliSort((struct ffAli **)(void*)&protoList, cmpProtoScore);
*rBestVal = protoList->score;
return protoList->hits;
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

int extendThroughN [static]

Definition at line 603 of file fuzzyFind.c.

Referenced by expandThroughNLeft(), expandThroughNRight(), and setFfExtendThroughN().

struct lm* ffMemPool = NULL [static]

Definition at line 83 of file fuzzyFind.c.

Referenced by ffMemCleanup(), ffMemInit(), and ffNeedMem().

jmp_buf ffRecover [static]

Definition at line 75 of file fuzzyFind.c.

Referenced by ffAbort(), and ffFind().

char const rcsid[] = "$Id: fuzzyFind.c,v 1.17 2006/05/09 01:05:55 markd Exp $" [static]

Definition at line 43 of file fuzzyFind.c.

boolean rwCheckGoodEnough [static]

Definition at line 1157 of file fuzzyFind.c.

double rwFreq[4] [static]

Definition at line 1155 of file fuzzyFind.c.

boolean rwIsCdna [static]

Definition at line 1156 of file fuzzyFind.c.

---