1 /* $Id: struct_dp.h 103491 2007-05-04 17:18:18Z kazimird $ 2 * =========================================================================== 3 * 4 * PUBLIC DOMAIN NOTICE 5 * National Center for Biotechnology Information 6 * 7 * This software/database is a "United States Government Work" under the 8 * terms of the United States Copyright Act. It was written as part of 9 * the author's official duties as a United States Government employee and 10 * thus cannot be copyrighted. This software/database is freely available 11 * to the public for use. The National Library of Medicine and the U.S. 12 * Government have not placed any restriction on its use or reproduction. 13 * 14 * Although all reasonable efforts have been taken to ensure the accuracy 15 * and reliability of the software and data, the NLM and the U.S. 16 * Government do not and cannot warrant the performance or results that 17 * may be obtained by using this software or data. The NLM and the U.S. 18 * Government disclaim all warranties, express or implied, including 19 * warranties of performance, merchantability or fitness for any particular 20 * purpose. 21 * 22 * Please cite the author in any work or product based on this material. 23 * 24 * =========================================================================== 25 * 26 * Authors: Paul Thiessen 27 * 28 * File Description: 29 * Dynamic programming-based alignment algorithms (C interface) 30 * 31 * =========================================================================== 32 */ 33 34 #ifndef STRUCT_DP__H 35 #define STRUCT_DP__H 36 37 #include <corelib/ncbi_limits.h> 38 39 #ifdef __cplusplus 40 extern "C" { 41 #endif 42 43 /* function result codes */ 44 #define STRUCT_DP_FOUND_ALIGNMENT 1 /* found an alignment */ 45 #define STRUCT_DP_NO_ALIGNMENT 2 /* algorithm successful, but no significant alignment found */ 46 #define STRUCT_DP_PARAMETER_ERROR 3 /* error/inconsistency in function parameters */ 47 #define STRUCT_DP_ALGORITHM_ERROR 4 /* error encountered during algorithm execution */ 48 #define STRUCT_DP_OKAY 5 /* generic ok status */ 49 50 /* lowest possible score */ 51 static const int DP_NEGATIVE_INFINITY = kMin_Int; 52 53 /* highest possible loop penalty */ 54 static const unsigned int DP_POSITIVE_INFINITY = kMax_UInt; 55 56 /* 57 * Block alignment structures and functions 58 */ 59 60 /* use for block that is not frozen */ 61 static const unsigned int DP_UNFROZEN_BLOCK = kMax_UInt; 62 63 /* info on block structure */ 64 typedef struct { 65 unsigned int nBlocks; /* number of blocks */ 66 unsigned int *blockPositions; /* first residue of each block on subject (zero-numbered) */ 67 unsigned int *blockSizes; /* length of each block */ 68 unsigned int *maxLoops; /* nBlocks-1 max loop sizes */ 69 unsigned int *freezeBlocks; /* first residue of each block on query (zero-numbered) if frozen; 70 DP_UNFROZEN_BLOCK otherwise (default); global alignment only! */ 71 } DP_BlockInfo; 72 73 /* convenience functions for allocating/destroying BlockInfo structures; 74 do not use free (MemFree), because these are C++-allocated! */ 75 extern 76 NCBI_STRUCTDP_EXPORT DP_BlockInfo * DP_CreateBlockInfo(unsigned int nBlocks); 77 extern 78 NCBI_STRUCTDP_EXPORT void DP_DestroyBlockInfo(DP_BlockInfo *blocks); 79 80 /* standard function for calculating max loop length, given a list of the sizes of all the 81 corresponding loops in each sequence/row of an existing multiple alignment: 82 83 if percentile < 1.0: 84 max = (len such that <percentile>% of loops are <= len) + extension 85 else if percentile >= 1.0: 86 max = (<percentile> * max loop len)(rounded) + extension 87 88 if cutoff > 0, max will be truncated to be <= cutoff 89 */ 90 extern 91 NCBI_STRUCTDP_EXPORT unsigned int DP_CalculateMaxLoopLength( 92 unsigned int nLoops, const unsigned int *loopLengths, /* based on existing alignment */ 93 double percentile, unsigned int extension, unsigned int cutoff); 94 95 /* callback function to get the score for a block at a specified position; should 96 return DP_NEGATIVE_INFINITY if the block can't be aligned at this position. For 97 local alignments, the average expected score for a random match must be <= zero. */ 98 typedef int (*DP_BlockScoreFunction)(unsigned int block, unsigned int queryPos); 99 100 /* returned alignment structure */ 101 typedef struct { 102 int score; /* alignment score */ 103 unsigned int nBlocks; /* number of blocks in this alignment */ 104 unsigned int firstBlock; /* first block aligned (w.r.t. subject blocks) */ 105 unsigned int *blockPositions; /* positions of blocks on query (zero-numbered) */ 106 } DP_AlignmentResult; 107 108 /* for destroying alignment result; do not use free (MemFree) */ 109 extern 110 NCBI_STRUCTDP_EXPORT void DP_DestroyAlignmentResult(DP_AlignmentResult *alignment); 111 112 /* global alignment routine */ 113 extern 114 NCBI_STRUCTDP_EXPORT int /* returns an above STRUCT_DP_ status code */ 115 DP_GlobalBlockAlign( 116 const DP_BlockInfo *blocks, /* blocks on subject */ 117 DP_BlockScoreFunction BlockScore, /* scoring function for blocks on query */ 118 unsigned int queryFrom, /* range of query to search */ 119 unsigned int queryTo, 120 DP_AlignmentResult **alignment /* alignment, if one found; caller should destroy */ 121 ); 122 123 /* local alignment routine */ 124 extern 125 NCBI_STRUCTDP_EXPORT int /* returns an above STRUCT_DP_ status code */ 126 DP_LocalBlockAlign( 127 const DP_BlockInfo *blocks, /* blocks on subject; NOTE: block freezing ignored! */ 128 DP_BlockScoreFunction BlockScore, /* scoring function for blocks on query */ 129 unsigned int queryFrom, /* range of query to search */ 130 unsigned int queryTo, 131 DP_AlignmentResult **alignment /* alignment, if one found; caller should destroy */ 132 ); 133 134 /* returned alignment container for multiple tracebacks */ 135 typedef struct { 136 unsigned int nAlignments; /* number of alignments returned */ 137 DP_AlignmentResult *alignments; /* individual alignments, highest-scoring first */ 138 } DP_MultipleAlignmentResults; 139 140 /* for destroying multiple alignment results; do not use free (MemFree) */ 141 extern 142 NCBI_STRUCTDP_EXPORT void DP_DestroyMultipleAlignmentResults(DP_MultipleAlignmentResults *alignments); 143 144 /* local alignment routine returning sorted list of highest-scoring alignments */ 145 extern 146 NCBI_STRUCTDP_EXPORT int /* returns an above STRUCT_DP_ status code */ 147 DP_MultipleLocalBlockAlign( 148 const DP_BlockInfo *blocks, /* blocks on subject; NOTE: block freezing ignored! */ 149 DP_BlockScoreFunction BlockScore, /* scoring function for blocks on query */ 150 unsigned int queryFrom, /* range of query to search */ 151 unsigned int queryTo, 152 DP_MultipleAlignmentResults **alignments, /* alignments, if any found; caller should destroy */ 153 unsigned int maxAlignments /* max # alignments to return, 0 == unlimited (all) */ 154 ); 155 156 /* callback function to get the score (a positive or zero penalty) for a given loop number and length */ 157 typedef unsigned int (*DP_LoopPenaltyFunction)(unsigned int loopNumber, unsigned int loopLength); 158 159 /* global alignment routine for generic loop scoring function */ 160 extern 161 NCBI_STRUCTDP_EXPORT int /* returns an above STRUCT_DP_ status code */ 162 DP_GlobalBlockAlignGeneric( 163 const DP_BlockInfo *blocks, /* blocks on subject; note that maxLoops are ignored! */ 164 DP_BlockScoreFunction BlockScore, /* scoring function for blocks on query */ 165 DP_LoopPenaltyFunction LoopScore, /* loop scoring function */ 166 unsigned int queryFrom, /* range of query to search */ 167 unsigned int queryTo, 168 DP_AlignmentResult **alignment /* alignment, if one found; caller should destroy */ 169 ); 170 171 /* local alignment routine for generic loop scoring */ 172 extern 173 NCBI_STRUCTDP_EXPORT int /* returns an above STRUCT_DP_ status code */ 174 DP_LocalBlockAlignGeneric( 175 const DP_BlockInfo *blocks, /* blocks on subject; NOTE: block freezing ignored! */ 176 DP_BlockScoreFunction BlockScore, /* scoring function for blocks on query */ 177 DP_LoopPenaltyFunction LoopScore, /* loop scoring function */ 178 unsigned int queryFrom, /* range of query to search */ 179 unsigned int queryTo, 180 DP_AlignmentResult **alignment /* alignment, if one found; caller should destroy */ 181 ); 182 183 /* local generic alignment routine returning sorted list of highest-scoring alignments */ 184 extern 185 NCBI_STRUCTDP_EXPORT int /* returns an above STRUCT_DP_ status code */ 186 DP_MultipleLocalBlockAlignGeneric( 187 const DP_BlockInfo *blocks, /* blocks on subject; NOTE: block freezing ignored! */ 188 DP_BlockScoreFunction BlockScore, /* scoring function for blocks on query */ 189 DP_LoopPenaltyFunction LoopScore, /* loop scoring function */ 190 unsigned int queryFrom, /* range of query to search */ 191 unsigned int queryTo, 192 DP_MultipleAlignmentResults **alignments, /* alignments, if any found; caller should destroy */ 193 unsigned int maxAlignments /* max # alignments to return, 0 == unlimited (all) */ 194 ); 195 196 #ifdef __cplusplus 197 } 198 #endif 199 200 #endif /* STRUCT_DP__H */ 201