Index

Class

Index

Contains preprocessing data of a fixed text. In combination with a Finder or a VSTree Iterator it allows fast dictionary look-up and advanced computations.

Index


	BucketRefinement




	OpenAddressing

IndexDfi

Index<TText[, TSpec]>

Include Headers

seqan/index.h

Parameters

TText	The text type. Metafunctions: Host Types: String, StringSet
TSpec	The index type. Metafunctions: Spec Types: FMIndex, IndexEsa, IndexQGram, IndexWotd Default: The result of DefaultIndexSpec: IndexEsa

Remarks

Indices allow fast dictionary look-ups and other advanced computations because they contain pre-computated information about the underlying text. These information are stored in so called fibres (see Fibre).

In order to search for a pattern one can use a Finder or a VSTree Iterator. The Finder is especially useful when searching for exact matches while the VSTree Iterator allows to iterate an index as if traversing a tree/trie.

These fibres are created on demand depending on the requirements of an algorithm.

Specializations

FMIndex	An index based on the Burrows-Wheeler transform.
IndexEsa	The enhanced suffix array index is very fast index, requiring more memory than other indices. In addition to the suffix array an lcp (longest common prefix) table and a child table (containing structural information of the suffix tree) are provided.
IndexQGram	An index based on an array of sorted q-grams. Especially useful for q-gram/k-mer searches.
IndexSa	An index based on a suffix array.
IndexWotd	This index represents a lazy suffix tree, meaning that a path from the tree of the index in only computed, if it is traversed. For details see Giegerich et al., "Efficient implementation of lazy suffix trees".
Pizza & Chili Index	An adapter for the Pizza & Chili index API.

Metafunctions

Fibre	Type of a specific container member (fibre).
SAValue	The default alphabet type of a suffix array, i.e. the type to store a position of a string or string set.

Functions

clear	Resets an object.
countSequences	Return the number of sequences in an index' underlying text.
end	The end of a container.
getFibre	Returns a specific fibre of a container.
indexCreate	Creates a specific Fibre.
indexRequire	On-demand creation of a specific Fibre.
indexSA	Shortcut for getFibre(.., FibreSA).
indexSupplied	Returns whether a specific Fibre is present.
indexText	Shortcut for getFibre(index, FibreText()).
length	The number of characters in the underlying text of the index is returned.
open	This functions opens an index from disk.
save	This functions saves an index to disk.
setHaystack	Sets the haystack of a Finder object.

Examples

The following code shows how to search for exact matches between the reference "tobeornottobe" and the pattern "to" with the means of a Finder.

File "index_finder.cpp"

1	#include <seqan/index.h>
2
3	using namespace seqan;
4
5	int main ()
6	{
7	typedef Index<CharString> TIndex;
8
9	TIndex index("tobeornottobe");
10	Finder<TIndex> finder(index);
11
12	// The Finder object has a pointer to the first, current and last hit
13	// Each consecutive call sets the current pointer to the appropriate hit
14	while (find(finder, "to"))
15	std::cout << "Hit at position: " << position(finder) << std::endl;
16
17	return 0;
18	}

Hit at position: 9
Hit at position: 0

This code shows how an index can be used with iterators to achieve a pre-order tree like traversal in DFS of the text "tobeornottobe". In order to do so a Top-Down History iterator is used.

File "index_iterator.cpp"

1	#include <seqan/index.h>
2
3	using namespace seqan;
4
5	int main ()
6	{
7	typedef Index<CharString> TIndex;
8
9	TIndex index("tobeornottobe");
10	Iterator<TIndex, TopDown<ParentLinks<> > >::Type it(index);
11
12	do {
13	// Print theletters from the root to the current node
14	std::cout << representative(it) << std::endl;
15
16	if (!goDown(it) && !goRight(it))
17	while (goUp(it) && !goRight(it)) ;
18	} while (!isRoot(it));
19
20	return 0;
21	}

be
beornottobe
e
eornottobe
nottobe
o
obe
obeornottobe
ornottobe
ottobe
rnottobe
t
tobe
tobeornottobe
ttobe

Note that you can also use specialised iterators such as:

Iterator<TIndex, TopDown<ParentLinks<PreOrder> > >::Type

Iterator<TIndex, TopDown<ParentLinks<PostOrder> > >::Type

You can achieve a post-order traversal like this:

1	Iterator< TIndex, TopDown< ParentLinks<Postorder> > >::Type it(index);
2
3	goBegin(it);
4	while (!atEnd(it))
5	{
6	std::cout << representative(it) << std::endl;
7	++it;
8	}

Snippet from "index_iterator_short.cpp"

beornottobe
be
eornottobe
e
nottobe
obeornottobe
obe
ornottobe
ottobe
o
rnottobe
tobeornottobe
tobe
ttobe
t

Example Programs

Maximal Repeats, Index Finder StringSet, Mummy, Maximal Unique Matches, Index lcpAt, saAt, Index Finder, Index countOccurrencesMultiple, Supermaximal Repeats, Index countChildren

SeqAn - Sequence Analysis Library - www.seqan.de