Publications related to A fast and exact algorithm for the exemplar breakpoint distance

Ancestral genome reconstruction enhances transposable element annotation by identifying degenerate integrants

Didier Trono, Evaristo Jose Planet Letschert, Wayo Matsushima

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, Ziang Li

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 Portfolio2024

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

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

Statistical learning quantifies transposable element-mediated cis-regulation

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

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

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

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, Adélaïde Alice Mohr, Stefano Zamuner, Daniel Maria Busiello

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

Giovanni Ciriello, 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

Worst-Case Delay Analysis of Time-Sensitive Networks with Network Calculus

Seyed Mohammadhossein Tabatabaee

Time-sensitive networks, as in the context of IEEE Time-Sensitive Networking (TSN) and IETF Deterministic Networking (DetNet), offer deterministic services with guaranteed bounded latency in order to support safety-critical applications. In this thesis, we ...

EPFL2023

Landscapes of DNA Mechanics and Genomes

Thomas Antonin Zwahlen

The local physical properties - such as shape and flexibility - of the DNA double-helix is today widely believed to be influenced by nucleic acid sequence in a non-trivial way. Furthermore, there is strong evidence that these properties play a role in many ...

EPFL2023

Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Serge Vaudenay, Bénédikt Minh Dang Tran

Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption construc ...

Springer2023

Genetic features and genomic targets of human KRAB-zinc finger proteins

Didier Trono, Priscilla Turelli, Julien Léonard Duc, Sandra Eloise Kjeldsen, Jonas Caspar De Tribolet-Hardy, Bara Khubieh, Jacques Fellay, Michaël Imbeault, Alexandre Coudray, Cyril David Son-Tuyên Pulver, Evaristo Jose Planet Letschert, Christian Axel Wandall Thorball, Romain Forey

Krüppel-associated box (KRAB) domain-containing zinc finger proteins (KZFPs) are one of the largest groups of transcription factors encoded by tetrapods, with 378 members in human alone. KZFP genes are often grouped in clusters reflecting amplification by ...

2023