jkOwnLib/ffSeedExtend.c File Reference

#include "common.h"
#include "dnaseq.h"
#include "localmem.h"
#include "memalloc.h"
#include "bits.h"
#include "genoFind.h"
#include "fuzzyFind.h"
#include "supStitch.h"
#include "bandExt.h"
#include "gfInternal.h"

Include dependency graph for ffSeedExtend.c:

Go to the source code of this file.

Data Structures
struct	seqHashEl
Functions
static void	extendExactRight (int qMax, int tMax, char **pEndQ, char **pEndT)
static void	extendExactLeft (int qMax, int tMax, char **pStartQ, char **pStartT)
static void	extendGaplessRight (int qMax, int tMax, int maxDrop, char **pEndQ, char **pEndT)
static void	extendGaplessLeft (int qMax, int tMax, int maxDrop, char **pStartQ, char **pStartT)
static int	ffHashFuncN (char *s, int seedSize)
static boolean	totalDegenerateN (char *s, int seedSize)
static struct ffAli *	ffFindExtendNmers (char *nStart, char *nEnd, char *hStart, char *hEnd, int seedSize)
static void	clumpToExactRange (struct gfClump *clump, bioSeq *qSeq, int tileSize, int frame, struct trans3 *t3, struct gfRange **pRangeList)
static void	addExtraHits (struct gfHit *hitList, int hitSize, struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli **pExtraList)
static struct ffAli *	foldInExtras (struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli *ffList, struct ffAli *extraList)
static struct ffAli *	scanIndexForSmallExons (struct genoFind *gf, struct gfSeqSource *target, struct dnaSeq *qSeq, Bits *qMaskBits, int qMaskOffset, struct dnaSeq *tSeq, struct lm *lm, struct ffAli *ffList)
static void	bandExtBefore (struct axtScoreScheme *ss, struct ffAli *ff, int qGap, int tGap, struct ffAli **pExtraList)
static void	bandExtAfter (struct axtScoreScheme *ss, struct ffAli *ff, int qGap, int tGap, struct ffAli **pExtraList)
static struct ffAli *	bandedExtend (struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli *ffList)
static struct ffAli *	expandGapless (struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli *ffList)
static int	seedResolvePower (int seedSize, int resolveLimit)
static char *	scanExactLeft (char *n, int nSize, int hSize, char *hEnd, int resolveLimit)
static char *	scanExactRight (char *n, int nSize, int hSize, char *hStart, int resolveLimit)
static struct ffAli *	fillInExact (char *nStart, char *nEnd, char *hStart, char *hEnd, boolean isRc, boolean scanLeft, boolean scanRight, int resolveLimit)
static struct ffAli *	findFromSmallerSeeds (char *nStart, char *nEnd, char *hStart, char *hEnd, boolean isRc, boolean scanLeft, boolean scanRight, int seedSize, int resolveLimit)
static int	countT (char *s, int size)
static int	countA (char *s, int size)
ffAli *	scanTinyOne (char *nStart, char *nEnd, char *hStart, char *hEnd, boolean isRc, boolean scanLeft, boolean scanRight, int seedSize)
static struct ffAli *	scanForSmallerExons (int seedSize, struct dnaSeq *qSeq, struct dnaSeq *tSeq, boolean isRc, struct ffAli *ffList)
static struct ffAli *	scanForTinyInternal (struct dnaSeq *qSeq, struct dnaSeq *tSeq, boolean isRc, struct ffAli *ffList)
static boolean	tradeMismatchToCloseSpliceGap (struct ffAli *left, struct ffAli *right, int orientation)
static int	calcSpliceScore (struct axtScoreScheme *ss, char a1, char a2, char b1, char b2, int orientation)
static void	grabAroundIntron (char *hpStart, int iPos, int iSize, int modPeelSize, char *hSeq)
static struct ffAli *	hardRefineSplice (struct ffAli *left, struct ffAli *right, struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli *ffList, int orientation)
static struct ffAli *	refineSpliceSites (struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli *ffList)
static boolean	smoothOneGap (struct ffAli *left, struct ffAli *right, struct ffAli *ffList)
static struct ffAli *	smoothSmallGaps (struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli *ffList)
int	aPenalty (char *s, int size)
static int	trimGapPenalty (int hGap, int nGap, char *iStart, char *iEnd, int orientation)
static struct ffAli *	trimFlakyEnds (struct dnaSeq *qSeq, struct dnaSeq *tSeq, struct ffAli *ffList)
static void	refineBundle (struct genoFind *gf, struct dnaSeq *qSeq, Bits *qMaskBits, int qMaskOffset, struct dnaSeq *tSeq, struct lm *lm, struct ssBundle *bun, boolean isRc)
ssBundle *	ffSeedExtInMem (struct genoFind *gf, struct dnaSeq *qSeq, Bits *qMaskBits, int qOffset, struct lm *lm, int minScore, boolean isRc)
Variables
static char const	rcsid [] = "$Id: ffSeedExtend.c,v 1.36 2006/06/22 16:24:43 kent Exp $"

---

Function Documentation

static void addExtraHits	(	struct gfHit *	hitList,
		int	hitSize,
		struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli **	pExtraList
	)			[static]

Definition at line 292 of file ffSeedExtend.c.

References AllocVar, dnaSeq::dna, ffExpandExactLeft(), ffExpandExactRight(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, gfHit::next, ffAli::nStart, gfHit::qStart, dnaSeq::size, and gfHit::tStart.

Referenced by scanIndexForSmallExons().

{
struct gfHit *hit;
struct ffAli *ff;
char *qs = qSeq->dna, *ts = tSeq->dna;
char *qe = qs + qSeq->size,  *te = ts + tSeq->size;
for (hit = hitList; hit != NULL; hit = hit->next)
    {
    AllocVar(ff);
    ff->nStart = ff->nEnd = qs + hit->qStart;
    ff->hStart = ff->hEnd = ts + hit->tStart;
    ff->nEnd += hitSize;
    ff->hEnd += hitSize;
    ff->left = *pExtraList;
    ffExpandExactLeft(ff, qs, ts);
    ffExpandExactRight(ff, qe, te);
    *pExtraList = ff;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int aPenalty	(	char *	s,
		int	size
	)

Definition at line 1116 of file ffSeedExtend.c.

Referenced by trimFlakyEnds().

{
int aCount = 0, tCount = 0;
int i;
char c;
for (i=0; i<size; ++i)
    {
    c = s[i];
    if (c == 'a') ++aCount;
    if (c == 't') ++tCount;
    }
if (tCount > aCount) aCount = tCount;
if (aCount >= size)
    return aCount-1;
else if (aCount >= size*0.75)
    return aCount * 0.90;
else
    return 0;
}

Here is the caller graph for this function:

static struct ffAli* bandedExtend	(	struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 462 of file ffSeedExtend.c.

References axtScoreSchemeRnaDefault(), bandExtAfter(), bandExtBefore(), dnaSeq::dna, foldInExtras(), dnaSeq::size, and ss.

Referenced by refineBundle().

{
struct ffAli *extraList = NULL, *ff = ffList, *lastFf = NULL;
struct axtScoreScheme *ss = axtScoreSchemeRnaDefault();
int qGap, tGap;

if (ff == NULL)
    return NULL;

/* Look for initial gap. */
qGap = ff->nStart - qSeq->dna;
tGap = ff->hStart - tSeq->dna;
bandExtBefore(ss, ff, qGap, tGap, &extraList);

/* Look for middle gaps. */
for (;;)
    {
    lastFf = ff;
    ff = ff->right;
    if (ff == NULL)
        break;
    qGap = ff->nStart - lastFf->nEnd;
    tGap = ff->hStart - lastFf->hEnd;
    bandExtAfter(ss, lastFf, qGap, tGap, &extraList);
    bandExtBefore(ss, ff, qGap, tGap, &extraList);
    }

/* Look for end gaps. */
qGap = qSeq->dna + qSeq->size - lastFf->nEnd;
tGap = tSeq->dna + tSeq->size - lastFf->hEnd;
bandExtAfter(ss, lastFf, qGap, tGap, &extraList);

ffList = foldInExtras(qSeq, tSeq, ffList, extraList);
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void bandExtAfter	(	struct axtScoreScheme *	ss,
		struct ffAli *	ff,
		int	qGap,
		int	tGap,
		struct ffAli **	pExtraList
	)			[static]

Definition at line 443 of file ffSeedExtend.c.

References bandExtFf(), ffCat(), ffAli::hEnd, maxGap, min, ffAli::nEnd, and ss.

Referenced by bandedExtend(), and findFromSmallerSeeds().

{
struct ffAli *ext;
int minGap = min(qGap, tGap);
int maxGap = minGap * 2;
if (minGap > 0)
    {
    if (qGap > maxGap) qGap = maxGap;
    if (tGap > maxGap) tGap = maxGap;
    ext = bandExtFf(NULL, ss, 3, ff, ff->nEnd, ff->nEnd + qGap,
            ff->hEnd, ff->hEnd + tGap, 1, maxGap);
    ffCat(pExtraList, &ext);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void bandExtBefore	(	struct axtScoreScheme *	ss,
		struct ffAli *	ff,
		int	qGap,
		int	tGap,
		struct ffAli **	pExtraList
	)			[static]

Definition at line 425 of file ffSeedExtend.c.

References bandExtFf(), ffCat(), ffAli::hStart, maxGap, min, ffAli::nStart, and ss.

Referenced by bandedExtend(), and findFromSmallerSeeds().

{
struct ffAli *ext;
int minGap = min(qGap, tGap);
int maxGap = minGap * 2;
if (minGap > 0)
    {
    if (qGap > maxGap) qGap = maxGap;
    if (tGap > maxGap) tGap = maxGap;
    ext = bandExtFf(NULL, ss, 3, ff, ff->nStart - qGap, ff->nStart, 
            ff->hStart - tGap, ff->hStart, -1, maxGap);
    ffCat(pExtraList, &ext);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int calcSpliceScore	(	struct axtScoreScheme *	ss,
		char	a1,
		char	a2,
		char	b1,
		char	b2,
		int	orientation
	)			[static]

Definition at line 799 of file ffSeedExtend.c.

References matchScore, and ss.

Referenced by hardRefineSplice().

{
int score = 0;
int matchScore = ss->matrix['c']['c'];
if (orientation >= 0)  /* gt/ag or gc/ag */
    {
    score += ss->matrix[(int)a1]['g'];
    if (a2 != 'c')
        score += ss->matrix[(int)a2]['t'];
    score += ss->matrix[(int)b1]['a'];
    score += ss->matrix[(int)b2]['g'];
    }
else                   /* ct/ac or ct/gc */
    {
    score += ss->matrix[(int)a1]['c'];
    score += ss->matrix[(int)a2]['t'];
    if (b1 != 'g')
        score += ss->matrix[(int)b1]['a'];
    score += ss->matrix[(int)b2]['c'];
    }
if (score >= 3* matchScore)
    score += matchScore;
return score;
}

Here is the caller graph for this function:

static void clumpToExactRange	(	struct gfClump *	clump,
		bioSeq *	qSeq,
		int	tileSize,
		int	frame,
		struct trans3 *	t3,
		struct gfRange **	pRangeList
	)			[static]

Definition at line 206 of file ffSeedExtend.c.

References AllocVar, cloneString(), dnaSeq::dna, extendExactLeft(), extendExactRight(), FALSE, gfRange::frame, gfRange::hitCount, gfClump::hitList, internalErr, dnaSeq::name, gfHit::next, gfRange::qEnd, gfRange::qStart, gfHit::qStart, gfSeqSource::seq, dnaSeq::size, slAddHead, gfSeqSource::start, gfRange::t3, gfClump::target, gfRange::tEnd, gfRange::tName, TRUE, gfRange::tSeq, gfRange::tStart, and gfHit::tStart.

Referenced by ffSeedExtInMem().

{
struct gfSeqSource *target = clump->target;
aaSeq *tSeq = target->seq;
BIOPOL *qs, *ts, *qe, *te;
struct gfHit *hit;
int qStart = 0, tStart = 0, qEnd = 0, tEnd = 0, newQ = 0, newT = 0;
boolean outOfIt = TRUE;         /* Logically outside of a clump. */
struct gfRange *range;
BIOPOL *lastQs = NULL, *lastQe = NULL, *lastTs = NULL, *lastTe = NULL;

if (tSeq == NULL)
    internalErr();

/* The termination condition of this loop is a little complicated.
 * We want to output something either when the next hit can't be
 * merged into the previous, or at the end of the list.  To avoid
 * duplicating the output code we're forced to complicate the loop
 * termination logic.  Hence the check for hit == NULL to break
 * the loop is not until near the end of the loop. */
for (hit = clump->hitList; ; hit = hit->next)
    {
    if (hit != NULL)
        {
        newQ = hit->qStart;
        newT = hit->tStart - target->start;
        }

    /* See if it's time to output merged (diagonally adjacent) hits. */
    if (!outOfIt)       /* Not first time through. */
        {
        /* As a micro-optimization handle strings of adjacent hits
         * specially.  Don't do the extensions until we've merged
         * all adjacent hits. */
        if (hit == NULL || newQ != qEnd || newT != tEnd)
            {
            qs = qSeq->dna + qStart;
            ts = tSeq->dna + tStart;
            qe = qSeq->dna + qEnd;
            te = tSeq->dna + tEnd;
            extendExactRight(qSeq->size - qEnd, tSeq->size - tEnd,
                &qe, &te);
            extendExactLeft(qStart, tStart, &qs, &ts);
            if (qs != lastQs || ts != lastTs || qe != lastQe || qs !=  lastQs)
                {
                lastQs = qs;
                lastTs = ts;
                lastQe = qe;
                lastTe = te;
                AllocVar(range);
                range->qStart = qs - qSeq->dna;
                range->qEnd = qe - qSeq->dna;
                range->tName = cloneString(tSeq->name);
                range->tSeq = tSeq;
                range->tStart = ts - tSeq->dna;
                range->tEnd = te - tSeq->dna;
                range->hitCount = qe - qs;
                range->frame = frame;
                range->t3 = t3;
                slAddHead(pRangeList, range);
                }
            outOfIt = TRUE;
            }
        }
    if (hit == NULL)
        break;

    if (outOfIt)
        {
        qStart = newQ;
        qEnd = qStart + tileSize;
        tStart = newT;
        tEnd = tStart + tileSize;
        outOfIt = FALSE;
        }
    else
        {
        qEnd = newQ + tileSize;
        tEnd = newT + tileSize;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int countA	(	char *	s,
		int	size
	)			[static]

Definition at line 682 of file ffSeedExtend.c.

Referenced by scanTinyOne().

{
int count = 0;
int i;
for (i=size-1; i >= 0; --i)
    {
    if (s[i] == 'a')
        ++count;
    else
        break;
    }
return count;
}

Here is the caller graph for this function:

static int countT	(	char *	s,
		int	size
	)			[static]

Definition at line 670 of file ffSeedExtend.c.

Referenced by scanTinyOne().

{
int i;
for (i=0; i<size; ++i)
    {
    if (s[i] != 't')
        break;
    }
return i;
}

Here is the caller graph for this function:

static struct ffAli* expandGapless	(	struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 501 of file ffSeedExtend.c.

References dnaSeq::dna, extendGaplessLeft(), extendGaplessRight(), ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ffAli::nStart, ffAli::right, and dnaSeq::size.

Referenced by refineBundle().

{
struct ffAli *ff = ffList, *lastFf = NULL;
char *nStart = qSeq->dna;
char *nEnd = qSeq->dna + qSeq->size;
char *hStart = tSeq->dna;
char *hEnd = tSeq->dna + tSeq->size;

/* Look for initial gap. */
extendGaplessLeft(ff->nStart - nStart, ff->hStart - hStart, 
        9, &ff->nStart, &ff->hStart);

/* Look for middle gaps. */
for (;;)
    {
    lastFf = ff;
    ff = ff->right;
    if (ff == NULL)
        break;
    extendGaplessRight(nEnd - lastFf->nEnd, hEnd - lastFf->hEnd, 9, 
        &lastFf->nEnd, &lastFf->hEnd);
    extendGaplessLeft(ff->nStart - nStart, ff->hStart - hStart, 9, 
        &ff->nStart, &ff->hStart);
    }
extendGaplessRight(nEnd - lastFf->nEnd,
        hEnd - lastFf->hEnd, 9,
        &lastFf->nEnd, &lastFf->hEnd);
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void extendExactLeft	(	int	qMax,
		int	tMax,
		char **	pStartQ,
		char **	pStartT
	)			[static]

Definition at line 35 of file ffSeedExtend.c.

References min.

Referenced by clumpToExactRange(), and ffFindExtendNmers().

{
int last = min(qMax, tMax);
int i;
char *q = *pStartQ - 1, *t = *pStartT - 1;

for (i=0; i<last; ++i)
    {
    if (*q != *t)
        break;
    q -= 1;
    t -= 1;
    }
*pStartQ = q + 1;
*pStartT = t + 1;
}

Here is the caller graph for this function:

static void extendExactRight	(	int	qMax,
		int	tMax,
		char **	pEndQ,
		char **	pEndT
	)			[static]

Definition at line 17 of file ffSeedExtend.c.

References min.

Referenced by clumpToExactRange(), and ffFindExtendNmers().

{
int last = min(qMax, tMax);
int i;
char *q = *pEndQ, *t = *pEndT;

for (i=0; i<last; ++i)
    {
    if (*q != *t)
        break;
    q += 1;
    t += 1;
    }
*pEndQ = q;
*pEndT = t;
}

Here is the caller graph for this function:

static void extendGaplessLeft	(	int	qMax,
		int	tMax,
		int	maxDrop,
		char **	pStartQ,
		char **	pStartT
	)			[static]

Definition at line 85 of file ffSeedExtend.c.

References min.

Referenced by expandGapless().

{
int score = 0, bestScore = -1, bestPos = 0;
int last = -min(qMax, tMax);
int i;
char *q = *pStartQ, *t = *pStartT;

for (i=-1; i>=last; --i)
    {
    if (q[i] == t[i])
        {
        ++score;
        if (score > bestScore)
            {
            bestScore = score;
            bestPos = i;
            }
        }
    else
        {
        score -= 3;
        if (bestScore - score >= maxDrop)
            break;
        }
    }
*pStartQ = q+bestPos;
*pStartT = t+bestPos;
}

Here is the caller graph for this function:

static void extendGaplessRight	(	int	qMax,
		int	tMax,
		int	maxDrop,
		char **	pEndQ,
		char **	pEndT
	)			[static]

Definition at line 53 of file ffSeedExtend.c.

References min.

Referenced by expandGapless().

{
int last = min(qMax, tMax);
int i;
char *q = *pEndQ, *t = *pEndT;
int score = 0, bestScore = -1, bestPos = -1;

for (i=0; i<last; ++i)
    {
    if (q[i] == t[i])
        {
        ++score;
        if (score > bestScore)
            {
            bestScore = score;
            bestPos = i;
            }
        }
    else
        {
        score -= 3;
        if (bestScore - score >= maxDrop)
            break;
        }
    }
++bestPos;
*pEndQ = q+bestPos;
*pEndT = t+bestPos;
}

Here is the caller graph for this function:

static struct ffAli* ffFindExtendNmers	(	char *	nStart,
		char *	nEnd,
		char *	hStart,
		char *	hEnd,
		int	seedSize
	)			[static, read]

Definition at line 155 of file ffSeedExtend.c.

References AllocVar, extendExactLeft(), extendExactRight(), ffHashFuncN(), lm, lmAllocArray, lmAllocVar, lmInit(), seqHashEl::next, seqHashEl::seq, slAddHead, and totalDegenerateN().

Referenced by findFromSmallerSeeds().

{
struct lm *lm = lmInit(32*1024);
struct seqHashEl **hashTable, *hashEl, **hashSlot;
struct ffAli *ffList = NULL, *ff;
char *n = nStart, *h = hStart, *ne = nEnd - seedSize, *he = hEnd - seedSize;

/* Hash the needle. */
lmAllocArray(lm, hashTable, 4*1024);
while (n <= ne)
    {
    if (!totalDegenerateN(n, seedSize))
        {
        hashSlot = ffHashFuncN(n, seedSize) + hashTable;
        lmAllocVar(lm, hashEl);
        hashEl->seq = n;
        slAddHead(hashSlot, hashEl);
        }
    ++n;
    }

/* Scan the haystack adding hits. */
while (h <= he)
    {
    for (hashEl = hashTable[ffHashFuncN(h, seedSize)]; 
        hashEl != NULL; hashEl = hashEl->next)
        {
        if (memcmp(hashEl->seq, h, seedSize) == 0)
            {
            AllocVar(ff);
            ff->hStart = h;
            ff->hEnd = h + seedSize;
            ff->nStart = hashEl->seq;
            ff->nEnd = hashEl->seq + seedSize;
            extendExactLeft(ff->nStart - nStart, ff->hStart - hStart, 
                &ff->nStart, &ff->hStart);
            extendExactRight(nEnd - ff->nEnd, hEnd - ff->hEnd, &ff->nEnd, &ff->hEnd);
            ff->left = ffList;
            ffList = ff;
            }
        }
    ++h;
    }
ffList = ffMakeRightLinks(ffList);
ffList = ffMergeClose(ffList, nStart, hStart);
lmCleanup(&lm);
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int ffHashFuncN	(	char *	s,
		int	seedSize
	)			[static]

Definition at line 116 of file ffSeedExtend.c.

References ntVal.

Referenced by ffFindExtendNmers().

{
int acc = 0;
int i;
for (i=0; i<seedSize; ++i)
    {
    acc <<= 1;
    acc += ntVal[(int)s[i]];
    }
return acc&0xfff;
}

Here is the caller graph for this function:

struct ssBundle* ffSeedExtInMem	(	struct genoFind *	gf,
		struct dnaSeq *	qSeq,
		Bits *	qMaskBits,
		int	qOffset,
		struct lm *	lm,
		int	minScore,
		boolean	isRc
	)			[read]

Definition at line 1251 of file ffSeedExtend.c.

References AllocVar, clumpToExactRange(), FALSE, ffCdna, ffIntronMax, gfClumpFreeList(), gfFindClumpsWithQmask(), gfRangeCmpTarget(), gfRangeFreeList(), gfRangesBundle(), gfRangesToFfItem(), lm, gfClump::next, rangeList, refineBundle(), slAddHead, slSort(), ssStitch(), genoFind::tileSize, and TRUE.

{
struct ssBundle *bunList = NULL, *bun;
int hitCount;
struct gfClump *clumpList, *clump;
struct gfRange *rangeList = NULL, *range;
struct dnaSeq *tSeq;

clumpList = gfFindClumpsWithQmask(gf, qSeq, qMaskBits, qOffset, lm, &hitCount);
for (clump = clumpList; clump != NULL; clump = clump->next)
    clumpToExactRange(clump, qSeq, gf->tileSize, 0, NULL, &rangeList);
slSort(&rangeList, gfRangeCmpTarget);
rangeList = gfRangesBundle(rangeList, ffIntronMax);
for (range = rangeList; range != NULL; range = range->next)
    {
    range->qStart += qOffset;
    range->qEnd += qOffset;
    tSeq = range->tSeq;
    AllocVar(bun);
    bun->qSeq = qSeq;
    bun->genoSeq = tSeq;
    bun->ffList = gfRangesToFfItem(range->components, qSeq);
    bun->isProt = FALSE;
    bun->avoidFuzzyFindKludge = TRUE;
    ssStitch(bun, ffCdna, 16, 10);
    refineBundle(gf, qSeq, qMaskBits, qOffset, tSeq, lm, bun, isRc);
    slAddHead(&bunList, bun);
    }
gfRangeFreeList(&rangeList);
gfClumpFreeList(&clumpList);
return bunList;
}

Here is the call graph for this function:

static struct ffAli* fillInExact	(	char *	nStart,
		char *	nEnd,
		char *	hStart,
		char *	hEnd,
		boolean	isRc,
		boolean	scanLeft,
		boolean	scanRight,
		int	resolveLimit
	)			[static, read]

Definition at line 591 of file ffSeedExtend.c.

References AllocVar, min, scanExactLeft(), and scanExactRight().

Referenced by scanForTinyInternal(), and scanTinyOne().

{
struct ffAli *ff = NULL;
char *hPos = NULL;
int nGap = nEnd - nStart;
int hGap = hEnd - hStart;
int minGap = min(nGap, hGap);

if (minGap <= 2)
    return NULL;
if (scanLeft)
    {
    if ((hPos = scanExactLeft(nStart, nGap, hGap, hEnd, resolveLimit)) != NULL)
        {
        AllocVar(ff);
        ff->nStart = nStart;
        ff->nEnd = nEnd;
        ff->hStart = hPos;
        ff->hEnd = hPos + nGap;
        return ff;
        }
    }
else
    {
    if ((hPos = scanExactRight(nStart, nGap, hGap, hStart, resolveLimit)) != NULL)
        {
        AllocVar(ff);
        ff->nStart = nStart;
        ff->nEnd = nEnd;
        ff->hStart = hPos;
        ff->hEnd = hPos + nGap;
        return ff;
        }
    }
return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* findFromSmallerSeeds	(	char *	nStart,
		char *	nEnd,
		char *	hStart,
		char *	hEnd,
		boolean	isRc,
		boolean	scanLeft,
		boolean	scanRight,
		int	seedSize,
		int	resolveLimit
	)			[static, read]

Definition at line 633 of file ffSeedExtend.c.

References axtScoreSchemeRnaDefault(), bandExtAfter(), bandExtBefore(), ffCat(), ffFindExtendNmers(), ffAli::right, seedResolvePower(), and ss.

Referenced by scanTinyOne().

{
int nGap = nEnd - nStart;
if (nGap >= seedSize)
    {
    struct ffAli *ffList;
    if (scanLeft || scanRight)
        {
        int hGap = hEnd - hStart;
        int maxSize = seedResolvePower(seedSize, resolveLimit);
        if (hGap > maxSize) hGap = maxSize;
        if (scanLeft)
            hStart = hEnd - hGap;
        if (scanRight)
            hEnd = hStart + hGap;
        }
    ffList = ffFindExtendNmers(nStart, nEnd, hStart, hEnd, seedSize);
    if (ffList != NULL)
        {
        struct ffAli *extensions = NULL, *ff;
        struct axtScoreScheme *ss = axtScoreSchemeRnaDefault();
        for (ff = ffList; ff != NULL; ff = ff->right)
            {
            bandExtBefore(ss, ff, ff->nStart - nStart, ff->hStart - hStart, &extensions);
            bandExtAfter(ss, ff, nEnd - ff->nEnd, hEnd - ff->hEnd, &extensions);
            }
        ffCat(&ffList, &extensions);
        }

    return ffList;
    }
return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* foldInExtras	(	struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli *	ffList,
		struct ffAli *	extraList
	)			[static, read]

Definition at line 314 of file ffSeedExtend.c.

References AllocVar, ssBundle::avoidFuzzyFindKludge, ssFfItem::ff, ffCdna, ssBundle::ffList, ssBundle::genoSeq, ssBundle::qSeq, slAddHead, ssBundleFree(), ssStitch(), and TRUE.

Referenced by bandedExtend(), scanForSmallerExons(), scanForTinyInternal(), and scanIndexForSmallExons().

{
if (extraList != NULL)
    {
    struct ssBundle *bun;
    struct ssFfItem *ffi;
    AllocVar(bun);
    bun->qSeq = qSeq;
    bun->genoSeq = tSeq;
    bun->avoidFuzzyFindKludge = TRUE;
    AllocVar(ffi);
    ffi->ff = ffList;
    slAddHead(&bun->ffList, ffi);
    AllocVar(ffi);
    ffi->ff = extraList;
    slAddHead(&bun->ffList, ffi);
    ssStitch(bun, ffCdna, 16, 1);
    if (bun->ffList != NULL)
        {
        ffList = bun->ffList->ff;
        bun->ffList->ff = NULL;
        }
    else
        {
        ffList = NULL;
        }
    ssBundleFree(&bun);
    }
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void grabAroundIntron	(	char *	hpStart,
		int	iPos,
		int	iSize,
		int	modPeelSize,
		char *	hSeq
	)			[static]

Definition at line 826 of file ffSeedExtend.c.

Referenced by hardRefineSplice().

{
memcpy(hSeq, hpStart, iPos);
memcpy(hSeq+iPos, hpStart+iPos+iSize, modPeelSize - iPos);
hSeq[modPeelSize] = 0;
}

Here is the caller graph for this function:

static struct ffAli* hardRefineSplice	(	struct ffAli *	left,
		struct ffAli *	right,
		struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli *	ffList,
		int	orientation
	)			[static, read]

Definition at line 857 of file ffSeedExtend.c.

References AllocVar, ArraySize, axtScoreSchemeRnaDefault(), axtScoreSym(), bandExt(), calcSpliceScore(), grabAroundIntron(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ffAli::nStart, ffAli::right, ss, TRUE, and verbose().

Referenced by refineSpliceSites().

{
/* Strategy: peel back about 6 bases on either side of intron.
 * Then try positioning the intron at each position in the
 * peeled area and assessing score. */
int peelSize = 12;
char nSeq[12+1], hSeq[12+1+1];
char nSym[25], hSym[25];
int symCount;
int seqScore, spliceScore, score, maxScore = 0;
int nGap = right->nStart - left->nEnd;
int hGap = right->hStart - left->hEnd;
int peelLeft = (peelSize - nGap)/2;
int intronSize = hGap - nGap;
char *npStart = left->nEnd - peelLeft;
char *npEnd = npStart + peelSize;
char *hpStart = left->hEnd - peelLeft;
char *hpEnd = npEnd + (right->hStart - right->nStart);
struct axtScoreScheme *ss = axtScoreSchemeRnaDefault();
static int modSize[3] = {0, 1, -1};
int modIx;
int bestPos = -1, bestMod = 0;
int iPos;

memcpy(nSeq, npStart, peelSize);
nSeq[peelSize] = 0;
for (modIx=0; modIx < ArraySize(modSize); ++modIx)
    {
    int modOne = modSize[modIx];
    int modPeelSize = peelSize - modOne;
    int iSize = intronSize + modOne;
    for (iPos=0; iPos <= modPeelSize; iPos++)
        {
        grabAroundIntron(hpStart, iPos, iSize, modPeelSize, hSeq);
        if (bandExt(TRUE, ss, 2, nSeq, peelSize, hSeq, modPeelSize, 1,
                sizeof(hSym), &symCount, nSym, hSym, NULL, NULL))
            {
            seqScore = axtScoreSym(ss, symCount, nSym, hSym);
            spliceScore = calcSpliceScore(ss, hpStart[iPos], hpStart[iPos+1],
                    hpStart[iPos+iSize-2], hpStart[iPos+iSize-1], orientation);
            score = seqScore + spliceScore;
            if (score > maxScore)
                {
                maxScore = score;
                bestPos = iPos;
                bestMod = modOne;
                }
            }
        }
    }
if (maxScore > 0)
    {
    int modPeelSize = peelSize - bestMod;
    int i,diff, cutSymIx = 0;
    int nIx, hIx;
    struct ffAli *ff;

    /* Regenerate the best alignment. */
    grabAroundIntron(hpStart, bestPos, intronSize + bestMod, modPeelSize, hSeq); 
    bandExt(TRUE, ss, 2, nSeq, peelSize, hSeq, modPeelSize, 1,
            sizeof(hSym), &symCount, nSym, hSym, NULL, NULL);

    /* Peel back surrounding ffAli's */
    if (left->nStart > npStart || right->nEnd < npEnd)
        {
        /* It would take a lot of code to handle this case. 
         * I believe it is rare enough that it's not worth
         * it.  This verbosity will help keep track of how
         * often it comes up. */
        verbose(2, "Unable to peel in hardRefineSplice\n");
        return ffList;
        }
    diff = left->nEnd - npStart;
    left->nEnd -= diff;
    left->hEnd -= diff;
    diff = right->nStart - npEnd;
    right->nStart -= diff;
    right->hStart -= diff;

    /* Step through base by base alignment from the left until
     * hit intron, converting it into ffAli format. */
    nIx = hIx = 0;
    ff = left;
    for (i=0; i<symCount; ++i)
        {
        if (hIx == bestPos)
            {
            cutSymIx = i;
            break;
            }
        if (hSym[i] == '-')
            {
            ff = NULL;
            nIx += 1;
            }
        else if (nSym[i] == '-')
            {
            ff = NULL;
            hIx += 1;
            }
        else
            {
            if (ff == NULL)
                {
                AllocVar(ff);
                ff->left = left;
                ff->right = right;
                left->right = ff;
                right->left = ff;
                left = ff;
                ff->nStart = ff->nEnd = npStart + nIx;
                ff->hStart = ff->hEnd = hpStart + hIx;
                }
            ++nIx;
            ++hIx;
            ff->nEnd += 1;
            ff->hEnd += 1;
            }
        }

    /* Step through base by base alignment from the right until
     * hit intron, converting it into ffAli format. */
    ff = right;
    hIx = nIx = 0;      /* Index from right side. */
    for (i = symCount-1; i >= cutSymIx; --i)
        {
        if (hSym[i] == '-')
            {
            ff = NULL;
            nIx += 1;
            }
        else if (nSym[i] == '-')
            {
            ff = NULL;
            hIx += 1;
            }
        else
            {
            if (ff == NULL)
                {
                AllocVar(ff);
                ff->left = left;
                ff->right = right;
                left->right = ff;
                right->left = ff;
                left = ff;
                ff->nStart = ff->nEnd = npEnd - nIx;
                ff->hStart = ff->hEnd = hpEnd - hIx;
                }
            ++nIx;
            ++hIx;
            ff->nStart -= 1;
            ff->hStart -= 1;
            }
        }
    }
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void refineBundle	(	struct genoFind *	gf,
		struct dnaSeq *	qSeq,
		Bits *	qMaskBits,
		int	qMaskOffset,
		struct dnaSeq *	tSeq,
		struct lm *	lm,
		struct ssBundle *	bun,
		boolean	isRc
	)			[static]

Definition at line 1222 of file ffSeedExtend.c.

References bandedExtend(), expandGapless(), ssFfItem::ff, ffCdna, ssBundle::ffList, gfFindNamedSource(), lm, dnaSeq::name, ssFfItem::next, refineSpliceSites(), scanForSmallerExons(), scanForTinyInternal(), scanIndexForSmallExons(), smoothSmallGaps(), ssStitch(), genoFind::tileSize, and trimFlakyEnds().

Referenced by ffSeedExtInMem().

{
struct ssFfItem *ffi;
struct gfSeqSource *target = gfFindNamedSource(gf, tSeq->name);

/* First do gapless expansions and restitch. */
for (ffi = bun->ffList; ffi != NULL; ffi = ffi->next)
    {
    ffi->ff = expandGapless(qSeq, tSeq, ffi->ff);
    }
ssStitch(bun, ffCdna, 16, 16);

for (ffi = bun->ffList; ffi != NULL; ffi = ffi->next)
    {
    ffi->ff = scanIndexForSmallExons(gf, target, qSeq, qMaskBits, qMaskOffset, 
        tSeq, lm, ffi->ff);
    ffi->ff = bandedExtend(qSeq, tSeq, ffi->ff);
    ffi->ff = scanForSmallerExons(gf->tileSize, qSeq, tSeq, isRc, ffi->ff);
    ffi->ff = refineSpliceSites(qSeq, tSeq, ffi->ff);
    ffi->ff = scanForTinyInternal(qSeq, tSeq, isRc, ffi->ff);
    ffi->ff = smoothSmallGaps(qSeq, tSeq, ffi->ff);
    ffi->ff = trimFlakyEnds(qSeq, tSeq, ffi->ff);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* refineSpliceSites	(	struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 1021 of file ffSeedExtend.c.

References ffIntronOrientation(), ffRemoveEmptyAlis(), ffSlideOrientedIntrons(), hardRefineSplice(), ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ffAli::nStart, ffAli::right, tradeMismatchToCloseSpliceGap(), and TRUE.

Referenced by refineBundle().

{
int orientation = ffIntronOrientation(ffList);
struct ffAli *ff, *nextFf;
if (orientation == 0)
    return ffList;
if (ffSlideOrientedIntrons(ffList, orientation))
    ffList = ffRemoveEmptyAlis(ffList, TRUE);
for (ff = ffList; ff != NULL; ff = nextFf)
    {
    int nGap, hGap;
    if ((nextFf = ff->right) == NULL)
        break;
    nGap = nextFf->nStart - ff->nEnd;
    hGap = nextFf->hStart - ff->hEnd;
    if (nGap > 0 && nGap <= 6 && hGap >= 30)
        {
        if (nGap == 1)
            {
            if (tradeMismatchToCloseSpliceGap(ff, nextFf, orientation))
                continue;
            }
        ffList = hardRefineSplice(ff, nextFf, qSeq, tSeq, ffList, orientation);
        }
    }
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static char* scanExactLeft	(	char *	n,
		int	nSize,
		int	hSize,
		char *	hEnd,
		int	resolveLimit
	)			[static]

Definition at line 547 of file ffSeedExtend.c.

References ffAli::hStart, and seedResolvePower().

Referenced by fillInExact().

{
/* Optimize a little by comparing the first character inline. */
char n1 = *n++;
char *hStart;
int maxSize = seedResolvePower(nSize, resolveLimit);

if (hSize > maxSize) hSize = maxSize;
nSize -= 1;
hStart = hEnd - hSize;

hEnd -= nSize;
while (hEnd >= hStart)
    {
    if (n1 == *hEnd && memcmp(n, hEnd+1, nSize) == 0)
        return hEnd;
    hEnd -= 1;
    }
return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static char* scanExactRight	(	char *	n,
		int	nSize,
		int	hSize,
		char *	hStart,
		int	resolveLimit
	)			[static]

Definition at line 569 of file ffSeedExtend.c.

References ffAli::hEnd, and seedResolvePower().

Referenced by fillInExact().

{
/* Optimize a little by comparing the first character inline. */
char n1 = *n++;
char *hEnd;
int maxSize = seedResolvePower(nSize, resolveLimit);

if (hSize > maxSize) hSize = maxSize;
hEnd = hStart + hSize;
nSize -= 1;

hEnd -= nSize;
while (hStart <= hEnd)
    {
    if (n1 == *hStart && memcmp(n, hStart+1, nSize) == 0)
        return hStart;
    hStart += 1;
    }
return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* scanForSmallerExons	(	int	seedSize,
		struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		boolean	isRc,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 718 of file ffSeedExtend.c.

References dnaSeq::dna, FALSE, ffCat(), foldInExtras(), scanTinyOne(), dnaSeq::size, and TRUE.

Referenced by refineBundle().

{
struct ffAli *extraList = NULL, *ff = ffList, *lastFf = NULL, *newFf;

if (ff == NULL)
    return NULL;

/* Look for initial gap. */
newFf = scanTinyOne(qSeq->dna, ff->nStart, tSeq->dna, ff->hStart, 
        isRc, TRUE, FALSE, seedSize); 
ffCat(&extraList, &newFf);

/* Look for middle gaps. */
for (;;)
    {
    lastFf = ff;
    ff = ff->right;
    if (ff == NULL)
        break;
    newFf = scanTinyOne(lastFf->nEnd, ff->nStart, lastFf->hEnd, ff->hStart, 
        isRc, FALSE, FALSE, seedSize);
    ffCat(&extraList, &newFf);
    }

/* Look for end gaps. */
newFf = scanTinyOne(lastFf->nEnd, qSeq->dna + qSeq->size, 
        lastFf->hEnd, tSeq->dna + tSeq->size, isRc, FALSE, TRUE, seedSize);
ffCat(&extraList, &newFf);

ffList = foldInExtras(qSeq, tSeq, ffList, extraList);
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* scanForTinyInternal	(	struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		boolean	isRc,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 754 of file ffSeedExtend.c.

References FALSE, ffCat(), fillInExact(), foldInExtras(), and ffAli::right.

Referenced by refineBundle().

{
struct ffAli *extraList = NULL, *ff = ffList, *lastFf = NULL, *newFf;

if (ff == NULL)
    return NULL;

/* Look for middle gaps. */
for (;;)
    {
    lastFf = ff;
    ff = ff->right;
    if (ff == NULL)
        break;
    newFf = fillInExact(lastFf->nEnd, ff->nStart, lastFf->hEnd, ff->hStart, isRc, 
        FALSE, FALSE, 0);
    ffCat(&extraList, &newFf);
    }

ffList = foldInExtras(qSeq, tSeq, ffList, extraList);
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* scanIndexForSmallExons	(	struct genoFind *	gf,
		struct gfSeqSource *	target,
		struct dnaSeq *	qSeq,
		Bits *	qMaskBits,
		int	qMaskOffset,
		struct dnaSeq *	tSeq,
		struct lm *	lm,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 348 of file ffSeedExtend.c.

References addExtraHits(), dnaSeq::dna, ffIntronMax, ffMakeRightLinks(), foldInExtras(), gfFindHitsInRegion(), ffAli::hEnd, lm, ffAli::nEnd, ffAli::nStart, ffAli::right, dnaSeq::size, genoFind::tileSize, tileSize, and ZeroVar.

Referenced by refineBundle().

{
int qGap, tGap, tStart, qStart;
struct ffAli *lastFf = NULL, *ff = ffList;
struct gfHit *hitList = NULL;
struct dnaSeq qSubSeq;
struct ffAli *extraList = NULL;
int tileSize = gf->tileSize;
int biggestToFind = 200;        /* Longer should be found at an earlier stage */

/* Handle problematic empty case immediately. */
if (ffList == NULL)
    return NULL;

ZeroVar(&qSubSeq);

/* Look for initial gap. */
qGap = ff->nStart - qSeq->dna;
tGap = ff->hStart - tSeq->dna;
if (qGap >= tileSize && qGap <= biggestToFind && tGap >= tileSize)
    {
    tStart = ff->hStart - tSeq->dna;
    if (tGap > ffIntronMax) 
        {
        tGap = ffIntronMax;
        }
    qSubSeq.dna = qSeq->dna;
    qSubSeq.size = qGap;
    hitList = gfFindHitsInRegion(gf, &qSubSeq, qMaskBits, qMaskOffset,
        lm, target, tStart - tGap, tStart);
    addExtraHits(hitList, tileSize, &qSubSeq, tSeq, &extraList);
    }

/* Look for middle gaps. */
for (;;)
    {
    lastFf = ff;
    ff = ff->right;
    if (ff == NULL)
        break;
    qGap = ff->nStart - lastFf->nEnd;
    tGap = ff->hStart - lastFf->hEnd;
    if (qGap >= tileSize && qGap <= biggestToFind && tGap >= tileSize)
         {
         qStart = lastFf->nEnd - qSeq->dna;
         tStart = lastFf->hEnd - tSeq->dna;
         qSubSeq.dna = lastFf->nEnd;
         qSubSeq.size = qGap;
         hitList = gfFindHitsInRegion(gf, &qSubSeq, qMaskBits, qMaskOffset + qStart, 
                lm, target, tStart, tStart + tGap);
         addExtraHits(hitList, tileSize, &qSubSeq, tSeq, &extraList);
         }
    }

/* Look for end gaps. */
qGap = qSeq->dna + qSeq->size - lastFf->nEnd;
tGap = tSeq->dna + tSeq->size - lastFf->hEnd;
if (qGap >= tileSize && qGap < biggestToFind && tGap >= tileSize)
    {
    if (tGap > ffIntronMax) tGap = ffIntronMax;
    qStart = lastFf->nEnd - qSeq->dna;
    tStart = lastFf->hEnd - tSeq->dna;
    qSubSeq.dna = lastFf->nEnd;
    qSubSeq.size = qGap;
    hitList = gfFindHitsInRegion(gf, &qSubSeq, qMaskBits, qMaskOffset + qStart, 
                lm, target, tStart, tStart + tGap);
    addExtraHits(hitList, tileSize, &qSubSeq, tSeq, &extraList);
    }
extraList = ffMakeRightLinks(extraList);
ffList = foldInExtras(qSeq, tSeq, ffList, extraList);
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct ffAli* scanTinyOne	(	char *	nStart,
		char *	nEnd,
		char *	hStart,
		char *	hEnd,
		boolean	isRc,
		boolean	scanLeft,
		boolean	scanRight,
		int	seedSize
	)			[read]

Definition at line 697 of file ffSeedExtend.c.

References countA(), countT(), fillInExact(), and findFromSmallerSeeds().

Referenced by scanForSmallerExons().

{
struct ffAli *ff;
int nGap = nEnd - nStart;
if (nGap > 80)          /* The index should have found things this big already. */
    return NULL;
if (scanLeft && isRc)
    nStart += countT(nStart, nGap);
if (scanRight && !isRc)
    nEnd -= countA(nStart, nGap);
ff = fillInExact(nStart, nEnd, hStart, hEnd, isRc, scanLeft, scanRight, 3);
if (ff != NULL)
    {
    return ff;
    }
return findFromSmallerSeeds(nStart, nEnd, hStart, hEnd, isRc,
        scanLeft, scanRight, seedSize, 3);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int seedResolvePower	(	int	seedSize,
		int	resolveLimit
	)			[static]

Definition at line 534 of file ffSeedExtend.c.

References ffIntronMax.

Referenced by findFromSmallerSeeds(), scanExactLeft(), and scanExactRight().

{
int res;
if (seedSize >= 14)     /* Avoid int overflow */
    return ffIntronMax;
res  = (1 << (seedSize+seedSize-resolveLimit));
if (res > ffIntronMax)
    res = ffIntronMax;
return res;
}

Here is the caller graph for this function:

static boolean smoothOneGap	(	struct ffAli *	left,
		struct ffAli *	right,
		struct ffAli *	ffList
	)			[static]

Definition at line 1053 of file ffSeedExtend.c.

References axtScoreSchemeRnaDefault(), axtScoreSym(), bandExt(), FALSE, ffAliFromSym(), ffCalcCdnaGapPenalty(), ffRightmost(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ffAli::nStart, ffAli::right, ss, and TRUE.

Referenced by smoothSmallGaps().

{
int nGap = right->nStart - left->nEnd;
int hGap = right->hStart - left->hEnd;
if (nGap > 0 && hGap > 0 && nGap < 10 && hGap < 10)
    {
    int sizeDiff = nGap - hGap;
    if (sizeDiff < 0) sizeDiff = -sizeDiff;
    if (sizeDiff <= 3)
        {
        struct axtScoreScheme *ss = axtScoreSchemeRnaDefault();
        char hSym[20], nSym[20];
        int symCount;
        if (bandExt(TRUE, ss, 3, left->nEnd, nGap, left->hEnd, hGap, 1,
                sizeof(hSym), &symCount, nSym, hSym, NULL, NULL))
            {
            int gapPenalty = -ffCalcCdnaGapPenalty(hGap, nGap) * ss->matrix['a']['a'];
            int score = axtScoreSym(ss, symCount, nSym, hSym);
            if (score >= gapPenalty)
                {
                struct ffAli *l, *r;
                l = ffAliFromSym(symCount, nSym, hSym, NULL, left->nEnd, left->hEnd);
                r = ffRightmost(l);
                left->right = l;
                l->left = left;
                r->right = right;
                right->left = r;
                return TRUE;
                }
            }
        }
    }
return FALSE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* smoothSmallGaps	(	struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 1093 of file ffSeedExtend.c.

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

Referenced by refineBundle().

{
struct ffAli *left = ffList, *right;
boolean smoothed = FALSE;

if (ffList == NULL) return NULL;
for (;;)
    {
    if ((right = left->right) == NULL)
        break;
    if (smoothOneGap(left, right, ffList))
        smoothed = TRUE;
    left = right;
    }
if (smoothed)
    {
    ffList = ffMergeNeedleAlis(ffList, TRUE);
    }
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean totalDegenerateN	(	char *	s,
		int	seedSize
	)			[static]

Definition at line 136 of file ffSeedExtend.c.

References FALSE, and TRUE.

Referenced by ffFindExtendNmers().

{
char c1 = s[0], c2 = s[1];
int i;
if (seedSize & 1)
    {
    seedSize -= 1;
    if (c1 != s[seedSize])
        return FALSE;
    }
for (i=2; i<seedSize; i += 2)
    {
    if (c1 != s[i] || c2 != s[i+1])
        return FALSE;
    }
return TRUE;
}

Here is the caller graph for this function:

static boolean tradeMismatchToCloseSpliceGap	(	struct ffAli *	left,
		struct ffAli *	right,
		int	orientation
	)			[static]

Definition at line 779 of file ffSeedExtend.c.

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

Referenced by refineSpliceSites().

{
if (intronOrientation(left->hEnd+1, right->hStart) == orientation)
    {
    left->hEnd += 1;
    left->nEnd += 1;
    return TRUE;
    }
if (intronOrientation(left->hEnd, right->hStart-1) == orientation)
    {
    right->hStart -= 1;
    right->nStart -= 1;
    return TRUE;
    }
return FALSE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ffAli* trimFlakyEnds	(	struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		struct ffAli *	ffList
	)			[static, read]

Definition at line 1156 of file ffSeedExtend.c.

References aPenalty(), ffAliCount(), ffIntronOrientation(), ffRightmost(), ffScoreMatch(), freeMem(), ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ffAli::nStart, ffAli::right, and trimGapPenalty().

Referenced by refineBundle().

{
int orientation = ffIntronOrientation(ffList);
struct ffAli *left, *right;
char *iStart, *iEnd;
int blockScore, gapPenalty;

/* If one or less block then don't bother. */
if (ffAliCount(ffList) < 2)
    return ffList;

/* Trim beginnings. */
left = ffList;
right = ffList->right;
while (right != NULL)
    {
    blockScore = ffScoreMatch(left->nStart, left->hStart, 
        left->nEnd-left->nStart);
    blockScore -= aPenalty(left->nStart, left->nEnd - left->nStart);
    iStart = left->hEnd;
    iEnd = right->hStart;
    gapPenalty = trimGapPenalty(iEnd-iStart, 
        right->nStart - left->nEnd, iStart, iEnd, orientation);
    if (gapPenalty >= blockScore)
        {
        freeMem(left);
        ffList = right;
        right->left = NULL;
        }
    else
        break;
    left = right;
    right = right->right;
    }

right = ffRightmost(ffList);
if (right == ffList)
    return ffList;
left = right->left;
while (left != NULL)
    {
    blockScore = ffScoreMatch(right->nStart, right->hStart, 
        right->nEnd-right->nStart);
    blockScore -= aPenalty(right->nStart, right->nEnd - right->nStart);
    iStart = left->hEnd;
    iEnd = right->hStart;
    gapPenalty = trimGapPenalty(iEnd-iStart, 
        right->nStart - left->nEnd, iStart, iEnd, orientation);
    if (gapPenalty >= blockScore)
        {
        freeMem(right);
        left->right = NULL;
        }
    else
        break;
    right = left;
    left = left->left;
    }
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int trimGapPenalty	(	int	hGap,
		int	nGap,
		char *	iStart,
		char *	iEnd,
		int	orientation
	)			[static]

Definition at line 1137 of file ffSeedExtend.c.

References ffCalcGapPenalty(), ffCdna, and ffScoreIntron().

Referenced by trimFlakyEnds().

{
int penalty =  ffCalcGapPenalty(hGap, nGap, ffCdna);
if (hGap > 2 || nGap > 2)       /* Not just a local extension. */
                                /* Score gap to favor introns. */
    {
    penalty <<= 1;
    if (nGap > 0)       /* Intron gaps are not in n side at all. */
         penalty += 3;
                        /* Good splice sites give you bonus 2,
                         * bad give you penalty of six. */
    penalty += 6 - 2*ffScoreIntron(iStart[0], iStart[1], 
        iEnd[-2], iEnd[-1], orientation);
    }
return penalty;
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

char const rcsid[] = "$Id: ffSeedExtend.c,v 1.36 2006/06/22 16:24:43 kent Exp $" [static]

Definition at line 15 of file ffSeedExtend.c.

---