#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