1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above copyright 13 // notice, this list of conditions and the following disclaimer in the 14 // documentation and/or other materials provided with the distribution. 15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of 16 // its contributors may be used to endorse or promote products derived 17 // from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE 23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 29 // DAMAGE. 30 // 31 // ========================================================================== 32 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de> 33 // ========================================================================== 34 35 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_LOCAL_ALIGNMENT_ENUMERATION_H_ 36 #define SEQAN_INCLUDE_SEQAN_ALIGN_LOCAL_ALIGNMENT_ENUMERATION_H_ 37 38 namespace seqan { 39 40 // ============================================================================ 41 // Forwards 42 // ============================================================================ 43 44 // ============================================================================ 45 // Tags, Classes, Enums 46 // ============================================================================ 47 48 // ---------------------------------------------------------------------------- 49 // Class LocalAlignmentEnumerator 50 // ---------------------------------------------------------------------------- 51 52 template <typename TScore, typename TSpec> 53 class LocalAlignmentEnumerator; 54 55 /*! 56 * @class LocalAlignmentEnumerator 57 * @headerfile <seqan/align.h> 58 * @brief Enumeration of local alignments. 59 * 60 * @signature template <typename TScore, typename TSpec> 61 * class LocalAlignmentEnumerator; 62 * 63 * @tparam TScore The type of the @link Score @endlink to use for the local alignment. 64 * @tparam TSpec The tag to use for specializing the enumerator. 65 * 66 * See the documentation of the specializations for examples. 67 * 68 * @section References 69 * 70 * <ul> 71 * <li>Waterman MS, Eggert M: A new algorithm for best subsequence alignments with application to tRNA-rRNA 72 * comparisons. J Mol Biol 1987, 197(4):723-728.</li> 73 * </ul> 74 */ 75 76 /*! 77 * @class UnbandedLocalAlignmentEnumerator 78 * @extends LocalAlignmentEnumerator 79 * @headerfile <seqan/align.h> 80 * @brief Unbanded enumeration of local alignments using the Waterman-Eggert algorithm. 81 * 82 * @signature template <typename TScore> 83 * class LocalAlignmentEnumerator<TScore, Unbanded>; 84 * 85 * @tparam TScore The @link Score @endlink type. 86 * 87 * @section Examples 88 * 89 * Enumerate all alignments into a @link Align @endlink object. 90 * 91 * @code{.cpp} 92 * SimpleScore scoringScheme(2, -1, -1, -2); 93 * LocalAlignmentEnumerator<SimpleScore, Unbanded> enumerator(scoringScheme, 5); 94 * 95 * Dna5String seqH = "CGAGAGAGACCGAGA"; 96 * Dna5String seqV = "TTCTGAGATCCGTTTTT"; 97 * 98 * Align<Dna5String> align; 99 * resize(rows(align), 2);@s 100 * assignSource(row(align), 0, seqH); 101 * assignSource(row(align), 1, seqV); 102 * 103 * int i = 0; 104 * while (nextLocalAlignment(align, enumerator)) 105 * { 106 * std::cout << i << "-th alignment:\n"; 107 * std::cout << align << "\n\n"; 108 * std::cout << "score == " << getScore(enumerator) << "\n"; 109 * } 110 * @endcode 111 */ 112 113 /*! 114 * @fn UnbandedLocalAlignmentEnumerator::LocalAlignmentEnumerator 115 * @brief Constructor. 116 * 117 * @signature LocalAlignmentEnumerator::LocalAlignmentEnumerator(scheme[, cutoff]); 118 * 119 * @param[in] scheme The @link Score @endlink object to use for the alignment score. 120 * @param[in] cutoff Alignments with scores <tt>< cutoff</tt> will be discarded (<tt>int</tt>, default 0). 121 */ 122 123 /*! 124 * @class BandedLocalAlignmentEnumerator 125 * @extends LocalAlignmentEnumerator 126 * @headerfile <seqan/align.h> 127 * @brief Banded enumeration of local alignments using the Waterman-Eggert algorithm. 128 * 129 * @signature template <typename TScore> 130 * class LocalAlignmentEnumerator<TScore, Banded>; 131 * 132 * @tparam TScore The @link Score @endlink type. 133 * 134 * @section Examples 135 * 136 * Enumerate all alignments in the band between -3 and 0 into an @link Align @endlink object. 137 * 138 * @code{.cpp} 139 * SimpleScore scoringScheme(2, -1, -1, -2); 140 * LocalAlignmentEnumerator<SimpleScore, Banded> enumerator(scoringScheme, -3, 0, 5); 141 * 142 * Dna5String seqH = "CGAGAGAGACCGAGA"; 143 * Dna5String seqV = "TTCTGAGATCCGTTTTT"; 144 * 145 * Align<Dna5String> align; 146 * resize(rows(align), 2); 147 * assignSource(row(align), 0, seqH); 148 * assignSource(row(align), 1, seqV); 149 * 150 * int i = 0; 151 * while (nextLocalAlignment(align, enumerator)) 152 * { 153 * std::cout << i << "-th alignment:\n"; 154 * std::cout << align << "\n\n"; 155 * std::cout << "score == " << getScore(enumerator) << "\n"; 156 * } 157 * @endcode 158 */ 159 160 /*! 161 * @fn BandedLocalAlignmentEnumerator::LocalAlignmentEnumerator 162 * @brief Constructor. 163 * 164 * @signature LocalAlignmentEnumerator::LocalAlignmentEnumerator(scheme, upperDiag, lowerDiag[, cutoff]); 165 * 166 * @param[in] scheme The @link Score @endlink object to use for the alignment score. 167 * @param[in] upperDiag An <tt>int</tt> with the upper diagonal. 168 * @param[in] lowerDiag An <tt>int</tt> with the lower diagonal. 169 * @param[in] cutoff Alignments with scores <tt>< cutoff</tt> will be discarded (<tt>int</tt>, default 0). 170 */ 171 172 // ============================================================================ 173 // Metafunctions 174 // ============================================================================ 175 176 // ============================================================================ 177 // Functions 178 // ============================================================================ 179 180 // ---------------------------------------------------------------------------- 181 // Function getScore() 182 // ---------------------------------------------------------------------------- 183 184 /*! 185 * @fn LocalAlignmentEnumerator#getScore 186 * @headerfile <seqan/align.h> 187 * @brief Get current alignment score. 188 * 189 * @signature TScoreVal getScore(enumerator); 190 * 191 * @param[in] enumerator The LocalAlignmentEnumerator to query. 192 * 193 * @return TScoreVal The current alignment score (@link Score#Value @endlink of <tt>TScore</tt>). 194 */ 195 196 // ---------------------------------------------------------------------------- 197 // Function nextLocalAlignment() 198 // ---------------------------------------------------------------------------- 199 200 /*! 201 * @fn LocalAlignmentEnumerator#nextLocalAlignment 202 * @headerfile <seqan/align.h> 203 * @brief Compute next suboptimal local alignment. 204 * 205 * @signature bool nextLocalAlignment(align, enumerator); 206 * @signature bool nextLocalAlignment(gapsH, gapsV, enumerator); 207 * 208 * @param[in] align @link Align @endlink object to use for the alignment representation. 209 * @param[in] gapsH @link Gaps @endlink object to use for the first/horizontal sequence in the alignment matrix. 210 * @param[in] gapsV @link Gaps @endlink object to use for the second/vertical sequence in the alignment matrix. 211 * @param[in] enumerator The LocalAlignmentEnumerator to advance. 212 * 213 * @return bool <tt>true</tt> if another suboptimal alignment above the given threshold was found and <tt> false 214 * otherwise. 215 */ 216 217 } // namespace seqan 218 219 #endif // #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_LOCAL_ALIGNMENT_ENUMERATION_H_ 220