Efficient assembly consensus algorithms for divergent contig sets - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Computational Biology and Chemistry Année : 2021

Efficient assembly consensus algorithms for divergent contig sets

Manuel Lafond
  • Fonction : Auteur
  • PersonId : 1079433

Résumé

Assembly is a fundamental task in genome sequencing, and many assemblers have been made available in the last decade. Because of the wide range of possible choices, it can be hard to determine which tool or parameter to use for a specific genome sequencing project. In this paper, we propose a consensus approach that takes the best parts of several contigs datasets produced by different methods, and combines them into a better assembly. This amounts to orienting and ordering sets of contigs, which can be viewed as an optimization problem where the aim is to find an alignment of two fragmented strings that maximizes an arbitrary scoring function between matched characters. In this work, we investigate the computational complexity of this problem. We first show that it is NP-hard, even in an alphabet with only two symbols and with all scores being either 0 or 1. On the positive side, we propose an efficient, quadratic time algorithm that achieves approximation factor 3.
Fichier principal
Vignette du fichier
main.pdf (441.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03244191 , version 1 (01-06-2021)

Identifiants

Citer

Annie Chateau, Tom Davot, Manuel Lafond. Efficient assembly consensus algorithms for divergent contig sets. Computational Biology and Chemistry, 2021, 93, pp.#107516. ⟨10.1016/j.compbiolchem.2021.107516⟩. ⟨lirmm-03244191⟩
53 Consultations
142 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More