jkOwnLib/supStitch.c File Reference

#include "common.h"
#include "dnautil.h"
#include "dlist.h"
#include "fuzzyFind.h"
#include "localmem.h"
#include "patSpace.h"
#include "trans3.h"
#include "supStitch.h"
#include "chainBlock.h"

Include dependency graph for supStitch.c:

Go to the source code of this file.

Data Structures
struct	ssNode
struct	ssEdge
struct	ssGraph
Functions
static void	ssFindBestBig (struct ffAli *ffList, bioSeq *qSeq, bioSeq *tSeq, enum ffStringency stringency, boolean isProt, struct trans3 *t3List, struct ffAli **retBestAli, int *retScore, struct ffAli **retLeftovers)
void	ssFfItemFree (struct ssFfItem **pEl)
void	ssFfItemFreeList (struct ssFfItem **pList)
void	ssBundleFree (struct ssBundle **pEl)
void	ssBundleFreeList (struct ssBundle **pList)
void	dumpNearCrossover (char *what, DNA *n, DNA *h, int size)
void	dumpFf (struct ffAli *left, DNA *needle, DNA *hay)
void	dumpBuns (struct ssBundle *bunList)
static int	bioScoreMatch (boolean isProt, char *a, char *b, int size)
static int	findCrossover (struct ffAli *left, struct ffAli *right, int overlap, boolean isProt)
static void	trans3Offsets (struct trans3 *t3List, AA *startP, AA *endP, int *retStart, int *retEnd)
static boolean	isMonotonic (struct ffAli *left)
static struct ffAli *	forceMonotonic (struct ffAli *aliList, struct dnaSeq *qSeq, struct dnaSeq *tSeq, enum ffStringency stringency, boolean isProt, struct trans3 *t3List)
ffAli *	smallMiddleExons (struct ffAli *aliList, struct ssBundle *bundle, enum ffStringency stringency)
static void	ssGraphFree (struct ssGraph **pGraph)
boolean	tripleCanFollow (struct ffAli *a, struct ffAli *b, aaSeq *qSeq, struct trans3 *t3List)
static struct ssGraph *	ssGraphMake (struct ffAli *ffList, bioSeq *qSeq, enum ffStringency stringency, boolean isProt, struct trans3 *t3List)
static struct ssNode *	ssDynamicProgram (struct ssGraph *graph)
static void	ssGraphFindBest (struct ssGraph *graph, struct ffAli **retBestAli, int *retScore, struct ffAli **retLeftovers)
static void	ssFindBestSmall (struct ffAli *ffList, bioSeq *qSeq, bioSeq *tSeq, enum ffStringency stringency, boolean isProt, struct trans3 *t3List, struct ffAli **retBestAli, int *retScore, struct ffAli **retLeftovers)
static int	ssGapCost (int dq, int dt, void *data)
static int	findOverlap (struct cBlock *a, struct cBlock *b)
static int	ssConnectCost (struct cBlock *a, struct cBlock *b, void *data)
static void	ssFindBest (struct ffAli *ffList, bioSeq *qSeq, bioSeq *tSeq, enum ffStringency stringency, boolean isProt, struct trans3 *t3List, struct ffAli **retBestAli, int *retScore, struct ffAli **retLeftovers)
ffAli *	cutAtBigIntrons (struct ffAli *ffList, int maxIntron, int *pScore, enum ffStringency stringency, struct ffAli **returnLeftovers)
void	ssStitch (struct ssBundle *bundle, enum ffStringency stringency, int minScore, int maxToReturn)
static struct ssBundle *	findBundle (struct ssBundle *list, struct dnaSeq *genoSeq)
ssBundle *	ssFindBundles (struct patSpace *ps, struct dnaSeq *cSeq, char *cName, enum ffStringency stringency, boolean avoidSelfSelf)
Variables
static char const	rcsid [] = "$Id: supStitch.c,v 1.38 2007/04/20 22:43:37 kent Exp $"
static enum ffStringency	ssStringency
static boolean	ssIsProt

---

Function Documentation

static int bioScoreMatch	(	boolean	isProt,
		char *	a,
		char *	b,
		int	size
	)			[static]

Definition at line 111 of file supStitch.c.

References dnaOrAaScoreMatch().

Referenced by ssConnectCost(), ssFindBestBig(), and ssGraphMake().

{
if (isProt)
    {
    return dnaOrAaScoreMatch(a, b, size, 2, -1, 'X');
    }
else
    {
    return dnaOrAaScoreMatch(a, b, size, 1, -1, 'n');
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct ffAli* cutAtBigIntrons	(	struct ffAli *	ffList,
		int	maxIntron,
		int *	pScore,
		enum ffStringency	stringency,
		struct ffAli **	returnLeftovers
	)			[read]

Definition at line 719 of file supStitch.c.

References ffCat(), ffScore(), ffAli::hEnd, ffAli::hStart, ffAli::left, and ffAli::right.

Referenced by ssStitch().

{
struct ffAli *prevFf, *ff, *cutFf = NULL;
prevFf = ffList;
for (ff = prevFf->right; ff != NULL; ff = ff->right)
    {
    int dt = ff->hStart - prevFf->hEnd;
    if (dt > maxIntron)
        {
        cutFf = prevFf;
        break;
        }
    prevFf = ff;
    }
if (cutFf != NULL)
    {
    ff = cutFf->right;
    cutFf->right = NULL;
    ff->left = NULL;
    ffCat(returnLeftovers, &ff);
    *pScore = ffScore(ffList, stringency);
    }
return ffList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void dumpBuns

(

struct ssBundle *

bunList

)

Definition at line 93 of file supStitch.c.

References dnaSeq::dna, dumpFf(), ssFfItem::ff, ssBundle::ffList, ssBundle::genoSeq, ssFfItem::next, ssBundle::next, ssBundle::qSeq, and slCount().

{
struct ssBundle *bun;
struct ssFfItem *ffl;
for (bun = bunList; bun != NULL; bun = bun->next)
    {
    struct dnaSeq *qSeq = bun->qSeq;        /* Query sequence (not owned by bundle.) */
    struct dnaSeq *genoSeq = bun->genoSeq;     /* Genomic sequence (not owned by bundle.) */
    printf("Bundle of %d between %s and %s\n", slCount(bun->ffList), qSeq->name, genoSeq->name);
    for (ffl = bun->ffList; ffl != NULL; ffl = ffl->next)
        {
        dumpFf(ffl->ff, bun->qSeq->dna, bun->genoSeq->dna);
        }
    }
}

Here is the call graph for this function:

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

Definition at line 81 of file supStitch.c.

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

{
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");
}

void dumpNearCrossover	(	char *	what,
		DNA *	n,
		DNA *	h,
		int	size
	)

Definition at line 70 of file supStitch.c.

References mustWrite().

{
printf("%s: ", what);
mustWrite(stdout, n, size);
printf("\n");
printf("%s: ", what);
mustWrite(stdout, h, size);
printf("\n");
}

Here is the call graph for this function:

static struct ssBundle* findBundle	(	struct ssBundle *	list,
		struct dnaSeq *	genoSeq
	)			[static, read]

Definition at line 831 of file supStitch.c.

References ssBundle::genoSeq, and ssBundle::next.

Referenced by ssFindBundles().

{
struct ssBundle *el;
for (el = list; el != NULL; el = el->next)
    if (el->genoSeq == genoSeq)
        return el;
return NULL;
}

Here is the caller graph for this function:

static int findCrossover	(	struct ffAli *	left,
		struct ffAli *	right,
		int	overlap,
		boolean	isProt
	)			[static]

Definition at line 125 of file supStitch.c.

References aaScore2(), aaScoreMatch(), dnaScore2(), dnaScoreMatch(), ffAli::hEnd, ffAli::hStart, and ffAli::nStart.

Referenced by ssConnectCost(), ssFindBestBig(), and ssGraphMake().

{
int bestPos = 0;
char *nStart = right->nStart;
char *lhStart = left->hEnd - overlap;
char *rhStart = right->hStart;
int i;
int (*scoreMatch)(char a, char b);
int score, bestScore;

if (isProt)
    {
    scoreMatch = aaScore2;
    score = bestScore = aaScoreMatch(nStart, rhStart, overlap);
    }
else
    {
    scoreMatch = dnaScore2;
    score = bestScore = dnaScoreMatch(nStart, rhStart, overlap);
    }

for (i=0; i<overlap; ++i)
    {
    char n = nStart[i];
    score += scoreMatch(lhStart[i], n);
    score -= scoreMatch(rhStart[i], n);
    if (score > bestScore)
        {
        bestScore = score;
        bestPos = i+1;
        }
    }
return bestPos;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int findOverlap	(	struct cBlock *	a,
		struct cBlock *	b
	)			[static]

Definition at line 553 of file supStitch.c.

References min, cBlock::qEnd, cBlock::qStart, cBlock::tEnd, and cBlock::tStart.

Referenced by ssConnectCost(), and ssFindBestBig().

{
int dq = b->qStart - a->qEnd;
int dt = b->tStart - a->tEnd;
return -min(dq, dt);
}

Here is the caller graph for this function:

static struct ffAli* forceMonotonic	(	struct ffAli *	aliList,
		struct dnaSeq *	qSeq,
		struct dnaSeq *	tSeq,
		enum ffStringency	stringency,
		boolean	isProt,
		struct trans3 *	t3List
	)			[static, read]

Definition at line 208 of file supStitch.c.

References ffFreeAli(), isMonotonic(), and ssFindBestBig().

Referenced by smallMiddleExons(), ssFindBestSmall(), and ssStitch().

{
if (!isProt)
    {
    if (!isMonotonic(aliList))
        {
        struct ffAli *leftovers = NULL;
        int score;
        ssFindBestBig(aliList, qSeq, tSeq, stringency, isProt, t3List, &aliList, &score,
           &leftovers);
        ffFreeAli(&leftovers);
        }
    }
return aliList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static boolean isMonotonic

(

struct ffAli *

left

)

[static]

Definition at line 189 of file supStitch.c.

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

Referenced by forceMonotonic().

{
struct ffAli *right;

while ((right = left->right) != NULL)
    {
    if (left->nEnd <= right->nStart && left->hEnd <= right->hStart)
        left = right;
    else
        {
        verbose(2, "not monotonic dn %d, dh %d\n", (int)(right->nStart - left->nEnd), 
                (int)(right->hStart - right->hEnd));
        return FALSE;
        }
    }
return TRUE;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct ffAli* smallMiddleExons	(	struct ffAli *	aliList,
		struct ssBundle *	bundle,
		enum ffStringency	stringency
	)			[read]

Definition at line 228 of file supStitch.c.

References ffFind(), ffRightmost(), forceMonotonic(), ssBundle::genoSeq, ffAli::hEnd, ffAli::hStart, ssBundle::isProt, ffAli::left, ffAli::nEnd, ffAli::nStart, ssBundle::qSeq, ffAli::right, and ssBundle::t3List.

Referenced by ssStitch().

{
if (bundle->t3List != NULL)
    return aliList;     /* Can't handle intense translated stuff. */
else
    {
    struct dnaSeq *qSeq =  bundle->qSeq;
    struct dnaSeq *genoSeq = bundle->genoSeq;
    struct ffAli *right, *left = NULL, *newLeft, *newRight;

    left = aliList;
    for (right = aliList->right; right != NULL; right = right->right)
        {
        if (right->hStart - left->hEnd >= 3 && right->nStart - left->nEnd >= 3)
            {
            newLeft = ffFind(left->nEnd, right->nStart, left->hEnd, right->hStart, stringency);
            if (newLeft != NULL)
                {
                newLeft = forceMonotonic(newLeft, qSeq, genoSeq, 
                    stringency, bundle->isProt, bundle->t3List );
                newRight = ffRightmost(newLeft);
                if (left != NULL)
                    {
                    left->right = newLeft;
                    newLeft->left = left;
                    }
                else
                    {
                    aliList = newLeft;
                    }
                if (right != NULL)
                    {
                    right->left = newRight;
                    newRight->right = right;
                    }
                }
            }
        left = right;
        }
    }
return aliList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ssBundleFree

(

struct ssBundle **

pEl

)

Definition at line 47 of file supStitch.c.

References ssBundle::ffList, freez(), and ssFfItemFreeList().

Referenced by foldInExtras(), gfAlignSomeClumps(), gfAlignStrand(), gfAlignTrans(), gfAlignTransTrans(), gfFindAlignAaTrans(), and ssBundleFreeList().

{
struct ssBundle *el;
if ((el = *pEl) != NULL)
    {
    ssFfItemFreeList(&el->ffList);
    freez(pEl);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ssBundleFreeList

(

struct ssBundle **

pList

)

Definition at line 58 of file supStitch.c.

References ssBundle::next, and ssBundleFree().

Referenced by addToBigBundleList().

{
struct ssBundle *el, *next;
for (el = *pList; el != NULL; el = next)
    {
    next = el->next;
    ssBundleFree(&el);
    }
*pList = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int ssConnectCost	(	struct cBlock *	a,
		struct cBlock *	b,
		void *	data
	)			[static]

Definition at line 561 of file supStitch.c.

References bioScoreMatch(), cBlock::data, findCrossover(), findOverlap(), ffAli::hEnd, ffAli::hStart, ffAli::nEnd, cBlock::qEnd, cBlock::qStart, cBlock::score, ssGapCost(), ssIsProt, cBlock::tEnd, and cBlock::tStart.

Referenced by ssFindBestBig().

{
struct ffAli *aFf = a->data, *bFf = b->data;
int overlapAdjustment = 0;
int overlap = findOverlap(a, b);
int dq = b->qStart - a->qEnd;
int dt = b->tStart - a->tEnd;

if (overlap > 0)
    {
    int aSize = aFf->hEnd - aFf->hStart;
    int bSize = bFf->hEnd - bFf->hStart;
    if (overlap >= bSize || overlap >= aSize)
        {
        /* Give stiff overlap adjustment for case where
         * one block completely enclosed in the other on
         * either sequence. This will make it never happen. */
        overlapAdjustment = a->score + b->score;
        }
    else
        {
        /* More normal case - partial overlap on one or both strands. */
        int crossover = findCrossover(aFf, bFf, overlap, ssIsProt);
        int remain = overlap - crossover;
        overlapAdjustment =
            bioScoreMatch(ssIsProt, aFf->nEnd - remain, aFf->hEnd - remain, 
                remain)
          + bioScoreMatch(ssIsProt, bFf->nStart, bFf->hStart, 
                crossover);
        dq -= overlap;
        dt -= overlap;
        }
    }
return overlapAdjustment + ssGapCost(dq, dt, data);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ssNode* ssDynamicProgram

(

struct ssGraph *

graph

)

[static, read]

Definition at line 426 of file supStitch.c.

References ssNode::cumScore, ssEdge::next, ssGraph::nodeCount, ssEdge::nodeIn, ssGraph::nodes, ssEdge::score, and ssNode::waysIn.

Referenced by ssGraphFindBest().

{
int veryBestScore = -0x3fffffff;
struct ssNode *veryBestNode = NULL;
int nodeIx;

for (nodeIx = 1; nodeIx <= graph->nodeCount; ++nodeIx)
    {
    int bestScore = -0x3fffffff;
    int score;
    struct ssEdge *bestEdge = NULL;
    struct ssNode *curNode = &graph->nodes[nodeIx];
    struct ssEdge *edge;

    for (edge = curNode->waysIn; edge != NULL; edge = edge->next)
        {
        score = edge->score + edge->nodeIn->cumScore;
        if (score > bestScore)
            {
            bestScore = score;
            bestEdge = edge;
            }
        }
    curNode->bestWayIn = bestEdge;
    curNode->cumScore = bestScore;
    if (bestScore >= veryBestScore)
        {
        veryBestScore = bestScore;
        veryBestNode = curNode;
        }
    }
return veryBestNode;
}

Here is the caller graph for this function:

void ssFfItemFree

(

struct ssFfItem **

pEl

)

Definition at line 24 of file supStitch.c.

References ssFfItem::ff, ffFreeAli(), and freez().

Referenced by ssFfItemFreeList().

{
struct ssFfItem *el;
if ((el = *pEl) != NULL)
    {
    ffFreeAli(&el->ff);
    freez(pEl);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ssFfItemFreeList

(

struct ssFfItem **

pList

)

Definition at line 35 of file supStitch.c.

References ssFfItem::next, and ssFfItemFree().

Referenced by ssBundleFree().

{
struct ssFfItem *el, *next;
for (el = *pList; el != NULL; el = next)
    {
    next = el->next;
    ssFfItemFree(&el);
    }
*pList = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void ssFindBest	(	struct ffAli *	ffList,
		bioSeq *	qSeq,
		bioSeq *	tSeq,
		enum ffStringency	stringency,
		boolean	isProt,
		struct trans3 *	t3List,
		struct ffAli **	retBestAli,
		int *	retScore,
		struct ffAli **	retLeftovers
	)			[static]

Definition at line 701 of file supStitch.c.

References ffAliCount(), ssFindBestBig(), and ssFindBestSmall().

Referenced by ssStitch().

{
int count = ffAliCount(ffList);
if (count >= 10)
    {
    ssFindBestBig(ffList, qSeq, tSeq, stringency, isProt, t3List,
        retBestAli, retScore, retLeftovers);
    }
else
    {
    ssFindBestSmall(ffList, qSeq, tSeq, stringency, isProt, t3List,
        retBestAli, retScore, retLeftovers);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void ssFindBestBig	(	struct ffAli *	ffList,
		bioSeq *	qSeq,
		bioSeq *	tSeq,
		enum ffStringency	stringency,
		boolean	isProt,
		struct trans3 *	t3List,
		struct ffAli **	retBestAli,
		int *	retScore,
		struct ffAli **	retLeftovers
	)			[static]

Definition at line 600 of file supStitch.c.

References BIGNUM, bioScoreMatch(), chain::blockList, chainBlocks(), chainFreeList(), dnaSeq::dna, ffMakeRightLinks(), findCrossover(), findOverlap(), ffAli::hEnd, ffAli::hStart, ffAli::left, lm, lmAllocVar, lmCleanup(), lmInit(), dnaSeq::name, ffAli::nEnd, chain::next, cBlock::next, ffAli::nStart, ffAli::right, chain::score, dnaSeq::size, slAddHead, ssConnectCost(), ssGapCost(), ssIsProt, ssStringency, chain::tEnd, and trans3Offsets().

Referenced by forceMonotonic(), and ssFindBest().

{
struct cBlock *boxList = NULL, *box, *prevBox;
struct ffAli *ff, *farRight = NULL;
struct lm *lm = lmInit(0);
int boxSize;
DNA *firstH = tSeq->dna;
struct chain *chainList, *chain, *bestChain;
int tMin = BIGNUM, tMax = -BIGNUM;


/* Make up box list for chainer. */
for (ff = ffList; ff != NULL; ff = ff->right)
    {
    lmAllocVar(lm, box);
    boxSize = ff->nEnd - ff->nStart;
    box->qStart = ff->nStart - qSeq->dna;
    box->qEnd = box->qStart + boxSize;
    if (t3List)
        {
        trans3Offsets(t3List, ff->hStart, ff->hEnd, &box->tStart, &box->tEnd);
        }
    else
        {
        box->tStart = ff->hStart - firstH;
        box->tEnd = box->tStart + boxSize;
        }
    box->data = ff;
    box->score = bioScoreMatch(isProt, ff->nStart, ff->hStart, boxSize);
    if (tMin > box->tStart) tMin = box->tStart;
    if (tMax < box->tEnd) tMax = box->tEnd;
    slAddHead(&boxList, box);
    }

/* Adjust boxes so that tMin is always 0. */
for (box = boxList; box != NULL; box = box->next)
    {
    box->tStart -= tMin;
    box->tEnd -= tMin;
    }
tMax -= tMin;

ssStringency = stringency;
ssIsProt = isProt;
chainList = chainBlocks(qSeq->name, qSeq->size, '+', "tSeq", tMax, &boxList,
        ssConnectCost, ssGapCost, NULL, NULL);

/* Fixup crossovers on best (first) chain. */
bestChain = chainList;
prevBox = bestChain->blockList;
for (box = prevBox->next; box != NULL; box = box->next)
    {
    int overlap = findOverlap(prevBox, box);
    if (overlap > 0)
        {
        struct ffAli *left = prevBox->data;
        struct ffAli *right = box->data;
        int crossover = findCrossover(left, right, overlap, isProt);
        int remain = overlap - crossover;
        left->nEnd -= remain;
        left->hEnd -= remain;
        right->nStart += crossover;
        right->hStart += crossover;
        }
    prevBox = box;
    }

/* Copy stuff from first chain to bestAli. */
farRight = NULL;
for (box = chainList->blockList; box != NULL; box = box->next)
    {
    ff = box->data;
    ff->left = farRight;
    farRight = ff;
    }
*retBestAli = ffMakeRightLinks(farRight);

/* Copy stuff from other chains to leftovers. */
farRight = NULL;
for (chain = chainList->next; chain != NULL; chain = chain->next)
    {
    for (box = chain->blockList; box != NULL; box = box->next)
        {
        ff = box->data;
        ff->left = farRight;
        farRight = ff;
        }
    }
*retLeftovers = ffMakeRightLinks(farRight);

*retScore = bestChain->score;
for (chain = chainList; chain != NULL; chain = chain->next)
    chain->blockList = NULL;    /* Don't want to free this, it's local. */
chainFreeList(&chainList);
lmCleanup(&lm);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void ssFindBestSmall	(	struct ffAli *	ffList,
		bioSeq *	qSeq,
		bioSeq *	tSeq,
		enum ffStringency	stringency,
		boolean	isProt,
		struct trans3 *	t3List,
		struct ffAli **	retBestAli,
		int *	retScore,
		struct ffAli **	retLeftovers
	)			[static]

Definition at line 524 of file supStitch.c.

References forceMonotonic(), ssGraphFindBest(), ssGraphFree(), and ssGraphMake().

Referenced by ssFindBest().

{
struct ssGraph *graph = ssGraphMake(ffList, qSeq, stringency, isProt, t3List);
ssGraphFindBest(graph, retBestAli, retScore, retLeftovers);
*retBestAli = forceMonotonic(*retBestAli, qSeq, tSeq, stringency, isProt, t3List);
ssGraphFree(&graph);
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct ssBundle* ssFindBundles	(	struct patSpace *	ps,
		struct dnaSeq *	cSeq,
		char *	cName,
		enum ffStringency	stringency,
		boolean	avoidSelfSelf
	)			[read]

Definition at line 843 of file supStitch.c.

References AllocVar, patClump::bacIx, dnaSeq::dna, ssFfItem::ff, ffFind(), findBundle(), dnaSeq::name, patClump::next, patSpaceFindOne(), sameString, patClump::seq, patClump::seqIx, dnaSeq::size, patClump::size, slAddHead, slFreeList(), and patClump::start.

{
struct patClump *clumpList, *clump;
struct ssBundle *bundleList = NULL, *bun = NULL;
DNA *cdna = cSeq->dna;
int totalCdnaSize = cSeq->size;
DNA *endCdna = cdna+totalCdnaSize;
struct ssFfItem *ffl;
struct dnaSeq *lastSeq = NULL;
int maxSize = 700;
int preferredSize = 500;
int overlapSize = 250;

for (;;)
    {
    int cSize = endCdna - cdna;
    if (cSize > maxSize)
        cSize = preferredSize;
    clumpList = patSpaceFindOne(ps, cdna, cSize);
    for (clump = clumpList; clump != NULL; clump = clump->next)
        {
        struct ffAli *ff;
        struct dnaSeq *seq = clump->seq;
        DNA *tStart = seq->dna + clump->start;
        if (!avoidSelfSelf || !sameString(seq->name, cSeq->name))
            {
            ff = ffFind(cdna, cdna+cSize, tStart, tStart + clump->size, stringency);
            if (ff != NULL)
                {
                if (lastSeq != seq)
                    {
                    lastSeq = seq;
                    if ((bun = findBundle(bundleList, seq)) == NULL)
                        {
                        AllocVar(bun);
                        bun->qSeq = cSeq;
                        bun->genoSeq = seq;
                        bun->genoIx = clump->bacIx;
                        bun->genoContigIx = clump->seqIx;
                        slAddHead(&bundleList, bun);
                        }
                    }
                AllocVar(ffl);
                ffl->ff = ff;
                slAddHead(&bun->ffList, ffl);
                }
            }
        }
    cdna += cSize;
    if (cdna >= endCdna)
        break;
    cdna -= overlapSize;
    slFreeList(&clumpList);
    }
slReverse(&bundleList);
cdna = cSeq->dna;

for (bun = bundleList; bun != NULL; bun = bun->next)
    {
    ssStitch(bun, stringency, 20, 16);
    }
return bundleList;
}

Here is the call graph for this function:

static int ssGapCost	(	int	dq,
		int	dt,
		void *	data
	)			[static]

Definition at line 541 of file supStitch.c.

References ffCalcGapPenalty(), and ssStringency.

Referenced by ssConnectCost(), and ssFindBestBig().

{
int cost;
if (dt < 0) dt = 0;
if (dq < 0) dq = 0;
cost = ffCalcGapPenalty(dt, dq, ssStringency);
return cost;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void ssGraphFindBest	(	struct ssGraph *	graph,
		struct ffAli **	retBestAli,
		int *	retScore,
		struct ffAli **	retLeftovers
	)			[static]

Definition at line 463 of file supStitch.c.

References ssNode::bestWayIn, ssEdge::crossover, ssNode::cumScore, ssNode::ff, ffAli::hEnd, ffAli::hStart, ffAli::left, ffAli::nEnd, ssEdge::nodeIn, ssGraph::nodes, ffAli::nStart, ssEdge::overlap, ffAli::right, and ssDynamicProgram().

Referenced by ssFindBestSmall().

{
struct ssEdge *edge;
struct ssNode *node;
struct ssNode *startNode = &graph->nodes[0];
struct ffAli *bestAli = NULL, *leftovers = NULL;
struct ffAli *ff, *left = NULL;
int i;
int overlap, crossover, crossDif;

/* Find best path and save score. */
node = ssDynamicProgram(graph);
*retScore = node->cumScore;

/* Trace back and trim overlaps. */
while (node != startNode)
    {
    ff = node->ff;
    ff->right = bestAli;
    bestAli = ff;
    node->ff = NULL;
    edge = node->bestWayIn;
    if ((overlap = edge->overlap) > 0)
        {
        left = edge->nodeIn->ff;
        crossover = edge->crossover;
        crossDif = overlap-crossover;
        left->hEnd -= crossDif;
        left->nEnd -= crossDif;
        ff->hStart += crossover;
        ff->nStart += crossover;
        }
    node = node->bestWayIn->nodeIn;
    }

/* Make left links. */
left = NULL;
for (ff = bestAli; ff != NULL; ff = ff->right)
    {
    ff->left = left;
    left = ff;
    }

/* Make leftover list. */
for (i=1, node=graph->nodes+1; i<=graph->nodeCount; ++i,++node)
    {
    if ((ff = node->ff) != NULL)
        {
        ff->left = leftovers;
        leftovers = ff;
        }
    }
leftovers = ffMakeRightLinks(leftovers);

*retBestAli = bestAli;
*retLeftovers = leftovers;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void ssGraphFree

(

struct ssGraph **

pGraph

)

[static]

Definition at line 304 of file supStitch.c.

References ssGraph::edges, freeMem(), freez(), and ssGraph::nodes.

Referenced by ssFindBestSmall().

{
struct ssGraph *graph;
if ((graph = *pGraph) != NULL)
    {
    freeMem(graph->nodes);
    freeMem(graph->edges);
    freez(pGraph);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct ssGraph* ssGraphMake	(	struct ffAli *	ffList,
		bioSeq *	qSeq,
		enum ffStringency	stringency,
		boolean	isProt,
		struct trans3 *	t3List
	)			[static, read]

Definition at line 326 of file supStitch.c.

References AllocArray, AllocVar, bioScoreMatch(), ssEdge::crossover, ssGraph::edgeCount, ssGraph::edges, ffAliCount(), ffCalcGapPenalty(), findCrossover(), ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ssGraph::nodeCount, ssEdge::nodeIn, ssGraph::nodes, ssNode::nodeScore, ffAli::nStart, ssEdge::overlap, ffAli::right, ssEdge::score, slAddHead, slReverse(), trans3Offsets(), tripleCanFollow(), and ssNode::waysIn.

Referenced by ssFindBestSmall().

{
int nodeCount = ffAliCount(ffList);
int maxEdgeCount = (nodeCount+1)*(nodeCount)/2;
int edgeCount = 0;
struct ssEdge *edges, *e;
struct ssNode *nodes;
struct ssGraph *graph;
struct ffAli *ff, *mid;
int i, midIx;
int overlap;
boolean canFollow;

if (nodeCount == 1)
    maxEdgeCount = 1;
    
AllocVar(graph);
graph->nodeCount = nodeCount;
graph->nodes = AllocArray(nodes, nodeCount+1);
for (i=1, ff = ffList; i<=nodeCount; ++i, ff = ff->right)
    {
    nodes[i].ff = ff;
    nodes[i].nodeScore = bioScoreMatch(isProt, ff->nStart, ff->hStart, ff->hEnd - ff->hStart);
    }

graph->edges = AllocArray(edges, maxEdgeCount);
for (mid = ffList, midIx=1; mid != NULL; mid = mid->right, ++midIx)
    {
    int midScore;
    struct ssNode *midNode = &nodes[midIx];
    e = &edges[edgeCount++];
    assert(edgeCount <= maxEdgeCount);
    e->nodeIn = &nodes[0];
    e->score = midScore = midNode->nodeScore;
    midNode->waysIn = e;
    for (ff = ffList,i=1; ff != mid; ff = ff->right,++i)
        {
        int mhStart = 0, mhEnd = 0;
        if (t3List)
            {
            canFollow = tripleCanFollow(ff, mid, qSeq, t3List);
            trans3Offsets(t3List, mid->hStart, mid->hEnd, &mhStart, &mhEnd);
            }
        else 
            {
            canFollow = (ff->nStart < mid->nStart && ff->nEnd < mid->nEnd 
                        && ff->hStart < mid->hStart && ff->hEnd < mid->hEnd);
            }
        if (canFollow)
            {
            struct ssNode *ffNode = &nodes[i];
            int score;
            int hGap;
            int nGap;
            int crossover;

            nGap = mid->nStart - ff->nEnd;
            if (t3List)
                {
                int fhStart, fhEnd;
                trans3Offsets(t3List, ff->hStart, ff->hEnd, &fhStart, &fhEnd);
                hGap = mhStart - fhEnd;
                }
            else
                {
                hGap = mid->hStart - ff->hEnd;
                }
            e = &edges[edgeCount++];
            assert(edgeCount <= maxEdgeCount);
            e->nodeIn = ffNode;
            e->overlap = overlap = -nGap;
            if (overlap > 0)
                {
                int midSize = mid->hEnd - mid->hStart;
                int ffSize = ff->hEnd - ff->hStart;
                int newMidScore, newFfScore;
                e->crossover = crossover = findCrossover(ff, mid, overlap, isProt);
                newMidScore = bioScoreMatch(isProt, mid->nStart, mid->hStart, midSize-overlap+crossover);
                newFfScore = bioScoreMatch(isProt, ff->nStart+crossover, ff->hStart+crossover,
                                ffSize-crossover);
                score = newMidScore - ffNode->nodeScore + newFfScore;
                nGap = 0;
                hGap -= overlap;
                }
            else
                {
                score = midScore;
                }
            score -= ffCalcGapPenalty(hGap, nGap, stringency);
            e->score = score;
            slAddHead(&midNode->waysIn, e);
            }
        }
    slReverse(&midNode->waysIn);
    }
return graph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void ssStitch	(	struct ssBundle *	bundle,
		enum ffStringency	stringency,
		int	minScore,
		int	maxToReturn
	)

Definition at line 748 of file supStitch.c.

References AllocVar, ssBundle::avoidFuzzyFindKludge, cutAtBigIntrons(), dnaSeq::dna, FALSE, ssFfItem::ff, ffAliSort(), ffCat(), ffCdna, ffCmpHitsNeedleFirst(), ffFreeAli(), ffIntronMax, ffIntronMaxDefault, ssBundle::ffList, ffMergeClose(), ffMergeHayOverlaps(), ffMergeNeedleAlis(), ffRemoveEmptyAlis(), ffSlideIntrons(), forceMonotonic(), ssBundle::genoSeq, ssBundle::isProt, ssFfItem::next, ssBundle::qSeq, slAddHead, slFreeList(), slReverse(), smallMiddleExons(), ssFindBest(), ssBundle::t3List, and TRUE.

Referenced by ffSeedExtInMem(), foldInExtras(), gfAlignSomeClumps(), gfAlignStrand(), gfAlignTrans(), gfAlignTransTrans(), gfClumpsToBundles(), gfFindAlignAaTrans(), gfTransTransFindBundles(), and refineBundle().

{
struct dnaSeq *qSeq =  bundle->qSeq;
struct dnaSeq *genoSeq = bundle->genoSeq;
struct ffAli *ffList = NULL;
struct ssFfItem *ffl;
struct ffAli *bestPath;
int score;
boolean firstTime = TRUE;

if (bundle->ffList == NULL)
    return;

/* The score may improve when we stitch together more alignments,
 * so don't let minScore be too harsh at this stage. */
if (minScore > 20)
    minScore = 20;

/* Create ffAlis for all in bundle and move to one big list. */
for (ffl = bundle->ffList; ffl != NULL; ffl = ffl->next)
    {
    ffCat(&ffList, &ffl->ff);
    }
slFreeList(&bundle->ffList);

ffAliSort(&ffList, ffCmpHitsNeedleFirst);
ffList = ffMergeClose(ffList, qSeq->dna, genoSeq->dna);

while (ffList != NULL)
    {
    ssFindBest(ffList, qSeq, genoSeq, stringency, 
        bundle->isProt, bundle->t3List,
        &bestPath, &score, &ffList);

    bestPath = ffMergeNeedleAlis(bestPath, TRUE);
    bestPath = ffRemoveEmptyAlis(bestPath, TRUE);
    bestPath = ffMergeHayOverlaps(bestPath);
    bestPath = ffRemoveEmptyAlis(bestPath, TRUE);
    bestPath = forceMonotonic(bestPath, qSeq, genoSeq, stringency,
        bundle->isProt, bundle->t3List);

    if (firstTime && stringency == ffCdna && bundle->avoidFuzzyFindKludge == FALSE)
        {
        /* Only look for middle exons the first time.  Next times
         * this might regenerate most of the first alignment... */
        bestPath = smallMiddleExons(bestPath, bundle, stringency);
        }
    bestPath = ffMergeNeedleAlis(bestPath, TRUE);
    if (ffIntronMax != ffIntronMaxDefault)
        {
        bestPath = cutAtBigIntrons(bestPath, ffIntronMax, &score, stringency,
                &ffList);
        }
    if (!bundle->isProt)
        ffSlideIntrons(bestPath);
    bestPath = ffRemoveEmptyAlis(bestPath, TRUE);
    if (score >= minScore)
        {
        AllocVar(ffl);
        ffl->ff = bestPath;
        slAddHead(&bundle->ffList, ffl);
        }
    else
        {
        ffFreeAli(&bestPath);
        ffFreeAli(&ffList);
        break;
        }
    firstTime = FALSE;
    if (--maxToReturn <= 0)
        {
        ffFreeAli(&ffList);
        break;
        }
    }
slReverse(&bundle->ffList);
return;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void trans3Offsets	(	struct trans3 *	t3List,
		AA *	startP,
		AA *	endP,
		int *	retStart,
		int *	retEnd
	)			[static]

Definition at line 165 of file supStitch.c.

References dnaSeq::dna, trans3::next, trans3::seq, dnaSeq::size, trans3::start, and trans3::trans.

Referenced by ssFindBestBig(), ssGraphMake(), and tripleCanFollow().

{
struct trans3 *t3;
int frame;
aaSeq *seq;

for (t3 = t3List; t3 != NULL; t3 = t3->next)
    {
    for (frame = 0; frame < 3; ++frame)
        {
        seq = t3->trans[frame];
        if (seq->dna <= startP && startP < seq->dna + seq->size)
            {
            *retStart = 3*(startP - seq->dna)+frame + t3->start;
            *retEnd = 3*(endP - seq->dna)+frame + t3->start;
            return;
            }
        }
    }
internalErr();
}

Here is the caller graph for this function:

boolean tripleCanFollow	(	struct ffAli *	a,
		struct ffAli *	b,
		aaSeq *	qSeq,
		struct trans3 *	t3List
	)

Definition at line 316 of file supStitch.c.

References ffAli::hEnd, ffAli::hStart, ffAli::nEnd, ffAli::nStart, and trans3Offsets().

Referenced by ssGraphMake().

{
int ahStart, ahEnd, bhStart, bhEnd;
trans3Offsets(t3List, a->hStart, a->hEnd, &ahStart, &ahEnd);
trans3Offsets(t3List, b->hStart, b->hEnd, &bhStart, &bhEnd);
return  (a->nStart < b->nStart && a->nEnd < b->nEnd && ahStart < bhStart && ahEnd < bhEnd);
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

char const rcsid[] = "$Id: supStitch.c,v 1.38 2007/04/20 22:43:37 kent Exp $" [static]

Definition at line 18 of file supStitch.c.

boolean ssIsProt [static]

Definition at line 539 of file supStitch.c.

Referenced by ssConnectCost(), and ssFindBestBig().

enum ffStringency ssStringency [static]

Definition at line 538 of file supStitch.c.

Referenced by ssFindBestBig(), and ssGapCost().

---