Distribution équitable de points sur de multiples droites

Bonjour à tous,

Je voudrais aborder un problème au quel je suis confronter et dont je n'arrive pas à percevoir de solution simple, il m'as sembler que ce forum était le plus adapter à mes besoins:

On peut conceptualiser mon problème de la manière suivante:

On as un ensemble de droites de taille variées, sur chaque droite on trouve un nombre variable de points d’intérêts.
Les point d’intérêt on une répartition variable pour chaque problème.
On cherche à récupérer une liste de n points d’intérêt régulièrement distribuer le long des droites.
Sachant que les coordonnées de chaque point d’intérêt sont connues, le nombre et les tailles des droites sont connues.

Cet énoncer est une tentative pour expliquer mon problème métier qui est : à partir d'une liste de polymorphisms (considérant uniquement des SNP) connue sur un génome donné retourné une liste de polymorphismes régulièrement réparti sur ce dernier.

La solution que j'ai envisagées est la suivante:
1) calculer la distance optimal séparant chacun des point d’intérêt sélectionnée
2) prendre le premier point d’intérêt l'ajouté à la liste des point d’intérêt sélectionnée, puis chercher le prochain d’intérêt se trouvant le plus proche de la distance optimal.
3) itérer

J'ai l'impression (peut-être fausse) qu'il existe déjà dans la littérature des algorithme résolvant des problèmes approchant celui-ci, j'ai néanmoins été incapable de les trouver.

Si vous avez d'autres pistes à me proposer je suis ouvert à toute proposition :)

Je tien à préciser que je ne suis pas un habituer de ce forum, ni de ce sujet, il se pourrais donc que je rate des solution évidente ou bien des concepts.

D'avance merci

Bonjour,

Je n'ai pas tout compris à la problématique que tu expose :

Quand tu parle de tes "N points régulièrement distribuer le long des droites", quels sont ces points ?

J'ai bien compris qu'on avait plusieurs droites de longueur variable avec X point d'intérêts et qu'il fallait calculer une "distances optimal". Que je j'exprimerai plus en un "point central optimal".

Si c'est bien le cas, il va falloir que tu regarde du côté des barycentres. De mémoire, il y a le barycentre classique et il y a le une autre version qui limite la distance basé sur "le carrés pondérés des distances".

Cependant, je ne vois pas bien sur quel liste de points, on réalise l'opération . Est-ce sur une opération par point ? Ce qui fait qu'on a 1 point optimal pour N droites ?

Cordialement,
Patrick Kolodziejczyk.

salut


si j'ai bien tout compris tu veut contrôler la place de marqueur précis dans différents génome pour en définir des similitudes ?

si j'ai bien compris ... ma première approche serais de trouver un point médian et à partir de celui ci essayer de retrouver mes différents éléments avec des "pas" défini entre les SNP .

mais bon j'ai peut être pas tout compris

Sous réserve d'avoir pigé ton problème...

Soit x_i l'emplacement d'un point d'intérêt sur un segment de longueur L, tel que i est la position d'un point d'intérêt.

Soit N le nombre de points d'intérêt.

Il faut donc trouver une distance d telle qu'il existe un x_i où x_i+k.d est aussi un point d'intérêt avec k entier naturel.

Une façon naïve de procéder est de considérer une matrice carré M de dimensions NxN où M_ij = distance entre les points d'intérêt x_i et x_j.
Ensuite, pour chaque longueur possible d'intervalle d, entre 1 et L, rechercher dans la matrice les cases M_ij = d.
Ainsi à chaque itération, on obtient l'ensemble des points d'intérêts séparés par une distance de d.

Bonjours à tous,

Tout d'abord merci de vous intéresse à mon problème , je vois que je n'ai pas du tout été clair, je vais donc tenter de clarifier avec un exemple imagé :



Voici des droites au départ avec les points d’intérêts connues :
Pièce jointe 169165
les droites sont en bleu, en dessous nous avons une graduation, et en rouge les positions des points d’intérêts.



Une des question qui serais posée à l’algorithme serais la suivante :
«Donne moi une liste de 25 points d’intérêts répartis le plus régulièrement sur mes droites»


Une des solution donnée par algorithme pourrais être:
Pièce jointe 169174
Ici les flèches bleu représentant les points d’intérêts qui ont été sélectionnés par l'algorithme.

Par contre avec mon algorithme naïf j'aurais probablement obtenu le résultats suivant:
Pièce jointe 169173


Les différence entre un algorithme optimiser (solution bleu) et mon implémentation naïve se ressente surtout proche des «zone de trou» de points d’intérêts, et proche du début de la droite, mais finisse par converger avec un peu de chance.




@kolodz:

Citation:

---

Quand tu parle de tes "N points régulièrement distribuer le long des droites", quels sont ces points ?

---

Je n'ai pas été claire les points dont je parles ici sont un sous-ensemble de point contenue par l’ensemble des «points d’intérêts».

Citation:

---

De mémoire, il y a le barycentre classique et il y a le une autre version qui limite la distance basé sur "le carrés pondérés des distances".

---

je vais creuser de ce coté la, sachant que je ne me souviens plus très bien de ce que sont les barycentres.

@anapurna:
je pense que tu ne m'as pas compris, et du coup je ne t'ais pas compris :(
Pour être plus biologique voici le «problème» complet: sur mon génome, j'ai une liste connue de polymorphisms («points d’intérêts») et je souhaite en récupérer une sous partie qui soit disposé le plus régulièrement possible le long de mon génome. Les «droites» que j'évoque sont simplement des représentation de mes chromosomes.

@yahiko:

Citation:

---

une matrice carré M de dimensions NxN où M_ij = distance entre les points d'intérêt x_i et x_j

---

Est-ce que seul la moitié de la matrice n'est pas suffisante puisque M_ij = M_ji ?

mais je ne comprend pas cette notation la :

Citation:

---

Il faut donc trouver une distance d telle qu'il existe un xi où x_i+k.d est aussi un point d'intérêt avec k entier naturel.

---

que veux dire le _+k.d ? je suis un peu perdu :s désolé :(
du coup le reste de ta réflexion ne m'est pas accessible.



Encore une fois merci pour vos réponse et votre réactivité :)

D'après, moi tu devrais faire la chose suivant :

Prendre le min et le max de ta droite et placer régulièrement l'ensemble de test points d'intérêt.
Supposons que ton mix soit à 100 et ton max à 200 et que tu lui demande 11 points d'intérêt.(Je fait tel que ça m'arrange là)
Tu va avoir les valeur suivantes :

Citation:

---

100
110
120
130
140
150
170
180
190
200

---

Je ne te fait pas l'affront de donnée la formule mathématique pour faire ça. courbe affine toute ça.(cours de 3ième)
Note : Peut-être ajouter un peu de marge par rapport au min et au max de tes points de bases (genre +5% de chaque côtés)

Après tu peux avoir, un groupement de points dont tu voudrait te rapproché à l'intérieur de ta droite.

Supposons qu'on ait :

Citation:

---

100, 111, 112 114 115,130 ...

---

Il serait peut-être intéressante, d'avoir une légère divergence dans la régularité pour coller un peu plus à cette mesure.
Dans ce cas, tu peux potentiellement appliqué un correctif local. C'est à dire prendre la moyen des points proche et l'appliqué. Supposons que c'est 114, pour le point 110. On décale le point 110 de "4" vers le "haut", mais dans une limite de "2" et donc on replace notre point 110 par 112 ! Les points seront moins régulier, mais tu collera, un peu plus au point d'intérêt.
Note : Cela va automatiquement décalé tes points extérieur vers l'intérieur, surtout si tu as mis une marge.(Vue que les points seront tous d'un seul côté par rapport à ton point d'intérêt)

Donc, les deux principaux réglage se trouve dans :

• La définition de la limite de ton intervalle (ajout de marge ou non)
• L'ajustement de tes points par rapport à une moyenne local (si cela à un intérêt dans ton domaine)

Cordialement,
Patrick Kolodziejczyk.

+k.d = "+ k fois d"

Sinon, oui, la matrice M est symétrique donc pour optimiser tu peux te contenter de ne considérer qu'une moitié.

Tu veux 25 points , et tu veux que l'espace entre 2 points consécutifs soit toujours le même ?
C'est assez surprenant.
Si les points rouges sont répartis de façon irrégulière, on aurait bien imaginé 25 points, répartis de façon irrégulière .. et qui symbolisent au mieux les points d'origine.

Si on veut 25 points répartis de façon régulière, je propose:
- Calculer la moyenne et l'écart-type des points rouges.
- Calculer 25 points régulièrement répartis, qui vont donner la même moyenne et le même écart-type.
Je n'ai pas les équations en tête pour ce 2ème point... mais ça devrait se solutionner assez facilement.

Je ne sais pas si j'ai compris, mais je vais exposer mon point de vue quand même :D

Pour chaque droite :

• diviser sa longueur par le nb de points demandé (+ ou - 1 suivant qu'on veut avoir un vide de chaque côté ou qu'on veut avoir un point à chaque extrémité) => on a un incrément de longueur
  
  
• partir de 0, et à chaque incrément, trouver le point significatif (point d'intérêt) le plus proche (au dessus ou en dessous du x considéré), par une bête distance...

Ai-je mal compris quelque chose ??

salut

ta solution serais correcte si les écarts étaient uniformément reparti tout au long du segment


imaginons maintenant que 75% des valeurs se trouve dans la moitié de ton segment, ta répartition n'aura plus aucun sens.

Citation:

---

Envoyé par anapurna

ta solution serais correcte si les écarts étaient uniformément reparti tout au long du segment

imaginons maintenant que 75% des valeurs se trouve dans la moitié de ton segment, ta répartition n'aura plus aucun sens.

---

Ben quand je regarde ses 2 graphiques, avec ses fêches pointées là où il verrait ses points, ça me semble pas mal proche de ce que je dis, non ???

Il dit "le plus régulièrement possible", pas forcément régulièrement... Or, vu qu'il parle du génome, on peut considérer qu'on aura une certaine "continuité", je pense... donc je pense que "75% es valeurs dans la moitié" sera faux, car si je ne m'abuse les droites considérées sont justement des "segments d'intérêt"...

En fait, on doit faire des appariements..

Dans la figure attachée les appariements sont indiqués en gros traits rouges sur la figure du milieu..

En fait, je pense que la seule chose à vérifier c'est qu'on ne tombe pas dans le cas de la fin du premier cas, avec 3 points en dehors de tout.. Mais pour ça il suffit d'ajuster la longueur de la droite..

Pièce jointe 169305


Mais j'ai peut-être pas compris.. Là, je me demande si il ne cherche pas la meilleure position d'un peigne régulier pour minimiser l'écart-type entre la position d'une dent et la position du point de référence le plus proche..... Si c'est ça, alors je verrais plutôt une approche dichotomique entre les positions 0 et 1/2 taille de l'incrément pour le début du peigne...

salut

pour en revenir a la question première.

Citation:

---

J'ai l'impression (peut-être fausse) qu'il existe déjà dans la littérature des algorithme résolvant des problèmes approchant celui-ci, j'ai néanmoins été incapable de les trouver.

---

regarde du coté de "Cake-Cutting Algorithms" ou en français "algorithme de découpe de gâteau"

Pour l'algorithme que tu as réalisé ne me parais pas si faux
Avec de légère modification tu peut retrouver trois solution différentes
la modification se fait sur le choix de l’élément de départ
je m'explique

reprenons ta solution

Citation:

---

La solution que j'ai envisagées est la suivante:
1) calculer la distance optimal séparant chacun des point d’intérêt sélectionnée
2) prendre le premier point d’intérêt l'ajouté à la liste des point d’intérêt sélectionnée, puis chercher le prochain d’intérêt se trouvant le plus proche de la distance optimal.
3) itérer

---

dans ton cas tu a pris la plus petites valeurs que tu incrémente

tu pourrais choisir la plus grande valeur et tu décrémente la valeur de la distance optimal

a mon sens pour que se soit plus équilibré et réduire tes itérations tu aurais due partir du centre et à chaque itération décrémenter d'un coté et incrémenté de l'autre
ce qui devrais normalement diviser le nombre d’itération "principal" par deux
un peut comme la construction d'un arbre ou la racine de l'arbre est le point d’intérêt centrale .