Édition en mode texte de {Site WWW de Laurent Bloch}
Sommaire de la page :
Articles
Brèves
Articles récents
Rubrique : {Boîte à outils}
Installer un serveur de boot sur un NAS DS-106e de Synology
Le mercredi 18 juin 2008
par Laurent Bloch
Cet article vient à la suite de celui sur la configuration du Synology 106e, et il suppose réalisées au préalable les opérations de configuration en question, notamment l’installation d’un environnement Debian chrooté.
#Sommaire-
Comment faire sans lecteur de cédérom ?
En fait, l’idée de cette installation m’est venue lorsque j’ai reçu mon nouvel ordinateur portable Toshiba Portégé R500-10U, une machine géniale parce qu’elle ne pèse que 776 g. Pour ce poids-là on n’a ni lecteur de CD/DVD ni de disquette, ce qui convient à mes usages, mais le lecteur de CD de mes portables précédents avait quand même une utilité : installer un système d’exploitation décent à la place de celui que le fournisseur se croit obligé de mettre sur le disque dur, et dont je vous laisse deviner le nom. Là je suis resté sec, et j’ai même dû passer un week-end avec Vista, non sans répercussions fâcheuses sur mon état psychologique.
J’ai trouvé pas mal de documents consacrés à l’installation d’un système libre à partir d’une clé USB ou d’autres périphériques USB, mais j’ai dû mal m’y prendre, en tout cas je n’ai pas réussi à booter, ou quand j’ai réussi à booter le système d’installation ne trouvait pas l’image ISO de cédérom contenant les paquetages de base, bref je n’y arrivais pas. J’ai donc pensé à l’installation par le réseau.
Choix d’une méthode d’installation
Le réseau de mon employeur bien-aimé comporte un serveur de boot destiné à l’installation de divers systèmes, et effectivement j’ai réussi dans un premier temps à installer ainsi une version un peu ancienne de CentOS, ce qui m’a déjà mis de meilleure humeur, mais ce n’était pas encore ce qu’il me fallait. J’ai essayé de bricoler le serveur DHCP pour ajouter le système qu’il me fallait, mais c’était une mauvaise idée parce que ce serveur n’était pas là pour faire des essais mais pour la production.
Je me suis donc décidé à installer ce qu’il fallait à la maison, et, pourquoi pas, sur mon NAS, après tout c’est une machine tout indiquée pour ce genre d’usage. Je m’imaginais cette manœuvre très compliquée, parce que je ne l’avais jamais réalisée. En fait, pendant une réunion particulièrement ennuyeuse et stérile avec les commerciaux d’un grand fournissseur de SGBD et d’ERP, j’ai commencé à explorer le Web sur le sujet, et je suis tombé sur l’excellent tutorial Setting Up A PXE Install Server For Multiple Linux Distributions With Ubuntu Edgy Eft.
Ce tutorial est pour Ubuntu, mais ce n’est pas trop différent de la Debian, pourtant antique, installée sur mon NAS Synology. En fait, comme la suite allait le montrer, ce tutorial appliqué à la lettre fonctionne parfaitement sur Debian, à quelques nuances près quant à la postion du fichier de configuration du serveur DHCP dans l’arborescence /etc. On trouvera d’autres explications (en français cette fois) sur le site Comment ça marche et sur le site Debian.
Amorçage et installation système par le réseau
La possibilité pour un ordinateur d’amorcer son système d’exploitation (booter en jargon) nécessite que son microcode de démarrage (firmware, ou BIOS) le permette, ce qui est le cas de pratiquement toutes les machines modernes, et cela repose sur trois protocoles : Dynamic Host Configuration Protocol (DHCP), Trivial File Transfer Protocol (TFTP) et Preboot Execution Environment (PXE).
PXE est programmé dans le microcode, et se déclenchera à la mise sous tension de la machine à condition que l’option de boot par le réseau ait été sélectionnée dans le menu de configuration du BIOS.
Le travail du microcode PXE sera de trouver sur le réseau un serveur DHCP qui accepte de lui répondre.
Si tel est bien le cas, le travail du serveur DHCP sera d’envoyer les informations nécessaires à la poursuite des opérations, essentiellement l’emplacement des fichiers d’amorçage (noyau du système d’exploitation et image pré-configurée du contenu de la mémoire au démarrage).
Une fois renseigné, le microcode PXE ira chercher les fichiers d’amorçage désirés, les récupérera par TFTP et les chargera dans la mémoire de l’ordinateur. Il existe des fichiers d’amorçage spécialement configurés pour démarrer l’installation d’un système d’exploitation neuf sur l’ordinateur.
Toujours pendant la réunion, je me suis connecté au NAS à la maison et j’ai commencé les opérations. À la fin de la réunion, le serveur sera opérationnel.
Installer DHCP
Première chose à faire, installer un serveur DHCP. DHCP est le protocole qui permet à votre ordinateur, lorsqu’il se connecte à un réseau, d’obtenir une adresse IP. C’est grâce à DHCP que Free, Orange ou InterPC attribuent une adresse à leurs abonnés. Si vous avez un petit routeur genre Linksys ou Netgear, c’est lui qui obtient l’adresse fournie par le fournisseur d’accès, et il comporte lui-même un petit serveur DHCP qui donne à son tour des adresses à vos ordinateurs. Mais le serveur DHCP de ces petits routeurs est insuffisant pour ce que nous voulons faire, il va donc falloir le désactiver au profit de celui que nous allons installer sur le NAS, plus complet et surtout plus configurable. En effet, le protocole DHCP permet d’envoyer à un système distant des informations bien plus raffinées que juste une adresse prise dans un intervalle, ce à quoi sont limités les petits routeurs.
Le fichier de configuration du serveur DHCP, /etc/dhcp3/dhcpd.conf,
contient les informations nécessaires à l’amorçage et à la configuration réseau
des clients, le mien ressemble à cela :
L’instruction filename donne le nom du fichier initial d’amorçage, l’instruction next-server donne l’adresse du serveur où aller chercher ce fichier et les autres fichiers d’amorçage.
Ne pas oublier la ligne deny unknown-clients;, sinon vos voisins de réseau vont peut-être installer Ubuntu sur leur ordinateur sans vraiment l’avoir voulu :-)
Comment installer ces fichiers, ce que nous diront la section suivante, et le tutorial déjà cité de Falko Timme, Setting Up A PXE Install Server For Multiple Linux Distributions..., auquel nous renvoyons pour les détails.
Installer TFTP
Ensuite, installer TFTP et les fichiers adéquats comme indiqué dans le tutorial. En bref, les clients s’attendent à trouver les fichiers dont ils ont besoin dans l’arborescence
/var/lib/tftpboot/, avec les détails de configuration dans
le fichier /var/lib/tftpboot/pxelinux.cfg/default ; le mien ressemble à cela :
L’antislash après append vga=normal dans la configuration de ubuntu_i386_install est pour indiquer une ligne de continuation, mais dans le fichier réel tout doit être sur la même ligne. Les chemins indiqués dans le fichier sont relatifs à la racine /var/lib/tftpboot/.
Il faut en outre modifier le fichier /var/lib/tftpboot/boot.txt, qui anonce le menu des options possibles :
Vérifier avec la commande tree que l’arborescence est bien conforme à ce qui donné dans le tutorial,
Difficulté éventuelle pour le boot avec TFTF et PXE
En réitérant cette opération avec un serveur de boot installé sur un système plus récent, j’ai buté sur un problème : la machine que j’essayais de faire booter par le réseau détectait correctement le serveur, obtenait bien du serveur DHCP une adresse IP convenable et les autres informations utiles (adresses des serveurs de noms...), mais au moment de charger le fichier d’amorçage par TFTP, l’opération échouait avec un timeout.
En consultant les journaux (/var/log/syslog) du serveur, on trouvait les messages suivants :
En fait, l’adresse fournie était IPv6.
J’ai mis un certain temps à trouver la correction, très simple dès qu’on la connaît : dans le fichier /etc/inetd.conf, remplacer udp par udp4 :
Pour finir !
Lancer l’installation, aller dîner, au dessert tout sera installé. L’essayer c’est l’adopter !
{Consulter} l'article avec son forum.
Rubrique : {Algorithmes pour la biologie}
Alignement de séquences
Algorithme de Needleman et Wunsch
Le mardi 27 mai 2008
par Laurent Bloch
L'algorithme de Needleman et Wunsch
L'algorithme de Needleman et Wunsch
Laurent Bloch
Le 10 mai 2006 |
Sommaire-
Principes de l’algorithme
Dans un autre article de ce site sont présentés des algorithmes de
recherche d’un mot dans un texte, notamment celui de
Knuth-Morris-Pratt (KMP). Ces algorithmes sont dévolus
au problème de la recherche exacte : il s’agit de trouver, si
elle existe, la première occurrence exacte de ce mot dans
ce texte.
Nous allons maintenant étudier, parce que c’est un problème
central en bioinformatique, une recherche approximative : il
s’agit de savoir si deux mots se ressemblent, quel est leur
degré de ressemblance, ou de trouver, dans un ensemble de mots,
celui qui ressemble le plus à un mot-cible. Et nous allons voir
que ce problème relève de solutions très différentes de celles
qui valent pour la recherche exacte.
Notons d’abord que la ressemblance est une notion
imprécise : la plupart des algorithmes utilisés proposent différents
paramètres pour ajuster les facteurs de ressemblance aux
caractéristiques du problème traité.
Les algorithmes utilisés fournissent en général deux résultats :
-
pour chaque comparaison de deux chaînes, un score de
ressemblance, qui permet ensuite de trouver la meilleure
ressemblance parmi un ensemble de comparaisons ;
- un alignement des deux chaînes (qui n’ont pas forcément
la même longueur) selon la configuration qui procure le meilleur
score ; on dit bien un alignement, et non pas
l’alignement, parce qu’en effet, comme nous le verrons plus
loin, le problème peut admettre plusieurs solutions conduisant au
même score.
Le plus caractéristique de cette famille d’algorithmes est peut-être
celui de Needleman et Wunsch, que nous étudierons ici ; il réalise un
alignement global de deux séquences (chaînes de caractères).
Calculer un alignement global peut être coûteux si les séquences à
aligner sont longues, ou s’il y en a beaucoup. D’autres algorithmes,
qui ressemblent à celui-ci, ont été conçus pour limiter la taille du
problème en ne réalisant l’alignement que pour des régions
« intéressantes ». La détermination des régions intéressantes est
bien sûr en elle-même un problème intéressant. Citons l’algorithme de
Smith et Waterman, qui réalise des alignements locaux, et le logiciel
BLAST1, qui mettent en
oeuvre des méthodes similaires à celles de Needleman et Wunsch,
après des optimisations éventuellement complexes.
Le problème de la comparaison de séquences est exponentiel, la
solution est en O(kn) ; ces algorithmes
sont susceptibles d’une multiplicité de solutions ; une des techniques les plus généralement utilisées pour en réduire la complexité est la
programmation dynamique, qui fait l’objet d’un autre
article sur ce site.
La programmation dynamique résout des problèmes en combinant des
solutions de sous-problèmes.
(Thomas Cormen, Charles Leiserson, Ronald Rivest et Clifford Stein, Introduction à l’algorithmique)
L’idée de la programmation dynamique
est de mémoriser les résultats de calculs intermédiaires qui
seront probablement répétés.
La programmation dynamique est par exemple souvent un bon choix
lorsque l’on aura besoin, après les avoir calculées, des valeurs
stockées dans tous les noeuds d’un arbre ou dans toutes les cases
d’un tableau. Parfois aussi cette conservation des résultats
intermédiaires est imposée par un problème tel que le calcul d’une
valeur se fait en fonction de toutes les précédentes. L’art
algorithmique consiste à chercher des solutions qui évitent ce type de
contrainte mais c’est parfois impossible. Et puis il y a des problèmes
intrinsèquement récursifs pour lesquels n’existe pas d’algorithme
itératif.
Nous allons donc chercher des procédés pour associer
un algorithme qui calcule des valeurs successives avec une structure
de données qui les archive.
Cette section doit beaucoup au travail préalable de William
Saurin pour cet enseignement, ainsi qu’à une page créée par Eric C.
Rouchka, de l’université Washington à Saint-Louis, et reprise
par Per Kraulis au Stockholm Bioinformatics Center :
http://www.sbc.su.se/~pjk/molbioinf...
Supposons que nous souhaitions calculer un alignement global
de deux séquences :
séquence n° 1 : G A A T T C A G T T A
séquence n° 2 : G G A T C G A
La séquence n° 1 a m=11 résidus, la séquence n° 2 n=7 résidus.
Nous allons ici étudier l’algorithme avec des paramètres
particulièrement simples, peut-être même simplistes : pénalité nulle
pour les trous (gaps) et les discordances (substitutions), une
pénalité négative, ou prime, égale à 1 pour les concordances (matches). Le but
est d’acquérir une vue d’ensemble de l’architecture de la solution,
qui permettra au lecteur d’envisager ensuite des exemples plus
compliqués, avec des formules de calcul plus élaborées pour les scores
et pour les pénalités de gap.
Le principe de pondération que nous adopterons sera le suivant :
-
la « prime de score » pour la comparaison du résidu de rang
i de la première séquence avec le résidu de rang j de le seconde
séquence sera Si,j = 1 si les deux résidus sont identiques,
sinon :
- Si,j = 0 (score de discordance) ;
- w = 0 (pénalité de gap).
L’algorithme opère en trois étapes :
-
initialisation ;
- calcul des scores et remplissage de la matrice ;
- calcul de l’alignement en « remontant » dans la matrice.
Initialisation
Création d’une matrice M de m+2=13 colonnes et n+2=9 lignes : la
ligne et la colonne de rangs 0 contiendront les textes des
séquences, la seconde ligne (de rang 1, les M1,j) et la première
colonne (les Mi,1) de M sont remplies de 0 parce que nous
avons posé qu’il n’y avait pas de pénalités pour des gaps
initiaux ou finals.
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
|
|
|
|
|
|
|
|
|
|
|
| G |
0 |
|
|
|
|
|
|
|
|
|
|
|
| A |
0 |
|
|
|
|
|
|
|
|
|
|
|
| T |
0 |
|
|
|
|
|
|
|
|
|
|
|
| C |
0 |
|
|
|
|
|
|
|
|
|
|
|
| G |
0 |
|
|
|
|
|
|
|
|
|
|
|
| A |
0 |
|
|
|
|
|
|
|
|
|
|
|
Remplissage de la matrice
À chaque position Mi,j de la matrice M (i est le numéro de
ligne, j le numéro de colonne) le score se calcule ainsi :
| Mi,j = Maximum de : |
| Mi−1,j−1 + Si,j |
(concordance ou discordance |
| |
dans la diagonale) |
| Mi,j−1 + w |
(gap dans la séquence n° 1) |
| Mi−1,j + w |
(gap dans la séquence n° 2) |
|
|
Nous voyons que pour calculer Mi,j il faut (et il suffit
de) connaître Mi−1,j, Mi,j−1 et Mi−1,j−1 ; de ce point de vue le problème est assez analogue à ceux posés par Fibonacci ou par le triangle de Pascal.
Ainsi, comme chaque séquence commence par le résidu G
(concordance), S1,1=1. Nous avons posé par hypothèse w=0.
Donc :
|
|
| M1,1 |
= Max[M0,0+1, M1,0+0, M0,1+0] |
|
|
|
|
|
|
|
|
(1) |
| |
= Max[1,0,0] |
|
|
|
|
|
|
|
|
(2) |
| |
= 1
|
|
|
|
|
|
|
|
|
(3) |
|
Nous pouvons donc inscrire un 1 en M1,1 :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
| G |
0 |
|
|
|
|
|
|
|
|
|
|
|
| A |
0 |
|
|
|
|
|
|
|
|
|
|
|
| T |
0 |
|
|
|
|
|
|
|
|
|
|
|
| C |
0 |
|
|
|
|
|
|
|
|
|
|
|
| G |
0 |
|
|
|
|
|
|
|
|
|
|
|
| A |
0 |
|
|
|
|
|
|
|
|
|
|
|
Ceci fait, toujours parce que w=0, nous pouvons facilement remplir
la ligne 1 et la colonne 1 avec des 1 ; ainsi :
|
|
| M2,1 |
= Max[M1,0+0, M2,0+0, M1,1+0] |
|
|
|
|
|
|
|
|
(4) |
| |
= Max[0,0,1] |
|
|
|
|
|
|
|
|
(5) |
| |
= 1
|
|
|
|
|
|
|
|
|
(6) |
|
soit :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
| A |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
| T |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
| C |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
| G |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
| A |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
Finalement :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
Nous avons signalé ci-dessus que le problème général de
la comparaison de séquences était exponentiel (O(kn)).
L’utilisation de la programmation dynamique, avec le
graphe représenté par ce tableau, permet
de le réduire à un problème quadratique (O(m × n),
m et n étant les longueurs respectives des séquences).
En effet, il y a m × n valeurs dans la table, et le
calcul de chacune s’effectue en temps constant.
Déterminer l’alignement optimal
L’étape précédente nous a déjà permis de savoir que le
score d’alignement maximum pour nos deux séquences est 6.
Souvent, cette information est suffisante, parce que
l’on cherche en fait les meilleurs scores parmi une
collection de séquences à comparer à la cible. Mais
peut être aussi intéressant de connaître un alignement
qui donne ce score.
Nous allons maintenant déterminer l’alignement effectif
qui donne ce résultat.
Pour cela, on considère la case du tableau qui contient le
score maximum, qui est Mm,n, et on la
compare à ses voisines. Ici toutes les voisines contiennent la valeur
5. Comme la différence de scores est 1 dans tous les
cas, et que le seul moyen d’avoir un accroissement de 1
est une concordance (match) (toutes les autres situations donnent
un accroissement nul), c’est que la case précédente était
la voisine en diagonale :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
Ce qui nous donne un alignement :
Maintenant nous considérons la case courante et
cherchons celle qui la précède : c’est la voisine avec
le score maximum, soit celle de la même ligne.
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
Cet alignement correspond à un gap dans la séquence n° 2 :
Encore une fois, le prédécesseur immédiat donne un gap dans la
séquence n° 2 :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
Au bout du compte :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
| G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| | |
|
| |
|
| |
| |
|
| |
|
|
| |
| G |
G |
A |
_ |
T |
C |
_ |
G |
_ |
_ |
A |
Il y a une autre solution possible :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
qui donne l’alignement suivant :
| G |
_ |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| | |
|
|
| |
|
| |
| |
|
| |
|
|
| |
| G |
G |
_ |
A |
_ |
T |
C |
_ |
G |
_ |
_ |
A |
L’algorithme
Algo : NW
Données : s1, s2, S et gap ; des chaînes numérotées de
; 1 à longueur(s1) et de 1 à longueur(s2),
; S le score de concordance entre caractères
; et gap un coût de gap.
Résultat : la matrice de calcul des scores
Créer C une matrice à longueur(s1) + 2 colonnes et
à longueur(s2) + 2 lignes
pour j allant de 2 à longueur(s1)+2 faire
C[1, j] <- gap * j-2
fait
pour i allant de 2 à longueur(s2)+2 faire
C[i, 1] <- gap * i-2
pour j allant de 2 à longueur(s2)+2 faire
C[i, j] = max(C[i-1,j-1] + si s1[i] = s2[j]
alors 1 sinon 0,
C[i-1,j] + gap,
C[i,j-1] + gap)
fait
fait
retourner C
Nous verrons dans un prochain article l’algorithme
de remontée dans le graphe (backtracking) pour trouver
un alignement optimal.
Au sujet de ces algorithmes on consultera avec profit le livre de
Maxime Crochemore, Christophe Hancart et Thierry Lecroq,
Algorithmique du texte, chez Vuibert.
Le programme
| (module nw:lb
(main main)
(import nw:matrices)
(import nw:chains)
(import nw:alignment))
(define (nw-2 s1 s2 match-bonus gap-penalty)
(let ((ncol (+ (chain-length s1) 2))
(nlin (+ (chain-length s2) 2)))
(let ((C (make-matrix nlin ncol 0)))
(matrix:margins C s1 s2) ;;
(do ((j 2 (+ j 1)))
((= j nlin) 'fait)
(matrix:set! C j 1 (* j gap-penalty)))
(do ((i 2 (+ i 1)))
((= i ncol) 'fait)
(matrix:set! C 1 i (* gap-penalty i)))
(do ((i 2 (+ i 1)))
((= i ncol) C)
(do ((j 2 (+ j 1)))
((= j nlin) 'fait)
(let
((val
(max
(+ (matrix:ref C (- j 1) (- i 1))
(if (char=? (matrix:ref C 0 i)
(matrix:ref C j 0))
match-bonus 0))
(+ (matrix:ref C j (- i 1)) gap-penalty)
(+ (matrix:ref C (- j 1) i) gap-penalty))))
(matrix:set! C j i val)))))))
;; là on suppose qu'une séquence est dans un fichier fasta
;; read-fasta lit un fichier fasta et rend la premiere séquence trouvée
(define (read-fasta port)
(let ((titre (read-line port)))
(if (or (eof-object? titre)
(zero? (string-length titre))
(not (char=? (string-ref titre 0)
#\>)))
(error 'read-fasta "not a fasta file" port)
(let loop ((str ""))
(let ((lu (read-line port)))
(if (or (eof-object? lu)
(char=? #\> (string-ref lu 0)))
(cons titre str)
(begin (print lu)
(loop (string-append str lu)))))))))
(define (f-concorde base1 base2 match-bonus)
(if (char=? base1 base2)
match-bonus 0))
;;
(define (usage)
(print "nw fichier-1 fichier-2 match-bonus gap-penalty")
(exit 1))
(define (main argv)
(if (not (= (length argv) 5))
(usage)
(let ((f1 (cadr argv))
(f2 (caddr argv))
(match-bonus
(string->number (cadddr argv)))
(gap-penalty (string->number (cadddr (cdr argv)))))
(let* ((s1 (make-chain
(cdr (let ((port (open-input-file f1)))
(read-fasta port)))))
(s2 (make-chain
(cdr (let ((port (open-input-file f2)))
(read-fasta port)))))
(the-score-matrix
(nw-2 s1 s2 match-bonus gap-penalty)))
(matrix:print the-score-matrix)
(matrix:print (alignment the-score-matrix
match-bonus gap-penalty)))))) |
Le module de manipulation de matrices
Voici les deux séquences au format FASTA :
> La séquence 1
GAATTCAGTTA
> La séquence 2
GGATCGA
Le module de matrices :
| (module nw:matrices
(export
(make-matrix n m . fill)
(matrix? obj)
(matrix:ref T i j)
(matrix:set! T i j val)
(matrix:nlines T)
(matrix:ncols T)
(matrix:margins M s1 s2)
(matrix:print T))
(import nw:chains))
;; il nous faut des matrices
(define matrix:tag "*MATRIX*")
(define (make-matrix lin col . fill)
(let ((the-table
(vector "*MATRIX*"
(make-vector lin #f))))
(do ((i 0 (+ i 1)))
((= i lin))
(vector-set! (vector-ref the-table 1)
i
(if (null? fill)
(make-vector col)
(make-vector col (car fill)))))
the-table))
;; un prédicat d'appartenance, pour vérifier qu'un
;; objet appartient bien au type :
(define (matrix? obj)
(and (vector? obj)
(string=? (vector-ref obj 0) "*MATRIX*")
(vector? (vector-ref obj 1))))
;; un mutateur, pour modifier un objet du type en
;; affectant une valeur à un élément du tableau :
(define (matrix:set! T i j val)
(if (matrix? T)
(vector-set!
(vector-ref
(vector-ref T 1) i)
j
val)))
;; un sélecteur, pour accéder à un élément d'un
;; tableau du type :
(define (matrix:ref T i j)
(if (matrix? T)
(vector-ref
(vector-ref
(vector-ref T 1)
i)
j)))
(define (matrix:margins M s1 s2)
(let ((nlin (matrix:nlines M))
(ncol (matrix:ncols M)))
(do ((j 2 (+ j 1))
(c (chain-ref s1 1)
(chain-ref s1
(min j (- ncol 2)))))
((= j ncol) 'fait)
(matrix:set! M 0 j c))
(do ((i 2 (+ i 1))
(c (chain-ref s2 1)
(chain-ref s2
(min i (- nlin 2)))))
((= i nlin) 'fait)
(matrix:set! M i 0 c))
(matrix:set! M 0 0 #\space)
(matrix:set! M 0 1 #\space)
(matrix:set! M 1 0 #\space)))
;; diverses procédures utilitaires dont la fonction se
;; comprend d'elle-même :
(define (matrix:nlines T)
(if (matrix? T)
(vector-length
(vector-ref T 1))))
(define (matrix:ncols T)
(if (matrix? T)
(vector-length
(vector-ref
(vector-ref T 1) 0))))
(define (matrix:print T)
(if (matrix? T)
(let ((n (matrix:nlines T))
(m (matrix:ncols T)))
(do ((i 0 (+ 1 i)))
((= i n))
(let ((this-line
(vector-ref
(vector-ref T 1) i)))
(do ((j 0 (+ 1 j)))
((= j m))
(display
(vector-ref this-line j))
(display " "))
(newline)))))) |
Le module de chaînes :
(module nw:chains
(export
(make-chain s)
(chain-ref s i)
(chain-set! s i c)
(chain-length s)))
;; il nous faut des chaîne numérotées de 1 à longueur de chaîne:
(define (make-chain s) ; prend une string et rend un chaîne à partir de 1
s)
(define (chain-ref s i)
(string-ref s (- i 1)))
(define (chain-set! s i c)
(string-set! s (- i 1) c))
(define (chain-length s)
(string-length s))
Le Makefile :
BIGLOO = bigloo
AFILE = NW-afile.scm
BGL_FLAGS = -afile $(AFILE) -Obench -farithmetic -static-bigloo
CIBLE = nw
REPERT_CIBLE = .
%.o: %.scm
@ $(BIGLOO) $(BGL_FLAGS) -c $*.scm -o $*.o
OBJECTS = NW-lb.o NW-matrices.o NW-chains.o NW-alignment.o
SOURCES = NW-lb.scm NW-matrices.scm NW-chains.scm NW-alignment.scm
all: $(REPERT_CIBLE)/$(CIBLE)
$(REPERT_CIBLE)/$(CIBLE): $(OBJECTS)
@ echo "Edition de liens..."
@ $(BIGLOO) $(BGL_FLAGS) $(OBJECTS) \
-o $(REPERT_CIBLE)/$(CIBLE)
@ echo "$(REPERT_CIBLE)/$(CIBLE) construit."
@ echo "-------------------------------"
$(REPERT_CIBLE):
@ mkdir -p $(REPERT_CIBLE)
install:
cp $(REPERT_CIBLE)/$(CIBLE) $(REPERT_CGI)
clean:
-rm -f $(OBJECTS) $(SOURCES_C)
-rm -f *~ Src/*~ Src/*.o Src/*.mco
@ echo "nettoyage fait..."
@ echo "-------------------------------"
# destruction aussi des binaires :
cleanall: clean
-rm -f $(REPERT_CIBLE)/$(CIBLE)
- 1
- BLAST (Basic Local Alignment Search Tool) est un
logiciel écrit par S.F. Altschul, W. Gish, W. Miller, Gene Myers et
D.J. Lipman. Il est l'outil de travail quotidien de tous ceux qui
travaillent en biologie moléculaire (cf.
http://en.wikipedia.org/wiki/BLAST).
This document was translated from LATEX by
HEVEA.
{Consulter} l'article avec son forum.
Rubrique : {Algorithmes pour la biologie}
Alignement de séquences
Needleman et Wunsch, once again
Le mardi 27 mai 2008
par Laurent Bloch
Needleman et Wunsch : le retour
Needleman et Wunsch : le retour
Laurent Bloch
Le 18 mai 2006 |
Calculer un alignement d’après un graphe
Cet article est la suite de l’Algorithme de
Needleman et Wunsch, où nous avions montré comment
déterminer le score maximum, c’est-à-dire le coût minimum,
d’alignement de deux séquences. Nous avions eu recours à
une méthode de programmation dynamique, par
la construction d’une matrice des scores. Ceci fait, restait
à exhiber un alignement optimal : c’est l’objet du présent
article. Nous obtiendrons ce résultat en remontant dans le
graphe représenté par la matrice, selon un chemin qui va
nous donner l’alignement. Reprenons la démarche de
l’article.
Pour cela, on part de la case du tableau qui contient le
score maximum, qui est Mm,n, et on considère ses
voisines. Ici toutes les voisines contiennent la valeur
5. Comme la différence de scores est 1 dans tous les
cas, et que le seul moyen d’avoir un accroissement de 1
est une concordance (toutes les autres situations donnent
un accroissement nul), c’est que la case précédente était
la voisine en diagonale :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
Ce qui nous donne un alignement :
Maintenant nous considérons la case courante et
cherchons celle qui la précède : c’est la voisine avec
le score maximum, soit celle de la même ligne.
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
Cet alignement correspond à un gap dans la séquence n° 2 :
Encore une fois, le prédécesseur immédiat donne un gap dans la
séquence n° 2 :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
Au bout du compte :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
| G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| | |
|
| |
|
| |
| |
|
| |
|
|
| |
| G |
G |
A |
_ |
T |
C |
_ |
G |
_ |
_ |
A |
Il y a une autre solution possible :
| |
|
G |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
3 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| G |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
4 |
5 |
5 |
5 |
5 |
| A |
0 |
1 |
2 |
3 |
3 |
3 |
4 |
5 |
5 |
5 |
5 |
6 |
qui donne l’alignement suivant :
| G |
_ |
A |
A |
T |
T |
C |
A |
G |
T |
T |
A |
| | |
|
|
| |
|
| |
| |
|
| |
|
|
| |
| G |
G |
_ |
A |
_ |
T |
C |
_ |
G |
_ |
_ |
A |
Au sujet de cet algorithme on consultera avec profit le livre de
Maxime Crochemore, Christophe Hancart et Thierry Lecroq,
Algorithmique du texte, chez Vuibert.
Le programme
(module nw:alignment
(export (alignment C match-bonus gap-penalty))
(import nw:matrices))
(define (alignment-col-set! align col . vals)
(matrix:set! align 0 col (car vals))
(matrix:set! align 1 col (cadr vals))
(matrix:set! align 2 col (caddr vals)))
(define (alignment C match-bonus gap-penalty)
(let* ((ncol (matrix:ncols C))
(nlin (matrix:nlines C))
(line-length (+ nlin ncol (- 4)))
(this-alignment (make-matrix 3 line-length #\space)))
(let boucle ((i (- nlin 1))
(j (- ncol 1))
(p-align (- (+ nlin ncol) 5)))
(if (and (= i 1) (= j 1))
'fait
(cond
((and (= j 1) (> i 1))
(alignment-col-set! this-alignment p-align
#\_
#\space
(matrix:ref C i 0))
(boucle (- i 1) j (- p-align 1)))
((and (= i 1) (> j 1))
(alignment-col-set! this-alignment p-align
(matrix:ref C 0 j)
#\space
#\_)
(boucle i (- j 1) (- p-align 1)) )
((and
(= (matrix:ref C i j)
(+ (matrix:ref C (- i 1) (- j 1))
match-bonus))
(char=? (matrix:ref C i 0)
(matrix:ref C 0 j)))
(alignment-col-set! this-alignment p-align
(matrix:ref C 0 j)
#\|
(matrix:ref C i 0))
(boucle (- i 1) (- j 1) (- p-align 1)))
((= (matrix:ref C i j)
(matrix:ref C (- i 1) (- j 1)))
(alignment-col-set! this-alignment p-align
(matrix:ref C 0 j)
#\x
(matrix:ref C i 0))
(boucle (- i 1) (- j 1) (- p-align 1)) )
((= (matrix:ref C i j)
(+ (matrix:ref C (- i 1) j)
gap-penalty))
(alignment-col-set! this-alignment p-align
#\_
#\space
(matrix:ref C i 0))
(boucle (- i 1) j (- p-align 1)))
((= (matrix:ref C i j)
(+ (matrix:ref C i (- j 1))
gap-penalty))
(alignment-col-set! this-alignment p-align
(matrix:ref C 0 j)
#\space
#\_)
(boucle i (- j 1) (- p-align 1))) ))
this-alignment)))
This document was translated from LATEX by
HEVEA.
{Consulter} l'article avec son forum.
Dernières brèves
Rubrique : {Travaux, CV, clé publique}
Séance de signature samedi 14 avril au Monde en Tique
Le samedi 24 mars 2007
Samedi 14 avril Christophe Wolfhugel et moi-même signerons notre livre Sécurité informatique - Principes et méthode :
à la librairie Le Monde en Tique,
6 rue Maître Albert,
Paris 5ème, métro Maubert-Mutualité,
de 15h à 18h.
{Consulter} la brève avec son forum.
Rubrique : {L’informatique : science et industrie}
Docteur Ordinateur !
Le mercredi 5 avril 2006
Ce soir en sortant du bureau je suis tombé sur une nouvelle boutique du quartier : Docteur Ordinateur ! Comme je m’attardais devant la vitrine, le Docteur Ordinateur est venu engager la conversation. Il s’agit d’une chaîne d’officines créées sur le principe de la franchise. Vous pouvez visiter leur site ou leur téléphoner au 0 826 105 107. Je leur souhaite tout le succès possible.
Cet entrepreneur n’est pas unique : vous pouvez aussi visiter le site de Philippe Herzog, dans un style peut-être un peu différent, plus personnel.
Si un peu de publicité leur est accordée ici, ce n’est pas parce que le Docteur Ordinateur m’aurait offert l’apéritif : simplement la création de telles entreprises répond à un besoin et peut créer de la richesse, donc des emplois dont nous sommes paraît-il gravement dépourvus. Et si la clientèle prend l’habitude de faire appel à eux, les pauvres informaticiens, lorsqu’ils sont invités à dîner, ne seront plus condamnés à mettre en service l’abonnement Internet de la maîtresse de maison et à réparer les disques durs de sa progéniture pendant que les autres convives devisent agréablement autour d’un verre. On paie bien le médecin, le plombier et le mécanicien, pourquoi pas le Docteur Ordinateur !
{Consulter} la brève avec son forum.
Rubrique : {Travaux, CV, clé publique}
Lien RSS vers ce site
Le mardi 6 septembre 2005
Pour vous abonner aux nouveautés de ce site par un flux RSS, il vous suffit de cliquer sur le carré orange strié de blanc en bas à droite de la page. Le fichier backend pour la syndication de ce site est :
http://www.laurent-bloch.org/spip.php?page=backend.
{Consulter} la brève avec son forum.
Rechercher sur ce site :