Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

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 ...

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 ...

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 ...

Translation elongation plays an important role in regulating protein concentrations in the cell, and dysregulation of this process has been linked to several human diseases. In this study, we use data from ribo-seq experiments to model ribosome densities, ...

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 ...

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...

In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation functio ...

Graph machine learning offers a powerful framework with natural applications in scientific fields such as chemistry, biology and material sciences. By representing data as a graph, we encode the prior knowledge that the data is composed of a set of entiti ...

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using ...

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 ...

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 ...

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 ...

The arms race between viruses and their hosts shaped the evolutionary history and the genome composition of both parties. Restriction factors are the first-line antiviral effectors encoded by the host genomes and are often conserved through evolution to pr ...

DNA-binding proteins physically interact with the DNA and directly affect genomic functions. The eukaryotic genome is compacted into chromatin, limiting the DNA access to nuclear factors. In this Ph.D. thesis, I explored the dynamic mechanisms, that allow ...

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

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 ...

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Whole genome doubling (WGD) events are drivers of genetic innovation across vertebrate evolution. While generally detrimental to mammalian organisms, WGDs are crucial in the development of various plants and fungi, as well as for the terminal differentiati ...

Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion

Chattez avec Graph Search

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Ancestral genome reconstruction enhances transposable element annotation by identifying degenerate integrants

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

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

Towards improving full-length ribosome density prediction by bridging sequence and graph-based representations

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

Non-planarity of Markoff graphs mod p

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Equivariant Neural Architectures for Representing and Generating Graphs

A full characterization of invariant embeddability of unimodular planar graphs

Landscapes of DNA Mechanics and Genomes

Results on Sparse Integer Programming and Geometric Independent Sets

Individual and combined benefits of different nonequilibrium proofreading mechanisms

PSGL-1 is an evolutionarily conserved antiviral restriction factor

Development of multiplexed single-molecule imaging techniques to study chromatin invasion dynamics of chromatin effector proteins

Maximum Independent Set: Self-Training through Dynamic Programming

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

Better Trees for Santa Claus

Whole genome doubling promotes tumorigenesis through loss of chromatin segregation and compartment repositioning