Efficient assembly consensus algorithms for divergent contig sets - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Computational Biology and Chemistry Year : 2021

Efficient assembly consensus algorithms for divergent contig sets

Manuel Lafond
  • Function : Author
  • PersonId : 1079433


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
Origin Files produced by the author(s)

Dates and versions

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



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⟩
56 View
145 Download



Gmail Mastodon Facebook X LinkedIn More