L'alignement des séquences
Saviez-vous ...
SOS Enfants a essayé de rendre le contenu plus accessible Wikipedia par cette sélection des écoles. parrainage SOS enfant est cool!
En bioinformatique , un alignement de séquences est une façon d'organiser l' des séquences primaires de l'ADN , ARN, ou protéine pour identifier des régions de similarité qui peuvent être une conséquence de fonctionnelle, structurelles ou évolutives relations entre les séquences. Séquences alignées de nucléotidiques ou d'acides aminés sont typiquement de résidus représentés sous forme de lignes dans une matrice . Les lacunes sont insérés entre les résidus de sorte que les résidus avec des caractères identiques ou similaires sont alignés en colonnes successives.
Si deux séquences dans un alignement partagent un ancêtre commun, décalages peuvent être interprétées comme des mutations ponctuelles et des lacunes que indels (ce est-à insertion ou la suppression des mutations) introduites dans une ou deux lignées dans le temps car ils divergent les uns des autres. Dans un alignement de séquences de protéines, le degré de similitude entre les acides aminés occupant une position particulière dans la séquence peut être interprété comme une mesure approximative de la conservé une région particulière ou motif de séquence est l'une des lignées. L'absence de substitutions, ou la présence de seulement des substitutions très conservatrices (ce est la substitution d'acides aminés dont chaînes latérales ont des propriétés biochimiques similaires) dans une région particulière de la séquence, suggèrent que cette région a une importance structurelle ou fonctionnelle. Bien que l'ADN et l'ARN bases nucléotidiques sont plus similaires les uns aux autres pour que les acides aminés, la conservation de la appariement de base peut indiquer un rôle fonctionnelle ou structurelle similaire. L'alignement de séquences peut être utilisée pour les séquences non-biologiques, tels que ceux présents dans langage naturel ou dans les données financières.
Très court ou très séquences similaires peuvent être alignés à la main; Cependant, les problèmes les plus intéressants nécessitent l'alignement de séquences longues, très variables ou extrêmement nombreux qui ne peuvent pas être alignées uniquement par l'effort humain. Au lieu de cela, la connaissance humaine est principalement appliquée pour la construction des algorithmes pour produire des alignements de séquences de haute qualité, et parfois à ajuster les résultats définitifs de refléter les habitudes qui sont difficiles à représenter algorithmique (surtout dans le cas de séquences nucléotidiques). Approches informatiques à l'alignement de séquence répartissent généralement en deux catégories: les alignements mondiaux et alignements locaux. Calcul d'un alignement global est une forme de optimisation globale que les «forces» l'alignement se étende sur toute la longueur de toutes les séquences de la requête. En revanche, les alignements locaux identifient des régions de similitude dans les longues séquences qui sont souvent très divergentes globale. Alignements locaux sont souvent préférables, mais peut être plus difficile à calculer en raison de la difficulté supplémentaire d'identifier les régions de similarité. Une variété d'algorithmes de calcul ont été appliquées au problème de l'alignement de séquence, y compris, mais lent formellement l'optimisation des méthodes telles que programmation dynamique et efficace heuristiques ou probabilistes méthodes conçues pour la recherche de base de données à grande échelle.
Représentations
Les alignements sont couramment représentés graphiquement et en format texte. Dans presque tous les représentations d'alignement de séquences, les séquences sont écrites en rangées agencées de manière à ce que les résidus alignés apparaissent dans des colonnes successives. Dans les formats de texte, colonnes alignées contenant des caractères identiques ou similaires sont indiqués par un système de symboles de conservation. Comme dans l'image ci-dessus, un astérisque ou un tuyau est utilisé pour montrer l'identité entre deux colonnes; autres symboles moins courantes comprennent deux points pour les substitutions conservatrices et une période pour les substitutions semiconservative. De nombreux programmes de visualisation de séquences utilisent également la couleur à afficher des informations sur les propriétés des éléments de séquence individuels; dans des séquences d'ADN et d'ARN, ce qui équivaut à attribuer à chaque nucléotide sa propre couleur. Dans les alignements de protéines, telles que celle dans l'image ci-dessus, la couleur est souvent utilisé pour indiquer les propriétés d'acides aminés pour aider à juger de la conservation d'une substitution d'acide aminé donné. Pour plusieurs séquences la dernière ligne de chaque colonne est souvent le séquence consensus déterminée par l'alignement; la séquence consensus est également souvent représentée sous forme graphique avec un logo de séquence dans lequel la taille de chaque lettre nucléotide ou acide aminé correspond à son degré de conservation.
Les alignements de séquences peuvent être stockées dans une grande variété de formats de fichier à base de texte, dont beaucoup ont été initialement mis au point conjointement avec un programme d'alignement spécifique ou la mise en œuvre. La plupart des outils basés sur le Web permettent un certain nombre de formats d'entrée et de sortie, tels que FASTA et Le format GenBank; Cependant, l'utilisation d'outils spécifiques rédigés par des laboratoires de recherche individuels peut être compliquée par la compatibilité de format de fichier limitée. Un programme de conversion générale est disponible au Baser l'ADN ou Readseq (pour readseq vous devez télécharger vos fichiers sur un serveur étranger et de fournir votre adresse e-mail).
Alignements globaux et locaux
Alignements globaux, qui tentent d'aligner chaque résidu dans chaque séquence, sont les plus utiles lorsque les séquences dans le jeu de requête sont similaires et de taille à peu près égale. (Cela ne signifie pas alignements globales ne peuvent pas aboutir à des lacunes.) Une technique d'alignement globale générale est appelée Algorithme de Needleman-Wunsch et est basé sur une programmation dynamique. Alignements locaux sont plus utiles pour les séquences dissemblables qui sont soupçonnés de contenir des régions de similitude ou de motifs de séquences similaires dans leur contexte de plus grande séquence. Le Algorithme de Smith-Waterman est un procédé d'alignement général local également sur la base de la programmation dynamique. Avec séquences suffisamment semblables, il n'y a pas de différence entre les alignements locaux et mondiaux.
Les méthodes hybrides, appelés semiglobale ou méthodes «glocal», pour tenter de trouver le meilleur alignement possible que inclut le début et la fin de l'une ou l'autre séquence. Cela peut être particulièrement utile lorsque la partie en aval d'une séquence chevauche avec la partie amont de l'autre séquence. Dans ce cas, ni alignement global, ni locale est tout à fait approprié: un alignement global serait tenter de forcer l'alignement de prolonger au-delà de la région de chevauchement, tandis qu'un alignement local pourrait ne pas couvrir entièrement la zone de recouvrement.
Alignement par paires
Méthodes d'alignement de séquences par paires sont utilisés pour trouver la meilleure morceaux de correspondance (local) ou mondiaux alignements de deux séquences de requête. Alignements par paires ne peuvent être utilisés entre deux séquences à la fois, mais ils sont efficaces pour le calcul et sont souvent utilisés pour les méthodes qui ne nécessitent pas une grande précision (par exemple, la recherche d'une base de données pour les séquences à haut homologie à une requête). Les trois principales méthodes de production alignements par paires sont des méthodes matricielles, programmation dynamique, et les méthodes de mots; Cependant, plusieurs techniques d'alignement de séquences peuvent également aligner des paires de séquences. Bien que chaque méthode a ses forces et faiblesses, les trois méthodes paires avoir de la difficulté avec des séquences très répétitives de faible le contenu de l'information - en particulier lorsque le nombre de répétitions diffèrent dans les deux séquences à aligner. Une manière de quantifier l'utilité d'un alignement par paire donnée est la "correspondance unique maximum», ou la plus longue sous-séquence qui se produit à la fois dans la séquence de requête. Des séquences plus longues MUM reflètent généralement proche parenté.
Méthodes matricielles
 | Wikiversity a des matériaux d'apprentissage sur Méthodes matricielles |
L'approche matricielle, qui produit implicitement une famille d'alignements pour les différentes régions de séquence, est qualitatif et simple, bien que de temps à analyser sur une grande échelle. Il est très facile d'identifier visuellement certaine séquence dispose-telle que des insertions, délétions, répétitions, ou répétitions de-inversées une parcelle matricielle. Pour construire une intrigue matricielle, les deux séquences sont écrits le long de la rangée du haut et la colonne la plus à gauche d'un à deux dimensions matrice et un point est placé à ne importe quel point où les personnages dans les colonnes appropriées correspondent-ce est un typique parcelle récidive. Certaines mises en œuvre varient selon la taille ou de l'intensité du point en fonction du degré de similitude entre les deux caractères, pour tenir compte des substitutions conservatrices. Les tracés de points de séquences très étroitement liés apparaîtront comme une seule ligne le long de la matrice de diagonale principale.
Dot emplacements peuvent également être utilisés pour évaluer la répétitivité en une seule séquence. Une séquence peut être relevée en lui-même et régions qui partagent des similitudes importantes apparaîtra comme lignes hors la diagonale principale. Cet effet peut se produire lorsque une protéine se compose de multiples similaires domaines structuraux.
La programmation dynamique
La technique de programmation dynamique peut être appliquée à produire des alignements mondiaux via le Algorithme de Needleman-Wunsch, et les alignements locaux via le Algorithme de Smith-Waterman. En utilisation normale, les alignements de protéines utilisent un matrice de substitution d'attribuer des notes aux matchs ou les discordances acides aminés, et un pénalité de brèche correspondant à un acide aminé dans une séquence à un intervalle dans l'autre. ADN et ARN alignements peuvent utiliser une matrice de notation, mais dans la pratique souvent simplement attribuer un score positif du match, un score négatif de décalage, et une pénalité d'écart négatif. (Dans la programmation dynamique standard, le score de chaque position d'acide aminé est indépendante de l'identité de ses voisins, et par conséquent effets de base d'empilement ne sont pas prises en compte. Cependant, il est possible de tenir compte de ces effets en modifiant l'algorithme).
La programmation dynamique peut être utile dans l'alignement de nucleotides des séquences de protéines, une tâche compliquée par la nécessité de prendre en compte mutations de déphasage (généralement des insertions ou délétions). La méthode de framesearch produit une série de alignements par paires mondiales ou locales entre une séquence requête de nucléotides et un ensemble de recherche de séquences de protéines, ou vice versa. Bien que le procédé est très lent, sa capacité à évaluer déphasages compensée par un nombre arbitraire de nucleotides réalise un procédé utile pour des séquences contenant un grand nombre d'indels, qui peut être très difficile d'aligner avec des méthodes heuristiques plus efficaces. Dans la pratique, la méthode nécessite de grandes quantités d'énergie ou d'un système dont l'architecture est spécialisée pour le calcul de la programmation dynamique. Le BLAST et EMBOSS suites offrent des outils de base pour la création d'alignements traduits (même si certaines de ces approches profitent des effets secondaires de capacités de séquence de recherche des outils). Plus méthodes générales sont disponibles auprès de sources commerciales, telles que FrameSearch, distribué dans le cadre de la Accelrys package GCG et Open Source des logiciels tels que GeneWise.
La méthode de programmation dynamique est garantie pour trouver un alignement optimal donné une fonction de notation particulier; Toutefois, l'identification d'une bonne fonction de notation est souvent empirique plutôt que d'une question théorique. Bien que la programmation dynamique est extensible à plus de deux séquences, il est excessivement lente pour un grand nombre de très longues séquences ou.
méthodes Word
méthodes de Word, également connus sous le nom de méthodes k -uple, sont méthodes heuristiques qui ne sont pas garantis pour trouver une solution optimale d'alignement, mais sont beaucoup plus efficaces que la programmation dynamique. Ces méthodes sont particulièrement utiles dans les recherches de base de données à grande échelle où il est entendu qu'une grande partie des séquences candidates aura essentiellement aucune correspondance importante avec la séquence d'interrogation. méthodes de Word sont surtout connus pour leur mise en œuvre dans les outils de recherche de base de données FASTA et le famille BLAST. méthodes Word identifient une série de courtes séquences, ne se chevauchent pas ("mots") dans la séquence de requête qui sont appariés à des séquences de bases de données de candidat. Les positions relatives du mot dans les deux séquences comparées sont soustraites pour obtenir un décalage; cela indique une région de l'alignement si plusieurs mots distincts produisent le même décalage. Seulement si cette région est détectée faire ces méthodes se appliquent des critères d'alignement les plus sensibles; Ainsi, de nombreuses comparaisons inutiles avec des séquences de pas de similitude notable sont éliminés.
Dans le procédé de FASTA, l'utilisateur définit une valeur k à utiliser comme longueur de mot pour rechercher la base de données. Le procédé est plus lent mais plus sensibles à des valeurs plus faibles de k, qui sont également préférés pour des recherches portant sur une séquence requête très court. La famille BLAST de méthodes de recherche fournit un certain nombre d'algorithmes optimisés pour certains types de requêtes, telles que la recherche pour la séquence de loin liés correspond. BLAST a été développé pour fournir une alternative plus rapide à FASTA sans pour autant sacrifier la précision; comme FASTA, BLAST utilise une recherche de mot de longueur k, mais ne évalue que les matchs les plus importants de mots, plutôt que chaque match de texte comme le fait FASTA. La plupart des implémentations de BLAST utilisent une longueur de mot fixe par défaut qui est optimisé pour la requête et base de données de type, et que ne est modifiée que dans des circonstances particulières, comme lors de la recherche avec des séquences de requêtes répétitives ou très courtes. Les implémentations peuvent être trouvés via un certain nombre de portails Web, tels que EMBL et FASTA BLAST NCBI.
L'alignement multiple de séquences
L'alignement multiple des séquences est une extension de l'alignement par paires pour incorporer plus de deux séquences à la fois. Méthodes d'alignement multiples tentent de se aligner toutes les séquences dans un jeu de requête donnée. Alignements multiples sont souvent utilisés dans l'identification régions de séquences conservées à travers un groupe de séquences hypothétiques d'être évolutif connexe. Ces motifs de séquences conservées peuvent être utilisés en conjonction avec la structure et information sur le mécanisme pour localiser le catalytique sites actifs enzymes. Les alignements sont également utilisés pour aider à établir les relations évolutives en construisant des arbres phylogénétiques. Alignements multiples de séquences de calcul sont difficiles à produire et la plupart des formulations de la tête de problème à NP-complet problèmes d'optimisation combinatoire. Toutefois, l'utilité de ces alignements en bioinformatique a conduit au développement d'une variété de procédés appropriés pour aligner trois ou plusieurs séquences.
La programmation dynamique
La technique de programmation dynamique est théoriquement applicable à ne importe quel nombre de séquences; cependant, parce qu'il est coûteux en calculs à la fois dans le temps et la mémoire, il est rarement utilisé pendant plus de trois ou quatre séquences dans sa forme la plus basique. Cette méthode nécessite la construction de l'équivalent de dimension n de la matrice de la séquence formée à partir de deux séquences, où n est le nombre de séquences dans la requête. Programmation dynamique standard est utilisé en premier sur toutes les paires de séquences de requête et puis «l'espace d'alignement" est rempli en considérant les matchs ou les éventuelles lacunes à des positions intermédiaires, éventuellement construire un alignement essentiellement entre chaque alignement de deux séquences. Bien que cette technique est coûteuse en ressources informatiques, la garantie d'une solution optimum global est utile dans les cas où seules quelques séquences doivent être alignées avec précision. Un procédé pour réduire les demandes de calcul de la programmation dynamique, qui se appuie sur la "somme de paires" fonction objectif, a été mis en œuvre dans le Logiciel MSA.
Méthodes progressistes
Progressive, ou les méthodes d'arbres hiérarchiques générer un alignement de séquences multiples d'abord aligner les séquences les plus similaires, puis en ajoutant successivement des séquences ou des groupes moins liés à l'alignement jusqu'à ce que l'ensemble de la requête a été incorporé dans la solution. L'arbre initial décrivant la parenté de séquence est basée sur les comparaisons par paires qui peuvent inclure des méthodes heuristiques d'alignement par paires semblables à FASTA. Les résultats de l'alignement progressif dépendent sur le choix des séquences plus "connexes" et peut donc être sensible à des inexactitudes dans les alignements par paires initiales. La plupart des multiples méthodes d'alignement de séquences progressives pèsent en outre les séquences dans la requête fixés conformément à leur parenté, ce qui réduit la probabilité de faire un mauvais choix de séquences initiales et améliore ainsi l'exactitude alignement.
De nombreuses variantes de la Mise en oeuvre progressive Clustal sont utilisées pour l'alignement de séquences multiples, la construction de l'arbre phylogénétique, et comme entrée pour prédiction de la structure des protéines. Une variante plus lente mais plus précise de la méthode est connue sous progressive T-café; implémentations peuvent être trouvés à ClustalW et T-Coffee.
Méthodes itératives
Méthodes itératives tentent d'améliorer sur le point des méthodes progressives, la forte dépendance de la précision des alignements par paires initiales faible. Méthodes itératives optimiser une fonction objective basée sur un alignement méthode de notation choisie par l'attribution d'un alignement global initial, puis le réalignement des sous-ensembles de séquence. Les sous-ensembles sont ensuite réalignés se sont alignés pour produire alignement de séquences multiples de la prochaine itération. Différentes façons de sélectionner les sous-groupes de séquence et fonction objectif sont examinés.
Motif conclusion
Motif constatation, aussi connu comme l'analyse du profil, construit alignements de séquences multiples mondiaux qui tentent d'aligner à court conservé séquence motifs parmi les séquences dans l'ensemble de la requête. Ceci est habituellement fait par la construction d'un premier alignement multiple de séquences global général, après quoi le hautement régions conservées sont isolés et utilisés pour construire un ensemble de matrices profil. La matrice de profil pour chaque région conservée est agencé comme une matrice de notation mais ses chiffres de fréquence pour chacun des acides aminés ou nucleotides au niveau de chaque position sont dérivées de la distribution de caractère de la région conservée au lieu de partir d'une distribution plus générale empirique. Le profil matrices sont ensuite utilisés pour la recherche d'autres séquences pour les occurrences du motif ils caractérisent. Dans les cas où l'original ensemble de données contenait un petit nombre de séquences, ou des séquences seulement très liés, pseudocounts sont ajoutés pour normaliser les distributions de caractères représentés dans le motif.
Techniques inspirées par la science informatique
Diverses générale des algorithmes d'optimisation couramment utilisés en informatique ont également été appliquées au problème de l'alignement de séquences multiples. Modèles de Markov cachés ont été utilisées pour produire des scores de probabilité pour une famille de possibles alignements de séquences multiples pour un ensemble de requête donnée; bien que les méthodes à base de HMM-premières produites performances décevante, les applications ultérieures ont trouvés particulièrement efficace dans la détection des séquences liées à distance parce qu'ils sont moins sensibles au bruit créé par des substitutions conservatives ou semiconservative. Algorithmes génétiques et recuit simulé ont également été utilisés dans l'optimisation de multiples partitions d'alignement de séquences tel que jugé par une fonction de notation comme la méthode de somme de paires. Des détails plus complets et des logiciels peuvent être trouvés dans l'article principal alignement de séquences multiples .
Alignement structurel
Alignements structurels, qui sont généralement spécifiques à la protéine et parfois séquences ARN, utilisent des informations sur le secondaire et la structure tertiaire de la molécule de protéine ou d'ARN pour aider à l'alignement des séquences. Ces procédés peuvent être utilisés pour deux ou plusieurs séquences et produisent généralement des alignements locaux; cependant, parce qu'ils dépendent de la disponibilité de l'information structurelle, ils ne peuvent être utilisés pour des séquences dont les structures correspondant sont connus (généralement par le biais de La cristallographie aux rayons X ou spectroscopie RMN ). Parce que les deux la structure des protéines et de l'ARN est plus évolutif conservé de séquence, alignements structurels peuvent être plus fiable entre des séquences qui sont très lointainement apparentée et qui ont divergé de façon extensive que la comparaison de la séquence ne peut pas détecter de manière fiable leur similitude.
Alignements structurels sont utilisés comme "étalon-or" dans l'évaluation des alignements de base-homologie la prédiction de la structure des protéines, car ils aligner explicitement régions de la séquence de protéine qui sont structurellement similaires plutôt que de compter sur des renseignements séquence. Toutefois, clairement alignements structuraux ne peuvent pas être utilisés dans la prédiction de la structure, car au moins une séquence dans l'ensemble d'interrogation est la cible à modéliser, dont la structure ne est pas connue. Il a été montré que, compte tenu de l'alignement structural entre une cible et une séquence de modèles, des modèles très précises de la séquence de protéine cible peuvent être produits; une pierre d'achoppement majeure dans la prédiction de structure basée homologie est la production d'alignements structurellement précis donnés uniquement informations séquence.
DALI
La méthode DALI, ou l'alignement de matrice de distance, est une méthode basée sur les fragments pour construire des alignements structurels en fonction des modèles de similarité de contact entre hexapeptides successives dans les séquences de la requête. Il peut générer des paires ou des alignements multiples et identifier voisins structurelles d'une séquence d'interrogation dans le Protein Data Bank (PDB). Il a été utilisé pour construire le FSSP base de données d'alignement structurel (classification basée sur l'alignement Fold Structure-structure des protéines, ou des familles de protéines structurellement similaires). Un serveur web DALI peut être consulté à EBI DALI et la FSSP est situé au La base de données Dali.
SSAP
SSAP (programme d'alignement de structure séquentielle) est une méthode dynamique basée programmation de l'alignement structurel qui utilise des vecteurs atome-à-atome dans la structure espace comme points de comparaison. Il a été étendu depuis sa description initiale pour inclure de multiples ainsi que les alignements par paires, et a été utilisé dans la construction de la CATH (classe, Architecture, topologie, homologie) classement de base de données hiérarchique des plis de protéines. La base de données de CATH peut être consulté à CATH Protein Structure Classification.
L'extension combinatoire
Procédé d'extension de l'alignement structurel combinatoire génère un alignement structurel par paires à l'aide de la géométrie locale pour aligner des fragments courts des deux protéines d'être analysés et assemble ensuite ces fragments dans un alignement plus grand. Basé sur des mesures telles que corps rigide racine de la moyenne distance au carré, les distances de résidus, structure secondaire locale, et entourant les caractéristiques environnementales telles que les résidus voisin hydrophobie, alignements locaux appelés «paires de fragments alignés" sont générés et utilisés pour construire une matrice de similarité représentant tous les alignements structurels possibles dans les critères de coupure prédéfinis. Un chemin d'une protéine état de la structure à l'autre est alors tracée à travers la matrice en étendant l'alignement un fragment de plus en plus à la fois. Le chemin optimal comme définissant l'alignement combinatoire-extension. Un serveur en ligne mise en oeuvre du procédé et de fournir une base de données d'alignements par paires de structures dans la Protein Data Bank se trouve au Site Extension combinatoire.
L'analyse phylogénétique
Phylogenetics et l'alignement de séquence sont étroitement liés champs en raison de la nécessité d'évaluer partagé séquence parenté. Le domaine de la phylogénétique fait un usage intensif des alignements de séquences dans la construction et l'interprétation des arbres phylogénétiques, qui sont utilisés pour classer les relations évolutives entre homologues gènes représentés dans le génomes d'espèces divergentes. La mesure dans laquelle les séquences d'un ensemble de requêtes est qualitativement différent lié à distance évolutive des séquences les unes des autres. Grosso modo, l'identité de séquence élevée suggère que les séquences en question ont une relativement jeune le plus récent ancêtre commun, tout en bas identité suggère que la divergence est plus ancienne. Ce rapprochement, qui reflète la " horloge moléculaire "d'hypothèse qu'une vitesse à peu près constante de changement évolutif peut être utilisée pour extrapoler le temps écoulé depuis deux gènes premier divergent (ce est la temps de coalescence), on suppose que les effets de la mutation et de sélection sont constants à travers les lignées de séquence. Par conséquent, il ne tient pas compte d'une éventuelle différence entre les organismes ou espèces dans les taux de réparation de l'ADN ou de la conservation fonctionnelle possible des régions spécifiques dans une séquence. (Dans le cas de séquences nucléotidiques, l'hypothèse de l'horloge moléculaire dans sa forme la plus basique écarte aussi la différence des taux d'acceptation entre mutations silencieuses qui ne modifient pas le sens d'une donnée codon et d'autres mutations qui en résultent dans un autre acide aminé étant incorporés dans la protéine.) Plus statistiquement méthodes précises permettent le taux d'évolution de chaque branche de l'arbre phylogénétique de varier, produisant ainsi une meilleure estimations de temps de coalescence pour les gènes.
Techniques d'alignement multiple progressif produisent un arbre phylogénétique par nécessité parce qu'ils intègrent séquences dans l'alignement de plus en plus afin de parenté. D'autres techniques qui assemblent plusieurs alignements de séquences et arbres phylogénétiques marquer et trier arbres première et de calculer un alignement de séquences multiples de l'arbre le plus haut score. Méthodes couramment utilisées pour la construction de l'arbre phylogénétique sont principalement heuristique parce que le problème de la sélection de l'arborescence optimale, comme le problème de la sélection de l'alignement de séquences multiples optimale, est NP-difficile.
Évaluation de l'importance
Des alignements de séquences sont utiles en bioinformatique pour identifier similarité de séquence, produisant des arbres phylogénétiques, et le développement de modèles d'homologie de structures de protéines. Cependant, la pertinence biologique des alignements de séquences ne est pas toujours claire. Alignements sont souvent supposées refléter un degré de changement évolutionnaire entre les séquences descendent d'un ancêtre commun; cependant, il est formellement possible que évolution convergente peut se produire pour produire apparente similitude entre les protéines qui sont sans rapport avec l'évolution, mais exécuter des fonctions similaires et ont des structures similaires.
Dans les recherches de base de données tels que BLAST, des méthodes statistiques peuvent déterminer la probabilité d'un alignement particulier entre les séquences ou régions de séquence résultant par hasard étant donné la taille et la composition de la base de données consultée. Ces valeurs peuvent varier considérablement en fonction de l'espace de recherche. En particulier, la probabilité de trouver un alignement donné par hasard augmente si la base de données ne comprend que des séquences provenant du même organisme que la séquence de requête. Séquences répétitives dans la base de données ou d'une requête peut également fausser les deux les résultats de la recherche et l'évaluation de la signification statistique; BLAST filtre automatiquement ces séquences répétitives dans la requête pour éviter les coups apparentes qui sont des artefacts statistiques.
fonctions de notation
Le choix d'une fonction de score qui reflète les observations biologiques ou statistiques sur les séquences connues est important de produire de bons alignements. des séquences protéiques sont alignées en utilisant fréquemment matrices de substitution qui reflètent les probabilités de données à caractère caractères substitutions. Une série de matrices appelée Matrices PAM (matrices point Accepted Mutation, définies à l'origine par Margaret Dayhoff et parfois appelés «matrices Dayhoff") coder explicitement approximations évolutives concernant les taux et les probabilités de particuliers mutations d'acides aminés. Une autre série commune de matrices de notation, connu sous le nom BLOSUM (blocs Remplacement Matrix), code empirique probabilités de substitution. Des variantes de ces deux types de matrices sont utilisées pour détecter des séquences avec différents niveaux de divergence, permettant ainsi aux utilisateurs de BLAST ou FASTA pour restreindre les recherches aux matchs plus étroitement liés ou développer pour détecter des séquences les plus divergentes. pénalités de brèche représentent l'introduction d'un écart - sur le modèle évolutif, une mutation par insertion ou délétion - dans les deux séquences de nucleotides et de protéines, et par conséquent, les valeurs de pénalité devrait être proportionnelle à la vitesse attendue de telles mutations. La qualité des alignements produites dépend donc de la qualité de la fonction de notation.
Il peut être très utile et instructif d'essayer le même alignement à plusieurs reprises avec des choix différents pour matrice de notation et / ou valeurs de pénalité de gap et de comparer les résultats. Les régions où la solution est faible ou non unique peuvent souvent être identifiées par les régions qui observent de l'alignement sont robustes aux variations des paramètres d'alignement.
Les utilisations non-biologiques
Les méthodes utilisées pour l'alignement de séquence biologique ont également trouvé des applications dans d'autres domaines, notamment dans traitement du langage naturel. Techniques qui génèrent l'ensemble des éléments à partir desquels mots seront sélectionnés dans les algorithmes de génération en langage naturel ont emprunté de multiples techniques d'alignement de séquences de bioinformatique pour produire des versions linguistiques de preuves mathématiques générées par ordinateur. Dans le domaine de l'historique et comparative de la linguistique , l'alignement de séquence a été utilisé pour automatiser partiellement le méthode comparative qui linguistes reconstruire traditionnellement langues. D'affaires et de la recherche marketing a également présenté plusieurs techniques d'alignement de séquences à analyser série d'achats au fil du temps.
Logiciel
Outils logiciels courants utilisés pour les tâches d'alignement de séquence générale comprennent ClustalW et T-café pour l'alignement, et BLAST pour la recherche de base de données. Une liste plus complète des logiciels disponibles et classées par l'algorithme et le type d'alignement est disponible au un logiciel d'alignement de séquences.
Algorithmes et logiciels alignement peuvent être directement comparés les uns aux autres en utilisant un ensemble normalisé de Indice de référence alignements de séquences multiples connus comme BAliBASE. L'ensemble de données comprend des alignements structurels, ce qui peut être considéré comme une norme à laquelle des méthodes purement basés sur les séquences sont comparées. La performance relative des nombreuses méthodes d'alignement commune sur les problèmes d'alignement fréquemment rencontrés ont été les résultats sous forme de tableaux et sélectionnés publié en ligne à BAliBASE. Une liste complète des scores BAliBASE pour beaucoup (actuellement 12) différents outils d'alignement peuvent être calculées dans le plan de travail de la protéine STRAP.
