Sorting by weighted inversions considering length and symmetry

Abstract : Large-scale mutational events that occur when stretches of DNA sequence move throughout genomes are called genome rearrangements. In bacteria, inversions are one of the most frequently observed rearrangements. In some bacterial families, inversions are biased in favor of symmetry as shown by recent research. In addition, several results suggest that short segment inversions are more frequent in the evolution of microbial genomes. Despite the fact that symmetry and length of the reversed segments seem very important, they have not been considered together in any problem in the genome rearrangement field. Here, we define the problem of sorting genomes (or permutations) using inversions whose costs are assigned based on their lengths and asymmetries. We consider two formulations of the same problem depending on whether we know the orientation of the genes. Several procedures are presented and we assess these procedure performances on a large set of more than 4.4 × 10^9 permutations. The ideas presented in this paper provide insights to solve the problem and set the stage for a proper theoretical analysis.
Type de document :
Article dans une revue
BMC Bioinformatics, BioMed Central, 2015, 16 (Suppl 19), pp.11. 〈10.1186/1471-2105-16-S19-S3〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01316998
Contributeur : Marie-France Sagot <>
Soumis le : mardi 17 mai 2016 - 21:06:14
Dernière modification le : jeudi 19 avril 2018 - 14:49:47
Document(s) archivé(s) le : vendredi 19 août 2016 - 18:01:48

Fichier

art_10.1186_1471-2105-16-S19-S...
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Christian Baudet, Ulisses Dias, Zanoni Dias. Sorting by weighted inversions considering length and symmetry. BMC Bioinformatics, BioMed Central, 2015, 16 (Suppl 19), pp.11. 〈10.1186/1471-2105-16-S19-S3〉. 〈hal-01316998〉

Partager

Métriques

Consultations de la notice

101

Téléchargements de fichiers

70