lib/chainBlock.c File Reference

#include "common.h"
#include "localmem.h"
#include "linefile.h"
#include "dlist.h"
#include "chainBlock.h"

Include dependency graph for chainBlock.c:

Go to the source code of this file.

Data Structures
struct	kdBranch
struct	kdLeaf
struct	kdTree
struct	predScore
Functions
static int	kdLeafCmpQ (const void *va, const void *vb)
static int	kdLeafCmpT (const void *va, const void *vb)
static int	kdLeafCmpTotal (const void *va, const void *vb)
static int	medianVal (struct dlList *list, int medianIx, int dim)
static int	splitList (struct dlList *oldList, struct dlList *newList)
static void	clearHits (struct dlList *list)
static struct kdBranch *	kdBuild (int nodeCount, struct dlList *lists[2], int dim, struct lm *lm)
static struct kdTree *	kdTreeMake (struct kdLeaf *leafList, struct lm *lm)
static struct predScore	bestPredecessor (struct kdLeaf *lonely, ConnectCost connectCost, GapCost gapCost, void *gapData, int dim, struct kdBranch *branch, struct predScore bestSoFar)
static void	updateScoresOnWay (struct kdBranch *branch, int dim, struct kdLeaf *leaf)
static void	findBestPredecessors (struct kdTree *tree, struct kdLeaf *leafList, ConnectCost connectCost, GapCost gapCost, void *gapData)
static double	scoreBlocks (struct cBlock *blockList, ConnectCost connectCost, void *gapData)
static struct chain *	peelChains (char *qName, int qSize, char qStrand, char *tName, int tSize, struct kdLeaf *leafList, FILE *details)
chain *	chainBlocks (char *qName, int qSize, char qStrand, char *tName, int tSize, struct cBlock **pBlockList, ConnectCost connectCost, GapCost gapCost, void *gapData, FILE *details)
Variables
static char const	rcsid [] = "$Id: chainBlock.c,v 1.17 2005/04/10 14:41:21 markd Exp $"

---

Function Documentation

static struct predScore bestPredecessor	(	struct kdLeaf *	lonely,
		ConnectCost	connectCost,
		GapCost	gapCost,
		void *	gapData,
		int	dim,
		struct kdBranch *	branch,
		struct predScore	bestSoFar
	)			[static, read]

Definition at line 205 of file chainBlock.c.

References kdBranch::cutCoord, kdBranch::hi, kdBranch::leaf, kdBranch::lo, kdBranch::maxQ, kdBranch::maxScore, kdBranch::maxT, predScore::pred, and predScore::score.

Referenced by findBestPredecessors().

{
struct kdLeaf *leaf;
double maxScore = branch->maxScore + lonely->cb->score;

/* If best score in this branch of tree wouldn't be enough
 * don't bother exploring it. First try without calculating
 * gap score in case gap score is a little expensive to calculate. */
if (maxScore < bestSoFar.score)
    return bestSoFar;
maxScore -= gapCost(lonely->cb->qStart - branch->maxQ, 
        lonely->cb->tStart - branch->maxT, gapData);
if (maxScore < bestSoFar.score)
    return bestSoFar;


/* If it's a terminal branch, then calculate score to connect
 * with it. */
else if ((leaf = branch->leaf) != NULL)
    {
    if (leaf->cb->qStart < lonely->cb->qStart 
     && leaf->cb->tStart < lonely->cb->tStart)
        {
        double score = leaf->totalScore + lonely->cb->score - 
                connectCost(leaf->cb, lonely->cb, gapData);
        if (score > bestSoFar.score)
           {
           bestSoFar.score = score;
           bestSoFar.pred = branch;
           }
        }
    return bestSoFar;
    }

/* Otherwise explore sub-trees that could harbor predecessors. */
else
    {
    int newDim = 1-dim;
    int dimCoord = (dim == 0 ? lonely->cb->qStart : lonely->cb->tStart);
    
    /* Explore hi branch first as it is more likely to have high
     * scores.  However only explore it if it can have things starting
     * before us. */
    if (dimCoord > branch->cutCoord)
         bestSoFar = bestPredecessor(lonely, connectCost, gapCost, gapData,
                newDim, branch->hi, bestSoFar);
    bestSoFar = bestPredecessor(lonely, connectCost, gapCost, gapData,
        newDim, branch->lo, bestSoFar);
    return bestSoFar;
    }
}

Here is the caller graph for this function:

struct chain* chainBlocks	(	char *	qName,
		int	qSize,
		char	qStrand,
		char *	tName,
		int	tSize,
		struct cBlock **	pBlockList,
		ConnectCost	connectCost,
		GapCost	gapCost,
		void *	gapData,
		FILE *	details
	)			[read]

Definition at line 392 of file chainBlock.c.

References chainCmpScore(), findBestPredecessors(), kdLeafCmpT(), kdLeafCmpTotal(), kdTreeMake(), lm, lmAllocVar, lmCleanup(), lmInit(), chain::next, cBlock::next, peelChains(), cBlock::score, scoreBlocks(), slAddHead, slSort(), cBlock::tEnd, and cBlock::tStart.

Referenced by ssFindBestBig().

{
struct kdTree *tree;
struct kdLeaf *leafList = NULL, *leaf;
struct cBlock *block;
struct chain *chainList = NULL, *chain;
struct lm *lm;

/* Empty lists will be problematic later, so deal with them here. */
if (*pBlockList == NULL)
   return NULL;

/* Make a leaf for each block. */
lm = lmInit(0);  /* Memory for tree, branches and leaves. */
for (block = *pBlockList; block != NULL; block = block->next)
    {
    /* Watch out for 0-length blocks in input: */
    if (block->tStart == block->tEnd)
        continue;
    lmAllocVar(lm, leaf);
    leaf->cb = block;
    leaf->totalScore = block->score;
    slAddHead(&leafList, leaf);
    }

/* Figure out chains. */
slSort(&leafList, kdLeafCmpT);
tree = kdTreeMake(leafList, lm);
findBestPredecessors(tree, leafList, connectCost, gapCost, gapData);
slSort(&leafList, kdLeafCmpTotal);
chainList = peelChains(qName, qSize, qStrand, tName, tSize, leafList, details);

/* Rescore chains (since some truncated) */
for (chain = chainList; chain != NULL; chain = chain->next)
    chain->score = scoreBlocks(chain->blockList, connectCost, gapData);
slSort(&chainList,  chainCmpScore);

/* Clean up and go home. */
lmCleanup(&lm);
*pBlockList = NULL;
return chainList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void clearHits

(

struct dlList *

list

)

[static]

Definition at line 110 of file chainBlock.c.

References dlEnd, FALSE, dlList::head, dlNode::next, and dlNode::val.

Referenced by kdBuild().

{
struct dlNode *node;
for (node = list->head; !dlEnd(node); node = node->next)
    {
    struct kdLeaf *leaf = node->val;
    leaf->hit = FALSE;
    }
}

Here is the caller graph for this function:

static void findBestPredecessors	(	struct kdTree *	tree,
		struct kdLeaf *	leafList,
		ConnectCost	connectCost,
		GapCost	gapCost,
		void *	gapData
	)			[static]

Definition at line 284 of file chainBlock.c.

References kdLeaf::bestPred, bestPredecessor(), kdLeaf::next, kdTree::root, kdLeaf::totalScore, and updateScoresOnWay().

Referenced by chainBlocks().

{
static struct predScore noBest;
struct kdLeaf *leaf;
struct kdLeaf *bestLeaf = NULL;
double bestScore = 0;

for (leaf = leafList; leaf != NULL; leaf = leaf->next)
    {
    struct predScore best;
    best = bestPredecessor(leaf, connectCost, gapCost, gapData, 0, tree->root, noBest);
    if (best.score > leaf->totalScore)
        {
        leaf->totalScore = best.score;
        leaf->bestPred = best.pred;
        }
    updateScoresOnWay(tree->root, 0, leaf);
    if (bestScore < leaf->totalScore)
        {
        bestScore = leaf->totalScore;
        bestLeaf = leaf;
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct kdBranch* kdBuild	(	int	nodeCount,
		struct dlList *	lists[2],
		int	dim,
		struct lm *	lm
	)			[static, read]

Definition at line 122 of file chainBlock.c.

References kdLeaf::cb, clearHits(), kdBranch::cutCoord, dlList::head, kdBranch::hi, kdBranch::leaf, lm, lmAllocVar, kdBranch::lo, max, kdBranch::maxQ, kdBranch::maxT, medianVal(), cBlock::qEnd, splitList(), cBlock::tEnd, and dlNode::val.

Referenced by kdTreeMake().

{
struct kdBranch *branch;
lmAllocVar(lm, branch);
if (nodeCount == 1)
    {
    struct kdLeaf *leaf = lists[0]->head->val;
    branch->leaf = leaf;
    branch->maxQ = leaf->cb->qEnd;
    branch->maxT = leaf->cb->tEnd;
    }
else
    {
    int newCount;
    struct dlList *newLists[2];
    struct dlList newQ, newT;
    int nextDim = 1-dim;

    /* Subdivide lists along median.  */
    newLists[0] = &newQ;
    newLists[1] = &newT;
    clearHits(lists[0]);
    branch->cutCoord = medianVal(lists[dim], nodeCount/2, dim);
    newCount = splitList(lists[0], newLists[0]);
    splitList(lists[1], newLists[1]);

    /* Recurse on each side. */
    branch->lo = kdBuild(nodeCount - newCount, lists, nextDim, lm);
    branch->hi = kdBuild(newCount, newLists, nextDim, lm);
    branch->maxQ = max(branch->lo->maxQ, branch->hi->maxQ);
    branch->maxT = max(branch->lo->maxT, branch->hi->maxT);
    }
return branch;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int kdLeafCmpQ	(	const void *	va,
		const void *	vb
	)			[static]

Definition at line 45 of file chainBlock.c.

References kdLeaf::cb, and cBlock::qStart.

Referenced by kdTreeMake().

{
const struct kdLeaf *a = *((struct kdLeaf **)va);
const struct kdLeaf *b = *((struct kdLeaf **)vb);
return a->cb->qStart - b->cb->qStart;
}

Here is the caller graph for this function:

static int kdLeafCmpT	(	const void *	va,
		const void *	vb
	)			[static]

Definition at line 53 of file chainBlock.c.

References kdLeaf::cb, and cBlock::tStart.

Referenced by chainBlocks().

{
const struct kdLeaf *a = *((struct kdLeaf **)va);
const struct kdLeaf *b = *((struct kdLeaf **)vb);
return a->cb->tStart - b->cb->tStart;
}

Here is the caller graph for this function:

static int kdLeafCmpTotal	(	const void *	va,
		const void *	vb
	)			[static]

Definition at line 61 of file chainBlock.c.

References kdLeaf::totalScore.

Referenced by chainBlocks().

{
const struct kdLeaf *a = *((struct kdLeaf **)va);
const struct kdLeaf *b = *((struct kdLeaf **)vb);
double diff = b->totalScore - a->totalScore;
if (diff < 0) return -1;
else if (diff > 0) return 1;
else return 0;
}

Here is the caller graph for this function:

static struct kdTree* kdTreeMake	(	struct kdLeaf *	leafList,
		struct lm *	lm
	)			[static, read]

Definition at line 159 of file chainBlock.c.

References AllocArray, dlAddTail(), dlListInit(), dlSort(), freeMem(), kdBuild(), kdLeafCmpQ(), lm, lmAllocVar, kdLeaf::next, kdTree::root, slCount(), and dlNode::val.

Referenced by chainBlocks().

{
struct kdLeaf *leaf;
int nodeCount = slCount(leafList);
struct kdTree *tree;
struct dlList qList, tList,*lists[2];
struct dlNode *qNodes, *tNodes;
int i;

/* Build lists sorted in each dimension. This
 * will let us quickly find medians while constructing
 * the kd-tree. */
dlListInit(&qList);
dlListInit(&tList);
AllocArray(qNodes, nodeCount);
AllocArray(tNodes, nodeCount);
for (i=0 , leaf=leafList; leaf != NULL; leaf = leaf->next, ++i)
    {
    qNodes[i].val = tNodes[i].val = leaf;
    dlAddTail(&qList, &qNodes[i]);
    dlAddTail(&tList, &tNodes[i]);
    }
/* Just sort qList since tList is sorted because it was
 * constructed from sorted leafList. */
dlSort(&qList, kdLeafCmpQ); 
lists[0] = &qList;
lists[1] = &tList;

/* Allocate master data structure and call recursive builder. */
lmAllocVar(lm, tree);
tree->root = kdBuild(nodeCount, lists, 0, lm);

/* Clean up and go home. */
freeMem(qNodes);
freeMem(tNodes);
return tree;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int medianVal	(	struct dlList *	list,
		int	medianIx,
		int	dim
	)			[static]

Definition at line 72 of file chainBlock.c.

References kdLeaf::cb, dlList::head, kdLeaf::hit, dlNode::next, cBlock::qStart, TRUE, cBlock::tStart, and dlNode::val.

Referenced by kdBuild().

{
struct dlNode *node = list->head;
struct kdLeaf *leaf = NULL;
int i;

for (i=0; i<medianIx; ++i)
    {
    leaf = node->val;
    leaf->hit = TRUE;  
    node = node->next;
    }
return (dim == 0 ? leaf->cb->qStart : leaf->cb->tStart);
}

Here is the caller graph for this function:

static struct chain* peelChains	(	char *	qName,
		int	qSize,
		char	qStrand,
		char *	tName,
		int	tSize,
		struct kdLeaf *	leafList,
		FILE *	details
	)			[static, read]

Definition at line 327 of file chainBlock.c.

References AllocVar, kdLeaf::cb, chainWriteHead(), cloneString(), FALSE, kdLeaf::hit, kdLeaf::next, cBlock::qEnd, slAddHead, cBlock::tEnd, kdLeaf::totalScore, and TRUE.

Referenced by chainBlocks().

{
struct kdLeaf *leaf;
struct chain *chainList = NULL, *chain;
for (leaf = leafList; leaf != NULL; leaf = leaf->next)
    leaf->hit = FALSE;
for (leaf = leafList; leaf != NULL; leaf = leaf->next)
    {
    if (!leaf->hit)
        {
        struct kdLeaf *lf;
        AllocVar(chain);
        chain->qName = cloneString(qName);
        chain->qSize = qSize;
        chain->qStrand = qStrand;
        chain->tName = cloneString(tName);
        chain->tSize = tSize;
        chain->qEnd = leaf->cb->qEnd;
        chain->tEnd = leaf->cb->tEnd;
        if (details)
            {
            chain->score = leaf->totalScore;
            chain->id = -1;
            chainWriteHead(chain, details);
            chain->score = 0;
            chain->id = 0;
            }
        slAddHead(&chainList, chain);
        for (lf = leaf; ; )
            {
            lf->hit = TRUE;
            slAddHead(&chain->blockList, lf->cb);
            chain->qStart = lf->cb->qStart;
            chain->tStart = lf->cb->tStart;
            if (details)
                {
                struct cBlock *b = lf->cb;
                fprintf(details, "%d\t%f\t%d\t%d\t%d\n", b->score, lf->totalScore,
                        b->tStart, b->qStart, b->qEnd - b->qStart);
                }
            if (lf->bestPred == NULL)
                 break;
            else
                {
                if (details)
                    {
                    struct cBlock *b = lf->cb;
                    struct cBlock *a = lf->bestPred->leaf->cb;
                    fprintf(details, " gap %d\t%d\n", 
                        b->tStart - a->tEnd, b->qStart - a->qEnd);
                    }
                }
            lf = lf->bestPred->leaf;
            if (lf->hit)
                break;
            }
        }
    }
slReverse(&chainList);
return chainList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static double scoreBlocks	(	struct cBlock *	blockList,
		ConnectCost	connectCost,
		void *	gapData
	)			[static]

Definition at line 311 of file chainBlock.c.

References cBlock::next, and cBlock::score.

Referenced by chainBlocks().

{
struct cBlock *block, *lastBlock = NULL;
double score = 0;
for (block = blockList; block != NULL; block = block->next)
    {
    score += block->score;
    if (lastBlock != NULL)
        score -= connectCost(lastBlock, block, gapData);
    lastBlock = block;
    }
return score;
}

Here is the caller graph for this function:

static int splitList	(	struct dlList *	oldList,
		struct dlList *	newList
	)			[static]

Definition at line 89 of file chainBlock.c.

References dlAddTail(), dlEnd, dlListInit(), dlRemove(), dlList::head, kdLeaf::hit, kdLeaf::next, dlNode::next, and dlNode::val.

Referenced by kdBuild().

{
struct dlNode *node, *next;
struct kdLeaf *leaf;
int newCount = 0;
dlListInit(newList);
for (node = oldList->head; !dlEnd(node); node = next)
    {
    next = node->next;
    leaf = node->val;
    if (!leaf->hit)
        {
        dlRemove(node);
        dlAddTail(newList, node);
        ++newCount;
        }
    }
return newCount;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void updateScoresOnWay	(	struct kdBranch *	branch,
		int	dim,
		struct kdLeaf *	leaf
	)			[static]

Definition at line 267 of file chainBlock.c.

References kdLeaf::cb, kdBranch::cutCoord, kdBranch::hi, kdBranch::leaf, kdBranch::lo, kdBranch::maxScore, cBlock::qStart, kdLeaf::totalScore, and cBlock::tStart.

Referenced by findBestPredecessors().

{
int newDim = 1-dim;
int dimCoord = (dim == 0 ? leaf->cb->qStart : leaf->cb->tStart);
if (branch->maxScore < leaf->totalScore) branch->maxScore = leaf->totalScore;
if (branch->leaf == NULL)
    {
    if (dimCoord <= branch->cutCoord)
        updateScoresOnWay(branch->lo, newDim, leaf);
    if (dimCoord >= branch->cutCoord)
        updateScoresOnWay(branch->hi, newDim, leaf);
    }
}

Here is the caller graph for this function:

---

Variable Documentation

char const rcsid[] = "$Id: chainBlock.c,v 1.17 2005/04/10 14:41:21 markd Exp $" [static]

Definition at line 12 of file chainBlock.c.

---