seq_match.hpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:7k
源码类别:

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: seq_match.hpp,v $
  4.  * PRODUCTION Revision 1000.0  2003/10/29 19:29:03  gouriano
  5.  * PRODUCTION PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.5
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. /*  $Id: seq_match.hpp,v 1000.0 2003/10/29 19:29:03 gouriano Exp $
  10.  * ===========================================================================
  11.  *
  12.  *                            PUBLIC DOMAIN NOTICE
  13.  *               National Center for Biotechnology Information
  14.  *
  15.  *  This software/database is a "United States Government Work" under the
  16.  *  terms of the United States Copyright Act.  It was written as part of
  17.  *  the author's official duties as a United States Government employee and
  18.  *  thus cannot be copyrighted.  This software/database is freely available
  19.  *  to the public for use. The National Library of Medicine and the U.S.
  20.  *  Government have not placed any restriction on its use or reproduction.
  21.  *
  22.  *  Although all reasonable efforts have been taken to ensure the accuracy
  23.  *  and reliability of the software and data, the NLM and the U.S.
  24.  *  Government do not and cannot warrant the performance or results that
  25.  *  may be obtained by using this software or data. The NLM and the U.S.
  26.  *  Government disclaim all warranties, express or implied, including
  27.  *  warranties of performance, merchantability or fitness for any particular
  28.  *  purpose.
  29.  *
  30.  *  Please cite the author in any work or product based on this material.
  31.  *
  32.  * ===========================================================================
  33.  *
  34.  * Authors:  Josh Cherry
  35.  *
  36.  * File Description:  Simple pattern matching for sequences
  37.  *
  38.  */
  39. #ifndef GUI_CORE_ALGO_BASIC___SEQ_MATCH__HPP
  40. #define GUI_CORE_ALGO_BASIC___SEQ_MATCH__HPP
  41. #include <corelib/ncbistd.hpp>
  42. BEGIN_NCBI_SCOPE
  43. ///
  44. /// This class provides functions for determining where
  45. /// sequences, perhaps containing ambiguity codes,
  46. /// must or can match patterns.
  47. ///
  48. /// The functions are highly templatized.  The main
  49. /// reason is to allow reuse of pattern-matching code with
  50. /// different 'alphabets'.  A second reason is to allow use
  51. /// of different container classes for sequences and patterns,
  52. /// e.g., the ncbi8na matching will work with both
  53. /// string and vector<char>.
  54. /// This would be much nicer with template template parameters,
  55. /// but MSVC doesn't support them.
  56. ///
  57. class CSeqMatch
  58. {
  59. public:
  60.     enum EMatch {
  61.         eNo,
  62.         eYes,
  63.         eMaybe
  64.     };
  65.     /// determine whether ncbi8na base s is a match to q.
  66.     static EMatch CompareNcbi8na(char s, char q);
  67.     /// determine whether seq matches pattern pat starting at position pos.
  68.     ///
  69.     /// It is the caller's responsibility to ensure that there are
  70.     /// enough 'characters' in seq, i.e., that pos + pat.size() <= seq.size()
  71.     template<class Seq, class Pat, class Compare_fun>
  72.     static EMatch Match(const Seq& seq, const Pat& pat, TSeqPos pos,
  73.                         const Compare_fun compare_fun)
  74.     {
  75.         // for efficiency, no check is made that we're not looking
  76.         // past the end of seq; caller must assure this
  77.         EMatch rv = eYes;
  78.         // check pattern positions in succession
  79.         for (unsigned int i = 0;  i < pat.size();  i++) {
  80.             EMatch res = compare_fun(seq[pos+i], pat[i]);
  81.             if (res == eNo) {
  82.                 return eNo;
  83.             }
  84.             if (res == eMaybe) {
  85.                 rv = eMaybe;
  86.             }
  87.         }
  88.         // if we got here, everybody at least could have matched
  89.         return rv;
  90.     }
  91.     template<class Seq, class Pat>
  92.     static EMatch MatchNcbi8na(const Seq& seq,
  93.                                const Pat& pat, TSeqPos pos)
  94.     {
  95.         return Match(seq, pat, pos, CompareNcbi8na);
  96.     }
  97.     template <class Seq, class Pat>
  98.     struct SMatchNcbi8na
  99.     {
  100.         EMatch operator() (const Seq& seq,
  101.                            const Pat& pat, TSeqPos pos) const
  102.         {
  103.             return CSeqMatch::Match(seq, pat, pos, CompareNcbi8na);
  104.         }
  105.     };
  106.     /// find all places where seq must or might match pat
  107.     template<class Seq, class Pat, class Match_fun>
  108.     static void FindMatches(const Seq& seq,
  109.                             const Pat& pat,
  110.                             vector<TSeqPos>& definite_matches,
  111.                             vector<TSeqPos>& possible_matches,
  112.                             Match_fun match)
  113.     {
  114.         for (unsigned int i = 0;  i < seq.size() - pat.size() + 1; i++) {
  115.             EMatch res = match(seq, pat, i);
  116.             if (res == eNo) {
  117.                 continue;
  118.             }
  119.             if (res == eYes) {
  120.                 definite_matches.push_back(i);
  121.                 continue;
  122.             }
  123.             // otherwise must be eMaybe
  124.             possible_matches.push_back(i);
  125.         }
  126.     }
  127.     template<class Seq, class Pat>
  128.     static void FindMatchesNcbi8na(const Seq& seq,
  129.                                    const Pat& pat,
  130.                                    vector<TSeqPos>& definite_matches,
  131.                                    vector<TSeqPos>& possible_matches)
  132.     {
  133.         FindMatches(seq, pat,
  134.                     definite_matches, possible_matches,
  135.                     SMatchNcbi8na<Seq, Pat>());
  136.     }
  137.     /// stuff for dealing with ncbi8na.
  138.     /// doesn't really belong here, but oh well
  139.     /// convert a single base from IUPAC to ncbi8na
  140.     NCBI_XALGOSEQ_EXPORT static char IupacToNcbi8na(char in);
  141.     /// convert a whole string from IUPAC to ncbi8na
  142.     NCBI_XALGOSEQ_EXPORT static void IupacToNcbi8na(const string& in, string& out);
  143.     /// complement an ncbi8na sequence in place
  144.     NCBI_XALGOSEQ_EXPORT static void CompNcbi8na(string& seq8na);
  145.     /// complement a single ncbi8na base
  146.     NCBI_XALGOSEQ_EXPORT static char CompNcbi8na(char);
  147. };
  148. // works on ncbi8na
  149. // s can match q iff they have some set bits in common
  150. // s must match q iff it represents a subset,
  151. // i.e., if no bits set in s are unset in q
  152. inline
  153. CSeqMatch::EMatch CSeqMatch::CompareNcbi8na(char s, char q)
  154. {
  155.     if (!(s & q)) {
  156.         // nothing in common
  157.         return eNo;
  158.     }
  159.     if (s & ~q) {
  160.         return eMaybe;
  161.     }
  162.     return eYes;
  163. }
  164. END_NCBI_SCOPE
  165. #endif   // GUI_CORE_ALGO_BASIC___SEQ_MATCH__HPP
  166. /*
  167.  * ===========================================================================
  168.  * $Log: seq_match.hpp,v $
  169.  * Revision 1000.0  2003/10/29 19:29:03  gouriano
  170.  * PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R1.5
  171.  *
  172.  * Revision 1.5  2003/08/18 20:07:04  dicuccio
  173.  * Corrected export specifiers
  174.  *
  175.  * Revision 1.4  2003/08/18 20:01:06  jcherry
  176.  * Changed function argument name to avoid confusion with std::compare
  177.  *
  178.  * Revision 1.3  2003/08/18 19:22:13  jcherry
  179.  * Moved orf and seq_match to algo/sequence
  180.  *
  181.  * Revision 1.2  2003/08/13 16:42:11  dicuccio
  182.  * Compilation fixes for MSVC
  183.  *
  184.  * Revision 1.1  2003/08/12 18:52:58  jcherry
  185.  * Initial version
  186.  *
  187.  * ===========================================================================
  188.  */