- Timestamp:
- Sep 14, 2007, 8:59:46 PM (15 years ago)
- Location:
- trunk/yat/utility
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/yat/utility/Alignment.cc
r867 r869 26 26 #include "Alignment.h" 27 27 #include "matrix.h" 28 #include "yat/utility/stl_utility.h" 28 29 30 #include <algorithm> 29 31 #include <utility> 30 32 #include <vector> … … 33 35 namespace yat { 34 36 namespace utility { 35 36 unsigned int ssearch(std::string first, std::string second)37 {38 matrix m(first.size(), second.size());39 for (size_t i=0; i<first.size(); ++i)40 for (size_t j=0; j<second.size(); ++j)41 m(i,j) = (first[i]==second[j] ? 1 : 0);42 std::vector<std::pair<size_t, size_t> > path;43 return static_cast<unsigned int>(NeedlemanWunsch(m,path,0));44 }45 46 37 47 38 double NeedlemanWunsch(const utility::matrix& s, … … 95 86 } 96 87 88 89 double ssearch(std::string first, std::string second, double gap, 90 double open_gap) 91 { 92 matrix m(first.size(), second.size()); 93 for (size_t i=0; i<first.size(); ++i) 94 for (size_t j=0; j<second.size(); ++j) 95 m(i,j) = (first[i]==second[j] ? 1 : 0); 96 return SmithWaterman(m, gap, open_gap); 97 } 98 99 100 double SmithWaterman(const utility::matrix& s, 101 double gap, double open_gap) 102 { 103 // Calculating S-W matrix 104 matrix m(s.rows()+2,s.columns()+2); 105 for (size_t i=2; i<m.rows(); ++i) 106 for (size_t j=2; j<m.columns(); ++j) 107 m(i,j) = max(0.0, m(i-1,j-1)+s(i-2,j-2), 108 m(i-1,j)-gap-open_gap, m(i-2,j)-2*gap, 109 m(i,j-1)-gap-open_gap, m(i,j-2)-2*gap); 110 111 return max(m); 112 } 113 97 114 }}} // of namespace utility, yat, and theplu -
trunk/yat/utility/Alignment.h
r867 r869 27 27 */ 28 28 29 #include <string> 29 30 #include <utility> 30 31 #include <vector> … … 61 62 62 63 /** 63 SSearch does a rigorous Smith-Waterman (Needleman-Wunsch with no gap 64 cost) search for similarity between a sequnces. For long sequences this 65 may be very expensive (both in time and space) and BLAST or FASTA is 66 preferable. 64 \brief Local alignment following the Smith-Waterman 65 algorithm. 67 66 68 @return number of matches 67 The original paper can be found here: 68 http://gel.ym.edu.tw/~chc/AB_papers/03.pdf 69 70 Instead of looking at each sequence in its entirety the S-W algorithm 71 compares segemnt of all possible lengths (LOCAL alignment) and chooses 72 whichever maximises the similarity measure. 73 74 \param s score matrix in which element $(i,j)$ is the score between 75 element $i$ in first sequence vs element $j$ in second sequence. 76 \param gap cost for having a gap (insertion or deletion) 77 \param open_gap cost for open up a gap in sequence, in other words, for a 78 gap of length $l$ the total cost is $open_gap + l*gap$. 69 79 */ 70 unsigned int ssearch(std::string first, std::string second); 80 double SmithWaterman(const utility::matrix& s, 81 double gap, double open_gap); 82 83 /** 84 SSearch does a rigorous Smith-Waterman search for similarity between 85 sequnces. For long sequences this may be very expensive (both in time and 86 space) and BLAST or FASTA is preferable. 87 88 @return score 89 */ 90 double ssearch(std::string first, std::string second, double gap, 91 double open_gap); 71 92 72 93 }}} // of namespace utility, yat, and theplu -
trunk/yat/utility/stl_utility.h
r865 r869 35 35 /// 36 36 37 #include <algorithm> 37 38 #include <ostream> 38 39 #include <string> … … 55 56 namespace yat { 56 57 namespace utility { 58 59 /** 60 \return max of values 61 */ 62 template <typename T> 63 T max(const T& a, const T& b, const T& c) 64 { 65 return std::max(std::max(a,b),c); 66 } 67 68 69 /** 70 \return max of values 71 */ 72 template <typename T> 73 T max(const T& a, const T& b, const T& c, const T& d) 74 { 75 return std::max(std::max(a,b), std::max(c,d)); 76 } 77 78 79 /** 80 \return max of values 81 */ 82 template <typename T> 83 T max(const T& a, const T& b, const T& c, const T& d, const T& e) 84 { 85 return std::max(max(a,b,c,d), e); 86 } 87 88 89 /** 90 \return max of values 91 */ 92 template <typename T> 93 T max(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f) 94 { 95 return std::max(max(a,b,c,d), std::max(e,f)); 96 } 57 97 58 98
Note: See TracChangeset
for help on using the changeset viewer.