In this paper we consider two combinatorial problems related to genome comparison. The two problems, starting from possibly incomplete genomes produced from sequencing data, aim to reconstruct the complete genomes by inserting a collection of missing genes. More precisely, in the first problem, called One-sided scaffold filling, we are given an incomplete genome B and a complete genome A, and we look for the insertion of missing genes into B with the goal of maximizing the common adjacencies between the resulting genome and B′. In the second problem, called Two-sided scaffold filling, we are given two incomplete genomes A, B, and we look for the insertion of missing genes into both genomes so that the resulting genomes A′ and B′ have the same multi-set of genes, with the goal of maximizing the common adjacencies between A′ and B′. While both problems are known to be NP-hard, their parameterized complexity when parameterized by the number of common adjacencies of the resulting genomes is still open. In this paper, we settle this open problem and we present fixed-parameter algorithms for the One-sided scaffold filling problem and the Two-sided scaffold filling problem.

(2014). Fixed-Parameter Algorithms for Scaffold Filling [conference presentation - intervento a convegno]. Retrieved from http://hdl.handle.net/10446/31881

Fixed-Parameter Algorithms for Scaffold Filling

DONDI, Riccardo
2014-01-01

Abstract

In this paper we consider two combinatorial problems related to genome comparison. The two problems, starting from possibly incomplete genomes produced from sequencing data, aim to reconstruct the complete genomes by inserting a collection of missing genes. More precisely, in the first problem, called One-sided scaffold filling, we are given an incomplete genome B and a complete genome A, and we look for the insertion of missing genes into B with the goal of maximizing the common adjacencies between the resulting genome and B′. In the second problem, called Two-sided scaffold filling, we are given two incomplete genomes A, B, and we look for the insertion of missing genes into both genomes so that the resulting genomes A′ and B′ have the same multi-set of genes, with the goal of maximizing the common adjacencies between A′ and B′. While both problems are known to be NP-hard, their parameterized complexity when parameterized by the number of common adjacencies of the resulting genomes is still open. In this paper, we settle this open problem and we present fixed-parameter algorithms for the One-sided scaffold filling problem and the Two-sided scaffold filling problem.
2014
Bulteau, Laurent; Carrieri, Anna Paola; Dondi, Riccardo
File allegato/i alla scheda:
File Dimensione del file Formato  
ISCO2014.pdf

Solo gestori di archivio

Descrizione: publisher's version - versione dell'editore
Dimensione del file 234.92 kB
Formato Adobe PDF
234.92 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/31881
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact