Publications associées à A Fast and Exact Algorithm for the Exemplar Breakpoint Distance

Publications associées (32)

Genome-wide allele-specific expression in multi-tissue samples from healthy male baboons reveals the transcriptional complexity of mammals

Allele-specific expression (ASE) is pivotal in understanding the genetic underpinnings of phenotypic variation within species, differences in disease susceptibility, and responses to environmental factors. We processed 11 different tissue types collected f ...

2025

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit

Byzantine agreement allows n processes to decide on a common value, in spite of arbitrary failures. The seminal Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement exchanges Ω(n2) bits. In synchronous networks, with a known u ...

Society for Industrial and Applied Mathematics2025

Ancestral genome reconstruction enhances transposable element annotation by identifying degenerate integrants

Wayo Matsushima, Didier Trono, Evaristo Jose Planet Letschert

Growing evidence indicates that transposable elements (TEs) play important roles in evolution by providing genomes with coding and non-coding sequences. Identification of TE-derived functional elements, however, has relied on TE annotations in individual s ...

2024

Toward universal cell embeddings: integrating single-cell RNA-seq datasets across species with SATURN

Maria Brbic

Analysis of single-cell datasets generated from diverse organisms offers unprecedented opportunities to unravel fundamental evolutionary processes of conservation and diversification of cell types. However, interspecies genomic differences limit the joint ...

Nature Publishing Group2024

The cost of adaptability: resource availability constrains functional stability under pulsed disturbances

Hannes Markus Peter

Global change exposes ecosystems to changes in the frequency, magnitude, and concomitancy of disturbances, which impact the composition and functioning of these systems. Here, we experimentally evaluate the effects of salinity disturbances and eutrophicati ...

Amer Soc Microbiology2024

The microbial genomics of glacier-fed streams: adaptations to an extreme ecosystem

Massimo Bourquin

Glacier-fed streams are the cold, ultra-oligotrophic, and unstable streams that are fed by glacial meltwater. Despite these extreme conditions, they harbour a diverse and abundant microbial diversity that develops into biofilms, covering the boulders and s ...

EPFL2024

A ride time-oriented scheduling algorithm for dial-a-ride problems

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Pergamon-Elsevier Science Ltd2024

Single-mitosis dissection of acute and chronic DNA mutagenesis and repair

Christina Ernst

How chronic mutational processes and punctuated bursts of DNA damage drive evolution of the cancer genome is poorly understood. Here, we demonstrate a strategy to disentangle and quantify distinct mechanisms underlying genome evolution in single cells, dur ...

Nature Portfolio2024

Reconstruction and analysis of genome-scale metabolic networks in single organisms and microbial communities

Evangelia Vagena

Microorganisms are a key component in the chain of life. They are essential for agriculture, produce a large proportion of oxygen, and play a central role in the cycle of elements. Microorganisms are widely used in the production of food and alcoholic beve ...

EPFL2024

Genome sequences of Vibrio cholerae strains isolated in the DRC between 2009 and 2012

Melanie Blokesch, Sandrine Stutzmann, Natalia Carolina Drebes Dorr, Alexandre Lemopoulos

Vibrio cholerae has caused seven cholera pandemics in the past two centuries. The seventh and ongoing pandemic has been particularly severe on the African continent. Here, we report long read-based genome sequences of six V. cholerae strains isolated in th ...

2024

Succinct ordering and aggregation constraints in algebraic array theories

Viktor Kuncak, Rodrigo Raya

We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...

Elsevier Science Inc2024

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Paul Scharnhorst

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

EPFL2024

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Maryam Kamgarpour, Tony Alan Wood

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

2023

Wide-scale identification of novel/eliminated genes responsible for evolutionary transformations

Daria Korotkova

BackgroundIt is generally accepted that most evolutionary transformations at the phenotype level are associated either with rearrangements of genomic regulatory elements, which control the activity of gene networks, or with changes in the amino acid conten ...

2023

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Statistical learning quantifies transposable element-mediated cis-regulation

Didier Trono, Julien Léonard Duc, Evaristo Jose Planet Letschert, Alexandre Coudray, Cyril David Son-Tuyên Pulver, Raphaël Gérard Théodore Michel Marie de Deloÿe et Fourcade de Fondeville, Julien Paul André Pontis, Delphine Yvette L Grun, Shaoline Sheppard

Background: Transposable elements (TEs) have colonized the genomes of most metazoans, and many TE-embedded sequences function as cis-regulatory elements (CREs) for genes involved in a wide range of biological processes from early embryo- genesis to innate ...

2023

Modeling, analysis, and design of complex biological networks

Mohammadomid Oftadeh

Automating experimental procedures has resulted in an unprecedented increase in the volume of generated data, which, in turn, has caused an accumulation of unprocessed data. As a result, the need to develop tools to analyze data systematically has been ris ...

EPFL2023

Individual and combined benefits of different nonequilibrium proofreading mechanisms

Paolo De Los Rios, Daniel Maria Busiello, Stefano Zamuner, Adélaïde Alice Mohr

Genome duplication, transcription, and translation are among many crucial cellular processes that need to be performed with high fidelity. However, those extremely low error rates cannot be explained with simple equilibrium thermodynamic considerations. Th ...

Amer Physical Soc2023

Cis-regulatory effect of HPV integration is constrained by host chromatin architecture in cervical cancers

Daniele Tavernari

Human papillomavirus (HPV) infections are the primary drivers of cervical cancers, and often HPV DNA gets integrated into the host genome. Although the oncogenic impact of HPV encoded genes is relatively well known, the cis-regulatory effect of integrated ...

Wiley2023