The new sequencing technologies, called next-generation sequencing, provide a huge amount of data that can be used to reconstruct genomes. However, the methods applied to reconstruct genomes often are not able to reconstruct a complete genome and provide only an incomplete information. Here we consider two combinatorial problems that aim to reconstruct complete genomes by inserting a collection of missing genes. The first problem we consider, called One-sided scaffold filling, given an incomplete genome B and a complete genome A, asks for the insertion of missing genes into an incomplete genome B with the goal of maximizing the common adjacencies between genomes B′B′ (resulting from the insertion of missing genes in B) and A. The second problem, called Two-sided scaffold filling, given two incomplete genomes A, B , asks for the insertion of missing genes into both genomes so that the resulting genomes A′A′ and B′B′ have the same multiset of genes and the number of common adjacencies between A′A′ and B′B′ is maximized. Both problems were proved to be NP-hard, while their parameterized complexity, when the parameter is the number of common adjacencies of the resulting genomes, was left as an open problem. In this paper, we settle this open problem by presenting fixed-parameter algorithms for One-sided scaffold filling and Two-sided scaffold filling.

(2015). Fixed-parameter algorithms for scaffold filling [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from http://hdl.handle.net/10446/35151

Fixed-parameter algorithms for scaffold filling

Dondi, Riccardo
2015-02-23

Abstract

The new sequencing technologies, called next-generation sequencing, provide a huge amount of data that can be used to reconstruct genomes. However, the methods applied to reconstruct genomes often are not able to reconstruct a complete genome and provide only an incomplete information. Here we consider two combinatorial problems that aim to reconstruct complete genomes by inserting a collection of missing genes. The first problem we consider, called One-sided scaffold filling, given an incomplete genome B and a complete genome A, asks for the insertion of missing genes into an incomplete genome B with the goal of maximizing the common adjacencies between genomes B′B′ (resulting from the insertion of missing genes in B) and A. The second problem, called Two-sided scaffold filling, given two incomplete genomes A, B , asks for the insertion of missing genes into both genomes so that the resulting genomes A′A′ and B′B′ have the same multiset of genes and the number of common adjacencies between A′A′ and B′B′ is maximized. Both problems were proved to be NP-hard, while their parameterized complexity, when the parameter is the number of common adjacencies of the resulting genomes, was left as an open problem. In this paper, we settle this open problem by presenting fixed-parameter algorithms for One-sided scaffold filling and Two-sided scaffold filling.
articolo
23-feb-2015
Bulteau, Laurent; Carrieri, Anna Paola; Dondi, Riccardo
(2015). Fixed-parameter algorithms for scaffold filling [journal article - articolo]. In THEORETICAL COMPUTER SCIENCE. Retrieved from http://hdl.handle.net/10446/35151
File allegato/i alla scheda:
File Dimensione del file Formato  
Dondi - Fixed parameter algorithms for scaffold filling.pdf

Open Access dal 02/03/2017

Versione: postprint - versione referata/accettata senza referaggio
Licenza: Creative commons
Dimensione del file 390.43 kB
Formato Adobe PDF
390.43 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/35151
Citazioni
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 12
social impact