Pools features from multiple maps into a single 2D kd-tree on (RT, m/z) for fast range queries. More...

#include <OpenMS/ANALYSIS/QUANTITATION/KDTreeFeatureMaps.h>

Inheritance diagram for KDTreeFeatureMaps:

Collaboration diagram for KDTreeFeatureMaps:

Public Types
typedef KDTree::KDTree< 2, KDTreeFeatureNode >	FeatureKDTree
	2D kd-tree on (RT, m/z) holding KDTreeFeatureNode entries

Public Member Functions
	KDTreeFeatureMaps ()
	Default constructor; creates an empty container with no features and zero maps.

template<typename MapType >
	KDTreeFeatureMaps (const std::vector< MapType > &maps, const Param &param)
	Construct from a list of feature maps and a parameter set.

	~KDTreeFeatureMaps () override
	Destructor (does not delete the wrapped features)

template<typename MapType >
void	addMaps (const std::vector< MapType > &maps)
	Insert all features from `maps` and balance the kd-tree.

void	addFeature (Size mt_map_index, const BaseFeature *feature)
	Insert a single feature into the kd-tree.

const BaseFeature *	feature (Size i) const
	Pointer to the feature with global index `i`.

double	rt (Size i) const
	(Possibly transformed) retention time of feature `i`

double	mz (Size i) const
	m/z of feature `i` (read through the wrapped BaseFeature)

float	intensity (Size i) const
	Intensity of feature `i` (read through the wrapped BaseFeature)

Int	charge (Size i) const
	Charge of feature `i` (read through the wrapped BaseFeature)

Size	mapIndex (Size i) const
	Index of the source map that feature `i` was added with.

Size	size () const
	Number of features stored (across all maps)

Size	treeSize () const
	Number of points currently in the kd-tree.

Size	numMaps () const
	Number of source maps recorded in the most recent addMaps() call.

void	clear ()
	Discard all stored features and clear the kd-tree (does not delete the wrapped features)

void	optimizeTree ()
	Re-balance the kd-tree after incremental inserts.

void	getNeighborhood (Size index, std::vector< Size > &result_indices, double rt_tol, double mz_tol, bool mz_ppm, bool include_features_from_same_map=false, double max_pairwise_log_fc=-1.0) const
	Collect indices of all features compatible with the feature at `index`.

void	queryRegion (double rt_low, double rt_high, double mz_low, double mz_high, std::vector< Size > &result_indices, Size ignored_map_index=std::numeric_limits< Size >::max()) const
	Range query on the kd-tree: collect indices of features within the given (RT, m/z) rectangle.

void	applyTransformations (const std::vector< TransformationModelLowess * > &trafos)
	Apply a per-map RT transformation to the cached retention times.

Public Member Functions inherited from DefaultParamHandler
	DefaultParamHandler (const std::string &name)
	Constructor with name that is displayed in error messages.

	DefaultParamHandler (const DefaultParamHandler &rhs)
	Copy constructor.

virtual	~DefaultParamHandler ()
	Destructor.

DefaultParamHandler &	operator= (const DefaultParamHandler &rhs)
	Assignment operator.

virtual bool	operator== (const DefaultParamHandler &rhs) const
	Equality operator.

void	setParameters (const Param &param)
	Sets the parameters.

const Param &	getParameters () const
	Non-mutable access to the parameters.

const Param &	getDefaults () const
	Non-mutable access to the default parameters.

const std::string &	getName () const
	Non-mutable access to the name.

void	setName (const std::string &name)
	Mutable access to the name.

const std::vector< std::string > &	getSubsections () const
	Non-mutable access to the registered subsections.

Protected Member Functions
void	updateMembers_ () override
	This method is used to update extra member variables at the end of the setParameters() method.

Protected Member Functions inherited from DefaultParamHandler
void	defaultsToParam_ ()
	Updates the parameters after the defaults have been set in the constructor.

Protected Attributes
std::vector< const BaseFeature * >	features_
	Feature data (pointers owned by the caller)

std::vector< Size >	map_index_
	Map of origin for each feature (parallel to `features_`)

std::vector< double >	rt_
	(Potentially transformed) retention times, parallel to `features_`

Size	num_maps_
	Number of source maps (set by addMaps())

FeatureKDTree	kd_tree_
	2D kd-tree on features from all input maps (queried in (RT, m/z))

Protected Attributes inherited from DefaultParamHandler
Param	param_
	Container for current parameters.

Param	defaults_
	Container for default parameters. This member should be filled in the constructor of derived classes!

std::vector< std::string >	subsections_
	Container for registered subsections. This member should be filled in the constructor of derived classes!

std::string	error_name_
	Name that is displayed in error messages during the parameter checking.

bool	check_defaults_
	If this member is set to false no checking if parameters in done;.

bool	warn_empty_defaults_
	If this member is set to false no warning is emitted when defaults are empty;.

Additional Inherited Members
Static Public Member Functions inherited from DefaultParamHandler
static void	writeParametersToMetaValues (const Param &write_this, MetaInfoInterface &write_here, const std::string &key_prefix="")
	Writes all parameters to meta values.

Detailed Description

Pools features from multiple maps into a single 2D kd-tree on (RT, m/z) for fast range queries.

The class stores raw pointers to BaseFeature instances supplied by the caller (no copy is made), along with the map of origin for each feature. A balanced kd-tree over the (RT, m/z) plane is built so that subsequent neighbourhood searches across maps run in \(\mathcal{O}(\log n + k)\) instead of a linear scan over all features.

Typical use:

KD-tree based map alignment (see MapAlignmentAlgorithmKD), where pairwise RT correspondences between maps are collected from features that fall within an RT/m/z tolerance window.
KD-tree based feature grouping (see FeatureGroupingAlgorithmKD), where consensus features are built by clustering compatible features from different maps.

RT values are stored separately from the wrapped features so that an alignment transformation can later be applied via applyTransformations() without modifying the original features. m/z, intensity, and charge are always read through the feature pointer and reflect the current state of the underlying feature.

Ownership: the caller retains ownership of the wrapped BaseFeature objects. The kd-tree only stores pointers, so the wrapped features must outlive this object.

Note: This class derives from DefaultParamHandler but disables the parameter check (check_defaults_ is set to false), so subclasses or callers may pass arbitrary Param entries through the constructor without triggering a check against a fixed default schema.

Member Typedef Documentation

◆ FeatureKDTree

typedef KDTree::KDTree<2,KDTreeFeatureNode> FeatureKDTree

2D kd-tree on (RT, m/z) holding KDTreeFeatureNode entries

Constructor & Destructor Documentation

◆ KDTreeFeatureMaps() [1/2]

KDTreeFeatureMaps ( )

inline

Default constructor; creates an empty container with no features and zero maps.

◆ KDTreeFeatureMaps() [2/2]

template<typename MapType >

KDTreeFeatureMaps	(	const std::vector< MapType > &	maps,
		const Param &	param
	)

inline

Construct from a list of feature maps and a parameter set.

Equivalent to default-constructing, calling setParameters(param), and addMaps(maps).

Parameters

[in]	maps	Container of feature-map-like objects (each iterable over BaseFeature subclasses). All features from every map are inserted into the kd-tree.
[in]	param	Parameter set forwarded to setParameters().

◆ ~KDTreeFeatureMaps()

~KDTreeFeatureMaps ( )

inlineoverride

Destructor (does not delete the wrapped features)

Member Function Documentation

◆ addFeature()

void addFeature	(	Size	mt_map_index,
		const BaseFeature *	feature
	)

Insert a single feature into the kd-tree.

The feature's RT is cached internally (so it can be re-mapped by applyTransformations() later); m/z, intensity, and charge are always read through feature on demand.

After many incremental inserts call optimizeTree() to re-balance the kd-tree.

Parameters

[in]	mt_map_index	Index of the source map this feature belongs to.
[in]	feature	Pointer to the feature to add (must outlive this object).

◆ addMaps()

template<typename MapType >

void addMaps ( const std::vector< MapType > & maps )

inline

Insert all features from maps and balance the kd-tree.

Stores maps.size() as the number of input maps. Each feature is added via addFeature() using its map index, then optimizeTree() is called to balance the tree.

Parameters

[in] maps Container of feature-map-like objects (each iterable over BaseFeature subclasses). Pointers to the contained features are stored, so the maps must outlive this object.

References MSExperiment::begin(), and MSExperiment::end().

◆ applyTransformations()

void applyTransformations ( const std::vector< TransformationModelLowess * > & trafos )

Apply a per-map RT transformation to the cached retention times.

For each feature i, replaces the cached RT by trafos[mapIndex(i)]->evaluate(feature(i)->getRT()). The underlying BaseFeature objects are not modified.

Parameters

[in] trafos One transformation per source map. Size must equal numMaps().

◆ charge()

Int charge ( Size i ) const

Charge of feature i (read through the wrapped BaseFeature)

◆ clear()

void clear ( )

Discard all stored features and clear the kd-tree (does not delete the wrapped features)

◆ feature()

const BaseFeature * feature ( Size i ) const

Pointer to the feature with global index i.

◆ getNeighborhood()

void getNeighborhood	(	Size	index,
		std::vector< Size > &	result_indices,
		double	rt_tol,
		double	mz_tol,
		bool	mz_ppm,
		bool	include_features_from_same_map = `false`,
		double	max_pairwise_log_fc = `-1.0`
	)		const

Collect indices of all features compatible with the feature at index.

Performs a queryRegion() with an RT/m/z tolerance window centred on the feature at index. By default, features from the same source map as index are excluded (typical setting for cross-map matching). If max_pairwise_log_fc is non-negative, each candidate is additionally filtered by |log10(I_candidate / I_index)| <= max_pairwise_log_fc; candidates whose log fold change is NaN or +inf (e.g. due to zero/negative intensities) are silently dropped.

Results are appended to result_indices (the existing contents are preserved).

Parameters

[in]	index	Global index of the query feature.
[in,out]	result_indices	Indices of neighbouring features are appended here.
[in]	rt_tol	Tolerance on retention time (absolute, same unit as RT).
[in]	mz_tol	Tolerance on m/z (interpreted as ppm if `mz_ppm` is true, otherwise as Th).
[in]	mz_ppm	If true, `mz_tol` is treated as parts-per-million.
[in]	include_features_from_same_map	If true, features from the same source map as `index` are kept too.
[in]	max_pairwise_log_fc	If >= 0, filter on absolute log10 intensity ratio; if < 0 (default), no intensity filter is applied.

◆ intensity()

float intensity ( Size i ) const

Intensity of feature i (read through the wrapped BaseFeature)

◆ mapIndex()

Size mapIndex ( Size i ) const

Index of the source map that feature i was added with.

◆ mz()

double mz ( Size i ) const

m/z of feature i (read through the wrapped BaseFeature)

◆ numMaps()

Size numMaps ( ) const

Number of source maps recorded in the most recent addMaps() call.

◆ optimizeTree()

void optimizeTree ( )

Re-balance the kd-tree after incremental inserts.

◆ queryRegion()

void queryRegion	(	double	rt_low,
		double	rt_high,
		double	mz_low,
		double	mz_high,
		std::vector< Size > &	result_indices,
		Size	ignored_map_index = `std::numeric_limits< Size >::max()`
	)		const

Range query on the kd-tree: collect indices of features within the given (RT, m/z) rectangle.

Replaces (does not append to) result_indices.

Parameters

[in]	rt_low	Lower bound on RT.
[in]	rt_high	Upper bound on RT.
[in]	mz_low	Lower bound on m/z.
[in]	mz_high	Upper bound on m/z.
[out]	result_indices	Indices of features inside the rectangle (cleared first, then filled).
[in]	ignored_map_index	If different from std::numeric_limits<Size>::max() (the default), features whose map index equals `ignored_map_index` are excluded from the result.

◆ rt()

double rt ( Size i ) const

(Possibly transformed) retention time of feature i

◆ size()

Size size ( ) const

Number of features stored (across all maps)

◆ treeSize()

Size treeSize ( ) const

Number of points currently in the kd-tree.

◆ updateMembers_()

void updateMembers_ ( )

overrideprotectedvirtual

This method is used to update extra member variables at the end of the setParameters() method.

Also call it at the end of the derived classes' copy constructor and assignment operator.

The default implementation is empty.

Reimplemented from DefaultParamHandler.

Member Data Documentation

◆ features_

std::vector<const BaseFeature*> features_

protected

Feature data (pointers owned by the caller)

◆ kd_tree_

FeatureKDTree kd_tree_

protected

2D kd-tree on features from all input maps (queried in (RT, m/z))

◆ map_index_

std::vector<Size> map_index_

protected

Map of origin for each feature (parallel to features_)

◆ num_maps_

Size num_maps_

protected

Number of source maps (set by addMaps())

◆ rt_

std::vector<double> rt_

protected

(Potentially transformed) retention times, parallel to features_

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ FeatureKDTree

Constructor & Destructor Documentation

◆ KDTreeFeatureMaps() [1/2]

◆ KDTreeFeatureMaps() [2/2]

◆ ~KDTreeFeatureMaps()

Member Function Documentation

◆ addFeature()

◆ addMaps()

◆ applyTransformations()

◆ charge()

◆ clear()

◆ feature()

◆ getNeighborhood()

◆ intensity()

◆ mapIndex()

◆ mz()

◆ numMaps()

◆ optimizeTree()

◆ queryRegion()

◆ rt()

◆ size()

◆ treeSize()

◆ updateMembers_()

Member Data Documentation

◆ features_

◆ kd_tree_

◆ map_index_

◆ num_maps_

◆ rt_