Partitionnement optimal et élagage fonctionnel pour la détection de ruptures multiples. Application à des données d’Hybridation Génomique Comparative CGH
Résumé
We consider the problem of detecting multiple change-points in a signal of size n corrupted by a Gaussian noise. We aim at detecting the change-points that maximize the log-likelihood or minimize the quadratic loss. We illustrate this problem on real Comparative Genomic Hybridization data where n is typically larger than 105 or 106. We describe an algorithm, fpop, which combines optimal partitioning and function pruning. This algorithm is exact and fast. We demonstrate that the pruning of fpop is at least as efficient as the pruning of two recently proposed algorithms PELT and pDPA. We empirically show on simulated and real data that the runtime of fpop is faster than PELT and pDPA.
Nous nous intéressons à la détection de ruptures multiples dans un signal de taille $n$ corrompu par un bruit gaussien. Nous cherchons à identifier les ruptures qui maximisent la log-vraisemblance ou minimisent l'erreur quadratique. Nous illustrons ce problème sur des données d'hybridation génomique comparative où $n$ est de l'ordre du million. Nous présentons un algorithme, fpop, intégrant des techniques d'élagage fonctionnel à l'algorithme de partitionnement optimal. Cet algorithme est exact et rapide. Nous démontrons que élagage opéré par fpop est au moins aussi efficace que celui de deux algorithmes récemment proposés PELT et pDPA. En pratique, sur des données simulées et réelles, nous montrons que fpop est plus rapide que PELT et pDPA.