Edge Selection in a Noisy Graph by Concept Analysis – Application to a Genomic Network

Abstract : MicroRNAs (miRNAs) are small RNA molecules that bind messengerRNAs (mRNAs) to silence their expression. Understanding this regulation mech-anism requires the study of the miRNA/mRNA interaction network. State of theart methods for predicting interactions lead to a high level of false positive: theinteraction score distribution may be roughly described as a mixture of two over-lapping Gaussian laws that need to be discriminated with a threshold. In order tofurther improve the discrimination between true and false interactions, we presenta method that considers the structure of the underlying graph. We assume that thegraph is formed on a relatively simple structure of formal concepts (associated toregulation modules in the regulation mechanism). Specifically, the formal contexttopology of true edges is assumed to be less complex than in the case of a noisygraph including spurious interactions or missing interactions. Our approach consiststhus in selecting edges below an edge score threshold and applying a repair processon the graph, adding or deleting edges to decrease the global concept complexity.To validate our hypothesis and method, we have extracted parameters from a realbiological miRNA/mRNA network and used them to build random networks withfixed concept topology and true/false interaction ratio. Each repaired network canbe evaluated with a score balancing the number of edge changes and the conceptualadequacy in the spirit of the minimum description length principle.
Document type :
Book sections
Complete list of metadatas

Contributor : Jacques Nicolas <>
Submitted on : Wednesday, December 10, 2014 - 3:16:13 PM
Last modification on : Friday, November 16, 2018 - 1:38:37 AM


  • HAL Id : hal-01093337, version 1


Valentin Wucher, Denis Tagu, Jacques Nicolas. Edge Selection in a Noisy Graph by Concept Analysis – Application to a Genomic Network. Lausen, Berthold; Krolak-Schwerdt, Sabine; Böhmer, Matthias. Data Science, Learning by Latent Structures, and Knowledge Discovery, Springer, pp.550, 2014, 978-3-662-44982-0. ⟨hal-01093337⟩



Record views