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