Publication

An Exact Algorithm to Compute the Double-Cut-and-Join Distance for Genomes with Duplicate Genes

Related publications (49)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

New Genome Similarity Measures based on Conserved Gene Adjacencies

Bernard Moret, Shachi Shailesh Deshpande

Many important questions in molecular biology, evolution, and biomedicine can be addressed by comparative genomic approaches. One of the basic tasks when comparing genomes is the definition of measures of similarity (or dissimilarity) between two genomes, ...

Mary Ann Liebert2017

Efficient Linear Programming for Dense CRFs

Mathieu Salzmann

The fully connected conditional random field (CRF) with Gaussian pairwise potentials has proven popular and effective for multi-class semantic segmentation. While the energy of a dense CRF can be minimized accurately using a linear programming (LP) relaxat ...

2017

A Fast and Exact Algorithm for the Exemplar Breakpoint Distance

Bernard Moret, Mingfu Shao

A fundamental problem in comparative genomics is to compute the distance between two genomes. For two genomes without duplicate genes, we can easily compute a variety of distance measures in linear time, but the problem is NP-hard under most models when ge ...

Mary Ann Liebert, Inc2016

Group-Sparse Model Selection: Hardness and Relaxations

Volkan Cevher, Anastasios Kyrillidis, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. The main promise of these models is the recovery of ``interpretable" signals along with ...

Institute of Electrical and Electronics Engineers2016

A fast and exact algorithm for the exemplar breakpoint distance

Bernard Moret, Mingfu Shao

Springer2015

Models and Algorithms for Comparative Genomics

Mingfu Shao

The deluge of sequenced whole-genome data has motivated the study of comparative genomics, which provides global views on genome evolution, and also offers practical solutions in deciphering the functional roles of components of genomes. A fundamental comp ...

EPFL2015

Comparing genomes with rearrangements and segmental duplications

Bernard Moret, Mingfu Shao

Motivation: Large-scale evolutionary events such as genomic rearrange. ments and segmental duplications form an important part of the evolution of genomes and are widely studied from both biological and computational perspectives. A basic computational pro ...

Oxford University Press2015

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...

IEEE Computer Society2015

Whole genome duplications and recruitment of ecologically relevant genes in alpine Mustards

Stéphane Joost, Kevin Leempoel, Béatrice North

Polyploid taxa represent excellent models to address the underpinnings of genome evolution and the building up of new species in heterogeneous environments. Here, we present an overview of recent works in the alpine Biscutella laevigata autopolyploid compl ...

2015

Method and device for proving his identity

Serge Vaudenay, Ioana Cristina Carlson

The invention is related to a method allowing a prover holding a secret key (x) to prove its identity to a verifier and to prove to this verifier that he is within a predetermined distance of this verifier, said method comprising an initialization phase du ...

2015