include/wordLookupDFA.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	group
Functions
void	wordLookupDFA_build (struct PSSMatrix PSSMatrix, int4 numCodes, int4 wordLength)
void	wordLookupDFA_print ()
void	wordLookupDFA_free ()
Variables
uint2 *	wordLookupDFA_additionalQueryPositions
int4	wordLookupDFA_numAdditionalQueryPositions
group *	wordLookupDFA_groups
int4	wordLookupDFA_numCodes
int4	wordLookupDFA_wordLength
int4	wordLookupDFA_numBlocks

---

Function Documentation

void wordLookupDFA_build	(	struct PSSMatrix	PSSMatrix,
		int4	numCodes,
		int4	wordLength
	)

Definition at line 51 of file wordLookupDFA.c.

References initialWord::allocQueryPositions, memSingleBlock::block, codeword::codeword, neighbour::codeword, queryPosition::codewords, constants_initialAllocCodewordQueryPositions, constants_max_int2, encoding_alphabetType, encoding_nucleotide, global_malloc(), global_realloc(), aaFrequencyGroup::groups, int2, int4, PSSMatrix::length, memSingleBlock_free(), memSingleBlock_getEntry(), memSingleBlock_initialize(), memSingleBlock_newEntry(), codeword::next, group::nextGroups, group::nextWords, memSingleBlock::numEntries, initialWord::numQueryPositions, qPosList_addList(), qPosList_free(), qPosList_initialize(), qPosList_numQPosLists, qPosList_processLists(), qPosList_qPosLists, qPosList_reset(), queryPosition::queryPosition, initialWord::queryPositions, uint2, wordLookupDFA, wordLookupDFA_additionalQueryPositions, wordLookupDFA_blockAddresses, wordLookupDFA_calcFrequencyGroups(), wordLookupDFA_getNeighbours(), wordLookupDFA_groups, wordLookupDFA_numAdditionalQueryPositions, wordLookupDFA_numBlocks, wordLookupDFA_numCodes, and wordLookupDFA_wordLength.

Referenced by main().

{
        struct initialWord* initialWords, *initialWord;
    int4 numExternalPositions = 0;
    unsigned char *currentBlock, *currentPosition;
    int2 *startExternalPositions, *endExternalPositions;
    int2 *externalPositions[numCodes];
        int4 count, count2, groupCount, groupCodeword, match;
        struct aaFrequencyGroup* aaFrequencyGroups;
    int4 codeword, codeword2, queryPosition, *groupList1, *groupList2 = NULL;
        unsigned char code;
        int4 queryPositionCount;
    struct neighbour* neighbours = NULL;
    int4 numNeighbours;
    int4 numWords, numGroups;
        struct memSingleBlock** groupsHash, **groupLists, *groupList;
        struct memSingleBlock* queryPositionList;
    struct queryPosition* queryPositionEntry;
    struct codeword* oldCodeword;

    // Record word lookup structure size details
    wordLookupDFA_numCodes = numCodes;
    wordLookupDFA_wordLength = wordLength;

    // Start with no additional query positions
        wordLookupDFA_additionalQueryPositions = NULL;
    wordLookupDFA_numAdditionalQueryPositions = 0;

    // Maximum number of entry codewords and group codewords
    numWords = ceil(pow(numCodes, wordLength));
        numGroups = ceil(pow(numCodes, wordLength - 1));

    // Declare memory to construct initial words
        initialWords = (struct initialWord*)global_malloc(sizeof(struct initialWord)
                 * numWords);

    // Declare memory to hold list of neighbours for current query word
    if (encoding_alphabetType != encoding_nucleotide)
        neighbours = (struct neighbour*)global_malloc(sizeof(struct neighbour) * numWords);

    // Stage 1 - Build initial word structure which contains, for each gram
    // a list of query positions that are high scoring

    // Iterate through every possible codeword
    codeword = 0;
    while (codeword < numWords)
    {
        // Initialize list of query positions as empty
                initialWords[codeword].queryPositions = NULL;
                initialWords[codeword].numQueryPositions = 0;
                initialWords[codeword].allocQueryPositions = 0;

        codeword++;
    }

    // Slide a word-sized window across the query
    queryPosition = 0;
    while (queryPosition < PSSMatrix.length - wordLength + 1)
    {
        // Get neighbours for the current query word
        numNeighbours = 0;
        wordLookupDFA_getNeighbours(PSSMatrix, queryPosition, &numNeighbours,
                                    neighbours);

        while (numNeighbours > 0)
        {
                numNeighbours--;
            codeword = neighbours[numNeighbours].codeword;

            initialWord = initialWords + codeword;

            initialWord->numQueryPositions++;

            // Allocate memory to store additional query position if needed
            if (initialWord->numQueryPositions > initialWord->allocQueryPositions)
            {
                initialWord->allocQueryPositions
                    += constants_initialAllocCodewordQueryPositions;
                initialWord->queryPositions = (int2*)global_realloc(initialWord->queryPositions,
                    sizeof(int2) * initialWord->allocQueryPositions);
            }

            // Add query position to codeword (record position at END of word)
            initialWord->queryPositions[initialWord->numQueryPositions - 1] =
                queryPosition + wordLength - 1;

            // Record total number of query positions that will not fit into
            // a unsigned char and will need to be stored externally
            if (initialWord->numQueryPositions == 1)
            {
                numExternalPositions += 2;
            }
            else
            {
                numExternalPositions++;
            }
        }

        queryPosition++;
    }

    free(neighbours);

    // Contruct array of list of groups that share the same first query position
    groupsHash = (struct memSingleBlock**)global_malloc(sizeof(struct memSingleBlock*) * PSSMatrix.length);

    // Initialize each array cell to an empty list
    queryPosition = 0;
    while (queryPosition < PSSMatrix.length)
    {
                groupsHash[queryPosition] = memSingleBlock_initialize(sizeof(struct memSingleBlock*), 10);
        queryPosition++;
        }

    // Go through each group
    groupCodeword = 0;
    while (groupCodeword < numGroups)
    {
        // Find the first query position in the group
        code = 0;
        queryPosition = 0;
        while (code < numCodes && queryPosition == 0)
        {
            codeword = groupCodeword * numCodes + code;

            // Found an entry
            if (initialWords[codeword].numQueryPositions > 0)
            {
                                queryPosition = initialWords[codeword].queryPositions[0];
            }

            code++;
        }

        // Add group's code to hash using that query position
        // (If no query positions, add to hash under the zero entry)
        groupList = memSingleBlock_initialize(sizeof(struct memSingleBlock*), 1);
        *((int4*)memSingleBlock_newEntry(groupList)) = groupCodeword;
                *((struct memSingleBlock**)memSingleBlock_newEntry(groupsHash[queryPosition])) = groupList;

                groupCodeword++;
    }

    // For each entry in the hash table
    queryPosition = 0;
    while (queryPosition < PSSMatrix.length)
    {
        groupLists = (struct memSingleBlock**)groupsHash[queryPosition]->block;
        // For each group entry A in that hash
        count = 0;
        while (count < groupsHash[queryPosition]->numEntries)
        {
                        // For each group entry B after A in the hash
            count2 = count + 1;
                        while(count2 < groupsHash[queryPosition]->numEntries)
            {
                // If both entries contain at least one group
                if (groupLists[count]->numEntries > 0 && groupLists[count2]->numEntries > 0)
                {
                    // Check if they have matching query positions
                    match = 1;
                    code = 0;
                    while (code < numCodes)
                    {
                        // For each word in the group
                        groupList1 = (int4*)(groupLists[count]->block);
                        groupList2 = (int4*)(groupLists[count2]->block);

                        codeword = groupList1[0] * numCodes + code;
                        codeword2 = groupList2[0] * numCodes + code;

                        // Check if the number of positions matches
                        if (initialWords[codeword].numQueryPositions !=
                            initialWords[codeword2].numQueryPositions)
                        {
                            // No match, break out
                            match = 0;
                            break;
                        }

                        // Move though the query positions and check for matches
                        queryPositionCount = 0;
                        while (queryPositionCount < initialWords[codeword].numQueryPositions)
                        {
                            // If they don't match at this position
                            if (initialWords[codeword].queryPositions[queryPositionCount] !=
                                initialWords[codeword2].queryPositions[queryPositionCount])
                            {
                                // No match, break out
                                match = 0;
                                break;
                            }
                            queryPositionCount++;
                        }

                        code++;
                    }

                    if (match)
                    {
                        // Move group in entry B to entry A
                        *((int4*)memSingleBlock_newEntry(groupLists[count])) = groupList2[0];

                        // Remove group from entry B
                        groupLists[count2]->numEntries = 0;
                    }
                                }

                count2++;
            }

                count++;
        }

        queryPosition++;
        }

    // Calculate frequencies of all possible groups of codes length one less than
    // the full word length and then arrange them so the most frequent have central positions
    aaFrequencyGroups = wordLookupDFA_calcFrequencyGroups(groupsHash, PSSMatrix,
                                                          numCodes, wordLength - 1);

    // Declare memory for addresses of group sized blocks
    wordLookupDFA_blockAddresses = (unsigned char**)global_malloc(sizeof(unsigned char*) * numGroups);

    // Declare memory for final words
        wordLookupDFA = (unsigned char*)global_malloc(sizeof(char) * numWords + sizeof(int2)
                  * numExternalPositions + sizeof(int2) * numExternalPositions);

    // Declare memory to store additional query positions
    // (we assume worst case scenario where all positions are addition positions)
    wordLookupDFA_additionalQueryPositions
        = (uint2*)((char*)wordLookupDFA + sizeof(char) * numWords
          + sizeof(int2) * numExternalPositions);

        currentBlock = wordLookupDFA;

    // Initialize query position list construction
    qPosList_initialize(numCodes);

    // Stage 2 - Construct the more compact, final wordLookupDFA structure that is arranged
    // with high frequency words in the middle (protein only)

    // For each collection of groups with the same set of query positions
    count = 0;
        while (count < wordLookupDFA_numBlocks)
    {
        groupList = aaFrequencyGroups[count].groups;
        groupList1 = (int4*)(groupList->block);

        // Use first group entry for constructing the block
        groupCodeword = groupList1[0];

        // First comes the external codes.
        startExternalPositions = (int2*)(currentBlock);
        endExternalPositions = startExternalPositions;

                qPosList_reset();

        // For each word in this block
        code = 0;
        while (code < numCodes)
        {
                // Determine codeword
            codeword = groupCodeword * numCodes + code;
            queryPositionCount = initialWords[codeword].numQueryPositions;

            // Add list of query positions for this word to the qPosList structure
                        qPosList_addList(initialWords[codeword].queryPositions,
                             initialWords[codeword].numQueryPositions, code);

                        code++;
        }

        // Process the list of query positions to create an optimal set of lists
                qPosList_processLists();

        // For each query position list in order from shortest to longest
        while (qPosList_numQPosLists > 0)
        {
                qPosList_numQPosLists--;
            queryPositionList = qPosList_qPosLists + qPosList_numQPosLists;

            // First check that there is room for the list in external area,
            // plus at least 3 int2s for each remaining code all within
            // the range of an unsigned char (256)
            if (endExternalPositions - startExternalPositions + queryPositionList->numEntries
                + 1 >= 256 - 3 * numCodes)
                        {
                // If not, we need to store this word's query positions
                // at a completely external location

                // Copy values to additional positions address
                count2 = queryPositionList->numEntries;
                while (count2 > 0)
                {
                        count2--;
                        queryPositionEntry = memSingleBlock_getEntry(queryPositionList, count2);

                                        // Copy the query position
                    wordLookupDFA_additionalQueryPositions[
                        wordLookupDFA_numAdditionalQueryPositions]
                        = queryPositionEntry->queryPosition;

                    // If a codeword list starts at this point
                                        while (queryPositionEntry->codewords != NULL)
                    {
                        // Get each code
                        code = queryPositionEntry->codewords->codeword;

                        // Add address information to external positions
                        // First flag to indicate additional positions
                        *endExternalPositions = 0;

                        // That's where the word->queryPosition will point to
                        externalPositions[code] = endExternalPositions;
                        endExternalPositions++;

                        // Then the offset into the array where they start
                        // (Record across two int2's to support very long queries)
                        *endExternalPositions = wordLookupDFA_numAdditionalQueryPositions / constants_max_int2;
                        endExternalPositions++;
                        *endExternalPositions = wordLookupDFA_numAdditionalQueryPositions % constants_max_int2;
                        endExternalPositions++;

                        // Free the current codeword before moving to the next
                        oldCodeword = queryPositionEntry->codewords;
                        queryPositionEntry->codewords = queryPositionEntry->codewords->next;
                        free(oldCodeword);
                    }

                        // Increment number of additional query positions
                    wordLookupDFA_numAdditionalQueryPositions++;
                }

                // Add terminating zero
                wordLookupDFA_additionalQueryPositions[
                    wordLookupDFA_numAdditionalQueryPositions] = 0;

                // Increment number of additional query positions
                wordLookupDFA_numAdditionalQueryPositions++;
            }
            else
            {
                // Use external location for list of query positions

                // Copy values to external positions address
                count2 = queryPositionList->numEntries;
                while (count2 > 0)
                {
                        count2--;
                        queryPositionEntry = memSingleBlock_getEntry(queryPositionList, count2);

                                        // Copy the query position
                    *endExternalPositions = queryPositionEntry->queryPosition;

                    // If a codeword list starts at this point
                                        while (queryPositionEntry->codewords != NULL)
                    {
                        // Get each code
                        code = queryPositionEntry->codewords->codeword;

                        // The word will point to this external position
                        externalPositions[code] = endExternalPositions;

                        // Free the current codeword before moving to the next
                        oldCodeword = queryPositionEntry->codewords;
                        queryPositionEntry->codewords = queryPositionEntry->codewords->next;
                        free(oldCodeword);
                                        }

                    endExternalPositions++;
                                }

                // Add zero terminal code
                *endExternalPositions = 0;
                endExternalPositions++;
            }
        }

        // Next comes the block structure
        currentPosition = (unsigned char*)endExternalPositions;

        // For each group, point to that block
        groupCount = 0;
        while (groupCount < groupList->numEntries)
        {
            wordLookupDFA_blockAddresses[groupList1[groupCount]] = currentPosition;
            groupCount++;
        }

        // Free the group list
        memSingleBlock_free(groupList);

        code = 0;
        while (code < numCodes)
        {
            codeword = groupCodeword * numCodes + code;

            queryPositionCount = initialWords[codeword].numQueryPositions;

            // No query positions, store NULL both 16-bit integers
            if (queryPositionCount == 0)
            {
                *currentPosition = 0;
            }
            // At least one query position
            else
            {
                // Give location of external query positions
                *currentPosition
                        = (unsigned char)(((char*)endExternalPositions -
                                       (char*)externalPositions[code]) / sizeof(int2));
            }

            // Free memory used by initial structure
            free(initialWords[codeword].queryPositions);

            code++;
            currentPosition++;
        }
        currentBlock = currentPosition;

        count++;
        }

    free(initialWords);
    free(aaFrequencyGroups);

    // Free the query position lists structure
    qPosList_free();

    // New stage 3 - construct groups lookup FSA structure

    // Declare memory for group states
    wordLookupDFA_groups = (struct group*)global_malloc(sizeof(struct group) * numGroups);

    // For each group
    groupCodeword = 0;
    while (groupCodeword < numGroups)
    {
        // Get block associated with current group
        currentBlock = wordLookupDFA_blockAddresses[groupCodeword];

                // Set pointer to block of words
        wordLookupDFA_groups[groupCodeword].nextWords = currentBlock;

        // Set pointer to next groups
                wordLookupDFA_groups[groupCodeword].nextGroups =
                        wordLookupDFA_groups + ((groupCodeword * numCodes) % numGroups);

        groupCodeword++;
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void wordLookupDFA_free

(

)

Definition at line 917 of file wordLookupDFA.c.

References wordLookupDFA, wordLookupDFA_blockAddresses, and wordLookupDFA_groups.

Referenced by main().

{
        free(wordLookupDFA_groups);
    free(wordLookupDFA);
    free(wordLookupDFA_blockAddresses);
}

Here is the caller graph for this function:

void wordLookupDFA_print

(

)

Definition at line 798 of file wordLookupDFA.c.

References encoding_alphabetType, encoding_getLetter(), encoding_protein, int4, uint2, uint4, wordLookupDFA_additionalQueryPositions, wordLookupDFA_blockAddresses, wordLookupDFA_getCodeword(), wordLookupDFA_numBlocks, wordLookupDFA_numCodes, and wordLookupDFA_wordLength.

{
    unsigned char *currentBlock;
        unsigned char codes[wordLookupDFA_wordLength + 1], code;
        unsigned char word;
        int4 groupCodeword;
        uint2* queryPositions;
    int4 totalQueryPositions = 0, totalEmptySlots = 0;
        int4 count;
    int4 numWords, numGroups;
    int4 numCodes, wordLength;
    uint4 codeCount;

        numCodes = wordLookupDFA_numCodes;
    wordLength = wordLookupDFA_wordLength;

    // Determine number of codewords and number of groups
    numGroups = ceil(pow(numCodes, wordLength - 1));
    numWords = ceil(pow(numCodes, wordLength));

    // Initialize word to first position
    codeCount = 0;
    while (codeCount <= wordLength - 1)
    {
        codes[codeCount] = 0;
        codeCount++;
    }

    // Iterate - For each possible group
        while (!codes[wordLength - 1])
    {
        // Construct the codeword for array of codes
                groupCodeword = wordLookupDFA_getCodeword(codes, wordLength - 1);

        // Get current block
        currentBlock = wordLookupDFA_blockAddresses[groupCodeword];

        // For each word in the group
        code = 0;
        while (code < numCodes)
        {
            // Get word in the block
            word = currentBlock[code];

            if (encoding_alphabetType == encoding_protein || word != 0)
            {
                //  Print the word
                codeCount = 0;
                while (codeCount < wordLength - 1)
                {
                    printf("%c", encoding_getLetter(codes[codeCount]));
                    codeCount++;
                }
                printf("%c", encoding_getLetter(code));

                printf(" QueryPositions ");
                fflush(stdout);

                printf("[%d]: ", word);

                if (word == 0)
                {
                    // No query positions
                    totalEmptySlots++;
                }
                else
                {
                    // At least one position at an external address
                    queryPositions = ((uint2*)currentBlock) - word;

                    // If the zero flag is stored at the first query position
                    if (!*queryPositions)
                    {
                        // Go to an outside address for additional positions
                                                queryPositions = wordLookupDFA_additionalQueryPositions
                                       + *(queryPositions + 1);
                    }

                    count = 0;
                    while (queryPositions[count] != 0)
                    {
                        printf("%d ", queryPositions[count] - 1);
                        totalQueryPositions++;
                        fflush(stdout);
                        count++;
                    }
                }

                printf("\n");
            }

            code++;
                }

        // Move to next word
                codes[0]++;
        codeCount = 0;
        while (codeCount < wordLength - 1)
        {
                        if (codes[codeCount] >= numCodes)
            {
                codes[codeCount] = 0;
                codes[codeCount + 1]++;
            }
            else
            {
                break;
            }
            codeCount++;
        }
    }

    printf("Total query positions=%d\n", totalQueryPositions);
    printf("Empty slots=%d/%d (%d%%)\n", totalEmptySlots, numWords,
                                         totalEmptySlots * 100 / numWords);
        printf("Number of blocks/groups=%d/%d\n", wordLookupDFA_numBlocks, numGroups);
}

Here is the call graph for this function:

---

Variable Documentation

uint2* wordLookupDFA_additionalQueryPositions

Definition at line 14 of file wordLookupDFA.c.

Referenced by search_protein1hit(), search_protein2hit(), wordLookupDFA_build(), and wordLookupDFA_print().

struct group* wordLookupDFA_groups

Definition at line 16 of file wordLookupDFA.c.

Referenced by search_protein1hit(), search_protein2hit(), wordLookupDFA_build(), and wordLookupDFA_free().

int4 wordLookupDFA_numAdditionalQueryPositions

Definition at line 15 of file wordLookupDFA.c.

Referenced by wordLookupDFA_build().

int4 wordLookupDFA_numBlocks

Definition at line 17 of file wordLookupDFA.c.

Referenced by wordLookupDFA_build(), wordLookupDFA_calcFrequencyGroups(), and wordLookupDFA_print().

int4 wordLookupDFA_numCodes

Definition at line 17 of file wordLookupDFA.c.

Referenced by search_protein1hit(), search_protein2hit(), wordLookupDFA_build(), wordLookupDFA_findNeighbours(), wordLookupDFA_getCodes(), wordLookupDFA_getCodeword(), and wordLookupDFA_print().

int4 wordLookupDFA_wordLength

Definition at line 17 of file wordLookupDFA.c.

Referenced by wordLookupDFA_build(), wordLookupDFA_findNeighbours(), wordLookupDFA_getNeighbours(), and wordLookupDFA_print().

---