HashTable/HashTablePacked.h

Go to the documentation of this file.

/*  Last edited: Mar 27 16:30 2002 (ac2) */

// #######################################################################

// SSAHA : Sequence Search and Alignment by Hashing Algorithm
// Version 3.2, released 1st March 2004
// Copyright (c) Genome Research 2002

// SSAHA is free software; you can redistribute it and/or modify 
// it under the terms of version 2 of the GNU General Public Licence
// as published by the Free Software Foundation.
 
// This program 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 Licence for more details.
 
// You should have received a copy of the GNU General Public Licence
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
// or see the on-line version at http://www.gnu.org/copyleft/gpl.txt

// #######################################################################

// Module Name  : HashTablePacked
// File Name    : HashTablePacked.h
// Language     : C++
// Module Author: Anthony J. Cox (ac2@sanger.ac.uk)

// Include guard:
#ifndef INCLUDED_HashTablePacked
#define INCLUDED_HashTablePacked

// Description:

// Includes:
#include "HashTableGeneric.h"

// NB it is good practise for #include statements in header files to be
// replaced by forward declarations if at all possible

// ### Class Declarations ###

typedef unsigned int PositionPacked;
typedef unsigned int SeqStartPos;

typedef pair<PositionPacked, int> HitPacked;
struct PackedHitStore : public vector<HitPacked>
{
  void addHit( PositionPacked pos, int baseOffset )
  { 
    push_back(HitPacked(pos,baseOffset)); 
  }

};
static const HitPacked zeroHit = HitPacked(0,0);


// Class Name : RadixSorter
// Description: Sorts a vector of HitPacked by the first element of each
// entry using a radix sorting method.

class RadixSorter
{
// capacity of CountInt determines the max number of elements that 
// can be sorted
typedef unsigned int CountInt;
 
public:
  RadixSorter( const unsigned int digits, const unsigned int bits );
  void operator()( vector<HitPacked>& v );
  void CountDigits( const vector<HitPacked>& v );
  void SortByDigit( PositionPacked digit );

protected:
  const unsigned int digits_;
  const unsigned int bits_;
  const unsigned long base_;
  const PositionPacked mask_;
  vector<HitPacked> v1_;
  vector< vector<CountInt> > counts_; 
  vector<HitPacked>* source_;
  vector<HitPacked>* target_;
  vector< vector<HitPacked>::iterator > places_;

}; // ~class RadixSorter

class LessThanDiff
{
  public:
  bool operator()( const HitInfo& lhs, const HitInfo& rhs ) const
  {
    return ( lhs.diff < rhs.diff ); 
  }
};


void generateSubstitutesDNA
(Word w, vector<Word>& subs, int wordLength);

void generateSubstitutesProtein
(Word w, vector<Word>& subs, int wordLength);

// 0  *
// 1  A 
// 2  C
// 3  D
// 4  E
// 5  F
// 6  G
// 7  H
// 8  I
// 9  K
// 10 L
// 11 M
// 12 N
// 13 P
// 14 Q
// 15 R
// 16 S
// 17 T
// 18 V
// 19 W
// 20 X
// 21 Y

const Word subVals[] =
{
              // *
  16,         // AS: 1
              // BD: 4 BE: 1 BN: 3 BZ: 1 - not used 
              // C
  4,  12,     // DB: 4 DE: 2 DN: 1 DZ: 1 - B,Z not used
  3,  9, 14,  // EB: 1 ED: 2 EK: 1 EQ: 2 EZ: 4 - B,Z not used
  19, 21,     // FW: 1 FY: 3
              // G 
  12, 21,     // HN: 1 HY: 2
  10, 11, 18, // IL: 2 IM: 1 IV: 3
  4,  14, 15, // KE: 1 KQ: 1 KR: 2 KZ: 1 -  Z not used
  8,  11, 18, // LI: 2 LM: 2 LV: 1
  8,  10, 18, // MI: 1 ML: 2 MV: 1
  3,  7,  16, // NB: 3 ND: 1 NH: 1 NS: 1 - B not used
              // P 
  4,  9,  15, // QE: 2 QK: 1 QR: 1 QZ: 3 - Z not used
  9,  14,     // RK: 2 RQ: 1
  1,  12, 17, // SA: 1 SN: 1 ST: 1
  16,         // TS: 1
  8,  10, 11, // VI: 3 VL: 1 VM: 1
  5,  21,     // WF: 1 WY: 2
  5,  7,  19, // YF: 3 YH: 2 YW: 2
             //  ZB: 1 ZD: 1 ZE: 4 ZK: 1 ZQ: 3 - Z not used
  99999
};

const int subStarts[] =
{
0,  // 0  *
0,  // 1  A 
1,  // 2  C
1,  // 3  D
3,  // 4  E
6,  // 5  F
8,  // 6  G
8,  // 7  H
10, // 8  I
13, // 9  K
16, // 10 L
19, // 11 M
22, // 12 N
25, // 13 P
25, // 14 Q
28, // 15 R
30, // 16 S
33, // 17 T
34, // 18 V
37, // 19 W
39, // 20 X
39, // 21 Y
42
};


#ifdef POSITIVE_SCORING_BLOSUM_SUBS 
Original table: generated from BLOSUM62 table in MatchStore.h
AS: 1
BD: 4 BE: 1 BN: 3 BZ: 1 
DB: 4 DE: 2 DN: 1 DZ: 1
EB: 1 ED: 2 EK: 1 EQ: 2 EZ: 4
FW: 1 FY: 3
HN: 1 HY: 2
IL: 2 IM: 1 IV: 3
KE: 1 KQ: 1 KR: 2 KZ: 1
LI: 2 LM: 2 LV: 1
MI: 1 ML: 2 MV: 1
NB: 3 ND: 1 NH: 1 NS: 1
QE: 2 QK: 1 QR: 1 QZ: 3
RK: 2 RQ: 1
SA: 1 SN: 1 ST: 1
TS: 1
VI: 3 VL: 1 VM: 1
WF: 1 WY: 2
YF: 3 YH: 2 YW: 2
ZB: 1 ZD: 1 ZE: 4 ZK: 1 ZQ: 3
#endif








class HashTablePacked : 
public HashTableView<PositionPacked,HashTablePacked>
{
  friend class HashTableTranslated;
 public:
  static AllocatorLocal<PositionInHitList> defaultArrayAllocator;
  static AllocatorLocal<PositionPacked> defaultHitListAllocator;

  typedef void (HashTablePacked::* MatchSequencePointer)
    (WordSequence&, HitList&);

  typedef void (HashTablePacked::* MatchWordPointer)
    (Word, PackedHitStore&, int);

  typedef void (* GenerateSubstitutesPointer)
    (Word, vector<Word>&, int);

  HashTablePacked( ostream& monitoringStream=cerr,
                   string name="",
                   Allocator<PositionPacked>& hitListAllocator 
                   = defaultHitListAllocator,
                   Allocator<PositionInHitList>& arrayAllocator 
                   = defaultArrayAllocator ):
    HashTableView<PositionPacked,HashTablePacked>
    (monitoringStream, name, hitListAllocator, arrayAllocator),
    wordNum_(0),
    pMatchSequence_(&HashTablePacked::matchSequenceStandard),
    pMatchWord_(&HashTablePacked::matchWordStandard),
    pGenerateSubstitutes_(&generateSubstitutesDNA),
    numRepeats_(0),
    substituteThreshold_(0),
    sorter_(4,(sizeof(PositionPacked)*8)/4)
    {
      hitListFormat_ = g32BitPacked;
      seqStarts_.push_back(0);
      monitoringStream_ << "constructing HashTablePacked\n";
      //      cout << pArrayAllocator_->name_ << " " 
      //           << pHitListAllocator_->name_ << endl; // %%%%

    }

  //  HashTablePacked( ostream& monitoringStream=cerr) :
  //   HashTableView<PositionPacked,HashTablePacked>(monitoringStream),
  //   wordNum_(0){}

  inline static SequenceNumber getSequence( const_iterator i );
  inline static SequenceOffset getOffset( const_iterator i );


  virtual void hashWords
  ( SequenceAdapter& thisSeq, SequenceNumber seqNum );
  virtual void countWords( SequenceAdapter& thisSeq );
  
  virtual void matchSequence
  ( WordSequence& seq, HitList& hitListFwd )
    { (this->*pMatchSequence_)(seq,hitListFwd); }


  virtual void convertHits
  ( PackedHitStore& packedHits, HitList& hitListFwd );

  void matchWordDeluxe( Word w, PackedHitStore& hitList, int offset )
  {
    (this->*pMatchWord_)(w, hitList, offset);
  }

  // load and save need to be overloaded because seqStarts_ needs
  // to be loaded/saved as well
  virtual void loadHitList( unsigned long size );

  virtual void saveHitList( void );

  virtual void setNumRepeats(int numRepeats);
  virtual void setSubstituteThreshold( int ns );

  void matchSequenceStandard
    ( WordSequence& seq, HitList& hitListFwd );

  void matchSequenceRepeated
    ( WordSequence& seq, HitList& hitListFwd );

  void matchWordStandard( Word w, PackedHitStore& hitList, int offset )
  {
    HashTableView<PositionPacked,HashTablePacked>::matchWord
      ( w, hitList, offset );
  } // ~matchWordStandard( Word w, HitListVector hitList, int offset )

  void matchWordSubstitute( Word w, PackedHitStore& hitList, int offset );

 protected:
  vector<SeqStartPos> seqStarts_;
  unsigned int wordNum_;
  int numRepeats_;
  int substituteThreshold_;
  MatchSequencePointer pMatchSequence_;
  MatchWordPointer pMatchWord_;
  GenerateSubstitutesPointer pGenerateSubstitutes_;

  RadixSorter sorter_;

}; // ~class HashTablePacked



// ### Function Declarations ###

// Name:
// Arguments:
// TYPE  NAME  IN/OUT COMMENT
// Returns: TYPE COMMENT

// End of include guard:
#endif

// End of file HashTablePacked.h

---