A map alignment algorithm based on spectrum similarity (dynamic programming). More...

#include <OpenMS/ANALYSIS/MAPMATCHING/MapAlignmentAlgorithmSpectrumAlignment.h>

Inheritance diagram for MapAlignmentAlgorithmSpectrumAlignment:

Classes
class	Compare
	innerclass necessary for using the sort algo. More...
Public Member Functions
	MapAlignmentAlgorithmSpectrumAlignment ()
	Default constructor.
virtual	~MapAlignmentAlgorithmSpectrumAlignment ()
	Destructor.
virtual void	alignPeakMaps (std::vector< MSExperiment<> > &, std::vector< TransformationDescription > &)
	Aligns peak maps.
Static Public Member Functions
static MapAlignmentAlgorithm *	create ()
	Creates a new instance of this class (for Factory).
static String	getProductName ()
	Returns the product name (for the Factory).
Private Member Functions
	MapAlignmentAlgorithmSpectrumAlignment (const MapAlignmentAlgorithmSpectrumAlignment &)
	Copy constructor is not implemented -> private.
MapAlignmentAlgorithmSpectrumAlignment &	operator= (const MapAlignmentAlgorithmSpectrumAlignment &)
	Assignment operator is not implemented -> private.
void	prepareAlign_ (const std::vector< MSSpectrum<> * > &pattern, MSExperiment<> &aligned, std::vector< TransformationDescription > &transformation)
	A function to prepare the sequence for the alignment. It calls intern the main function for the alignment.
void	msFilter_ (MSExperiment<> &peakmap, std::vector< MSSpectrum<> * > &spectrum_pointer_container)
	filtered the MSLevel to gain only MSLevel 1
void	fourierActivation_ (std::vector< MSSpectrum<> * > &spectrum_pointer_container)
	does the transformation if the Discrete Cosines Fourier Transformation is selected.
void	transform_ (MSSpectrum<> &spec)
	calculate the Discrete Cosines Fourier Transformation.
bool	insideBand_ (Size i, Size j, Size n, Size m, Int k_)
	function for the test if cell i,j of the grid is inside the band
Int	bestk_ (const std::vector< MSSpectrum<> * > &pattern, std::vector< MSSpectrum<> * > &aligned, std::map< Size, std::map< Size, Real > > &buffer, bool column_row_orientation, Size xbegin, Size xend, Size ybegin, Size yend)
	calculate the size of the band for the alignment for two given Sequence
Real	scoreCalculation_ (Size i, Size j, Size patternbegin, Size alignbegin, const std::vector< MSSpectrum<> * > &pattern, std::vector< MSSpectrum<> * > &aligned, std::map< Size, std::map< Size, Real > > &buffer, bool column_row_orientation)
	calculate the score of two given MSSpectrums calls intern scoring_
Real	scoring_ (const MSSpectrum<> &a, MSSpectrum<> &b)
	return the score of two given MSSpectrums by calling the scorefunction
void	affineGapalign_ (Size xbegin, Size ybegin, Size xend, Size yend, const std::vector< MSSpectrum<> * > &pattern, std::vector< MSSpectrum<> * > &aligned, std::vector< int > &xcoordinate, std::vector< Real > &ycoordinate, std::vector< int > &xcoordinatepattern)
	affine gap cost Alignment
void	bucketFilter_ (const std::vector< MSSpectrum<> * > &pattern, std::vector< MSSpectrum<> * > &aligned, std::vector< Int > &xcoordinate, std::vector< Real > &ycoordinate, std::vector< Int > &xcoordinatepattern)
	preparation function of data points to construct later the spline function.
void	debugFileCreator_ (const std::vector< MSSpectrum<> * > &pattern, std::vector< MSSpectrum<> * > &aligned)
	Creates files for the debugging.
void	eraseFloatDataArrayEntry_ (std::vector< MSSpectrum<> * > &spectrum_pointer_container)
	Delete entries of the FloatDataArray which was made from CompareFouriertransform.
void	debugscoreDistributionCalculation_ (Real score)
	Rounding the score of two spectras, only necessary for debugging.
void	updateMembers_ ()
Private Attributes
Real	gap_
	Represent the gap cost for opening o closing a gap in the alignment.
Real	e_
	Extension cost after a gap ist open.
PeakSpectrumCompareFunctor *	c1_
	Pointer holds the scoringfunction, which can be selected.
Real	cutoffScore_
	This is the minimal score to be count as a mismatch(range 0.0 - 1.0).
Size	bucketsize_
	Defines the size of one bucket.
Size	anchorPoints_
	Defines the amount of ankerpoints which are selected within one bucket.
bool	debug_
	Debug mode flag default: False.
Real	mismatchscore_
	Represent the cost of a mismath in the alignment.
Real	threshold_
	This is the minimum score for counting as a match(1-cutoffScore_).
std::vector< std::vector< Real > >	debugmatrix_
	Container holding the score of the matchmatrix and also the insertmatrix.
std::vector< std::vector< Real > >	debugscorematrix_
	Container holding the only the score of Spectrums.
std::vector< std::pair< Real, Real > >	debugtraceback_
	Container holding the path of the traceback.
std::vector< Real >	scoredistribution_
	Container holding the score of each cell(matchmatrix,insertmatrix, traceback).

Detailed Description

A map alignment algorithm based on spectrum similarity (dynamic programming).

Parameters of this class are:

Name	Type	Default	Restrictions	Description
gapcost	float	1	min: 0	This Parameter stands for the cost of opining a gap in the Alignment. A Gap means that one Spectrum can not be aligned directly to another Spectrum in the Map. This happens, when the similarity of both spectra a too low or even not present. Imagen as a insert or delete of the spectrum in the map. The gap is necessary for aligning, if we open a gap there is a possibility that an another spectrum can be correct aligned with a higher score as before without gap. But to open a gap is a negative event and has to be punished a bit, so such only in case it 's a good choice to open a gap, if the score is bad enough. The Parameter is to giving as a positive number, the implementation convert it to a negative number.
affinegapcost	float	0.5	min: 0	This Parameter controls the cost of extension a already open gap. The idea behind the affine gapcost lies under the assumption, that it is better to get a long distance of connected gaps than to have a structure gap match gap match. There for the punishment for the extension of a gap has to be lower than the normal gapcost. If the the result of the aligmnet show high compression, it is a good idea to lower the affine gapcost or the normal gapcost.
cutoff_score	float	0.7	min: 0 max: 1	The Parameter defines the threshold which filtered Spectra, these Spectra are high potential candidate for deciding the interval of a sub-alignment. Only those pair of Spectra are selected, which has a score higher or same of the threshold.
bucketsize	int	100	min: 1	Defines the numbers of buckets. It is a quantize of the interval of those points, which defines the main alignment(match points). These points have to filtered, to reduce the amount of points for the calculating a smoother spline curve.
anchorpoints	int	100	min: 1 max: 100	Defines the percent of numbers of match points which a selected from one bucket. The high score pairs are previously selected. The reduction of match points helps to get a smoother spline curve.
debug	string	false	true, false	active the debug mode, there a files written starting with debug prefix.
mismatchscore	float	-5	max: 0	Defines the score of two Spectra if they have no similarity to each other.
scorefunction	string	SteinScottImproveScore	SteinScottImproveScore, ZhangSimilarityScore	The score function is the core of an alignment. The success of an alignment depends mostly of the elected score function. The score function return the similarity of two Spectrum back. The score influence defines later the way of possible traceback. There exist many way of algorithm to calculate the score.

Note:

If a section name is documented, the documentation is displayed as tooltip.
Advanced parameter names are italic.

Experimental classes:: This algorithm is work in progress and might change.

Constructor & Destructor Documentation

MapAlignmentAlgorithmSpectrumAlignment ( )

Default constructor.

virtual ~MapAlignmentAlgorithmSpectrumAlignment ( ) [virtual]

Destructor.

MapAlignmentAlgorithmSpectrumAlignment ( const MapAlignmentAlgorithmSpectrumAlignment & ) [private]

Copy constructor is not implemented -> private.

Member Function Documentation

void affineGapalign_	(	Size	xbegin,
		Size	ybegin,
		Size	xend,
		Size	yend,
		const std::vector< MSSpectrum<> * > &	pattern,
		std::vector< MSSpectrum<> * > &	aligned,
		std::vector< int > &	xcoordinate,
		std::vector< Real > &	ycoordinate,
		std::vector< int > &	xcoordinatepattern
	)			`[private]`

affine gap cost Alignment

This Alignment is based on the Needleman Wunsch Algorithm. To improve the time complexity a banded version was implemented, known as k - alignment. To save some space, the alignment is going to be calculated by position xbegin to xend of one sequence and ybegin and yend by another given sequence. The result of the alignment is stored in the second argument. The first sequence is used as a template for the alignment.

Parameters:

	xbegin	cordinate for the beginning of the template sequence.
	ybegin	cordinate for the beginning of the aligend sequence .
	xend	cordinate for the end of the template sequence.
	yend	cordinate for the end of the aligend sequence.
	pattern	template map.
	aligned	map to be aligned.
	xcoordinate	save the postion of ankerpoints
	ycoordinate	save the retentiontimes of an ankerpoints
	xcoordinatepattern	save the reference position of the ankerpoints from the pattern

Exceptions:

Exception::OutOfRange if a out of bound appear pattern or aligned

virtual void alignPeakMaps	(	std::vector< MSExperiment<> > &	,
		std::vector< TransformationDescription > &
	)			`[virtual]`

Aligns peak maps.

Exceptions:

Exception::NotImplemented

is thrown if an algorithm cannot align peak maps

Reimplemented from MapAlignmentAlgorithm.

Int bestk_	(	const std::vector< MSSpectrum<> * > &	pattern,
		std::vector< MSSpectrum<> * > &	aligned,
		std::map< Size, std::map< Size, Real > > &	buffer,
		bool	column_row_orientation,
		Size	xbegin,
		Size	xend,
		Size	ybegin,
		Size	yend
	)			`[private]`

calculate the size of the band for the alignment for two given Sequence

This function calculates the size of the band for the alignment. It takes three samples from the aligned sequence and tries to find the highscore pairs(matching against the template sequence). The highscore pair with the worst distance is to be chosen as the size of k.

Parameters:

	pattern	vector of pointers of the template sequence
	aligned	vector of pointers of the aligned sequence
	buffer	holds the calculated score of index i,j.
	column_row_orientation	indicate the order of the matrix
	xbegin	indicate the beginning of the template sequence
	xend	indicate the end of the template sequence
	ybegin	indicate the beginning of the aligned sequence
	yend	indicate the end of the aligned sequence

void bucketFilter_	(	const std::vector< MSSpectrum<> * > &	pattern,
		std::vector< MSSpectrum<> * > &	aligned,
		std::vector< Int > &	xcoordinate,
		std::vector< Real > &	ycoordinate,
		std::vector< Int > &	xcoordinatepattern
	)			`[private]`

preparation function of data points to construct later the spline function.

This function reduced the amount of data values for the next step. The reduction is done by using a number of buckets, where the data points a selected. Within the buckets, only defined number a selected, to be written back as a data point. The selection within the buckets is done by scoring.

Parameters:

	pattern	template map.
	aligned	map to be aligned.
	xcoordinate	save the position of anchor points
	ycoordinate	save the retention times of an anchor points
	xcoordinatepattern	save the reference position of the anchor points from the pattern

static MapAlignmentAlgorithm* create ( ) [inline, static]

Creates a new instance of this class (for Factory).

void debugFileCreator_	(	const std::vector< MSSpectrum<> * > &	pattern,
		std::vector< MSSpectrum<> * > &	aligned
	)			`[private]`

Creates files for the debugging.

This function is only active if the debugflag ist true. The debugfileCreator creates following files debugtraceback.txt(gnuplotScript), debugscoreheatmap.r and debugRscript. Debugscoreheatmap.r contains the scores of the Spectra to each other from the alignment and also the traceback. DebugRscript is the R script which reads those data. So both files are only working under R. Start R and type main(location of debugscoreheatmap.r). The output will be a heatmap of each sub-alignment. Debugtraceback.txt shows the way of the Traceback by using gnuplot.

Parameters:

	pattern	template map.
	aligned	map to be aligned.

void debugscoreDistributionCalculation_ ( Real score ) [private]

Rounding the score of two spectras, only necessary for debugging.

This function rounded the score of two spectras.This is necessary for some function in the Debug-Mode

void eraseFloatDataArrayEntry_ ( std::vector< MSSpectrum<> * > & spectrum_pointer_container ) [private]

Delete entries of the FloatDataArray which was made from CompareFouriertransform.

This function erase the entries with was done by the CompareFouriertransform function.

void fourierActivation_ ( std::vector< MSSpectrum<> * > & spectrum_pointer_container ) [private]

does the transformation if the Discrete Cosines Fourier Transformation is selected.

Call internally the function transform, only if the comparison score function Fourier is selected.

Parameters:

spectrum_pointer_container

is the sequence which has to be transform

static String getProductName ( ) [inline, static]

Returns the product name (for the Factory).

bool insideBand_	(	Size	i,
		Size	j,
		Size	n,
		Size	m,
		Int	k_
	)			`[private]`

function for the test if cell i,j of the grid is inside the band

The function returns true if the cell underlie these conditions: -k<=i-j<=k+n-m else retun false.

Parameters:

	i	coordinate i
	j	coordinate j
	n	size of column
	m	size of row
	k_	size of k_

void msFilter_	(	MSExperiment<> &	peakmap,
		std::vector< MSSpectrum<> * > &	spectrum_pointer_container
	)			`[private]`

filtered the MSLevel to gain only MSLevel 1

The alignment works only on MSLevel 1 data, so a filter has to be run.

Parameters:

	peakmap	map which has to be filtered
	spectrum_pointer_container	output container, where pointers of the MSSpectrum are saved(only with MS level 1)

Exceptions:

Exception::IllegalArgument is thrown if no spectra are contained in peakmap

MapAlignmentAlgorithmSpectrumAlignment& operator= ( const MapAlignmentAlgorithmSpectrumAlignment & ) [private]

Assignment operator is not implemented -> private.

void prepareAlign_	(	const std::vector< MSSpectrum<> * > &	pattern,
		MSExperiment<> &	aligned,
		std::vector< TransformationDescription > &	transformation
	)			`[private]`

A function to prepare the sequence for the alignment. It calls intern the main function for the alignment.

This function takes two arguments. These argument types are two MSExperiments. The first argument should have been filtered, so that only the type of MSLevel 1 exists in the Sequence. The second argument doesn't have to fulfill this restriction. It's going to be filtered automatically. With these two arguments a precalculation is done to find some corresponding data points(maximum 4) for building alignment blocks. After the alignment a retransformation is done, the new Retention Times appear in the original data.

The parameters are MSExperiments.

Parameters:

	pattern	template map.
	aligned	map which has to be aligned.
	transformation	container for rebuilding the alignment only by specific data-points

Real scoreCalculation_	(	Size	i,
		Size	j,
		Size	patternbegin,
		Size	alignbegin,
		const std::vector< MSSpectrum<> * > &	pattern,
		std::vector< MSSpectrum<> * > &	aligned,
		std::map< Size, std::map< Size, Real > > &	buffer,
		bool	column_row_orientation
	)			`[private]`

calculate the score of two given MSSpectrums calls intern scoring_

This function calculates the score from two MSSpectrums. These two MSSpectrums are chosen by the coordinates i,j. I,j indicate the index in the matrix. To find the right index on the sequence, each beginning is also given to the function. A flag indicates the labeling of the axes. The buffermatrix stores the result of the scoring. If the band expands only a lookup of known scores is done.

Parameters:

	i	is a index from the matrix.
	j	is a index from the matrix.
	patternbegin	indicate the beginning of the template sequence
	alignbegin	indicate the beginning of the aligned sequence
	pattern	vector of pointers of the template sequence
	aligned	vector of pointers of the aligned sequence
	buffer	holds the calculated score of index i,j.
	column_row_orientation	indicate the order of the matrix

Real scoring_	(	const MSSpectrum<> &	a,
		MSSpectrum<> &	b
	)			`[private]`

return the score of two given MSSpectrums by calling the scorefunction

void transform_ ( MSSpectrum<> & spec ) [private]

calculate the Discrete Cosines Fourier Transformation.

This Function transforms a given MSSpectrum to a Discrete Cosines Fourier Transformation. It stores only the part of the cosines of the FFT in the FloatDataArray which is a container from the MSSpectrum. Only call this function, if you are sure there is no other transformation done earlier over the same MSSpectrum, because it isn't checked if there already exists a transformation.

void updateMembers_ ( ) [private]

Member Data Documentation

Size anchorPoints_ [private]

Defines the amount of ankerpoints which are selected within one bucket.

Size bucketsize_ [private]

Defines the size of one bucket.

PeakSpectrumCompareFunctor* c1_ [private]

Pointer holds the scoringfunction, which can be selected.

Real cutoffScore_ [private]

This is the minimal score to be count as a mismatch(range 0.0 - 1.0).

bool debug_ [private]

Debug mode flag default: False.

std::vector<std::vector<Real> > debugmatrix_ [private]

Container holding the score of the matchmatrix and also the insertmatrix.

std::vector<std::vector<Real> > debugscorematrix_ [private]

Container holding the only the score of Spectrums.

std::vector<std::pair<Real, Real> > debugtraceback_ [private]

Container holding the path of the traceback.

Real e_ [private]

Extension cost after a gap ist open.

Real gap_ [private]

Represent the gap cost for opening o closing a gap in the alignment.

Real mismatchscore_ [private]

Represent the cost of a mismath in the alignment.

std::vector<Real> scoredistribution_ [private]

Container holding the score of each cell(matchmatrix,insertmatrix, traceback).

Real threshold_ [private]

This is the minimum score for counting as a match(1-cutoffScore_).

OpenMS / TOPP release 1.10.0

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

MapAlignmentAlgorithmSpectrumAlignment Class Reference [MapAlignment]

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

MapAlignmentAlgorithmSpectrumAlignment Class Reference
[MapAlignment]