jkOwnLib/patSpace.c File Reference

#include "common.h"
#include "portable.h"
#include "dnaseq.h"
#include "ooc.h"
#include "patSpace.h"

Include dependency graph for patSpace.c:

Go to the source code of this file.

Data Structures
struct	blockPos
struct	patSpace
Defines
#define	blockSize   (256)
#define	BIGONE
#define	maxBlockCount   (2*230*1024 - 1)
#define	psBits   bits32
#define	maxPatCount   (1024*16)
Functions
void	freePatSpace (struct patSpace **pPatSpace)
void	tooManyBlocks ()
static void	fixBlockSize (struct blockPos *bp, int blockIx)
static struct patSpace *	newPatSpace (int minMatch, int maxGap, int seedSize)
static void	countPatSpace (struct patSpace *ps, struct dnaSeq *seq)
static int	allocPatSpaceLists (struct patSpace *ps)
static int	addToPatSpace (struct patSpace *ps, int bacIx, int seqIx, struct dnaSeq *seq, int startBlock)
patSpace *	makePatSpace (struct dnaSeq **seqArray, int seqArrayCount, int seedSize, char *oocFileName, int minMatch, int maxGap)
void	bfFind (struct patSpace *ps, int block, struct blockPos *ret)
static struct patClump *	newClump (struct patSpace *ps, struct blockPos *first, struct blockPos *last)
static struct patClump *	clumpHits (struct patSpace *ps, int hitBlocks[], int hitCount, int posBuf[], DNA *dna, int dnaSize)
patClump *	patSpaceFindOne (struct patSpace *ps, DNA *dna, int dnaSize)
Variables
static char const	rcsid [] = "$Id: patSpace.c,v 1.3 2006/03/15 18:36:16 angie Exp $"

---

Define Documentation

#define BIGONE

Definition at line 14 of file patSpace.c.

#define blockSize   (256)

Definition at line 12 of file patSpace.c.

Referenced by addToPatSpace(), axtFromBlocks(), fixBlockSize(), newClump(), pslHasIntron(), pslWeightedIntronOrientation(), and savePslx().

#define maxBlockCount   (2*230*1024 - 1)

Definition at line 18 of file patSpace.c.

Referenced by addToPatSpace(), bfFind(), makePatSpace(), and tooManyBlocks().

#define maxPatCount   (1024*16)

Definition at line 35 of file patSpace.c.

Referenced by countPatSpace(), and makePatSpace().

#define psBits   bits32

Definition at line 19 of file patSpace.c.

Referenced by addToPatSpace(), allocPatSpaceLists(), makePatSpace(), and patSpaceFindOne().

---

Function Documentation

static int addToPatSpace	(	struct patSpace *	ps,
		int	bacIx,
		int	seqIx,
		struct dnaSeq *	seq,
		int	startBlock
	)			[static]

Definition at line 181 of file patSpace.c.

References blockPos::bacIx, patSpace::blockPos, blockSize, dnaSeq::dna, fixBlockSize(), patSpace::lists, patSpace::listSizes, mask, maxBlockCount, patSpace::maxPat, ntValNoN, blockPos::offset, psBits, patSpace::seedSize, patSpace::seedSpaceSize, blockPos::seq, blockPos::seqIx, dnaSeq::size, and tooManyBlocks().

Referenced by makePatSpace().

{
int size = seq->size;
int mask = ps->seedSpaceSize-1;
DNA *dna = seq->dna;
int i;
int bits = 0;
int bVal;
int blockMod = blockSize;
int curCount;
psBits maxPat = ps->maxPat;
psBits *listSizes = ps->listSizes;
psBits **lists = ps->lists;
struct blockPos *bp = &ps->blockPos[startBlock];

bp->bacIx = bacIx;
bp->seqIx = seqIx;
bp->seq = seq;
bp->offset = 0;
fixBlockSize(bp, startBlock);
++bp;
for (i=0; i<ps->seedSize-1; ++i)
    {
    bVal = ntValNoN[(int)dna[i]];
    bits <<= 2;
    bits += bVal;
    }
for (i=ps->seedSize-1; i<size; ++i)
    {
    bVal = ntValNoN[(int)dna[i]];
    bits <<= 2;
    bits += bVal;
    bits &= mask;
    if ((curCount = listSizes[bits]) < maxPat)
        {
        listSizes[bits] = curCount+1;
        lists[bits][curCount] = startBlock;
        }
    if (--blockMod == 0)
        {
        if (++startBlock >= maxBlockCount)
            tooManyBlocks();
        blockMod = blockSize;
        bp->bacIx = bacIx;
        bp->seqIx = seqIx;
        bp->seq = seq;
        bp->offset = i - (ps->seedSize-1) + 1;
        fixBlockSize(bp, startBlock);
        ++bp;
        }
    }
for (i=0; i<ps->seedSize-1; ++i)
    {
    if (--blockMod == 0)
        {
        if (++startBlock >= maxBlockCount)
            tooManyBlocks();
        blockMod = blockSize;
        }
    }
if (blockMod != blockSize)
    ++startBlock;
return startBlock;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int allocPatSpaceLists

(

struct patSpace *

ps

)

[static]

Definition at line 141 of file patSpace.c.

References patSpace::allocated, patSpace::lists, patSpace::listSizes, patSpace::maxPat, needLargeMem(), psBits, and patSpace::seedSpaceSize.

Referenced by makePatSpace().

{
int oneCount;
int count = 0;
int i;
psBits *listSizes = ps->listSizes;
psBits **lists = ps->lists;
psBits *allocated;
psBits maxPat = ps->maxPat;
int size;
int usedCount = 0, overusedCount = 0;
int seedSpaceSize = ps->seedSpaceSize;

for (i=0; i<seedSpaceSize; ++i)
    {
    /* If pattern is too much used it's no good to us, ignore. */
    if ((oneCount = listSizes[i]) < maxPat)
        {
        count += oneCount;
        usedCount += 1;
        }
    else
        {
        overusedCount += 1;
        }
    }
ps->allocated = allocated = needLargeMem(count*sizeof(allocated[0]));
for (i=0; i<seedSpaceSize; ++i)
    {
    if ((size = listSizes[i]) < maxPat)
        {
        lists[i] = allocated;
        allocated += size;
        }
    }
return count;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void bfFind	(	struct patSpace *	ps,
		int	block,
		struct blockPos *	ret
	)

Definition at line 319 of file patSpace.c.

References patSpace::blockPos, and maxBlockCount.

Referenced by clumpHits().

{
assert(block >= 0 && block < maxBlockCount);
*ret = ps->blockPos[block];
}

Here is the caller graph for this function:

static struct patClump* clumpHits	(	struct patSpace *	ps,
		int	hitBlocks[],
		int	hitCount,
		int	posBuf[],
		DNA *	dna,
		int	dnaSize
	)			[static, read]

Definition at line 354 of file patSpace.c.

References bfFind(), patSpace::maxGap, maxGap, newClump(), blockPos::offset, blockPos::seq, blockPos::size, slAddHead, and slReverse().

{
/* Clump together hits. */
int block;
int i;
int maxGap = ps->maxGap;
struct blockPos first, cur, pre;
struct patClump *patClump = NULL, *cl;

bfFind(ps, hitBlocks[0], &first);
pre = first;
for (i=1; i<hitCount; ++i)
    {
    block = hitBlocks[i];
    bfFind(ps, block, &cur);
    if (cur.seq != pre.seq || cur.offset - (pre.offset + pre.size) > maxGap)
        {
        /* Write old clump and start new one. */
        cl = newClump(ps, &first, &pre);
        slAddHead(&patClump, cl);
        first = cur;
        }
    else
        {
        /* Extend old clump. */
        }
    pre = cur;
    }
/* Write hitOut last clump. */
cl = newClump(ps, &first, &pre);
slAddHead(&patClump, cl);
slReverse(&patClump);
return patClump;
}

Here is the call graph for this function:

static void countPatSpace	(	struct patSpace *	ps,
		struct dnaSeq *	seq
	)			[static]

Definition at line 112 of file patSpace.c.

References dnaSeq::dna, patSpace::listSizes, mask, maxPatCount, ntValNoN, patSpace::seedSize, patSpace::seedSpaceSize, and dnaSeq::size.

Referenced by makePatSpace().

{
int size = seq->size;
int mask = ps->seedSpaceSize-1;
DNA *dna = seq->dna;
int i;
int bits = 0;
int bVal;
int ls;

for (i=0; i<ps->seedSize-1; ++i)
    {
    bVal = ntValNoN[(int)dna[i]];
    bits <<= 2;
    bits += bVal;
    }
for (i=ps->seedSize-1; i<size; ++i)
    {
    bVal = ntValNoN[(int)dna[i]];
    bits <<= 2;
    bits += bVal;
    bits &= mask;
    ls = ps->listSizes[bits];
    if (ls < maxPatCount)
        ps->listSizes[bits] = ls+1;
    }
}

Here is the caller graph for this function:

static void fixBlockSize	(	struct blockPos *	bp,
		int	blockIx
	)			[static]

Definition at line 85 of file patSpace.c.

References blockSize, blockPos::offset, blockPos::seq, blockPos::size, and dnaSeq::size.

Referenced by addToPatSpace().

{
struct dnaSeq *seq = bp->seq;
int size = seq->size - bp->offset;
if (size > blockSize)
        size = blockSize;
bp->size = size;
}

Here is the caller graph for this function:

void freePatSpace

(

struct patSpace **

pPatSpace

)

Definition at line 68 of file patSpace.c.

References patSpace::allocated, freeMem(), and freez().

{
struct patSpace *ps = *pPatSpace;
if (ps != NULL)
    {
    freeMem(ps->allocated);
    freez(pPatSpace);
    }
}

Here is the call graph for this function:

struct patSpace* makePatSpace	(	struct dnaSeq **	seqArray,
		int	seqArrayCount,
		int	seedSize,
		char *	oocFileName,
		int	minMatch,
		int	maxGap
	)			[read]

Definition at line 247 of file patSpace.c.

References addToPatSpace(), allocPatSpaceLists(), patSpace::blocksUsed, countPatSpace(), patSpace::listSizes, maxBlockCount, patSpace::maxPat, maxPatCount, newPatSpace(), dnaSeq::next, oocMaskCounts(), oocMaskSimpleRepeats(), psBits, patSpace::seedSize, patSpace::seedSpaceSize, dnaSeq::size, and tooManyBlocks().

{
struct patSpace *ps = newPatSpace(minMatch, maxGap,seedSize);
int i;
int startIx = 0;
int total = 0;
struct dnaSeq *seq;
psBits maxPat;
psBits *listSizes;
int seedSpaceSize = ps->seedSpaceSize;

maxPat = ps->maxPat = maxPatCount;
for (i=0; i<seqArrayCount; ++i)
    {
    for (seq = seqArray[i]; seq != NULL; seq = seq->next)
        {
        total += seq->size;
        countPatSpace(ps, seq);
        }
    }

listSizes = ps->listSizes;

/* Scan through over-popular patterns and set their count to value 
 * where they won't be added to pat space. */
oocMaskCounts(oocFileName, listSizes, ps->seedSize, maxPat);

/* Get rid of simple repeats as well. */
oocMaskSimpleRepeats(listSizes, ps->seedSize, maxPat);


allocPatSpaceLists(ps);

/* Zero out pattern counts that aren't oversubscribed. */
for (i=0; i<ps->seedSpaceSize; ++i)
    {
    if (listSizes[i] < maxPat)
        listSizes[i] = 0;
    }
for (i=0; i<seqArrayCount; ++i)
    {
        int j;
    for (seq = seqArray[i], j=0; seq != NULL; seq = seq->next, ++j)
        {
        startIx = addToPatSpace(ps, i, j, seq, startIx);
        if (startIx >= maxBlockCount)
            tooManyBlocks();
        }
    }
ps->blocksUsed = startIx;

/* Zero local over-popular patterns. */
for (i=0; i<seedSpaceSize; ++i)
    {
    if (listSizes[i] >= maxPat)
        listSizes[i] = 0;
    }

return ps;
}

Here is the call graph for this function:

static struct patClump* newClump	(	struct patSpace *	ps,
		struct blockPos *	first,
		struct blockPos *	last
	)			[static, read]

Definition at line 327 of file patSpace.c.

References AllocVar, patClump::bacIx, blockPos::bacIx, blockSize, blockPos::offset, patClump::seq, blockPos::seq, patClump::seqIx, blockPos::seqIx, patClump::size, dnaSeq::size, blockPos::size, and patClump::start.

Referenced by clumpHits(), and targetClump().

{
struct dnaSeq *seq = first->seq;
int seqIx = first->seqIx;
int bacIx = first->bacIx;
int start = first->offset;
int end = last->offset+last->size;
int extraAtEnds = blockSize/2;
struct patClump *cl;

start -= extraAtEnds;
if (start < 0)
    start = 0;
end += extraAtEnds;
if (end >seq->size)
    end = seq->size;
AllocVar(cl);
cl->bacIx = bacIx;
cl->seqIx = seqIx;
cl->seq = seq;
cl->start = start;
cl->size = end-start;
return cl;
}

Here is the caller graph for this function:

static struct patSpace* newPatSpace	(	int	minMatch,
		int	maxGap,
		int	seedSize
	)			[static, read]

Definition at line 95 of file patSpace.c.

References AllocVar, patSpace::lists, patSpace::listSizes, patSpace::maxGap, patSpace::minMatch, needLargeZeroedMem(), patSpace::seedSize, and patSpace::seedSpaceSize.

Referenced by makePatSpace().

{
struct patSpace *ps;
int seedBitSize = seedSize*2;
int seedSpaceSize;

AllocVar(ps);
ps->seedSize = seedSize;
seedSpaceSize = ps->seedSpaceSize = (1<<seedBitSize);
ps->lists = needLargeZeroedMem(seedSpaceSize * sizeof(ps->lists[0]));
ps->listSizes = needLargeZeroedMem(seedSpaceSize * sizeof(ps->listSizes[0]));
ps->minMatch = minMatch;
ps->maxGap = maxGap;
return ps;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct patClump* patSpaceFindOne	(	struct patSpace *	ps,
		DNA *	dna,
		int	dnaSize
	)			[read]

Definition at line 392 of file patSpace.c.

References patSpace::blocksUsed, patSpace::hitBlocks, patSpace::lists, patSpace::listSizes, minMatch, patSpace::minMatch, ntValNoN, patSpace::posBuf, psBits, and patSpace::seedSize.

Referenced by ssFindBundles().

{
int lastStart = dnaSize - ps->seedSize;
int i,j;
int pat;
int hitBlockCount = 0;
int totalSigHits = 0;
DNA *tile = dna;
int blocksUsed = ps->blocksUsed;
int *posBuf = ps->posBuf;
int *hitBlocks = ps->hitBlocks;
int minMatch = ps->minMatch;

memset(ps->posBuf, 0, sizeof(ps->posBuf[0]) * blocksUsed);
for (i=0; i<=lastStart; i += ps->seedSize)
    {
    psBits *list;
    psBits count;

    pat = 0;
    for (j=0; j<ps->seedSize; ++j)
        {
        int bVal = ntValNoN[(int)tile[j]];
        pat <<= 2;
        pat += bVal;
        }
    list = ps->lists[pat];
    if ((count = ps->listSizes[pat]) > 0)
        {
        for (j=0; j<count; ++j)
            posBuf[list[j]] += 1;            
        }
    tile += ps->seedSize;
    }

/* Scan through array that records counts of hits at positions. */
for (i=0; i<blocksUsed-1; ++i)
    {
    /* Save significant hits in a more compact array */
    int a = posBuf[i], b = posBuf[i+1];
    int sum = a + b;
    if (sum >= minMatch)
        {
        if (a > 0)
            {
            if (hitBlockCount == 0 || hitBlocks[hitBlockCount-1] != i)
                {
                hitBlocks[hitBlockCount++] = i;
                totalSigHits += a;
                }
            }
        if (b > 0)
            {
            hitBlocks[hitBlockCount++] = i+1;
            totalSigHits += b;
            }
        }
    }

/* Output data with significant hits. */
if (hitBlockCount > 0 && totalSigHits*ps->seedSize*8 > dnaSize)
    {
    return clumpHits(ps, hitBlocks, hitBlockCount, posBuf, dna, 
        dnaSize);
    }        
else
    return NULL;
}

Here is the caller graph for this function:

void tooManyBlocks

(

)

Definition at line 79 of file patSpace.c.

References errAbort(), and maxBlockCount.

Referenced by addToPatSpace(), and makePatSpace().

{
errAbort("Too many blocks, can only handle %d\n", maxBlockCount);
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

char const rcsid[] = "$Id: patSpace.c,v 1.3 2006/03/15 18:36:16 angie Exp $" [static]

Definition at line 10 of file patSpace.c.

---