HashTablePacked Class Reference

#include <HashTablePacked.h>

Inheritance diagram for HashTablePacked:

[legend]Collaboration diagram for HashTablePacked:

[legend]List of all members.

Public Types
typedef void(HashTablePacked::*)	MatchSequencePointer (WordSequence &, HitList &)
typedef void(HashTablePacked::*)	MatchWordPointer (Word, PackedHitStore &, int)
typedef void(*)	GenerateSubstitutesPointer (Word, vector< Word > &, int)
Public Member Functions
	HashTablePacked (ostream &monitoringStream=cerr, string name="", Allocator< PositionPacked > &hitListAllocator=defaultHitListAllocator, Allocator< PositionInHitList > &arrayAllocator=defaultArrayAllocator)
virtual void	hashWords (SequenceAdapter &thisSeq, SequenceNumber seqNum)
virtual void	countWords (SequenceAdapter &thisSeq)
virtual void	matchSequence (WordSequence &seq, HitList &hitListFwd)
virtual void	convertHits (PackedHitStore &packedHits, HitList &hitListFwd)
void	matchWordDeluxe (Word w, PackedHitStore &hitList, int offset)
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)
void	matchWordSubstitute (Word w, PackedHitStore &hitList, int offset)
Static Public Member Functions
static SequenceNumber	getSequence (const_iterator i)
static SequenceOffset	getOffset (const_iterator i)
Static Public Attributes
static AllocatorLocal< PositionInHitList >	defaultArrayAllocator
static AllocatorLocal< PositionPacked >	defaultHitListAllocator
Protected Attributes
vector< SeqStartPos >	seqStarts_
unsigned int	wordNum_
int	numRepeats_
int	substituteThreshold_
MatchSequencePointer	pMatchSequence_
MatchWordPointer	pMatchWord_
GenerateSubstitutesPointer	pGenerateSubstitutes_
RadixSorter	sorter_
Friends
class	HashTableTranslated

---

Detailed Description

Definition at line 213 of file HashTablePacked.h.

---

Member Typedef Documentation

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

Reimplemented in HashTablePackedProtein.

Definition at line 222 of file HashTablePacked.h.

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

Definition at line 225 of file HashTablePacked.h.

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

Definition at line 228 of file HashTablePacked.h.

---

Constructor & Destructor Documentation

HashTablePacked::HashTablePacked	(	ostream &	monitoringStream = cerr,
		string	name = "",
		Allocator< PositionPacked > &	hitListAllocator = defaultHitListAllocator,
		Allocator< PositionInHitList > &	arrayAllocator = defaultArrayAllocator
	)			[inline]

Definition at line 230 of file HashTablePacked.h.

References g32BitPacked, HashTableGeneric::hitListFormat_, HashTableGeneric::monitoringStream_, and seqStarts_.

                                            :
    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; // %%%%

    }

---

Member Function Documentation

static SequenceNumber HashTablePacked::getSequence

(

const_iterator

i

)

[inline, static]

static SequenceOffset HashTablePacked::getOffset

(

const_iterator

i

)

[inline, static]

void HashTablePacked::hashWords	(	SequenceAdapter &	thisSeq,
		SequenceNumber	seqNum
	)			[virtual]

Implements HashTableView< PositionPacked, HashTablePacked >.

Definition at line 146 of file HashTablePacked.cpp.

References gCursedWord, HashTableView< PositionPacked, HashTablePacked >::pHitListForAllWords_, HashTableGeneric::pHitsFoundSoFar_, HashTableGeneric::pWordPositionInHitList_, seqStarts_, SequenceAdapter::size(), and wordNum_.

Referenced by HashTableTranslated::hashAllWords(), and HashTableTranslated::hashWords().

{

  register Word              thisWord;
  register PositionInHitList currentPos;
  // NB We stop at the last but one element of the 
  // sequence (as the last isn't a full word)

   for ( int j(0) ; j < thisSeq.size() ; ++ j )
      {
        thisWord = thisSeq[j];

        // only hash words that have not been flagged
        if ((thisWord&gCursedWord)==(Word)0)
        {

          currentPos 
            = pHitsFoundSoFar_[thisWord]
            +( ( thisWord == 0 ) 
               ? 0 : pWordPositionInHitList_[thisWord - 1]) ;
                           
          if ( currentPos != pWordPositionInHitList_[thisWord] )
          { // then place position in the hit list
            pHitListForAllWords_[currentPos] = wordNum_;
            pHitsFoundSoFar_[thisWord]++;
            // next line moved: wordNum still needs incrementing even if
            // word is flagged
          //      wordNum_++;
          } // ~if
          else assert(1==0);
        } // ~if

        wordNum_++;

      } // ~ for thisWord

   seqStarts_.push_back(wordNum_);

} // ~HashTable::hashWords

Here is the call graph for this function:

Here is the caller graph for this function:

void HashTablePacked::countWords

(

SequenceAdapter &

thisSeq

)

[virtual]

Implements HashTableView< PositionPacked, HashTablePacked >.

Definition at line 132 of file HashTablePacked.cpp.

References gCursedWord, HashTableGeneric::pWordPositionInHitList_, and SequenceAdapter::size().

Referenced by HashTableTranslated::countWordsAndGetNames().

{

   for ( int j(0) ; j < thisSeq.size() ; ++ j )
   {
     // only count words that have not been flagged
     pWordPositionInHitList_[(thisSeq[j]&(~gCursedWord))]
       += ((thisSeq[j]&gCursedWord)==(Word)0);
     //     pWordPositionInHitList_[thisSeq[j]]++;
   }   
   //   cout << endl;
} // ~HashTable::countWords

Here is the call graph for this function:

Here is the caller graph for this function:

virtual void HashTablePacked::matchSequence	(	WordSequence &	seq,
		HitList &	hitListFwd
	)			[inline, virtual]

Implements HashTableGeneric.

Reimplemented in HashTablePackedProtein.

Definition at line 267 of file HashTablePacked.h.

References pMatchSequence_.

Referenced by main(), HashTableTranslated::matchSequenceProtein(), HashTablePackedProtein::matchSequenceProtein(), HashTableTranslated::matchSequenceTranslatedDNA(), and HashTablePackedProtein::matchSequenceTranslatedDNA().

    { (this->*pMatchSequence_)(seq,hitListFwd); }

Here is the caller graph for this function:

void HashTablePacked::convertHits	(	PackedHitStore &	packedHits,
		HitList &	hitListFwd
	)			[virtual]

Reimplemented in HashTableComponent, and HashTablePackedProtein.

Definition at line 225 of file HashTablePacked.cpp.

References HitListVector::addHit(), seqStarts_, sorter_, and HashTableGeneric::stepLength_.

Referenced by matchSequenceRepeated(), and matchSequenceStandard().

{

  //  sort(packedHits.begin(),packedHits.end());
  sorter_(packedHits);


  vector<HitPacked>::iterator i(packedHits.begin());
  vector<SeqStartPos>::iterator ub, j(seqStarts_.begin());
  HitListVector::size_type sortStart;
  //  hitListFwd.reserve(hitListFwd.size()+packedHits.size());

  // NB seqStarts_ must not be empty else call to back() segfaults

  while 
  (    (j!=static_cast<vector<SeqStartPos>::iterator>(&seqStarts_.back()))
    && (i!=packedHits.end()) )
  {
    ub = upper_bound(j,seqStarts_.end(),i->first);
    j=ub; j--;
    sortStart=hitListFwd.size();
    while ((i!=packedHits.end())&&(i->first<*ub))
    {
      //      cout << i->first << " ... " 
      //   << ub-seqStarts_.begin() << " " 
      //   << stepLength_*(i->first - *j) 
      //   << endl;
      hitListFwd.addHit( ub-seqStarts_.begin(), 
                         stepLength_*(i->first - *j),
                         i->second );
      i++;
      
    } // ~while
    sort
    ( static_cast<HitList::iterator>(&hitListFwd[sortStart]),
      hitListFwd.end(),
      LessThanDiff() );
    //    sort(hitListFwd.begin()+sortStart,hitListFwd.end(),LessThanDiff() );
    j=ub;  
  } // ~while

} // ~HashTablePacked::convertHits

Here is the call graph for this function:

Here is the caller graph for this function:

void HashTablePacked::matchWordDeluxe	(	Word	w,
		PackedHitStore &	hitList,
		int	offset
	)			[inline]

Definition at line 274 of file HashTablePacked.h.

References pMatchWord_.

Referenced by matchSequenceRepeated(), and matchSequenceStandard().

  {
    (this->*pMatchWord_)(w, hitList, offset);
  }

Here is the caller graph for this function:

void HashTablePacked::loadHitList

(

unsigned long

size

)

[virtual]

Reimplemented from HashTableView< PositionPacked, HashTablePacked >.

Definition at line 432 of file HashTablePacked.cpp.

References HashTableGeneric::getNumSequences(), loadFromFile(), HashTableView< T, SUBCLASS >::loadHitList(), HashTableGeneric::monitoringStream_, HashTableGeneric::name_, and seqStarts_.

{
  
  string startFileName(name_+(string)".start");

  ifstream startFile(startFileName.c_str());
  if (startFile.fail())
  {
    monitoringStream_ << "Could not open " << startFileName << endl;
    throw SSAHAException("Could not open .start file");
  } // ~if

  startFile.seekg(0,ios::end);
  long startFileSize = startFile.tellg();

  if ( getNumSequences() + 1 != startFileSize/sizeof(SeqStartPos))
  {
    seqStarts_.resize(startFileSize/sizeof(SeqStartPos));
    monitoringStream_ 
      << "Info: expecting " << seqStarts_.size()-1 << " sequences in file"
      << endl;
  } // ~if
  else seqStarts_.resize(getNumSequences()+1);

  loadFromFile(  startFileName,
                 (char*) &seqStarts_[0],
                 startFileSize  );

  HashTableView<PositionPacked,HashTablePacked>::loadHitList(size);

}

Here is the call graph for this function:

void HashTablePacked::saveHitList

(

void

)

[virtual]

Reimplemented from HashTableView< PositionPacked, HashTablePacked >.

Definition at line 466 of file HashTablePacked.cpp.

References HashTableGeneric::name_, HashTableView< T, SUBCLASS >::saveHitList(), saveToFile(), and seqStarts_.

{

  //  assert(seqStarts_.size()==getNumSequences()+1);
  // assertion removed, not true when part of a HashTableTranslated

  saveToFile(  name_+(string)".start",
               (char*) &seqStarts_[0],
               (seqStarts_.size())*sizeof(SeqStartPos)  );

  HashTableView<PositionPacked,HashTablePacked>::saveHitList();
} // ~HashTablePacked::saveHitList( void )

Here is the call graph for this function:

void HashTablePacked::setNumRepeats

(

int

numRepeats

)

[virtual]

Implements HashTableGeneric.

Definition at line 52 of file HashTablePacked.cpp.

References matchSequenceRepeated(), matchSequenceStandard(), numRepeats_, pMatchSequence_, and HashTableGeneric::stepLength_.

Referenced by main(), and HashTableTranslated::setNumRepeats().

{
  if ( (numRepeats<0) || (numRepeats>stepLength_) )
    throw SSAHAException("Invalid value for numRepeats!!");
  numRepeats_=numRepeats;
  pMatchSequence_ = ( numRepeats==0 )
    ? &HashTablePacked::matchSequenceStandard
    : &HashTablePacked::matchSequenceRepeated;
} // ~HashTablePacked::setNumRepeats( int numRepeats )

Here is the call graph for this function:

Here is the caller graph for this function:

void HashTablePacked::setSubstituteThreshold

(

int

ns

)

[virtual]

Reimplemented from HashTableGeneric.

Definition at line 62 of file HashTablePacked.cpp.

References matchWordStandard(), matchWordSubstitute(), HashTableGeneric::maxNumHits_, pMatchWord_, and substituteThreshold_.

Referenced by main(), and HashTableTranslated::setSubstituteThreshold().

{
  if ( (numSubs<0) || (numSubs>maxNumHits_) )
    throw SSAHAException("Invalid value for substituteThreshold!!");
  substituteThreshold_=numSubs;
  pMatchWord_ = ( numSubs==0 )
    ? &HashTablePacked::matchWordStandard
    : &HashTablePacked::matchWordSubstitute;
} // ~HashTablePacked::setSubstituteThreshold( int numSubs ) 

Here is the call graph for this function:

Here is the caller graph for this function:

void HashTablePacked::matchSequenceStandard	(	WordSequence &	seq,
		HitList &	hitListFwd
	)

Definition at line 187 of file HashTablePacked.cpp.

References HashTableGeneric::bitsPerSymbol_, convertHits(), WordSequence::getNumBasesInLast(), HashTableView< PositionPacked, HashTablePacked >::last(), matchWordDeluxe(), shiftSequence(), and HashTableGeneric::wordLength_.

Referenced by setNumRepeats().

{

  PackedHitStore packedHits;
  int numBasesInLast( seq.getNumBasesInLast() ), baseOffset;

  for ( int i(0) ; i < wordLength_ ; ++i )
  {
    //  matchWord( seq,    packedHits, i );
    if (seq.size()!=0)
    {
      baseOffset=i;
      WordSequence::const_iterator last(&seq.back());
      for ( WordSequence::const_iterator thisWord(seq.begin());
            thisWord != last ; ++thisWord )
      {
        int oldSize(packedHits.size()); // %%%%%%
        matchWordDeluxe( *thisWord, packedHits, baseOffset );
        //      cout << printResidue(*thisWord, wordLength_) << " "
        //  << packedHits.size()-oldSize;
        //      for (int fk(oldSize);fk!=packedHits.size();fk++) cout << " " << packedHits[fk].first;
        //      cout << endl;
        baseOffset += wordLength_;
      } // ~for
    } // ~if
    shiftSequence( seq, bitsPerSymbol_, wordLength_ );
    if ( i == numBasesInLast )
    {
      seq.pop_back();
    } // ~if
  } // ~for

  convertHits(packedHits,hitListFwd);
  
} // ~HashTablePacked::matchSequenceStandard

Here is the call graph for this function:

Here is the caller graph for this function:

void HashTablePacked::matchSequenceRepeated	(	WordSequence &	seq,
		HitList &	hitListFwd
	)

Definition at line 269 of file HashTablePacked.cpp.

References convertHits(), hits, HashTableView< PositionPacked, HashTablePacked >::matchWord(), matchWordDeluxe(), numRepeats_, seqStarts_, WordSequenceShifted::size(), HashTableGeneric::stepLength_, and HashTableGeneric::wordLength_.

Referenced by setNumRepeats().

{
    WordSequenceShifted seqShifted(seq, *this);
    //    screenRepeats( seqShifted, hitListFwd, numRepeats_ );

    PackedHitStore nonRepeatedHits;

    Word                thisWord;

    int m;

    //  cout << "my size: " << size() << endl;

    // i cycles through each full word in the query sequence
    for ( int i(0) ; i < seqShifted.size() ; ++i )
    {


      //      cout << "doing  i:" << i << endl;
      thisWord = seqShifted[i];
      m = 0;

      // look through the next numRepeats_ words for duplicates
      for ( int j(i+1) ; 
            ( ( j < seqShifted.size() ) && ( j <= i + numRepeats_ ) ); 
            ++j )
      {
        if ( thisWord == seqShifted[j] )
        {
          m = j - i;
          //      cout << "Tandem repeat: " << i << "-" << j << "\n"; // %%%%
          break;
        } // ~if
      } // ~for j
      if ( m == 0 )
      {
        //      cout << "doing bog standard matching for:" << i << endl;
        matchWordDeluxe( thisWord, nonRepeatedHits, i );
      } // ~if
      else
      {
          // ... then we have found a tandem repeat of length m
          int r(1);

          // scan forward until we reach either the end of the
          // repeated region or the end of the sequence
          while (    ( seqShifted[i+(r*m)]==thisWord )
                  && ( i+(r*m) < seqShifted.size() ) ) ++r;

          //          cout << "Num repeats: " << r << endl;

          // any hits in a run of matching hits that exceed lastRun are
          // ignored, because in that case the size of the repeated
          // region in the subject sequence exceeds the size of the
          // repeated region in the query sequence
          int lastRun((r-1)*m);

          //      cout << "size of repeated run: " << lastRun << endl;

          while ( seqShifted[i+lastRun] == seqShifted[i+lastRun-m] ) lastRun++;
          lastRun--;

          //      cout << "adjusted size of repeated run: " << lastRun << endl;

          //          HitListRepeated hits;
          PackedHitStore packedHits;
          HitListRepeated hits; 

          // as we proceed base by base along a region of tandem repeats
          // of motif length m, we encounter m distinct hash words, after
          // that, they repeat. Now get the hits for each of these words: 
          // passing in j tags each hit with its position in the repeat cycle
          for ( int j(0) ; j < m ; ++j ) 
          {
            matchWord( seqShifted[i+j], packedHits, j);
          } // ~for j

    
          sort(packedHits.begin(),packedHits.end());

          vector<HitPacked>::iterator pThisHit(packedHits.begin());
          vector<SeqStartPos>::iterator ub, j(seqStarts_.begin());
          //  hitListFwd.reserve(hitListFwd.size()+packedHits.size());
          
          // NB seqStarts_ must not be empty else call to back() segfaults

          // lastHit =  previous hit in list, initialized to all zeroes
          HitPacked lastHit; 
          // firstHit = first hit of a matching run, initialized to all zeroes
          HitPacked firstHit;

          // thisRun = size of current run of matching hits
          int thisRun(0);

          while 
          (    ( j!=static_cast<vector<SeqStartPos>::iterator>
                      ( &seqStarts_.back() ) ) 
            && ( pThisHit!=packedHits.end() ) )
          {
            ub = upper_bound(j,seqStarts_.end(),pThisHit->first);
            j=ub; j--;
            lastHit=*pThisHit; 
            // ensures if condition always false first time through while
            while ((pThisHit!=packedHits.end())&&(pThisHit->first<*ub))
            {
              if (    (    pThisHit->first
                           == lastHit.first+1 )
                      && (    pThisHit->second
                              == (( lastHit.second + stepLength_ ) % m)   ) )
              {
                if ( thisRun == 0 ) 
                { 
                  //    cout << " -s- ";
                  // then a run of matching hits has started
                  firstHit = lastHit; 
                  thisRun  = wordLength_;
                } // ~if
                else 
                {
                  //            cout << " -c- ";
                  // we continue an existing run             
                  thisRun += stepLength_;
                } // ~else
 

              } // ~if
              else 
              { 
                thisRun=0; 
                firstHit = *pThisHit;
              }
              //            cout << " -n- ";
              if (thisRun <= lastRun ) 
              { 
                // only output hits if length of repeated region in subject 
                // is less than or equal to that of query
                //    cout << "added" << (*thisHit).subjectPos.offset 
                //   << "-" << i + firstHit.cyclePos + thisRun;
                //            hitListFwd.addHit( thisHit->subjectPos, 
                //                         i + firstHit.cyclePos + thisRun ); 

                nonRepeatedHits.push_back
                  ( HitPacked( pThisHit->first, 
                               i + firstHit.second + thisRun ) ); 
              } // ~if
              else 
              {
                lastHit = *pThisHit;
              } // ~else
              pThisHit++;
            } // ~while
            j=ub;  
          } // ~while
          i += lastRun;
      } // ~else
    } // ~for i
    convertHits( nonRepeatedHits, hitListFwd );
    
} // ~HashTablePacked::matchSequenceRepeated

Here is the call graph for this function:

Here is the caller graph for this function:

void HashTablePacked::matchWordStandard	(	Word	w,
		PackedHitStore &	hitList,
		int	offset
	)			[inline]

Definition at line 294 of file HashTablePacked.h.

References HashTableView< T, SUBCLASS >::matchWord().

Referenced by setSubstituteThreshold().

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

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 73 of file HashTablePacked.cpp.

References gCursedWord, HashTableView< T, SUBCLASS >::matchWord(), HashTableView< PositionPacked, HashTablePacked >::size(), substituteThreshold_, and HashTableGeneric::wordLength_.

Referenced by setSubstituteThreshold().

{
  if ((w&gCursedWord)!=(Word)0) return;

  HashTableView<PositionPacked,HashTablePacked>::matchWord
    ( w, hitList, offset );
  assert((w&gCursedWord)==0);
  if (size(w)>substituteThreshold_) return;
  vector<Word> neighbours;
  (*pGenerateSubstitutes_)( w, neighbours, wordLength_);
  for( vector<Word>::iterator i(neighbours.begin());
       i!=neighbours.end(); i++)
  {
    HashTableView<PositionPacked,HashTablePacked>::matchWord
      ( *i, hitList, offset );
  } // ~for i
} // void HashTablePacked::matchWordSubstitute

Here is the call graph for this function:

Here is the caller graph for this function:

---

Friends And Related Function Documentation

friend class HashTableTranslated [friend]

Definition at line 216 of file HashTablePacked.h.

---

Member Data Documentation

AllocatorLocal< PositionInHitList > HashTablePacked::defaultArrayAllocator [static]

Definition at line 218 of file HashTablePacked.h.

AllocatorLocal< PositionPacked > HashTablePacked::defaultHitListAllocator [static]

Definition at line 219 of file HashTablePacked.h.

vector<SeqStartPos> HashTablePacked::seqStarts_ [protected]

Definition at line 303 of file HashTablePacked.h.

Referenced by HashTablePackedProtein::convertHits(), HashTableComponent::convertHits(), convertHits(), HashTablePackedCustom::convertHits(), HashTablePacked(), hashWords(), loadHitList(), matchSequenceRepeated(), and saveHitList().

unsigned int HashTablePacked::wordNum_ [protected]

Definition at line 304 of file HashTablePacked.h.

Referenced by hashWords().

int HashTablePacked::numRepeats_ [protected]

Definition at line 305 of file HashTablePacked.h.

Referenced by matchSequenceRepeated(), and setNumRepeats().

int HashTablePacked::substituteThreshold_ [protected]

Definition at line 306 of file HashTablePacked.h.

Referenced by matchWordSubstitute(), and setSubstituteThreshold().

MatchSequencePointer HashTablePacked::pMatchSequence_ [protected]

Reimplemented in HashTablePackedProtein.

Definition at line 307 of file HashTablePacked.h.

Referenced by matchSequence(), and setNumRepeats().

MatchWordPointer HashTablePacked::pMatchWord_ [protected]

Definition at line 308 of file HashTablePacked.h.

Referenced by matchWordDeluxe(), and setSubstituteThreshold().

GenerateSubstitutesPointer HashTablePacked::pGenerateSubstitutes_ [protected]

Definition at line 309 of file HashTablePacked.h.

Referenced by HashTableComponent::HashTableComponent(), and HashTablePackedProtein::HashTablePackedProtein().

RadixSorter HashTablePacked::sorter_ [protected]

Definition at line 311 of file HashTablePacked.h.

Referenced by HashTablePackedProtein::convertHits(), HashTableComponent::convertHits(), and convertHits().

---

The documentation for this class was generated from the following files:

• HashTable/HashTablePacked.h
• HashTable/HashTablePacked.cpp

---