include/fasterGappedExtension.h File Reference

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

Go to the source code of this file.

Functions
gappedExtension *	fasterGappedExtension_build (struct ungappedExtension *ungappedExtension, struct PSSMatrix PSSMatrix, int4 subjectSize, unsigned char *subject, int4 dropoff)
void	fasterGappedExtension_printBeforeRow (int4 *row, unsigned char *subject, unsigned char *rowDropoff, unsigned char *columnDropoff)
void	fasterGappedExtension_printAfterRow (int4 *row, unsigned char *subject, unsigned char *rowDropoff, unsigned char *columnDropoff)
void	fasterGappedExtension_score (struct gappedExtension *gappedExtension)
void	fasterGappedExtension_prune (struct gappedExtension *gappedExtension, struct ungappedExtension *ungappedExtension)
void	fasterGappedExtension_free ()

---

Function Documentation

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

Definition at line 31 of file fasterGappedExtension.c.

References dpResults::best, dpResults::bestScore, ungappedExtension::end, fasterGappedExtension_dpAfterSeed(), fasterGappedExtension_dpBeforeSeed(), fasterGappedExtension_joinTraces(), fasterGappedExtension_traceAfterSeed(), fasterGappedExtension_traceBeforeSeed(), global_malloc(), int4, PSSMatrix::length, PSSMatrix::matrix, ungappedExtension::nominalScore, PSSMatrix_chop(), coordinate::queryOffset, trace::queryStart, ungappedExtension::seed, ungappedExtension::start, PSSMatrix::strandLength, coordinate::subjectOffset, trace::subjectStart, gappedExtension::trace, and trace::traceCodes.

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;
    }

//    printf("Seed=%d,%d Length=%d,%d\n", seed.queryOffset, seed.subjectOffset, PSSMatrix.length, subjectSize);

        beforeDpResults = fasterGappedExtension_dpBeforeSeed(subject, PSSMatrix, seed, dropoff);

        // Trace back and create the trace which specifies the first half of the alignment
        beforeTrace = fasterGappedExtension_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 = fasterGappedExtension_dpAfterSeed(choppedSubject, choppedPSSMatrix,
                                                      dropoff, choppedSubjectSize);

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

        // Join afterTrace to the end of beforeTrace
        trace = fasterGappedExtension_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;

//      printf("Final trace length=%d\n", trace.length);

        // 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][choppedSubject[0]], 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][choppedSubject[0]];

    // 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;

    return gappedExtension;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void fasterGappedExtension_free

(

)

Definition at line 1229 of file fasterGappedExtension.c.

References fasterGappedExtension_insertQrow, fasterGappedExtension_insertSrow, fasterGappedExtension_matchRow, fasterGappedExtension_numRows, and fasterGappedExtension_traceback.

Referenced by main().

{
        // Free memory used by traceback array
        while (fasterGappedExtension_numRows > 0)
        {
        fasterGappedExtension_numRows--;
                free(fasterGappedExtension_traceback[fasterGappedExtension_numRows]);
        }
        free(fasterGappedExtension_traceback);

    free(fasterGappedExtension_matchRow);
    free(fasterGappedExtension_insertQrow);
    free(fasterGappedExtension_insertSrow);
}

Here is the caller graph for this function:

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

Definition at line 1284 of file fasterGappedExtension.c.

References dpResults::best, and int4.

{
        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");
}

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

Definition at line 1245 of file fasterGappedExtension.c.

References dpResults::best, and int4.

{
        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");
}

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

Definition at line 131 of file fasterGappedExtension.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 fasterGappedExtension_score

(

struct gappedExtension *

gappedExtension

)

Definition at line 120 of file fasterGappedExtension.c.

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

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

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

Here is the call graph for this function:

---