A Pseudo de Bruijn Graph Representation for Discretization Orders for Distance Geometry

Antonio Mucherino 1
1 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Instances of the distance geometry can be represented by a simple weighted undirected graph G. Vertex orders on such graphs are discretization orders if they allow for the discretization of the K-dimensional search space of the distance geometry. A pseudo de Bruijn graph B associated to G is proposed in this paper, where vertices correspond to (K+1)-cliques of G, and there is an arc from one vertex to another if, and only if, they admit an overlap, consisting of K vertices of G. This pseudo de Bruijn graph B can be exploited for constructing discretization orders for G for which the consecutivity assumption is satisfied. A new atomic order for protein backbones is presented, which is optimal in terms of length.
Type de document :
Communication dans un congrès
F. Ortuno; I. Rojas. Proceedings of IWBBIO15, May 2015, Granada, Spain. 9043, pp.514-523, 2015, Lectures Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/hal-01196707
Contributeur : Antonio Mucherino <>
Soumis le : jeudi 10 septembre 2015 - 11:58:48
Dernière modification le : jeudi 15 novembre 2018 - 11:57:53

Identifiants

  • HAL Id : hal-01196707, version 1

Citation

Antonio Mucherino. A Pseudo de Bruijn Graph Representation for Discretization Orders for Distance Geometry. F. Ortuno; I. Rojas. Proceedings of IWBBIO15, May 2015, Granada, Spain. 9043, pp.514-523, 2015, Lectures Notes in Computer Science. 〈hal-01196707〉

Partager

Métriques

Consultations de la notice

706