Robust Seriation and Applications to Cancer Genomics
TITLE: Robust Seriation and Applications to Cancer Genomics.
AUTHORS: A. Recanati, N. Servant, J.P. Vert, A. d'Aspremont
ABSTRACT: The seriation problem seeks to reorder a set of elements given pairwise similarity information, so that elements with higher similarity are closer in the resulting sequence. When a global ordering consistent with the similarity information exists, an exact spectral solution recovers it in the noiseless case and seriation is equivalent to the combinatorial 2SUM problem over permutations, for which several relaxations have been derived. However, in applications such as DNA assembly, similarity values are often heavily corrupted, and the solution of 2SUM may no longer yield an approximate serial structure on the elements. We introduce the robust seriation problem and show that it is equivalent to a modified 2SUM problem for a class of similarity matrices modeling those observed in DNA assembly. We explore several relaxations of this modified 2SUM problem and compare them empirically on both synthetic matrices and real DNA data. We then introduce the problem of seriation with duplications, which is a generalization of Seriation motivated by applications to cancer genome reconstruction. We propose an algorithm involving robust seriation to solve it, and present preliminary results on synthetic data sets.
STATUS: Submitted
ArXiv PREPRINT: 1806.00664
