/* $Id: smith_waterman.h,v 1.2 2005/12/19 15:38:01 gertz Exp $ * =========================================================================== * * PUBLIC DOMAIN NOTICE * National Center for Biotechnology Information * * This software/database is a "United States Government Work" under the * terms of the United States Copyright Act. It was written as part of * the author's official duties as a United States Government employee and * thus cannot be copyrighted. This software/database is freely available * to the public for use. The National Library of Medicine and the U.S. * Government have not placed any restriction on its use or reproduction. * * Although all reasonable efforts have been taken to ensure the accuracy * and reliability of the software and data, the NLM and the U.S. * Government do not and cannot warrant the performance or results that * may be obtained by using this software or data. The NLM and the U.S. * Government disclaim all warranties, express or implied, including * warranties of performance, merchantability or fitness for any particular * purpose. * * Please cite the author in any work or product based on this material. * * ===========================================================================*/ /** * @file smith_waterman.h * Definitions for computing Smith-Waterman alignments * * @author Alejandro Schaffer, E. Michael Gertz */ #ifndef __SMITH_WATERMAN__ #define __SMITH_WATERMAN__ #include #include #ifdef __cplusplus extern "C" { #endif /** * An instance of Blast_ForbiddenRanges is used by the Smith-Waterman * algorithm to represent ranges in the database that are not to be * aligned. */ typedef struct Blast_ForbiddenRanges { int isEmpty; /**< True if there are no forbidden ranges */ int *numForbidden; /**< how many forbidden ranges at each database position */ int **ranges; /**< forbidden ranges for each database position */ int capacity; /**< length of the query sequence */ } Blast_ForbiddenRanges; /** * Initialize a new, empty Blast_ForbiddenRanges * * @param self object to be initialized * @param capacity the number of ranges that may be stored * (must be at least as long as the length * of the query) */ NCBI_XBLAST_EXPORT int Blast_ForbiddenRangesInitialize(Blast_ForbiddenRanges * self, int capacity); /** Reset self to be empty */ NCBI_XBLAST_EXPORT void Blast_ForbiddenRangesClear(Blast_ForbiddenRanges * self); /** Add some ranges to self * @param self an instance of Blast_ForbiddenRanges [in][out] * @param queryStart start of the alignment in the query sequence * @param queryEnd the end of the alignment in the query sequence * @param matchStart start of the alignment in the subject sequence * @param matchEnd the end of the alignment in the subject sequence */ NCBI_XBLAST_EXPORT int Blast_ForbiddenRangesPush(Blast_ForbiddenRanges * self, int queryStart, int queryEnd, int matchStart, int matchEnd); /** * Release the storage associated with the fields of self, but do not * delete self * * @param self an instance of Blast_ForbiddenRanges [in][out] */ NCBI_XBLAST_EXPORT void Blast_ForbiddenRangesRelease(Blast_ForbiddenRanges * self); /** * Find the left-hand endpoints of the locally optimal Smith-Waterman * alignment given the score and right-hand endpoints computed by * Blast_SmithWatermanScoreOnly. * * @param *score_out the score of the optimal alignment -- should * equal score_in. * @param *matchSeqStart the left-hand endpoint of the alignment in * the database sequence * @param *queryStart the right-hand endpoint of the alignment * in the query sequence * @param subject_data the database sequence data * @param subject_length length of matchSeq * @param query_data the query sequence data * @param matrix amino-acid scoring matrix * @param gapOpen penalty for opening a gap * @param gapExtend penalty for extending a gap by one amino acid * @param matchSeqEnd right-hand endpoint of the alignment in * the database sequence * @param queryEnd right-hand endpoint of the alignment in * the query * @param score_in the score of the alignment * @param positionSpecific determines whether matrix is position * specific or not * @param forbiddenRanges ranges that must not be included in the alignment * * @return 0 on success, -1 on out-of-memory */ NCBI_XBLAST_EXPORT int Blast_SmithWatermanFindStart(int * score_out, int *matchSeqStart, int *queryStart, const Uint1 * subject_data, int subject_length, const Uint1 * query_data, int **matrix, int gapOpen, int gapExtend, int matchSeqEnd, int queryEnd, int score_in, int positionSpecific, const Blast_ForbiddenRanges * forbiddenRanges); /** * Compute the score and right-hand endpoints of the locally optimal * Smith-Waterman alignment, possibly subject to the restriction that some * ranges are forbidden. * * @param *score the computed score * @param *matchSeqEnd the right-hand end of the alignment in the * database sequence * @param *queryEnd the right-hand end of the alignment in the * query sequence * @param subject_data the database sequence data * @param subject_length length of matchSeq * @param query_data the query sequence data * @param query_length length of query * @param matrix amino-acid scoring matrix * @param gapOpen penalty for opening a gap * @param gapExtend penalty for extending a gap by one amino acid * @param forbiddenRanges lists areas that should not be aligned [in] * @param positionSpecific determines whether matrix is position * specific or not * @return 0 on success; -1 on out-of-memory */ NCBI_XBLAST_EXPORT int Blast_SmithWatermanScoreOnly(int *score, int *matchSeqEnd, int *queryEnd, const Uint1 * subject_data, int subject_length, const Uint1 * query_data, int query_length, int **matrix, int gapOpen, int gapExtend, int positionSpecific, const Blast_ForbiddenRanges * forbiddenRanges); #ifdef __cplusplus } #endif #endif