include/gappedExtension.h File Reference

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

Go to the source code of this file.

Functions
gappedExtension *	gappedExtension_build (struct ungappedExtension *ungappedExtension, struct PSSMatrix PSSMatrix, int4 subjectSize, unsigned char *subject, struct unpackRegion *unpackRegion, int4 dropoff)
void	gappedExtension_printBeforeRow (int4 *row, unsigned char *subject, unsigned char *rowDropoff, unsigned char *columnDropoff)
void	gappedExtension_printAfterRow (int4 *row, unsigned char *subject, unsigned char *rowDropoff, unsigned char *columnDropoff)
void	gappedExtension_score (struct gappedExtension *gappedExtension)
void	gappedExtension_prune (struct gappedExtension *gappedExtension, struct ungappedExtension *ungappedExtension)
void	gappedExtension_free ()

---

Function Documentation

struct gappedExtension* gappedExtension_build	(	struct ungappedExtension *	ungappedExtension,
		struct PSSMatrix	PSSMatrix,
		int4	subjectSize,
		unsigned char *	subject,
		struct unpackRegion *	unpackRegion,
		int4	dropoff
	)			[read]

Definition at line 34 of file gappedExtension.c.

References dpResults::best, dpResults::bestScore, blast_dloc, ungappedExtension::end, gappedExtension_dpAfterSeed(), gappedExtension_dpBeforeSeed(), gappedExtension_joinTraces(), gappedExtension_traceAfterSeed(), gappedExtension_traceBeforeSeed(), global_malloc(), int4, PSSMatrix::length, PSSMatrix::matrix, ungappedExtension::nominalScore, parameters_verboseDloc, PSSMatrix_chop(), coordinate::queryOffset, trace::queryStart, ungappedExtension::seed, ungappedExtension::start, PSSMatrix::strandLength, coordinate::subjectOffset, trace::subjectStart, gappedExtension::trace, trace::traceCodes, and unpackRegion::unpackedSubject.

Referenced by alignments_getTracebacks().

{
        struct coordinate seed;
        unsigned char *choppedSubject;
        struct dpResults beforeDpResults, afterDpResults;
        struct trace beforeTrace, afterTrace, trace;
        struct PSSMatrix choppedPSSMatrix;
        int4 choppedSubjectSize;
        struct gappedExtension* gappedExtension;
    int4 strandOffset = 0;

        // Perform dynamic programming for points before the seed
        seed = ungappedExtension->seed;
    if (seed.queryOffset > PSSMatrix.strandLength)
    {
            // If query position is in the second strand, remove first strand from PSSM
        strandOffset = PSSMatrix.strandLength;
                seed.queryOffset -= PSSMatrix.strandLength;
                PSSMatrix = PSSMatrix_chop(PSSMatrix, PSSMatrix.strandLength);
    }
    else
    {
        // Otherwise remove second strand
        PSSMatrix.length = PSSMatrix.strandLength;
    }

    beforeDpResults = gappedExtension_dpBeforeSeed(PSSMatrix, dropoff, seed, unpackRegion);

        // Trace back and create the trace which specifies the first half of the alignment
        beforeTrace = gappedExtension_traceBeforeSeed(beforeDpResults, seed);

        // Chop the start off the query and subject so they begin at the seed
        choppedPSSMatrix = PSSMatrix_chop(PSSMatrix, seed.queryOffset);
        choppedSubject = subject + seed.subjectOffset;
        choppedSubjectSize = subjectSize - (seed.subjectOffset);

        // Perform dynamic programming for points after the seed
        afterDpResults = gappedExtension_dpAfterSeed(choppedPSSMatrix, dropoff, unpackRegion,
                                                 choppedSubjectSize, seed.subjectOffset);

        // Trace back to get the trace for the seed onwards
        afterTrace = gappedExtension_traceAfterSeed(afterDpResults, choppedPSSMatrix.length);

        // Join afterTrace to the end of beforeTrace
        trace = gappedExtension_joinTraces(beforeTrace, afterTrace);
        free(afterTrace.traceCodes);

    // Adjust coordinates if extension was performed in the second strand
    afterDpResults.best.queryOffset += strandOffset;
    beforeDpResults.best.queryOffset += strandOffset;
        trace.queryStart += strandOffset;

        // Create gapped extension
        gappedExtension = (struct gappedExtension*)global_malloc(sizeof(struct gappedExtension));
        gappedExtension->trace = trace;
        gappedExtension->next = NULL;

        // Start of afterTrace is end of the gapped extension, but we need to add seed position
        // to get correct offset
        gappedExtension->queryEnd = seed.queryOffset + afterTrace.queryStart + strandOffset;
        gappedExtension->subjectEnd = seed.subjectOffset + afterTrace.subjectStart;

//      if (dloc == 88197331)
//              printf("final[%d,%d,%d](%d)\n", beforeDpResults.bestScore, afterDpResults.bestScore,
//              choppedPSSMatrix.matrix[0][unpackRegion->unpackedSubject[seed.subjectOffset]], seed.queryOffset);

        // Determine score by combining score from the two traces, and the match score at
        // the seed position
        gappedExtension->nominalScore = beforeDpResults.bestScore + afterDpResults.bestScore
                       + choppedPSSMatrix.matrix[0][unpackRegion->unpackedSubject[seed.subjectOffset]];

    // Update ungappedExtension start/end
    ungappedExtension->start.queryOffset = trace.queryStart;
    ungappedExtension->end.queryOffset = gappedExtension->queryEnd;
    ungappedExtension->start.subjectOffset = trace.subjectStart;
    ungappedExtension->end.subjectOffset = gappedExtension->subjectEnd;
        ungappedExtension->nominalScore = gappedExtension->nominalScore;

    #ifdef VERBOSE
    if (parameters_verboseDloc == blast_dloc)
    {
        printf("Gapped Extension from %d,%d to %d,%d score %d\n", trace.queryStart, trace.subjectStart,
               gappedExtension->queryEnd, gappedExtension->subjectEnd, gappedExtension->nominalScore);
    }
    #endif

    return gappedExtension;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void gappedExtension_free

(

)

Definition at line 1383 of file gappedExtension.c.

References gappedExtension_insertQrow, gappedExtension_insertSrow, gappedExtension_matchRow, gappedExtension_traceback, and gappedExtension_tracebackData.

Referenced by main().

{
        // Free memory used by traceback array
    free(gappedExtension_traceback);
    free(gappedExtension_tracebackData);

//    printf("gappedExtension_tracebackAlloc=%d\n", gappedExtension_tracebackAlloc);

    // Free memory used to store row scores
    free(gappedExtension_matchRow);
    free(gappedExtension_insertQrow);
    free(gappedExtension_insertSrow);
}

Here is the caller graph for this function:

void gappedExtension_printAfterRow	(	int4 *	row,
		unsigned char *	subject,
		unsigned char *	rowDropoff,
		unsigned char *	columnDropoff
	)

Definition at line 1438 of file gappedExtension.c.

References dpResults::best, and int4.

Referenced by bytepackGappedScoring_dpAfterSeed(), fasterBytepackGappedScoring_dpAfterSeed(), gappedScoring_dpAfterSeed(), and tableGappedScoring_dpAfterSeed().

{
        // TODO: Adjust to work with wrap-around
        unsigned char* subjectPosition = subject;
    int4 *oldRow, *best;

        while (subjectPosition < columnDropoff)
        {
                printf("     ");
                subjectPosition++;
                row++;
        }

    best = oldRow = row;

        while (subjectPosition < rowDropoff)
        {
        if (*row > *best)
                best = row;
                row++;
                subjectPosition++;
        }

    row = oldRow; subjectPosition = columnDropoff;

    while (subjectPosition < rowDropoff)
        {
        if (row == best)
                        printf("%4d*", *row);
        else
                        printf("%4d ", *row);
                row++;
                subjectPosition++;
        }

        printf("\n");
}

Here is the caller graph for this function:

void gappedExtension_printBeforeRow	(	int4 *	row,
		unsigned char *	subject,
		unsigned char *	rowDropoff,
		unsigned char *	columnDropoff
	)

Definition at line 1398 of file gappedExtension.c.

References dpResults::best, and int4.

Referenced by bytepackGappedScoring_dpBeforeSeed(), fasterBytepackGappedScoring_dpBeforeSeed(), gappedScoring_dpBeforeSeed(), and tableGappedScoring_dpBeforeSeed().

{
        // TODO: Adjust to work with wrap-around
        unsigned char* subjectPosition = subject;
    int4 *oldRow, *best;

        while (subjectPosition < rowDropoff)
        {
                printf("     ");
                subjectPosition++;
                row++;
        }

    best = oldRow = row;

        while (subjectPosition < columnDropoff)
        {
        if (*row > *best)
                best = row;
                row++;
                subjectPosition++;
        }

    row = oldRow; subjectPosition = rowDropoff;

    while (subjectPosition < columnDropoff)
        {
        if (row == best)
                        printf("%4d*", *row);
        else
                        printf("%4d ", *row);
                row++;
                subjectPosition++;
        }

        printf("\n");
}

Here is the caller graph for this function:

void gappedExtension_prune	(	struct gappedExtension *	gappedExtension,
		struct ungappedExtension *	ungappedExtension
	)

Definition at line 138 of file gappedExtension.c.

References ungappedExtension::end, int4, trace::length, ungappedExtension::next, coordinate::queryOffset, trace::queryStart, ungappedExtension::start, coordinate::subjectOffset, trace::subjectStart, gappedExtension::trace, and trace::traceCodes.

{
        int4 queryPosition, subjectPosition;
        unsigned char* traceCodes;
        int4 count = 0, offset;
        struct trace trace;
        struct ungappedExtension *currentExtension, *previousExtension;

        // Get trace start point and tracecodes
        trace = gappedExtension->trace;
        queryPosition = trace.queryStart;
        subjectPosition = trace.subjectStart;
        traceCodes = trace.traceCodes;

        // Determine start offset
        offset = subjectPosition - queryPosition;

        // For each position in the trace
        while (count < trace.length)
        {
                // Cycle through ungapped extensions and check if they overlap
                // with this part of the gapped extension
                previousExtension = ungappedExtension;
                currentExtension = ungappedExtension->next;
                while (currentExtension != NULL)
                {
                        // If on same offset, within start and end of the ungappedExtension
                        if (currentExtension->start.subjectOffset -
                currentExtension->start.queryOffset == offset &&
                            currentExtension->start.queryOffset <= queryPosition &&
                                currentExtension->end.queryOffset >= queryPosition)
                        {
                                // Remove current ungappedExtension from the list
                                previousExtension->next = currentExtension->next;
                                currentExtension = previousExtension->next;
                        }
                        else
                        {
                                previousExtension = currentExtension;
                                currentExtension = currentExtension->next;
                        }
                }

                // A match
                if (traceCodes[count] == 0)
                {
                        queryPosition++;
                        subjectPosition++;
                }
                // An insertion wrt. query
                else if (traceCodes[count] == 1)
                {
                        subjectPosition++;
                        offset++;
                }
                // An insertion wrt. subject
                else
                {
                        queryPosition++;
                        offset--;
                }
                count++;
        }
}

void gappedExtension_score

(

struct gappedExtension *

gappedExtension

)

Definition at line 127 of file gappedExtension.c.

References gappedExtension::eValue, gappedExtension::nominalScore, gappedExtension::normalizedScore, statistics_gappedCalculateEvalue(), and statistics_gappedNominal2normalized().

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

{
        gappedExtension->normalizedScore
                = statistics_gappedNominal2normalized(gappedExtension->nominalScore);

        gappedExtension->eValue
                = statistics_gappedCalculateEvalue(gappedExtension->normalizedScore);
}

Here is the call graph for this function:

Here is the caller graph for this function:

---