Class that implements a suffix array for a String. It can be used to find peptide Candidates for a MS spectrum. More...

#include <OpenMS/DATASTRUCTURES/SuffixArrayTrypticCompressed.h>

Inheritance diagram for SuffixArrayTrypticCompressed:

Public Member Functions
	SuffixArrayTrypticCompressed (const String &st, const String &filename, const WeightWrapper::WEIGHTMODE weight_mode=WeightWrapper::MONO)
	constructor taking the string and the filename for writing or reading
	SuffixArrayTrypticCompressed (const SuffixArrayTrypticCompressed &sa)
	copy constructor
virtual	~SuffixArrayTrypticCompressed ()
	destructor
String	toString ()
	transforms suffix array to a printable String
void	findSpec (std::vector< std::vector< std::pair< std::pair< SignedSize, SignedSize >, DoubleReal > > > &candidates, const std::vector< DoubleReal > &spec)
	the function that will find all peptide candidates for a given spectrum
bool	save (const String &file_name)
	saves the suffix array to disc
bool	open (const String &file_name)
	opens the suffix array
void	setTolerance (DoubleReal t)
	setter for tolerance
DoubleReal	getTolerance () const
	getter for tolerance
bool	isDigestingEnd (const char aa1, const char aa2) const
	returns if an enzyme will cut after first character
void	setTags (const std::vector< String > &tags)
	setter for tags
const std::vector< String > &	getTags ()
	getter for tags
void	setUseTags (bool use_tags)
	setter for use_tags
bool	getUseTags ()
	getter for use_tags
void	setNumberOfModifications (Size number_of_mods)
	setter for number of modifications
Size	getNumberOfModifications ()
	getter for number of modifications
void	printStatistic ()
	output for statistic
Protected Member Functions
	SuffixArrayTrypticCompressed ()
	constructor
SignedSize	getNextSep_ (const SignedSize p) const
	gets the index of the next sperator for a given index
SignedSize	getLCP_ (const std::pair< SignedSize, SignedSize > &last_point, const std::pair< SignedSize, SignedSize > &current_point)
	gets the lcp for two strings described as pairs of ints
SignedSize	findFirst_ (const std::vector< DoubleReal > &spec, DoubleReal &m)
	binary search for finding the index of the first element of the spectrum that matches the desired mass within the tolerance.
SignedSize	findFirst_ (const std::vector< DoubleReal > &spec, DoubleReal &m, SignedSize start, SignedSize end)
	binary search for finding the index of the first element of the spectrum that matches the desired mass within the tolerance. it searches recursivly.
void	parseTree_ (SignedSize start_index, SignedSize stop_index, SignedSize depth, SignedSize walked_in, SignedSize edge_len, std::vector< std::pair< SignedSize, SignedSize > > &out_number, std::vector< std::pair< SignedSize, SignedSize > > &edge_length, std::vector< SignedSize > &leafe_depth)
	treats the suffix array as a tree and parses the tree using postorder traversion. This is realised by a recursive algorithm.
bool	hasMoreOutgoings_ (SignedSize start_index, SignedSize stop_index, SignedSize walked_in)
	indicates if a node during traversal has more outgoings
Protected Attributes
const String &	s_
	the string with which the suffix array is build
DoubleReal	tol_
	mass tolerance for finding candidates
std::vector< std::pair < SignedSize, SignedSize > >	indices_
	vector of pairs of ints describing all relevant sufices
std::vector< SignedSize >	lcp_
	vector of ints with lcp values
std::vector< SignedSize >	skip_
	vector of ints with skip values
DoubleReal	masse_ [256]
	mass table
Size	number_of_modifications_
	number of allowed modifications
std::vector< String >	tags_
	all given tags
bool	use_tags_
	indicates whether tags are used or not
SignedSize	progress_

Detailed Description

Class that implements a suffix array for a String. It can be used to find peptide Candidates for a MS spectrum.

This class implements a suffix array. It can just be used for finding peptide Candidates for a given MS Spectrum within a certain mass tolerance. The suffix array can be saved to disc for reused so it has to be build just once. The suffix array consits of a vector of pair of ints for every suffix, a vector of LCP values and a so called skip vector. Only the sufices that are matching the function isDigestingEnd are created. Besides a suffix will not reach till the end of the string but till the next occurence of the separator ($). So only the interessting sufices will be saved. This will reduce the used space.

Constructor & Destructor Documentation

SuffixArrayTrypticCompressed	(	const String &	st,
		const String &	filename,
		const WeightWrapper::WEIGHTMODE	weight_mode = `WeightWrapper::MONO`
	)

constructor taking the string and the filename for writing or reading

Parameters:

	st	the string as const reference with which the suffix array will be build
	filename	the filename for writing or reading the suffix array
	weight_mode	if not monoistopic weight should be used, this parameters can be set to AVERAGE

Exceptions:

	Exception::InvalidValue	if string does not start with empty string ($)
	FileNotFound	is thrown if the given file was not found

The constructor checks if a suffix array with given filename (without file extension) exists or not. In the first case it will simple be loaded and otherwise it will be build. Bulding the suffix array consists of several steps. At first all indices for a digesting enzyme (defined by using function isDigestingEnd) are created as an vector of SignedSize pairs. After creating all relevant indices they are sorted and the lcp and skip vectors are created.

SuffixArrayTrypticCompressed ( const SuffixArrayTrypticCompressed & sa )

copy constructor

virtual ~SuffixArrayTrypticCompressed ( ) [virtual]

destructor

SuffixArrayTrypticCompressed ( ) [protected]

constructor

Member Function Documentation

SignedSize findFirst_	(	const std::vector< DoubleReal > &	spec,
		DoubleReal &	m
	)			`[protected]`

binary search for finding the index of the first element of the spectrum that matches the desired mass within the tolerance.

Parameters:

	spec	const reference to spectrum
	m	mass

Returns:: SignedSize with the index of the first occurence

Note:: requires that there is at least one occurence

SignedSize findFirst_	(	const std::vector< DoubleReal > &	spec,
		DoubleReal &	m,
		SignedSize	start,
		SignedSize	end
	)			`[protected]`

binary search for finding the index of the first element of the spectrum that matches the desired mass within the tolerance. it searches recursivly.

Parameters:

	spec	const reference to spectrum
	m	mass
	start	start index
	end	end index

Returns:: SignedSize with the index of the first occurence

Note:: requires that there is at least one occurence

void findSpec	(	std::vector< std::vector< std::pair< std::pair< SignedSize, SignedSize >, DoubleReal > > > &	candidates,
		const std::vector< DoubleReal > &	spec
	)

the function that will find all peptide candidates for a given spectrum

Parameters:

	spec	const reference of DoubleReal vector describing the spectrum
	candidates	output parameter which contains the candidates of the masses given in spec

Returns:: a vector of SignedSize pairs.

Exceptions:

InvalidValue

if the spectrum is not sorted ascendingly

for every mass within the spectrum all candidates described by as pairs of ints are returned. All masses are searched for the same time in just one suffix array traversal. In order to accelerate the traversal the skip and lcp table are used. The mass wont be calculated for each entry but it will be updated during traversal using a stack datastructure

SignedSize getLCP_	(	const std::pair< SignedSize, SignedSize > &	last_point,
		const std::pair< SignedSize, SignedSize > &	current_point
	)			`[protected]`

gets the lcp for two strings described as pairs of ints

Parameters:

	last_point	const pair of ints describing a substring
	current_point	const pair of ints describing a substring

Returns:: SignedSize with the length of the lowest common prefix

SignedSize getNextSep_ ( const SignedSize p ) const [protected]

gets the index of the next sperator for a given index

Parameters:

p

const SignedSize describing a position in the string

Returns:: SignedSize with the index of the next occurence of the sperator or -1 if there is no more separator

Size getNumberOfModifications ( )

getter for number of modifications

Returns:: unsigned SignedSize describing number of modifications

const std::vector<String>& getTags ( )

getter for tags

Returns:: const vector of string with tags

DoubleReal getTolerance ( ) const

getter for tolerance

Returns:: DoubleReal with tolerance

bool getUseTags ( )

getter for use_tags

Returns:: bool indicating whether tags are used or not

bool hasMoreOutgoings_	(	SignedSize	start_index,
		SignedSize	stop_index,
		SignedSize	walked_in
	)			`[protected]`

indicates if a node during traversal has more outgoings

Parameters:

	start_index	SignedSize describing the start index in indices_ vector
	stop_index	SignedSize describing the end index in indices_ vector
	walked_in	how many characters we have seen from root to actual position

bool isDigestingEnd	(	const char	aa1,
		const char	aa2
	)			const

returns if an enzyme will cut after first character

Parameters:

	aa1	const char as first aminoacid
	aa2	const char as second aminoacid

Returns:: bool descibing if it is a digesting site

bool open ( const String & file_name )

opens the suffix array

Parameters:

file_name

const reference string describing the filename

Returns:: bool if operation was succesful

Exceptions:

FileNotFound

void parseTree_	(	SignedSize	start_index,
		SignedSize	stop_index,
		SignedSize	depth,
		SignedSize	walked_in,
		SignedSize	edge_len,
		std::vector< std::pair< SignedSize, SignedSize > > &	out_number,
		std::vector< std::pair< SignedSize, SignedSize > > &	edge_length,
		std::vector< SignedSize > &	leafe_depth
	)			`[protected]`

treats the suffix array as a tree and parses the tree using postorder traversion. This is realised by a recursive algorithm.

Parameters:

	start_index	SignedSize describing the start index in indices_ vector
	stop_index	SignedSize describing the end index in indices_ vector
	depth	at with depth the traversion is at the actual position
	walked_in	how many characters we have seen from root to actual position
	edge_len	how many characters we have seen from last node to actual position
	out_number	reference to vector of pairs of ints. For every node it will be filled with how many outgoing edge a node has in dependece of its depth
	edge_length	will be filled with the edge_length in dependence of its depth
	leafe_depth	will be filled with the depth of every leafe

Note:: intialize: walked_in=0, depth=1, edge_len=1

void printStatistic ( )

output for statistic

bool save ( const String & file_name )

saves the suffix array to disc

Parameters:

file_name

const reference string describing the filename

Returns:: bool if operation was succesful

Exceptions:

Exception::UnableToCreateFile

if file could not be created (e.x. if you have no rigths)

void setNumberOfModifications ( Size number_of_mods )

setter for number of modifications

Parameters:

number_of_mods

void setTags ( const std::vector< String > & tags )

setter for tags

Parameters:

tags

const vector of strings with tags with length 3 each

Exceptions:

InvalidValue

if at least one tag does not have size of 3

void setTolerance ( DoubleReal t )

setter for tolerance

Parameters:

t

DoubleReal with tolerance

Exceptions:

Exception::InvalidValue

if tolerance is negative

void setUseTags ( bool use_tags )

setter for use_tags

Parameters:

use_tags

indicating whether tags should be used or not

String toString ( )

transforms suffix array to a printable String

Member Data Documentation

std::vector<std::pair<SignedSize, SignedSize> > indices_ [protected]

vector of pairs of ints describing all relevant sufices

std::vector<SignedSize> lcp_ [protected]

vector of ints with lcp values

DoubleReal masse_[256] [protected]

mass table

Size number_of_modifications_ [protected]

number of allowed modifications

SignedSize progress_ [protected]

const String& s_ [protected]

the string with which the suffix array is build

std::vector<SignedSize> skip_ [protected]

vector of ints with skip values

std::vector<String> tags_ [protected]

all given tags

DoubleReal tol_ [protected]

mass tolerance for finding candidates

bool use_tags_ [protected]

indicates whether tags are used or not

OpenMS / TOPP release 1.10.0

Documentation generated on Thu Mar 7 2013 09:42:53 using doxygen 1.7.1

SuffixArrayTrypticCompressed Class Reference

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation