Loading...
Searching...
No Matches
spectree.h
Go to the documentation of this file.
/**
* \file pappsomspp/processing/spectree/spectree.h
* \date 11/12/2023
* \author Olivier Langella
* \brief Matthieu David's SpecTree structure
*
* C++ implementation of algorithm already described in :
* 1. David, M., Fertin, G., Rogniaux, H. & Tessier, D. SpecOMS: A Full Open
* Modification Search Method Performing All-to-All Spectra Comparisons within
* Minutes. J. Proteome Res. 16, 3030–3038 (2017).
*
* https://www.theses.fr/2019NANT4092
*/
/*
* SpecTree
* Copyright (C) 2023 Olivier Langella
* <olivier.langella@universite-paris-saclay.fr>
*
* This program is free software: you can redistribute ipetide to spectrum
* alignmentt and/or modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*
*/
#pragma once
#include "bucketclustering.h"
#include <cstdlib>
#include <QString>
#include "../uimonitor/uimonitorinterface.h"
#include "specxtractinterface.h"
namespace pappso
{
namespace spectree
{
/**
* @todo write docs
*/
class PMSPP_LIB_DECL SpecTree
{
public:
/**
* Build a SpecTree with BucketClustering
*/
SpecTree(const BucketClustering &bucket_clustering);
/**
* Destructor
*/
virtual ~SpecTree();
QString toString() const;
/** @brief get the adress map of sepctrum index and their first node index
*
* convenience function intended for testing
* @return vector of the size of max spectrum index containing list of first
* node index
*/
const std::vector<std::size_t> &getSpectrumFirstNodeIndex() const;
/**
* Extract all similarities above a threshold value between all spectra from
* the deepest one up to the given limit using the predefined extraction
* algorithm. The results are stored in the mentionned reporter.
*
* Performs the extraction of the similarities above a given threshold for all
* spectra between the deepest one and a given index in the transversal
* accessor. The extracted pairs are feed to a shifter to try to improve the
* spectrum identification. Afterwards, the retained results are written to
* the given reporter. This extraction step represents most of SpecOMS
* execution time. Note: This function heavily evolved through the development
* process to match new needs, it became clumsy and heavy. A clean refactor
* might be appropriate.
*
* @param monitor progress monitor, indicates progression in spectree
* @param spec_xtract report results of similarities to the user (write in
* file or consolidate)
* @param cart_id_range_max The position in the transversal accessor from
* which the similarities must be reported (item cart id)
* @param cart_id_range_min The position in the transversal accessor up to
* which the similarities must be reported (item cart id)
* @param target_cart_id_max targeted item cart id relevant for comparison
* @param target_cart_id_min targeted item cart id relevant for comparison
*/
void xtract(UiMonitorInterface &monitor,
SpecXtractInterface &spec_xtract,
std::size_t minimum_count,
std::size_t cart_id_range_max,
std::size_t cart_id_range_min,
std::size_t target_cart_id_max,
std::size_t target_cart_id_min) const;
/** @brief get the number of common component for a pair of spectrum
* @param spectrum_a_index the first spectrum index
* @param spectrum_b_index the second spectrum index
* @return integer the number of common component between spectrum
*/
std::size_t extractSpectrumPairSimilarityCount(std::size_t spectrum_a_index,
std::size_t spectrum_b_index) const;
private:
static constexpr std::size_t index_not_defined{std::numeric_limits<std::size_t>::max()};
struct SpecTreeNode
{
std::size_t parentIndex = index_not_defined;
std::size_t nextIndex = index_not_defined;
std::size_t value;
std::size_t count;
};
struct MapSimilarityCountElement
{
std::size_t lastWitness = index_not_defined;
std::size_t count = 0;
bool aboveThreshold = false;
};
struct MapSimilarityCount
{
std::vector<std::size_t> keys;
std::vector<std::size_t> aboveThreshold;
std::vector<MapSimilarityCountElement> map_id_count;
};
void addNewNode(const SpecTreeNode &node);
void manageSideAccess(std::vector<std::size_t> &spectrumLastNodeIndex);
void walkBackInBranchFromNode(const SpecTree::SpecTreeNode &start_node,
MapSimilarityCount &map_count,
std::size_t minimum_count,
std::size_t target_cart_id_max,
std::size_t target_cart_id_min) const;
std::size_t walkBackInBranchFromNodeToTarget(const SpecTree::SpecTreeNode &start_node,
std::size_t spectrum_index_target) const;
/** @brief get a map of similarities for a given spectrum index
*
* this function can only retrieve spectrum index map lower than the spectrum
* index given in the parameters (check original publication for details)
*
* @param spectrum_index the spectrum index to retrieve similarities
* @param spectrum_index_lower_limit lower spectrum index limit to save CPU
* (do not use it if you want a full similarity map)
* @return map of spectrum_index keys containing the corresponding count value
* (similarity) for the targeted spectrum index
*/
void extractSpectrumSimilarityCount(MapSimilarityCount &map_count,
std::size_t minimum_count,
std::size_t spectrum_index,
std::size_t target_cart_id_max,
std::size_t target_cart_id_min) const;
private:
std::vector<SpecTreeNode> m_nodeList;
std::vector<std::size_t> m_spectrumFirstNodeIndex;
};
} // namespace spectree
} // namespace pappso
bucketclustering.h
pappso::UiMonitorInterface
Definition uimonitorinterface.h:50
pappso::spectree::BucketClustering
Definition bucketclustering.h:56
pappso::spectree::SpecTree::m_nodeList
std::vector< SpecTreeNode > m_nodeList
Definition spectree.h:169
pappso::spectree::SpecTree::walkBackInBranchFromNodeToTarget
std::size_t walkBackInBranchFromNodeToTarget(const SpecTree::SpecTreeNode &start_node, std::size_t spectrum_index_target) const
Definition spectree.cpp:361
pappso::spectree::SpecTree::getSpectrumFirstNodeIndex
const std::vector< std::size_t > & getSpectrumFirstNodeIndex() const
get the adress map of sepctrum index and their first node index
Definition spectree.cpp:219
pappso::spectree::SpecTree::index_not_defined
static constexpr std::size_t index_not_defined
Definition spectree.h:117
pappso::spectree::SpecTree::walkBackInBranchFromNode
void walkBackInBranchFromNode(const SpecTree::SpecTreeNode &start_node, MapSimilarityCount &map_count, std::size_t minimum_count, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
Definition spectree.cpp:307
pappso::spectree::SpecTree::m_spectrumFirstNodeIndex
std::vector< std::size_t > m_spectrumFirstNodeIndex
Definition spectree.h:170
pappso::spectree::SpecTree::toString
QString toString() const
Definition spectree.cpp:194
pappso::spectree::SpecTree::extractSpectrumPairSimilarityCount
std::size_t extractSpectrumPairSimilarityCount(std::size_t spectrum_a_index, std::size_t spectrum_b_index) const
get the number of common component for a pair of spectrum
Definition spectree.cpp:418
pappso::spectree::SpecTree::manageSideAccess
void manageSideAccess(std::vector< std::size_t > &spectrumLastNodeIndex)
Definition spectree.cpp:170
pappso::spectree::SpecTree::addNewNode
void addNewNode(const SpecTreeNode &node)
Definition spectree.cpp:164
pappso::spectree::SpecTree::extractSpectrumSimilarityCount
void extractSpectrumSimilarityCount(MapSimilarityCount &map_count, std::size_t minimum_count, std::size_t spectrum_index, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
get a map of similarities for a given spectrum index
Definition spectree.cpp:393
pappso::spectree::SpecTree::SpecTree
SpecTree(const BucketClustering &bucket_clustering)
Definition spectree.cpp:48
pappso::spectree::SpecTree::xtract
void xtract(UiMonitorInterface &monitor, SpecXtractInterface &spec_xtract, std::size_t minimum_count, std::size_t cart_id_range_max, std::size_t cart_id_range_min, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
Definition spectree.cpp:225
pappso::spectree::SpecXtractInterface
yield similarities between pairs of ItemCart
Definition specxtractinterface.h:53
PMSPP_LIB_DECL
#define PMSPP_LIB_DECL
Definition export-import-config.h:14
pappso::spectree
Definition bucket.cpp:43
pappso
tries to keep as much as possible monoisotopes, removing any possible C13 peaks and changes multichar...
Definition aa.cpp:39
specxtractinterface.h
pappso::spectree::SpecTree::MapSimilarityCountElement
Definition spectree.h:127
pappso::spectree::SpecTree::MapSimilarityCountElement::lastWitness
std::size_t lastWitness
Definition spectree.h:128
pappso::spectree::SpecTree::MapSimilarityCountElement::aboveThreshold
bool aboveThreshold
Definition spectree.h:130
pappso::spectree::SpecTree::MapSimilarityCountElement::count
std::size_t count
Definition spectree.h:129
pappso::spectree::SpecTree::MapSimilarityCount
Definition spectree.h:133
pappso::spectree::SpecTree::MapSimilarityCount::map_id_count
std::vector< MapSimilarityCountElement > map_id_count
Definition spectree.h:136
pappso::spectree::SpecTree::MapSimilarityCount::aboveThreshold
std::vector< std::size_t > aboveThreshold
Definition spectree.h:135
pappso::spectree::SpecTree::MapSimilarityCount::keys
std::vector< std::size_t > keys
Definition spectree.h:134
pappso::spectree::SpecTree::SpecTreeNode
Definition spectree.h:119
pappso::spectree::SpecTree::SpecTreeNode::count
std::size_t count
Definition spectree.h:123
pappso::spectree::SpecTree::SpecTreeNode::parentIndex
std::size_t parentIndex
Definition spectree.h:120
pappso::spectree::SpecTree::SpecTreeNode::nextIndex
std::size_t nextIndex
Definition spectree.h:121
pappso::spectree::SpecTree::SpecTreeNode::value
std::size_t value
Definition spectree.h:122
uimonitorinterface.h