#ifndef _theplu_yat_utility_alignment_ #define _theplu_yat_utility_alignment_ // $Id: Alignment.h 1514 2008-09-19 19:58:49Z peter$ /* Copyright (C) 2004 Jari Häkkinen, Peter Johansson Copyright (C) 2005 Peter Johansson Copyright (C) 2006 Jari Häkkinen Copyright (C) 2007 Jari Häkkinen, Peter Johansson Copyright (C) 2008 Peter Johansson This file is part of the yat library, http://dev.thep.lu.se/yat The yat library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. The yat library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with yat. If not, see . */ #include #include #include namespace theplu { namespace yat { namespace utility { class Matrix; /// /// Function performing alignment following the Needleman-Wunch /// algorithm. The algorithm starts from the dot-matrix, \a s, where /// \f$s_{ij} \f$ describes how well element \f$i \f$ in the first /// sequence match to element \f$j \f$ in the second sequence. A /// path through this matrix corresponds to an alignment of the two /// sequences, in which a diagonal step over a matrix element /// corresponds to a match between the corresponding sequnce /// elements and a vertical or a horizontal step corresponds to /// inserting a gap in one of the sequnces. The function maximizes /// \f$\sum s_{ij}-n \f$ \a gap, where the first sum goes over all /// matches and the second term is a penalty term for inserting \f$/// n \f$ gaps. Default is to have the \a gap cost set to zero. The /// vector \a path contains information about which elements that /// were matched. If the first element in the first sequence was /// matched to the first element in the second sequence, the last /// element in \a path is pair(0,0). /// /// @return the global maximum alignment score. /// double NeedlemanWunsch(const utility::Matrix& s, std::vector >& path, const double gap); /** \brief Local alignment following the Smith-Waterman algorithm. The original paper can be found here: http://gel.ym.edu.tw/~chc/AB_papers/03.pdf Instead of looking at each sequence in its entirety the S-W algorithm compares segment of all possible lengths (LOCAL alignment) and chooses whichever maximises the similarity measure. \param s score matrix in which element \f$(i,j)\f$ is the score between element \f$i\f$ in first sequence vs element \f$j\f$ in second sequence. \param gap cost for having a gap (insertion or deletion) \param open_gap cost for open up a gap in sequence, in other words, for a gap of length \f$l\f$ the total cost is \f$open_gap + l*gap\f$. */ double SmithWaterman(const utility::Matrix& s, double gap, double open_gap); /** SSearch does a rigorous Smith-Waterman search for similarity between sequnces. For long sequences this may be very expensive (both in time and space) and BLAST or FASTA is preferable. @return score */ double ssearch(std::string first, std::string second, double gap, double open_gap); }}} // of namespace utility, yat, and theplu #endif