Zobrazeno 1 - 10
of 68
pro vyhledávání: '"Labarre, Anthony"'
In this paper, we study the problem of sorting unichromosomal linear genomes by prefix double-cut-and-joins (or DCJs) in both the signed and the unsigned settings. Prefix DCJs cut the leftmost segment of a genome and any other segment, and recombine
Externí odkaz:
http://arxiv.org/abs/2208.14315
Publikováno v:
In Theoretical Computer Science 12 January 2025 1024
Autor:
Labarre, Anthony
We initiate the study of sorting permutations using prefix block-interchanges, which exchange any prefix of a permutation with another non-intersecting interval. The goal is to transform a given permutation into the identity permutation using as few
Externí odkaz:
http://arxiv.org/abs/2008.13640
We investigate a variant of the so-called "Internet Shopping Problem" introduced by Blazewicz et al. (2010), where a customer wants to buy a list of products at the lowest possible total cost from shops which offer discounts when purchases exceed a c
Externí odkaz:
http://arxiv.org/abs/1802.07944
Let $S=\{K_{1,3},K_3,P_4\}$ be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph $G$ into graphs taken from any non-empty $S'\subseteq S$. The problem is known to be NP-complete for any possible choic
Externí odkaz:
http://arxiv.org/abs/1604.08603
Autor:
Grusea, Simona, Labarre, Anthony
The prefix exchange distance of a permutation is the minimum number of exchanges involving the leftmost element that sorts the permutation. We give new combinatorial proofs of known results on the distribution of the prefix exchange distance for a ra
Externí odkaz:
http://arxiv.org/abs/1604.04766
A wide range of applications, most notably in comparative genomics, involve the computation of a shortest sorting sequence of operations for a given permutation, where the set of allowed operations is fixed beforehand. Such sequences are useful for i
Externí odkaz:
http://arxiv.org/abs/1602.06283
Autor:
Gambette, Philippe, Gunawan, Andreas D. M., Labarre, Anthony, Vialette, Stéphane, Zhang, Louxin
A fundamental problem in the study of phylogenetic networks is to determine whether or not a given phylogenetic network contains a given phylogenetic tree. We develop a quadratic-time algorithm for this problem for binary nearly-stable phylogenetic n
Externí odkaz:
http://arxiv.org/abs/1502.03379
Autor:
Labarre, Anthony
The dissertation covers two problems motivated by computational biology: genome rearrangements, and haplotype networks.Genome rearrangement problems are a particular case of edit distance problems, where one seeks to transform two given objects into