Spec PigeonholeFinder
Pigeonhole-based finder. Must be used together with PigeonholePattern.

Extends Finder
All Extended Finder
Defined in <seqan/index/find_pigeonhole.h>
Signature template <typename THaystack, typename TSpec> class Finder<THaystack, Pigeonhole<TSpec> >;

Template Parameters

TSpec Specifies the type of pigeonhole filter.
THaystack The type of the sequence that should be searched. Types: SequenceConcept

Member Function Overview

Member Functions Inherited From Finder

Interface Function Overview

Interface Functions Inherited From Finder

Member Typedef Overview

Interface Metafunction Overview

Interface Metafunctions Inherited From Finder

Detailed Description

Provides a fast filter algorithm that uses the pigeonhole lemma, i.e. if a pattern matches with k errors in the text, every partition into k+1 parts contains one part that matches without error.

The Pattern must be a q-gram index over multiple patterns. The tolerated error rate must be given when find or windowFindBegin is called. In these functions the length of the index Shape is set automatically thus it must be modifiable at runtime, e.g. OneGappedShape.

See Also

Interface Functions Detail

THitString getWindowFindHits(finder);

Returns the string of hits from the finder.


finder A PigeonFinder.


THitString String of Hits, see THitString.

See Also

windowFindBegin(finder, pattern, errorRate)

Initializes the pattern. Sets the finder on the begin position. Gets the first non-repeat range and sets it in the finder. Used together with windowFindEnd.


finder The PigeonholeFinder to use.
pattern The PigeonholePattern to use.
errorRate Error rate that is allowed between reads and reference. Should be the same in as in windowFindNext. Types: double

See Also

void windowFindEnd(finder, pattern);

Flushes the pattern. Used together with windowFindBegin and windowFindNext.


pattern A pattern with window interface.
finder A finder with window interface. Types: PigeonholeFinder

See Also

bool windowFindNext(finder, pattern, finderWindowLength)

Searches over the next window with the finder. The found hits can be retrieved with getWindowFindHits Used together with windowFindBegin and windowFindEnd.


finder The PigeonholeFinder to use.
pattern The PigeonholePattern to use.
finderWindowLength Number of bases that are scanned beginning from the position the finder is at. Including bases that are marked as repeats and that are skipped. Types: unsigned.


bool true, if there are bases that can be scanned, false otherwise.

See Also

Member Typedef Detail

typedef (...) PigeonholeFinder::THitString;

The type to use for the hit string returned in getWindowFindHits.