include/index.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	indexCoordinate
struct	wordList
struct	queryWord
Functions
void	index_initializeBuild (uint4 fromCodeword, uint4 toCodeword)
void	index_addSubject (unsigned char *subject, uint4 subjectLength, uint4 fromCodeword, uint4 toCodeword)
void	index_finishBuild (uint4 fromCodeword, uint4 toCodeword)
uint4 *	index_wordOffsetPositions ()
uint4	index_numWordOffsets (uint4 codeword)
unsigned char *	index_wordOffsets (uint4 codeword)
void	index_processQuery (unsigned char *startIndex, struct PSSMatrix PSSMatrix, uint4 collectionSize)
indexCoordinate *	index_getFirstCoordinate ()
indexCoordinate *	index_getNextCoordinate ()
uint4	index_generateCodeword (unsigned char *word, uint4 wordSize)
void	index_print ()
Variables
uint4	index_wordSize
uint4	index_intervalSize
indexCoordinate **	index_sequenceCoordinates
indexCoordinate *	index_coordinates
uint4	index_numCoordinates
uint4 *	index_sequencePositions
uint4 *	index_descriptionLocations

---

Function Documentation

void index_addSubject	(	unsigned char *	subject,
		uint4	subjectLength,
		uint4	fromCodeword,
		uint4	toCodeword
	)

Definition at line 77 of file index.c.

References index_addWord(), index_generateCodeword(), index_intervalSize, index_subjectNumber, index_wordSize, and uint4.

Referenced by main().

{
        uint4 codeword, wordOffset;

    // Add subjectNumber and offset to lists for each word
        wordOffset = 0;
    while (wordOffset + index_wordSize - 1 < subjectLength)
    {
        // For this word
        codeword = index_generateCodeword(subject + wordOffset, index_wordSize);

        // If it is in the range of codewords we are considering
        if (codeword >= fromCodeword && codeword < toCodeword)
        {
            // Record subject number and offset of word in index
            index_addWord(codeword, index_subjectNumber, wordOffset / index_intervalSize);// + (index_wordSize - 4));
                }

        // Index every Nth word
        wordOffset += index_intervalSize;
    }

    index_subjectNumber++;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void index_finishBuild	(	uint4	fromCodeword,
		uint4	toCodeword
	)

Definition at line 58 of file index.c.

References index_words, wordList::offsets, and uint4.

Referenced by main().

{
        uint4 codeword;

    // For each word
    codeword = fromCodeword;
    while (codeword < toCodeword)
    {
        // Free list
        free(index_words[codeword].offsets);
        codeword++;
    }

    // Free the lists
        index_words += fromCodeword;
    free(index_words);
}

Here is the caller graph for this function:

uint4 index_generateCodeword	(	unsigned char *	word,
		uint4	wordSize
	)

struct indexCoordinate* index_getFirstCoordinate

(

)

[read]

Definition at line 376 of file index.c.

References index_currentCoordinate, and index_getNextCoordinate().

{
    // Reset counters
        index_currentCoordinate = 0;

    // Get coordinate
    return index_getNextCoordinate();
}

Here is the call graph for this function:

struct indexCoordinate* index_getNextCoordinate

(

)

[read]

Definition at line 386 of file index.c.

References index_coordinates, index_currentCoordinate, and index_numCoordinates.

Referenced by index_getFirstCoordinate().

{
        struct indexCoordinate* coordinate;

    if (index_currentCoordinate >= index_numCoordinates)
        return NULL;

    // Get current coordinate and return it
        coordinate = index_coordinates + index_currentCoordinate;
        index_currentCoordinate++;

    return coordinate;
}

Here is the caller graph for this function:

void index_initializeBuild	(	uint4	fromCodeword,
		uint4	toCodeword
	)

Definition at line 32 of file index.c.

References wordList::allocated, global_malloc(), index_subjectNumber, index_words, wordList::lastOffset, wordList::lastSequenceNumber, wordList::length, wordList::offsets, and uint4.

Referenced by main().

{
        uint4 codeword;

//      index_numWords = pow(4, index_wordSize);
    index_words = (struct wordList*)global_malloc(sizeof(struct wordList) * (toCodeword - fromCodeword));
        index_words -= fromCodeword;

    // For each word
    codeword = fromCodeword;
    while (codeword < toCodeword)
    {
        // Initialize list of occurrences
        index_words[codeword].offsets = NULL;
                index_words[codeword].length = 0;
        index_words[codeword].allocated = 0;
        index_words[codeword].lastOffset = 0;
        index_words[codeword].lastSequenceNumber = 0;

        codeword++;
    }

    index_subjectNumber = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

uint4 index_numWordOffsets

(

uint4

codeword

)

Definition at line 144 of file index.c.

References index_words, and wordList::length.

Referenced by main().

{
        return index_words[codeword].length;
}

Here is the caller graph for this function:

void index_print

(

)

Definition at line 462 of file index.c.

References index_numWords, index_words, wordList::length, wordList::offsets, uint4, and vbyte_getVbyte.

{
        uint4 codeword = 0;
        struct wordList* wordList;
    unsigned char* offsets, *endOffsets;
    uint4 offsetGap, offset, numOffsets;
        uint4 totalSize = 0;

    while (codeword < index_numWords)
    {
        numOffsets = 0; offset = 0;

        wordList = index_words + codeword;

                offsets = wordList->offsets;
        endOffsets = offsets + wordList->length;

        totalSize += wordList->length;

        if (offsets < endOffsets)
                printf("\nCodeword=%u:", codeword);

        while (offsets < endOffsets)
        {
                        vbyte_getVbyte(offsets, (&offsetGap));
            offset += offsetGap;
            printf(" %u", offset);
            numOffsets++;
        }

//      printf("[%d/%d = %f]\n", wordList->length, numOffsets, (float)(wordList->length) / (float)numOffsets);

        codeword++;
    }

    printf("\nTotal table size=%d bytes\n", totalSize);
}

void index_processQuery	(	unsigned char *	startIndex,
		struct PSSMatrix	PSSMatrix,
		uint4	collectionSize
	)

Definition at line 161 of file index.c.

References alignments_compareCodeword(), alignments_compareQueryPosition(), PSSMatrix::bestMatchCodes, blast_numHits, queryWord::codeword, encoding_numRegularLetters, queryWord::endOffsets, global_malloc(), index_coordinates, index_descriptionLocations, index_generateCodeword(), index_intervalSize, index_loadedWords, index_numCoordinates, index_numWords, index_offsets, index_sequenceCoordinates, index_sequencePositions, index_wordSize, PSSMatrix::length, memBlocks_free(), memBlocks_getCurrent(), memBlocks_initialize(), memBlocks_newEntry(), memBlocks_resetCurrent(), memBlocks::numTotalEntries, queryWord::offsets, wordList::offsets, PSSMatrix::queryCodes, indexCoordinate::queryOffset, queryWord::queryPosition, PSSMatrix::strandLength, indexCoordinate::subjectNumber, indexCoordinate::subjectOffset, uint4, and vbyte_getVbyte.

{
        uint4 queryPosition, codeword = 0, queryPosition4;
    unsigned char* offsets, *endOffsets;
    uint4 offsetGap, offset, sequenceGap, sequenceNumber;
    struct indexCoordinate* coordinate;
        struct memBlocks* unsortedCoordinates;
    uint4 *numSubjectHits, numQueryPositions, queryWordCount, numOffsets;
    uint4 time, wordPosition, containsWildcard;
        struct queryWord* queryWords;

    // Read word and interval size from start of index
        vbyte_getVbyte(startIndex, &index_wordSize);
        vbyte_getVbyte(startIndex, &index_intervalSize);

        index_numWords = pow(4, index_wordSize);
    index_sequencePositions = (uint4*)startIndex;
    index_descriptionLocations = index_sequencePositions + numSequences;
        index_loadedWords = index_descriptionLocations + numSequences;
        index_offsets = (unsigned char*)(index_loadedWords + index_numWords + 1);

    time = clock();
    unsortedCoordinates = memBlocks_initialize(sizeof(struct indexCoordinate), numSequences);

    // Declare and initialize array for count number of hits for each sequence
    numSubjectHits = (uint*)global_malloc(sizeof(uint4) * numSequences);
        sequenceNumber = 0;
    while (sequenceNumber < numSequences)
    {
        numSubjectHits[sequenceNumber] = 0;
        sequenceNumber++;
    }

    // Memory to hold offsets string for each query word
    numQueryPositions = PSSMatrix.length - index_wordSize + 1;
        queryWords = (struct queryWord*)global_malloc(sizeof(struct queryWord) * numQueryPositions);

    // For each word in the query
    queryPosition = 0;
    while (queryPosition < numQueryPositions)
    {
        // Check if the word contains a wildcard
        containsWildcard = 0; wordPosition = 0;
        while (wordPosition < index_wordSize)
        {
            if (PSSMatrix.queryCodes[queryPosition + wordPosition] >= encoding_numRegularLetters)
                containsWildcard = 1;

            wordPosition++;
        }

        // Don't include words that cross the strand boundry or contain wildcards
        if (!containsWildcard && !(queryPosition < PSSMatrix.strandLength &&
              queryPosition >= PSSMatrix.strandLength - index_wordSize + 1))
                {
//            printf("--Query position=%d\n", queryPosition);

            // Get the codeword
            codeword = index_generateCodeword(PSSMatrix.bestMatchCodes + queryPosition, index_wordSize);

            // Get wordlist for that codeword
            offsets = index_offsets + index_loadedWords[codeword];
            endOffsets = index_offsets + index_loadedWords[codeword + 1];

            queryWords[queryPosition].offsets = offsets;
                        queryWords[queryPosition].endOffsets = endOffsets;
                        queryWords[queryPosition].queryPosition = queryPosition;
            queryWords[queryPosition].codeword = codeword;

//            printf("codeword=%d start=%d end=%d numHits=%d\n", codeword, index_loadedWords[codeword],
//                   index_loadedWords[codeword + 1], endOffsets - offsets);
                }
        else
        {
            queryWords[queryPosition].offsets = NULL;
                        queryWords[queryPosition].endOffsets = NULL;
                        queryWords[queryPosition].queryPosition = queryPosition;
            queryWords[queryPosition].codeword = codeword;
        }

//        printf("\n");
        queryPosition++;
    }

    // Sort the query words by codeword
        qsort(queryWords, numQueryPositions, sizeof(struct queryWord), alignments_compareCodeword);

    // For each query word
    queryWordCount = 0;
    while (queryWordCount < numQueryPositions)
    {
        // Ignoring those that cross the strand boundry
                if (queryWords[queryWordCount].offsets != NULL)
        {
                // Make in-memory copy of list of offsets
            numOffsets = queryWords[queryWordCount].endOffsets - queryWords[queryWordCount].offsets;
                        offsets = (char*)global_malloc(sizeof(char) * numOffsets);

            memcpy(offsets, queryWords[queryWordCount].offsets, numOffsets);
                        queryWords[queryWordCount].offsets = offsets;
            queryWords[queryWordCount].endOffsets = offsets + numOffsets;
                }

        queryWordCount++;
    }

    // Sort the query words by query position
        qsort(queryWords, numQueryPositions, sizeof(struct queryWord), alignments_compareQueryPosition);

    queryPosition = 0;
    while (queryPosition < numQueryPositions)
    {
        // Ignoring those that cross the strand boundry
                if (queryWords[queryPosition].offsets != NULL)
        {
                offsets = queryWords[queryPosition].offsets;
            endOffsets = queryWords[queryPosition].endOffsets;
            offset = 0;
            sequenceNumber = 0;
                queryPosition4 = queryPosition + (index_wordSize - 4);

            // Traverse the offsets
            while (offsets < endOffsets)
            {
                vbyte_getVbyte(offsets, (&sequenceGap));
                vbyte_getVbyte(offsets, (&offsetGap));

//                printf("[%d,%d]\n", sequenceGap, offsetGap);

                if (sequenceGap > 0)
                {
                        offset = offsetGap;
                    sequenceNumber += sequenceGap;
                }
                else
                {
                        offset += offsetGap;
                }
    //            printf(" %u", offset);

                // Add query/database coordinate of match to relevant bucket
//                printf("Sequence number=%d\n", sequenceNumber);
                coordinate = (struct indexCoordinate*)memBlocks_newEntry(unsortedCoordinates);
                coordinate->queryOffset = queryPosition4;
                coordinate->subjectOffset = offset * index_intervalSize + (index_wordSize - 4);
                coordinate->subjectNumber = sequenceNumber;

                numSubjectHits[sequenceNumber]++;
//                printf("[%d,%d]\n", queryPosition, offset);

                blast_numHits++;
            }

            free(queryWords[queryPosition].offsets);
                }

        queryPosition++;
        }


    printf("Time to process query=%f\n", (float)(clock() - time) / CLOCKS_PER_SEC);
    time = clock();

    // Make memory for sorted list
    index_numCoordinates = unsortedCoordinates->numTotalEntries;
        index_coordinates = (struct indexCoordinate*)global_malloc(
                         sizeof(struct indexCoordinate) * index_numCoordinates);
        index_sequenceCoordinates = (struct indexCoordinate**)global_malloc(
                                 sizeof(struct indexCoordinate*) * numSequences);

    // For each sequence
        coordinate = index_coordinates;
    sequenceNumber = 0;
    while (sequenceNumber < numSequences)
    {
        // If it has hits
        if (numSubjectHits[sequenceNumber] != 0)
        {
                // Point to location in sorted list of coordinates
                        index_sequenceCoordinates[sequenceNumber] = coordinate;
            coordinate += numSubjectHits[sequenceNumber];

            numSubjectHits[sequenceNumber] = 0;
        }
        sequenceNumber++;
    }

    // Move through list of unsorted coordinates
    memBlocks_resetCurrent(unsortedCoordinates);
    while ((coordinate = memBlocks_getCurrent(unsortedCoordinates)) != NULL)
    {
        sequenceNumber = coordinate->subjectNumber;
//      printf("%d,%d=[%d]\n", index_sequenceCoordinates[sequenceNumber], numSubjectHits[sequenceNumber], sequenceNumber);
        // Place into sorted list
                index_sequenceCoordinates[sequenceNumber][numSubjectHits[sequenceNumber]] = *coordinate;
                numSubjectHits[sequenceNumber]++;
    }

    memBlocks_free(unsortedCoordinates);

/*    // Print sorted coordinates
        coordinate = index_coordinates;
    while (coordinate < index_coordinates + index_numCoordinates)
    {
        printf("[%d]", coordinate);
        printf("Subject %d Offset %d,%d\n", coordinate->subjectNumber, coordinate->queryOffset,
                                            coordinate->subjectOffset);
        coordinate++;
    }*/

    printf("Time to sort buckets=%f\n", (float)(clock() - time) / CLOCKS_PER_SEC);
}

Here is the call graph for this function:

uint4* index_wordOffsetPositions

(

)

unsigned char* index_wordOffsets

(

uint4

codeword

)

Definition at line 150 of file index.c.

References index_words, and wordList::offsets.

Referenced by main().

{
        return index_words[codeword].offsets;
}

Here is the caller graph for this function:

---

Variable Documentation

struct indexCoordinate* index_coordinates

Definition at line 39 of file index.h.

Referenced by index_getNextCoordinate(), and index_processQuery().

uint4* index_descriptionLocations

Definition at line 43 of file index.h.

Referenced by index_processQuery().

uint4 index_intervalSize

Definition at line 19 of file index.c.

Referenced by index_addSubject(), index_processQuery(), and main().

uint4 index_numCoordinates

Definition at line 40 of file index.h.

Referenced by index_getNextCoordinate(), and index_processQuery().

struct indexCoordinate** index_sequenceCoordinates

Definition at line 38 of file index.h.

Referenced by index_processQuery().

uint4* index_sequencePositions

Definition at line 42 of file index.h.

Referenced by index_processQuery().

uint4 index_wordSize

Definition at line 19 of file index.c.

Referenced by index_addSubject(), index_processQuery(), and main().

---