Discretization Orders for Distance Geometry

28/08/2013
OAI : oai:www.see.asso.fr:2552:4899
DOI : You do not have permission to access embedded form.

Résumé

Discretization Orders for Distance Geometry

Média

Voir la vidéo

Métriques

67
8
442.77 Ko
 application/pdf
bitcache://58851873782e533d11fbfc22e6306e5bd500699c

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4899</identifier><creators><creator><creatorName>Carlile Lavor</creatorName></creator><creator><creatorName>Leo Liberti</creatorName></creator><creator><creatorName>Nelson Maculan</creatorName></creator><creator><creatorName>Antonio Mucherino</creatorName></creator></creators><titles>
            <title>Discretization Orders for Distance Geometry</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 17 Sep 2013</date>
	    <date dateType="Updated">Sun 25 Dec 2016</date>
            <date dateType="Submitted">Sat 17 Feb 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">58851873782e533d11fbfc22e6306e5bd500699c</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25062</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Discretization Orders for Distance Geometry Discretizable DG group Carlile Lavor, Leo Liberti, Nelson Maculan, Antonio Mucherino GSI13 Paris, France August 28th 2013 Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . The Distance Geometry Problem (for molecular conformations) Let G = (V, E, d) be a simple weighted undirected graph, where V the set of vertices of G − it is the set of atoms; E the set of edges of G − it is the set of known distances; E′ ⊂ E the subset of E where distances are exact; d the weights associated to the edges of G the numerical value of each weight corresponds to the known distance; it can be an interval. Definition The DGP. Determine whether there exists a function x : V −→ ℜK for which, for all edges (u, v) ∈ E, ||xu − xv || = d(u, v). Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Sphere intersections In the 3-dimensional space, the intersection of 2 spheres gives one circle 3 spheres gives two points 2 spheres and 1 spherical shell gives two disjont curves Spheres and spherical shells can be centered in known vertex positions, while their radii are related to the distance information. All this is true with probability 1: the reference vertices cannot be aligned, the strict triangular inequality needs to be satisfied. Generalization to any dimension K: the volume of the (K − 1)-simplex defined by the reference vertices needs to be strictly positive (simplex inequalities). Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . The Branch & Prune algorithm The Branch & Prune (BP) algorithm is based on the idea of branching over all possible positions for each vertex, and of pruning by using additional information not used in the discretization process. In this tree, it is supposed that all available distances are exact. D sample (exact) distances can be taken from interval distances. Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Importance of orders The definition of an order on the vertices in V allows us to ensure that vertex coordinates are available when needed. Given 1 a simple weighted undirected graph G = (V, E, d) 2 a vertex v ∈ V how to identify K vertices wi , with i = 1, 2, . . . , K, for which the coordinates of every wi are available every edge (wi , v) ∈ E ???? We refer to wi as a reference vertex for v (wi , v) as a reference distance for v Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Definition of order Definition An order for V is a sequence r : N → V ∪ {0} with length |r| ∈ N (for which ri = 0 for all i > |r|) such that, for each v ∈ V, there is an index i ∈ N for which ri = v. Some facts about orders: they allow for vertex repetitions (|r| ≥ |V|); however, each vertex can be used as a reference only once; simplex inequalities (generally satisfied with probability 1) would not be satisfied if the same vertex were used twice as a reference. Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Counting the reference vertices Let r be an order for V. Let us consider the following counters. α(ri ): counter of adjacent predecessors of ri; β(ri ): counter of adjacent successors of ri; αex (ri ): counter of adjacent predecessors of ri related to an exact distance. Necessary condition for V to admit a discretization order is that, for any order r on V, ∀i ∈ {1, 2, . . . , |r|}, α(ri ) + β(ri ) ≥ K. Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Discretization orders We refer to any order r that allows for the discretization of the DGP as Discretization order Two big families: Discretization orders with consecutive reference vertices for each ri , reference vertices always immediately precede ri in the order Discretization orders without consecutive reference vertices any vertex with rank < i can be a reference for ri Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Discretization orders For K = 3. the reference vertices for ri are searched only in the “window” [ri−K , . . . , ri−1] the simplex inequality must be satisfied on the window. the reference vertices for ri are in the “big window” [r1, . . . , ri−1] the simplex inequality must be satisfied for the K reference vertices inside the big window. Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Why different discretization assumptions? Different motivations: historical reasons the habit to handcraft orders symmetry properties of BP trees the methods for intersecting the spheres (and spherical shells) the interest in methods for automatic detection of discretization orders Consecutivity: IN FAVOUR vs. AGAINST Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Why different discretization assumptions? Different motivations: historical reasons the habit to handcraft orders symmetry properties of BP trees the methods for intersecting the spheres (and spherical shells) the interest in methods for automatic detection of discretization orders Consecutivity: IN FAVOUR vs. AGAINST Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . The ordering problem Definition Given a simple weighted undirected graph G = (V, E, d) and a positive integer K, establish whether there exists an order r such that: (a) GC = (VC , EC) ≡ G[{r1, r2, . . . , rK }] is a clique and EC ⊂ E′ ; (b) ∀i ∈ {K + 1, . . . , |r|}, α(ri ) ≥ K and αex (ri ) ≥ K − 1. Remarks: this problem is NP-complete when K is not fixed no consecutivity assumption: solvable in polynomial time when K is known when dealing with proteins, K = 3 Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . A greedy algorithm 0: reorder(G) while (a valid order r is not found yet) do let i = 0; find a K-clique C in G with exact distances; // position C at the beginning of new order for (all vertices v in C) do let i = i + 1; let ri = v; end for // greedy search while (V is not covered) do v = arg max{α(u) | ∃j ≤ i : rj = u and αex (u) ≥ K − 1}; if (α(v) < K) then break the inner loop: there are no possible orderings for C; end if // adding the vertex to the order let i = i + 1; let ri = v; end while end while return r; Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . An order for the protein backbone This order was automatically obtained by the greedy algorithm. Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Computational experiments NMR-like instances are considered in these experiments, including protein backbones and side chains. PDB name naa n |E| D LDE 1brv 4 51 368 3 2.10e-4 1brv 8 98 853 9 5.88e-4 1ccq 6 114 1181 3 1.16e-4 1ccq 10 183 2169 8 1.63e-4 1acz 6 94 929 3 1.63e-4 1acz 13 199 2144 3 1.95e-4 1acz 21 308 3358 10 4.93e-4 1k1v 6 110 1236 3 3.04e-4 1k1v 18 317 4169 3 3.66e-4 1k1v 30 519 7068 3 5.63e-4 All instances were automatically reordered by the greedy algorithm, and the BP algorithm was invoked for finding one solution. Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Computational experiments Two solutions obtained during the experiments. On the left, a 4-amino acid fragment of 1brv; on the right, a 18-amino acid fragment of 1k1v. Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Work in progress . . . Can we find orders that help BP in finding solutions? minimize in length the subsequences in the order having no pruning distances (for proteins) maximize the interval distances that are related to pairs of hydrogen atoms . . . Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Other work in progress . . . identify clusters of solutions in BP solution sets find a way for avoiding discretizing the intervals improve and tailor the parallel versions of BP to interval data (for proteins) use real NMR data and compare our results to what is currently available on the PDB . . . Discretization Orders for DG A. Mucherino Discretization of the DGP Getting started Discretization assumptions Ordering problem A greedy algorithm Computational experiments Ending . . . Thanks!