title: Reactome pathway analysis: a high-performance in-memory approach.
abstract: BACKGROUND
  Reactome aims to provide bioinformatics tools for visualisation, interpretation and analysis of pathway knowledge to support basic research, genome analysis, modelling, systems biology and education. Pathway analysis methods have a broad range of applications in physiological and biomedical research; one of the main problems, from the analysis methods performance point of view, is the constantly increasing size of the data samples.
  
  
  RESULTS
  Here, we present a new high-performance in-memory implementation of the well-established over-representation analysis method. To achieve the target, the over-representation analysis method is divided in four different steps and, for each of them, specific data structures are used to improve performance and minimise the memory footprint. The first step, finding out whether an identifier in the user's sample corresponds to an entity in Reactome, is addressed using a radix tree as a lookup table. The second step, modelling the proteins, chemicals, their orthologous in other species and their composition in complexes and sets, is addressed with a graph. The third and fourth steps, that aggregate the results and calculate the statistics, are solved with a double-linked tree.
  
  
  CONCLUSIONS
  Through the use of highly optimised, in-memory data structures and algorithms, Reactome has achieved a stable, high performance pathway analysis service, enabling the analysis of genome-wide datasets within seconds, allowing interactive exploration and analysis of high throughput data. The proposed pathway analysis approach is available in the Reactome production web site either via the AnalysisService for programmatic access or the user submission interface integrated into the PathwayBrowser. Reactome is an open data and open source project and all of its source code, including the one described here, is available in the AnalysisTools repository in the Reactome GitHub ( https://github.com/reactome/ ).
authors.affiliation: European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK.|Open Targets, Wellcome Genome Campus, Hinxton, UK.
authors.forename: Antonio
authors.initials: A
authors.lastname: Fabregat
authors.affiliation: European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK.
authors.forename: Konstantinos
authors.initials: K
authors.lastname: Sidiropoulos
authors.affiliation: European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK.
authors.forename: Guilherme
authors.initials: G
authors.lastname: Viteri
authors.affiliation: European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK.
authors.forename: Oscar
authors.initials: O
authors.lastname: Forner
authors.affiliation: Fundación Investigación INCLIVA, Universitat de València, Valencia, Spain.|Instituto de Medicina Genomica, Valencia, Spain.
authors.forename: Pablo
authors.initials: P
authors.lastname: Marin-Garcia
authors.affiliation: Escuela Técnica Superior de Ingenierías, Universitat de València, Valencia, Spain.|Institute for Integrative Systems Biology (I2SysBio), Universitat de València-CSIC, Paterna, Valencia, Spain.
authors.forename: Vicente
authors.initials: V
authors.lastname: Arnau
authors.affiliation: NYU Langone Medical Center, New York, USA.
authors.forename: Peter
authors.initials: P
authors.lastname: D'Eustachio
authors.affiliation: Ontario Institute for Cancer Research, Toronto, Canada.|Department of Molecular Genetics, University of Toronto, Toronto, Canada.
authors.forename: Lincoln
authors.initials: L
authors.lastname: Stein
authors.affiliation: European Molecular Biology Laboratory, European Bioinformatics Institute (EMBL-EBI), Wellcome Genome Campus, Hinxton, UK. hhe@ebi.ac.uk.|State Key Laboratory of Proteomics, Beijing Proteome Research Center, Beijing Institute of Radiation Medicine; National Center for Protein Sciences, 102206, Beijing, China. hhe@ebi.ac.uk.
authors.forename: Henning
authors.initials: H
authors.lastname: Hermjakob
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D016208:Databases, Factual; D006801:Humans; D009696:Nucleic Acids / Q000378:metabolism; D011506:Proteins / Q000378:metabolism; D012984:Software
chemical_list: D009696:Nucleic Acids; D011506:Proteins
keywords: Data structures; Over-representation analysis; Pathway analysis