include/alignments.h File Reference

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

Go to the source code of this file.

Functions
void	alignments_initialize ()
void	alignments_createNew (uint4 descriptionLocation, uint4 descriptionLength, unsigned char *subject, int4 subjectLength, int4 encodedLength)
void	alignments_addUngappedExtension (struct ungappedExtension *newExtension)
void	alignments_performScoring (struct PSSMatrix PSSMatrix)
void	alignments_getFinalAlignmentDescriptions ()
void	alignments_loadSubjectsIntoMemory (struct PSSMatrix PSSMatrix)
void	alignment_unpackSubject (struct alignment *alignment)
void	alignments_findGoodAlignments (struct PSSMatrix PSSMatrix)
void	alignments_findFinalAlignments (struct PSSMatrix PSSMatrix)
void	alignments_getTracebacks (struct PSSMatrix PSSMatrix)
int	alignments_isFinalAlignment (uint4 score)
void	alignments_addGappedExtension (struct alignment *alignment, struct gappedExtension *newExtension)
void	alignments_addFinalAlignment (int4 highestNominalScore, struct alignment *alignment)
void	alignments_sortFinalAlignments ()
void	alignments_free ()
Variables
memBlocks *	alignments_alignments
memSingleBlock *	alignments_goodAlignments
memSingleBlock *	alignments_finalAlignments
alignment *	alignments_currentAlignment
uint4	alignments_numClusters

---

Function Documentation

void alignment_unpackSubject

(

struct alignment *

alignment

)

void alignments_addFinalAlignment	(	int4	highestNominalScore,
		struct alignment *	alignment
	)

Definition at line 433 of file alignments.c.

References finalAlignment::alignment, alignments_finalAlignments, finalAlignment::description, finalAlignment::highestNominalScore, and memSingleBlock_newEntry().

Referenced by alignments_findFinalAlignments(), alignments_findTopFinalAlignments(), search_nucleotideSsearch(), and search_proteinSsearch().

{
        struct finalAlignment* finalAlignment;

    // Get a new final alignment entry
    finalAlignment = memSingleBlock_newEntry(alignments_finalAlignments);

        // Insert alignment information into the new final alignment
        finalAlignment->highestNominalScore = highestNominalScore;
        finalAlignment->alignment = alignment;
        finalAlignment->description = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_addGappedExtension	(	struct alignment *	alignment,
		struct gappedExtension *	newExtension
	)

Definition at line 164 of file alignments.c.

References alignment::gappedExtensions, gappedExtension::next, and gappedExtension::nominalScore.

Referenced by alignments_getTracebacks(), search_nucleotideSsearch(), and search_proteinSsearch().

{
        struct gappedExtension *currentExtension, *previousExtension;

        // If this is the first high-scoring gapped extension for this alignment
        if (alignment->gappedExtensions == NULL)
        {
                // Make this the first gapped extension in the alignment
                alignment->gappedExtensions = newExtension;
        }
        else
        {
                // Start at beginning of list of gapped extensions (one with highest score)
                currentExtension = alignment->gappedExtensions;
                previousExtension = NULL;

                // Move through list of existing extensions until we either reach the
                // end or reach one with a score less than newExtension
                while (currentExtension != NULL &&
                      (currentExtension->nominalScore > newExtension->nominalScore))
                {
                        previousExtension = currentExtension;
                        currentExtension = currentExtension->next;
                }

                if (previousExtension == NULL)
                {
                        // This is the highest scoring extension, insert at front of the queue
                        alignment->gappedExtensions = newExtension;
                        newExtension->next = currentExtension;
                }
                else
                {
                        // Insert between higher and lower scoring extensions
                        previousExtension->next = newExtension;
                        newExtension->next = currentExtension;
                }
        }
}

Here is the caller graph for this function:

void alignments_addUngappedExtension

(

struct ungappedExtension *

newExtension

)

Definition at line 122 of file alignments.c.

References alignments_currentAlignment, ungappedExtension::next, ungappedExtension::nominalScore, and alignment::ungappedExtensions.

Referenced by search_nucleotide(), search_nucleotide_largeTable(), search_nucleotide_longWord(), search_protein1hit(), and search_protein2hit().

{
        struct ungappedExtension *currentExtension, *previousExtension;

        // Start at beginning of ungapped extensions (one with highest score)
        currentExtension = alignments_currentAlignment->ungappedExtensions;

        // If there are none, add first/sole extension
        if (currentExtension == NULL)
        {
                alignments_currentAlignment->ungappedExtensions = newExtension;
        }
        else
        {
                previousExtension = NULL;

                // Else move through list of existing extensions until we either reach the
                // end or reach one with a score less than newExtension
                while (currentExtension != NULL &&
                      (currentExtension->nominalScore > newExtension->nominalScore))
                {
                        previousExtension = currentExtension;
                        currentExtension = currentExtension->next;
                }

                if (previousExtension == NULL)
                {
                        // This is the highest scoring alignment, insert at front of
                        // the queue
                        alignments_currentAlignment->ungappedExtensions = newExtension;
                        newExtension->next = currentExtension;
                }
                else
                {
                        // Insert between higher and lower scoring extensions
                        previousExtension->next = newExtension;
                        newExtension->next = currentExtension;
                }
        }
}

Here is the caller graph for this function:

void alignments_createNew	(	uint4	descriptionLocation,
		uint4	descriptionLength,
		unsigned char *	subject,
		int4	subjectLength,
		int4	encodedLength
	)

Definition at line 41 of file alignments.c.

References alignments_alignments, alignments_currentAlignment, blast_numTriggerSequences, alignment::cluster, alignment::descriptionLength, alignment::descriptionLocation, alignment::edits, alignment::encodedLength, encoding_alphabetType, encoding_nucleotide, alignment::gappedExtensions, alignment::inMemorySubject, alignment::joinChecked, memBlocks_newEntry(), alignment::numUnpackRegions, alignment::subject, alignment::subjectLength, alignment::ungappedExtensions, and alignment::unpackRegions.

Referenced by search_nucleotide(), search_nucleotide_largeTable(), search_nucleotide_longWord(), search_nucleotideSsearch(), search_protein1hit(), search_protein2hit(), and search_proteinSsearch().

{
        struct alignment* alignment;

        // Get slot for new alignment
        alignment = (struct alignment*)memBlocks_newEntry(alignments_alignments);

        // Create/initialize contents
        alignment->ungappedExtensions = NULL;
        alignment->gappedExtensions = NULL;
        alignment->descriptionLocation = descriptionLocation;
    alignment->descriptionLength = descriptionLength;
        alignment->subject = subject;
        alignment->subjectLength = subjectLength;
        alignment->joinChecked = 0;
    alignment->encodedLength = encodedLength;
    alignment->inMemorySubject = 0;
    alignment->unpackRegions = NULL;
        alignment->numUnpackRegions = 0;
    alignment->edits = NULL;
    alignment->cluster = 0;

    // Record pointer to wilcard edits if there are any for this subject
    if (encoding_alphabetType == encoding_nucleotide)
    {
        alignment->edits = subject + ((alignment->subjectLength + 3) / 4);
        if (alignment->edits == subject + encodedLength)
        {
            alignment->edits = NULL;
                }
    }

        alignments_currentAlignment = alignment;
    blast_numTriggerSequences++;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_findFinalAlignments

(

struct PSSMatrix

PSSMatrix

)

Definition at line 1147 of file alignments.c.

References finalAlignment::alignment, alignments_addFinalAlignment(), alignments_findTopFinalAlignments(), alignments_goodAlignments, alignments_regularGappedAlignment(), alignments_sortGoodAlignments(), blast_gappedNominalCutoff, blast_nominalR1cutoff, blast_nominalR2cutoff, alignment::descriptionLocation, finalAlignment::highestNominalScore, int4, memSingleBlock_getCurrent(), memSingleBlock_getEntry(), memSingleBlock_resetCurrent(), ungappedExtension::next, ungappedExtension::nominalScore, memSingleBlock::numEntries, parameters_numDisplayAlignments, parameters_verboseDloc, ungappedExtension::status, ungappedExtension_DELETED, ungappedExtension_print(), and alignment::ungappedExtensions.

Referenced by blast_search().

{
    struct finalAlignment* goodAlignment;
    struct alignment* alignment;
        struct ungappedExtension* ungappedExtension;
    int4 bestScore;

    // Sort good alignments by score
    // TODO: How long does this take?
    alignments_sortGoodAlignments();

    // If we have more good alignments than we can display
    if (parameters_numDisplayAlignments > 0 &&
            alignments_goodAlignments->numEntries > parameters_numDisplayAlignments)
        {
        goodAlignment = memSingleBlock_getEntry(alignments_goodAlignments,
                                                parameters_numDisplayAlignments - 1);

                // If it is clear we will have more final alignments than we can display
                if (goodAlignment->highestNominalScore > blast_nominalR2cutoff)
        {
                // Find the top N alignments
                        alignments_findTopFinalAlignments(PSSMatrix);
            return;
        }
    }

    // Further score all good alignments to see if they score above cutoff
    memSingleBlock_resetCurrent(alignments_goodAlignments);
    while ((goodAlignment = memSingleBlock_getCurrent(alignments_goodAlignments)) != NULL)
    {
                alignment = goodAlignment->alignment;

        bestScore = 0;
        // For each ungapped extension that hasn't been deleted
        ungappedExtension = alignment->ungappedExtensions;
        while (ungappedExtension != NULL)
        {
            #ifdef VERBOSE
            if (parameters_verboseDloc == alignment->descriptionLocation)
                                ungappedExtension_print(ungappedExtension);
            #endif

            if (ungappedExtension->status != ungappedExtension_DELETED)
            {
                // If it isn't clear if the extension is above cutoff
                if (ungappedExtension->nominalScore >= blast_nominalR1cutoff &&
                    ungappedExtension->nominalScore <= blast_nominalR2cutoff)
                {
                    // Perform regular gapped scoring
                    alignments_regularGappedAlignment(PSSMatrix, ungappedExtension, alignment);
                }

                // Update the alignment's best score
                if (ungappedExtension->nominalScore > bestScore)
                    bestScore = ungappedExtension->nominalScore;
            }
            ungappedExtension = ungappedExtension->next;
        }

        goodAlignment->highestNominalScore = bestScore;

        // If the alignment scores above cutoff, include in list of final alignments
        if (goodAlignment->highestNominalScore >= blast_gappedNominalCutoff)
        {
            alignments_addFinalAlignment(goodAlignment->highestNominalScore, alignment);
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_findGoodAlignments

(

struct PSSMatrix

PSSMatrix

)

Definition at line 748 of file alignments.c.

References alignments_addGoodAlignment(), alignments_alignments, alignments_expandCluster(), alignments_numVolumes, alignments_pruneRegion(), alignments_volumeAlignments, blast_dloc, blast_nominalR1cutoff, blast_numGoodAlignments, blast_numGoodExtensions, bytepackGappedScoring_score(), constants_initialAllocAlignments, encoding_alphabetType, encoding_protein, gappedScoring_score(), int4, memBlocks_getCurrent(), memBlocks_initialize(), memBlocks_resetCurrent(), ungappedExtension::next, parameters_bytepackedScoring, parameters_semiGappedScoring, parameters_tableScoring, semiGappedScoring_score(), statistics_gappedNominalDropoff, ungappedExtension::status, tableGappedScoring_score(), ungappedExtension_DELETED, ungappedExtension_findSeed(), ungappedExtension_GAPPED, and ungappedExtension_SEMIGAPPED.

Referenced by blast_search().

{
        struct alignment* alignment;
        struct ungappedExtension* ungappedExtension;
        int4 bestScore, numExtensions, hasChildren;

    // For each alignment
    memBlocks_resetCurrent(alignments_alignments);
        while ((alignment = (struct alignment*)memBlocks_getCurrent(alignments_alignments)) != NULL)
        {
        bestScore = 0;
                blast_dloc = alignment->descriptionLocation;

        // Record if subject has children
        if (encoding_alphabetType == encoding_protein &&
            alignment->encodedLength > alignment->subjectLength + 2)
                hasChildren = 1;
                else
                hasChildren = 0;

        // For each ungapped extension (in descending order of score)
        numExtensions = 0;
        ungappedExtension = alignment->ungappedExtensions;
        while (ungappedExtension != NULL)
        {
                if (ungappedExtension->status != ungappedExtension_DELETED)
            {
                // Find the seed
                ungappedExtension_findSeed(ungappedExtension, PSSMatrix, alignment->subject);

                // Byte-packed scoring
                if (parameters_bytepackedScoring)
                {
                    ungappedExtension->nominalScore
                        = bytepackGappedScoring_score(ungappedExtension, PSSMatrix, alignment->subjectLength,
                           alignment->subject, statistics_gappedNominalDropoff);

                    // Mark as semigapped
                    ungappedExtension->status = ungappedExtension_SEMIGAPPED;
                }
                // Table driven scoring
                else if (parameters_tableScoring)
                {
                    ungappedExtension->nominalScore
                        = tableGappedScoring_score(ungappedExtension, PSSMatrix, alignment->subjectLength,
                           alignment->subject, statistics_gappedNominalDropoff);

                    // Mark as semigapped
                    ungappedExtension->status = ungappedExtension_SEMIGAPPED;
                }
                // Semi-gapped scoring
                else if (parameters_semiGappedScoring)
                {
                    ungappedExtension->nominalScore
                        = semiGappedScoring_score(ungappedExtension, PSSMatrix, alignment->subjectLength,
                                                  alignment->subject, statistics_gappedNominalDropoff);

                    // Mark as semigapped
                    ungappedExtension->status = ungappedExtension_SEMIGAPPED;
                }
                // Regular gapped scoring
                else
                {
                    ungappedExtension->nominalScore
                        = gappedScoring_score(ungappedExtension, PSSMatrix, alignment->subjectLength,
                                              alignment->subject, statistics_gappedNominalDropoff);

                    // Mark as gapped
                    ungappedExtension->status = ungappedExtension_GAPPED;
                }

                // If alignment scores above R1 cutoff
                if (ungappedExtension->nominalScore >= blast_nominalR1cutoff)
                {
                    if (hasChildren)
                    {
                        // Subject has children so perform stage1 and 2 on children
                        alignments_expandCluster(alignment, PSSMatrix);
                                                bestScore = 0;
                        break;
                                        }
                    else if (ungappedExtension->nominalScore > bestScore)
                    {
                        // Update best score for the alignment
                        bestScore = ungappedExtension->nominalScore;
                    }
                }
                else
                {
                    // Else mark it as deleted
                    ungappedExtension->status = ungappedExtension_DELETED;
                }

                // Remove any ungapped extensions in this alignment that are in the area covered
                // by the gapped scoring just performed
                alignments_pruneRegion(alignment, ungappedExtension);

                numExtensions++;
                        }

            ungappedExtension = ungappedExtension->next;
                }

        // If this alignment contains gapped extensions that could score above cutoff
        if (bestScore >= blast_nominalR1cutoff)
        {
            // If a single sequence add to list of "good" alignments
            alignments_addGoodAlignment(bestScore, alignment);

            blast_numGoodExtensions += numExtensions;
            blast_numGoodAlignments++;
        }
    }

        // Record point to list of alignments for this volume
        alignments_volumeAlignments[alignments_numVolumes] = alignments_alignments;
        alignments_numVolumes++;

        // Construct new list for next volume (if there is one)
    alignments_alignments = memBlocks_initialize(sizeof(struct alignment),
                            constants_initialAllocAlignments);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_free

(

)

Definition at line 696 of file alignments.c.

References finalAlignment::alignment, alignment_freeAlignment(), alignments_alignments, alignments_finalAlignments, alignments_goodAlignments, alignments_numVolumes, alignments_volumeAlignments, finalAlignment::description, memBlocks_free(), memBlocks_getCurrent(), memBlocks_resetCurrent(), memSingleBlock_free(), memSingleBlock_getCurrent(), memSingleBlock_resetCurrent(), uint4, ungappedExtension_extensions, and unpack_free().

Referenced by blast_search().

{
        struct alignment* alignment;
        struct finalAlignment* finalAlignment;
        uint4 volumeCount;

    memBlocks_resetCurrent(alignments_alignments);

    // Free unused block of alignments
        memBlocks_free(alignments_alignments);

    // For each volume
        volumeCount = 0;
        while (volumeCount < alignments_numVolumes)
        {
                alignments_alignments = alignments_volumeAlignments[volumeCount];

                // For each alignment
        memBlocks_resetCurrent(alignments_alignments);
                while ((alignment = (struct alignment*)memBlocks_getCurrent(alignments_alignments)) != NULL)
                {
                        alignment_freeAlignment(alignment);
                }

                // Free blocks of alignments
                memBlocks_free(alignments_alignments);

                volumeCount++;
        }

    // Free memory used by ungapped extensions
        memBlocks_free(ungappedExtension_extensions);

    // Free good alignments
        memSingleBlock_free(alignments_goodAlignments);

    // For each final alignment, free the description
    memSingleBlock_resetCurrent(alignments_finalAlignments);
    while ((finalAlignment = memSingleBlock_getCurrent(alignments_finalAlignments)) != NULL)
    {
                free(finalAlignment->description);
    }

    // Free final alignments
        memSingleBlock_free(alignments_finalAlignments);

        // Free all the unpacked regions
        unpack_free();
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_getFinalAlignmentDescriptions

(

)

Definition at line 612 of file alignments.c.

References alignments_compareAlignmentDescriptionLocations(), alignments_compareFinalAlignments(), alignments_finalAlignments, memSingleBlock::block, descriptions_getDescription(), memSingleBlock_getCurrent(), memSingleBlock_resetCurrent(), and memSingleBlock::numEntries.

Referenced by blast_search().

{
        struct finalAlignment* finalAlignment;

    // Sort descriptions in order of description location (to speed up disk access)
        qsort(alignments_finalAlignments->block, alignments_finalAlignments->numEntries,
          sizeof(struct finalAlignment), alignments_compareAlignmentDescriptionLocations);

    // For each alignment, read the description
    memSingleBlock_resetCurrent(alignments_finalAlignments);
    while ((finalAlignment = memSingleBlock_getCurrent(alignments_finalAlignments)) != NULL)
    {
                finalAlignment->description
                = descriptions_getDescription(finalAlignment->alignment->descriptionLocation,
                                          finalAlignment->alignment->descriptionLength);
    }

    // Re-sort the final alignments by score
        qsort(alignments_finalAlignments->block, alignments_finalAlignments->numEntries,
          sizeof(struct finalAlignment), alignments_compareFinalAlignments);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_getTracebacks

(

struct PSSMatrix

PSSMatrix

)

Definition at line 1283 of file alignments.c.

References finalAlignment::alignment, alignments_addGappedExtension(), alignments_finalAlignments, alignments_pruneOverlappingExtensions(), alignments_pruneRegion(), alignments_selectRegion(), alignments_sortFinalAlignments(), alignments_unpruneRegion(), blast_dloc, blast_gappedExtendTime, blast_gappedNominalCutoff, blast_unpackTime, constants_maximumTracebackSize, alignment::descriptionLocation, fasterGappedExtension_build(), gappedExtension_build(), gappedExtension_score(), alignment::gappedExtensions, gappedScoring_score(), finalAlignment::highestNominalScore, int4, PSSMatrix::length, memSingleBlock_getCurrent(), memSingleBlock_getEntry(), memSingleBlock_getLastEntry(), memSingleBlock_resetCurrent(), ungappedExtension::next, gappedExtension::nominalScore, ungappedExtension::nominalScore, memSingleBlock::numEntries, alignment::numUnpackRegions, parameters_numDisplayAlignments, parameters_numDisplayTracebacks, parameters_tableScoring, ungappedExtension::seed, statistics_gappedFinalNominalDropoff, ungappedExtension::status, alignment::subject, unpackRegion::subject, alignment::subjectLength, coordinate::subjectOffset, gappedExtension::trace, trace::traceCodes, uint8, ungappedExtension_DELETED, alignment::ungappedExtensions, unpack_entireSubjectUnpacked(), unpack_selectRegion(), unpack_unpackSubject(), unpackRegion::unpackedSubject, and alignment::unpackRegions.

Referenced by blast_search().

{
    struct finalAlignment* finalAlignment;
        struct gappedExtension* gappedExtension;
        struct ungappedExtension* ungappedExtension, *highestScoringExtension, oldUngappedExtension;
    struct alignment* alignment;
    struct unpackRegion* unpackRegion;
    int4 numProcessed = 0, numAboveCutoff = 0, repeatComputeTracebacks = 1;
        int4 alignmentCount;
        unsigned char* subject;

    // Sort final alignments by score
    alignments_sortFinalAlignments();

//    alignments_printFinalAlignments();

    // Only keep alignments above cutoff
    while (alignments_finalAlignments->numEntries > 0)
    {
        // Get last alignment in list
                finalAlignment = memSingleBlock_getLastEntry(alignments_finalAlignments);

        // Stop if above cutoff
        if (finalAlignment->highestNominalScore != 0)
                break;

        // Otherwise remove it from the list
        alignments_finalAlignments->numEntries--;
    }

    // For each alignment that is in the top numDisplayAlignments but not the top numDisplayTracebacks
    alignmentCount = parameters_numDisplayTracebacks;
    while (alignmentCount < parameters_numDisplayAlignments &&
           alignmentCount < alignments_finalAlignments->numEntries)
        {
        finalAlignment = memSingleBlock_getEntry(alignments_finalAlignments, alignmentCount);
        alignment = finalAlignment->alignment;
        blast_dloc = alignment->descriptionLocation;

        // Get the highest scoring ungapped extension
        ungappedExtension = alignment->ungappedExtensions;
        highestScoringExtension = ungappedExtension;
        while (ungappedExtension != NULL)
        {
                if (ungappedExtension->nominalScore > highestScoringExtension->nominalScore &&
                ungappedExtension->status != ungappedExtension_DELETED)
            {
                                highestScoringExtension = ungappedExtension;
            }
                ungappedExtension = ungappedExtension->next;
                }

        if (highestScoringExtension != NULL)
        {
                subject = alignments_selectRegion(alignment, highestScoringExtension);

            // Perform gapped scoring with higher dropoff
            highestScoringExtension->nominalScore
                = gappedScoring_score(highestScoringExtension, PSSMatrix, alignment->subjectLength,
                                      subject, statistics_gappedFinalNominalDropoff);

                        finalAlignment->highestNominalScore = highestScoringExtension->nominalScore;
        }

//        printf("Rescore with larger dropoff num %d: Score=%d\n", alignmentCount, highestScoringExtension->nominalScore);
        alignmentCount++;
    }

        while (repeatComputeTracebacks)
    {
        numAboveCutoff = 0; numProcessed = 0;
        memSingleBlock_resetCurrent(alignments_finalAlignments);
        while (((finalAlignment = memSingleBlock_getCurrent(alignments_finalAlignments)) != NULL)
        && (numAboveCutoff < parameters_numDisplayTracebacks || parameters_numDisplayTracebacks == 0))
        {
            alignment = finalAlignment->alignment;
            blast_dloc = alignment->descriptionLocation;

            // If traceback haven't been computed for this alignment
            if (alignment->gappedExtensions == NULL)
            {
                // Unpack part or all of the subject (for nucleotide)
                blast_gappedExtendTime += clock();
                blast_unpackTime -= clock();
                unpack_unpackSubject(PSSMatrix, alignment);
                blast_unpackTime += clock();
                blast_gappedExtendTime -= clock();

                // For each ungapped extension that hasn't been deleted
                ungappedExtension = alignment->ungappedExtensions;
                while (ungappedExtension != NULL)
                {
                    // If extension scores above cutoff
                    if (ungappedExtension->status != ungappedExtension_DELETED)
                    {
                        // Make copy of ungapped extension
                        oldUngappedExtension = *ungappedExtension;

                        // If subject and query are short enough and sequence does not have multiple
                        // unpack regions, use faster but less memory efficient gapped alignment with traceback
                        if (((uint8)PSSMatrix.length * (uint8)alignment->subjectLength <
                            (uint8)constants_maximumTracebackSize) && unpack_entireSubjectUnpacked(alignment))
                        {
                            gappedExtension
                                = fasterGappedExtension_build(ungappedExtension, PSSMatrix,
                                  alignment->subjectLength, alignment->unpackRegions[0].unpackedSubject,
                                  statistics_gappedFinalNominalDropoff);
                        }
                        // Otherwise use slower but more memory-efficient gapped alignment
                        else
                        {
                            unpackRegion = unpack_selectRegion(alignment->unpackRegions,
                                           alignment->numUnpackRegions, ungappedExtension->seed.subjectOffset);

                            gappedExtension
                                = gappedExtension_build(ungappedExtension, PSSMatrix, alignment->subjectLength,
                                      alignment->subject, unpackRegion, statistics_gappedFinalNominalDropoff);
                        }

                        // Calculate normalized score and e-value
                        gappedExtension_score(gappedExtension);

                        // Add it to the current alignment
                        if (gappedExtension->nominalScore >= blast_gappedNominalCutoff)
                            alignments_addGappedExtension(alignment, gappedExtension);
                        else
                        {
                            free(gappedExtension->trace.traceCodes);
                            free(gappedExtension);
                        }

                        // Check for ungapped extensions that were mistakenly pruned
                        if (parameters_tableScoring)
                                alignments_unpruneRegion(alignment, &oldUngappedExtension,
                                                     ungappedExtension, PSSMatrix);

                        // Remove any ungapped extensions in this alignment that are in the area covered
                        // by the gapped scoring just performed
                        alignments_pruneRegion(alignment, ungappedExtension);
                   }
                   ungappedExtension = ungappedExtension->next;
                }

                // Finally prune extensions that share a start or end point
                alignments_pruneOverlappingExtensions(alignment);

//                printf("Was %d Now %d\n", finalAlignment->highestNominalScore, alignment->gappedExtensions->nominalScore);

                // Update final alignment's high-score to that of the first (and highest-scoring)
                // gapped extension in the list
                if (alignment->gappedExtensions != NULL)
                    finalAlignment->highestNominalScore = alignment->gappedExtensions->nominalScore;
                else
                    finalAlignment->highestNominalScore = 0;

                numProcessed++;
//                  printf("Computed alignment score=%d\n", finalAlignment->highestNominalScore);
                        }

            // Tally number of final alignments above cutoff
            if (finalAlignment->highestNominalScore > 0)
                numAboveCutoff++;
        }

//      printf("Traceback alignments performed=%d\n", numProcessed);

        // Sort final alignments by score
        alignments_sortFinalAlignments();

//        printf("repeatComputeTracebacks:");

        // If the first numDisplayTracebacks alignments have traceback computed, stop
        numProcessed = 0; repeatComputeTracebacks = 0;
        memSingleBlock_resetCurrent(alignments_finalAlignments);
        while ((finalAlignment = memSingleBlock_getCurrent(alignments_finalAlignments)) != NULL
               && numProcessed < parameters_numDisplayTracebacks)
        {
            alignment = finalAlignment->alignment;
            if (alignment->gappedExtensions == NULL && finalAlignment->highestNominalScore != 0)
            {
//              printf("1");
                repeatComputeTracebacks = 1;
                                break;
            }
//            printf("0");

            numProcessed++;
                }

        }

    // Only keep top N alignments
    if (parameters_numDisplayAlignments != 0 &&
        alignments_finalAlignments->numEntries > parameters_numDisplayAlignments)
        {
                alignments_finalAlignments->numEntries = parameters_numDisplayAlignments;
    }

    // Only keep alignments above cutoff
    while (alignments_finalAlignments->numEntries > 0)
    {
        // Get last alignment in list
                finalAlignment = memSingleBlock_getLastEntry(alignments_finalAlignments);

        // Stop if above cutoff
        if (finalAlignment->highestNominalScore != 0)
                break;

        // Otherwise remove it from the list
        alignments_finalAlignments->numEntries--;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_initialize

(

)

Definition at line 22 of file alignments.c.

References alignments_alignments, alignments_currentAlignment, alignments_finalAlignments, alignments_finalAlignmentsSorted, alignments_goodAlignments, alignments_numVolumes, blast_numGoodExtensions, constants_initialAllocAlignments, constants_initialAllocFinalAlignments, constants_initialAllocGoodAlignments, memBlocks_initialize(), memSingleBlock_initialize(), and unpack_initialize().

Referenced by blast_search().

{
        // Initialize alignments, good alignments and final alignments blocks
    alignments_alignments = memBlocks_initialize(sizeof(struct alignment),
                            constants_initialAllocAlignments);
        alignments_goodAlignments = memSingleBlock_initialize(sizeof(struct finalAlignment),
                                constants_initialAllocGoodAlignments);
        alignments_finalAlignments = memSingleBlock_initialize(sizeof(struct finalAlignment),
                                 constants_initialAllocFinalAlignments);

    // Initialize code for processing regions of a subject
    unpack_initialize(blast_numGoodExtensions);

    alignments_currentAlignment = NULL;
        alignments_numVolumes = 0;
    alignments_finalAlignmentsSorted = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int alignments_isFinalAlignment

(

uint4

score

)

Definition at line 1498 of file alignments.c.

References finalAlignment::alignment, alignment_freeAlignment(), alignments_finalAlignments, alignments_finalAlignmentsSorted, alignments_sortFinalAlignments(), finalAlignment::highestNominalScore, memSingleBlock_getEntry(), memSingleBlock::numEntries, and parameters_numDisplayAlignments.

Referenced by search_nucleotideSsearch(), and search_proteinSsearch().

{
        struct finalAlignment* finalAlignment;
    struct alignment* alignment;

//    printf("%d,%d\n", parameters_numDisplayAlignments, alignments_finalAlignments->numEntries);

        if (parameters_numDisplayAlignments == 0 ||
        alignments_finalAlignments->numEntries < parameters_numDisplayAlignments)
        return 1;

        if (!alignments_finalAlignmentsSorted)
    {
        // Sort final alignments by score
        alignments_sortFinalAlignments();
        alignments_finalAlignmentsSorted = 1;
    }

    // Get the N-1th final alignment
    finalAlignment = memSingleBlock_getEntry(alignments_finalAlignments,
                                             parameters_numDisplayAlignments - 1);

        // If new alignment scores high enough to be in the top N
        if (score > finalAlignment->highestNominalScore)
    {
                // Final alignments will need to be resorted
                alignments_finalAlignmentsSorted = 0;

        // Free the lowest scoring final alignment
                alignment = finalAlignment->alignment;
                alignment_freeAlignment(alignment);
        alignments_finalAlignments->numEntries--;

        return 1;
    }
    else
    {
        return 0;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_loadSubjectsIntoMemory

(

struct PSSMatrix

PSSMatrix

)

Definition at line 873 of file alignments.c.

References finalAlignment::alignment, alignments_finalAlignments, alignments_goodAlignments, alignments_sortGoodAlignments(), alignment::encodedLength, finalAlignment::highestNominalScore, alignment::inMemorySubject, int4, memSingleBlock_getEntry(), memSingleBlock::numEntries, parameters_numDisplayAlignments, parameters_semiGappedR1, parameters_semiGappedR2, and unpack_loadSubject().

Referenced by blast_search().

{
        struct finalAlignment *goodAlignment, *finalAlignment;
        struct alignment* alignment;
    int4 minimumDynamicCutoff, position, totalLengths = 0, totalCopied = 0;

    // First dismiss good alignments that can't make it into the top N
        if (parameters_numDisplayAlignments > 0 &&
            alignments_goodAlignments->numEntries > parameters_numDisplayAlignments)
    {
        // Sort good alignments by score
        alignments_sortGoodAlignments();

        // Get the Nth alignment
        goodAlignment = memSingleBlock_getEntry(alignments_goodAlignments, parameters_numDisplayAlignments);

        // Calculate the minimum possible dynamic cutoff
        minimumDynamicCutoff = goodAlignment->highestNominalScore / parameters_semiGappedR2
                             * parameters_semiGappedR1;

                // Move through good alignments
        position = parameters_numDisplayAlignments;
        while (position < alignments_goodAlignments->numEntries)
        {
                // Stop when score is below minimum dynamic cutoff
            goodAlignment = memSingleBlock_getEntry(alignments_goodAlignments, position);
            if (goodAlignment->highestNominalScore < minimumDynamicCutoff)
                        {
//              printf("Changed numGoodAlignments from %d to %d\n",
//                                      alignments_goodAlignments->numEntries, position); fflush(stdout);
                                alignments_goodAlignments->numEntries = position;
                break;
                        }
            position++;
                }
        }

    // For each good alignment (for BLAST)
    position = 0;
    while (position < alignments_goodAlignments->numEntries)
    {
        goodAlignment = memSingleBlock_getEntry(alignments_goodAlignments, position);
        alignment = goodAlignment->alignment;

        // Load subject sequence into memory if not already loaded
                if (alignment->inMemorySubject == 0)
        {
                totalCopied += unpack_loadSubject(PSSMatrix, alignment);
                totalLengths += alignment->encodedLength;
        }

                position++;
        }

    // For each final alignment (for protein SSEARCH)
    position = 0;
    while (position < alignments_finalAlignments->numEntries)
    {
        finalAlignment = memSingleBlock_getEntry(alignments_finalAlignments, position);
        alignment = finalAlignment->alignment;

        // Load subject sequence into memory if not already loaded
                if (alignment->inMemorySubject == 0)
            unpack_loadSubject(PSSMatrix, alignment);

                position++;
        }

//    printf("alignments_loadSubjectsIntoMemory=%d/%d\n", totalCopied, totalLengths);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void alignments_performScoring

(

struct PSSMatrix

PSSMatrix

)

void alignments_sortFinalAlignments

(

)

Definition at line 484 of file alignments.c.

References alignments_compareFinalAlignments(), alignments_finalAlignments, memSingleBlock::block, and memSingleBlock::numEntries.

Referenced by alignments_findTopFinalAlignments(), alignments_getTracebacks(), alignments_isFinalAlignment(), and search_proteinSsearch().

{
        qsort(alignments_finalAlignments->block, alignments_finalAlignments->numEntries,
          sizeof(struct finalAlignment), alignments_compareFinalAlignments);
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

struct memBlocks* alignments_alignments

Definition at line 5 of file alignments.h.

Referenced by alignments_createNew(), alignments_findGoodAlignments(), alignments_free(), and alignments_initialize().

struct alignment* alignments_currentAlignment

Definition at line 10 of file alignments.h.

Referenced by alignments_addUngappedExtension(), alignments_createNew(), alignments_expandCluster(), alignments_initialize(), search_nucleotide(), search_nucleotide_largeTable(), search_nucleotide_longWord(), search_nucleotideSsearch(), search_protein1hit(), search_protein2hit(), and search_proteinSsearch().

struct memSingleBlock* alignments_finalAlignments

Definition at line 9 of file alignments.h.

Referenced by alignments_addFinalAlignment(), alignments_findTopFinalAlignments(), alignments_free(), alignments_getFinalAlignmentDescriptions(), alignments_getTracebacks(), alignments_initialize(), alignments_isFinalAlignment(), alignments_loadSubjectsIntoMemory(), alignments_moveGoodToFinal(), alignments_printFinalAlignments(), alignments_sortFinalAlignments(), blast_search(), print_gappedAlignmentsBrief(), and print_gappedAlignmentsFull().

struct memSingleBlock* alignments_goodAlignments

Definition at line 7 of file alignments.h.

Referenced by alignments_addGoodAlignment(), alignments_findFinalAlignments(), alignments_findTopFinalAlignments(), alignments_free(), alignments_initialize(), alignments_loadSubjectsIntoMemory(), alignments_moveGoodToFinal(), alignments_printGoodAlignments(), and alignments_sortGoodAlignments().

uint4 alignments_numClusters

Definition at line 16 of file alignments.c.

Referenced by alignments_expandCluster(), and print_gappedAlignmentsFull().

---