| dbo:abstract
|
- L'algorisme de Needleman–Wunsch és un algorisme àmpliament utilitzat en bioinformàtica per a l'alineament global de seqüències proteiques o nucleotídiques. L'algorisme va ser proposar per primera per i el 1970. L'algorisme de Needleman–Wunsch és un exemple de programació dinàmica i es considera la primera aplicació de programació dinàmica en la comparació de seqüències biològiques. (ca)
- Needlemanův-Wunschův algoritmus je jedním ze základních algoritmů bioinformatiky. Provádí globální zarovnání sekvencí (tedy takové, ve kterém je v každé části zarovnání brán ohled na celou sekvenci) dovolující mezery, nejčastěji jde o sekvence nukleotidů v nukleových kyselinách či sekvence aminokyselin v proteinech. Jde o algoritmus dynamického programování, je to první algoritmus tohoto druhu použitý pro srovnávání biologických sekvencí. Byl sestaven v roce 1970 Saulem B. Needlemanem a Christianem D. Wunschem. (cs)
- Der Needleman-Wunsch-Algorithmus ist ein Optimierungsalgorithmus aus der Bioinformatik. Dort wird er zum Vergleich zweier Nukleotid- bzw. Aminosäuresequenzen eingesetzt. Er berechnet anhand eines Modells den optimalen globalen Similarity-Score bzw. mit Hilfe von Backtracking ein oder mehrere optimale globale Alignments zwischen zwei Sequenzen. Der Similarity-Score ist ein Maß für die Ähnlichkeit zweier Sequenzen; je höher der Score, umso ähnlicher sind die Sequenzen unter dem angewendeten Scoring-Modell. Der Algorithmus optimiert den Score des Alignments. Dabei ist ein Alignment eine Folge von Editierschritten, um die erste Sequenz in die zweite zu überführen. Für zwei nichttriviale Sequenzen gibt es viele Alignments – ein optimales Alignment hat einen maximalen Similarity-Score. Der Algorithmus verwendet die Methode der dynamischen Programmierung und erlaubt beliebige Scoring-Modelle (d. h. die Verwendung allgemeiner Gap-Kosten) für die Editierschritte. (de)
- Ο αλγόριθμος Νίντλμαν-Βουνς (Needleman-Wunsch) είναι ένας αλγόριθμος που χρησιμοποιείται για ολική στοίχιση ακολουθιών. Συγκεκριμένα χρησιμοποιείται για να υπολογιστεί η βέλτιστη ολική στοίχιση μεταξύ δύο ακολουθιών - συμβολοσειρών, μια διαδικασία ιδιαίτερα χρήσιμη σε διάφορους τομείς, όπως για παράδειγμα στη βιοπληροφορική. Ο συγκεκριμένος αλγόριθμος ανήκει στη φιλοσοφία αλγορίθμων δυναμικού προγραμματισμού. (el)
- El algoritmo de Needleman-Wunsch sirve para realizar alineamientos globales de dos secuencias. Se suele utilizar en el ámbito de la bioinformática para alinear secuencias de proteínas o de ácidos nucleicos.Fue propuesto por primera vez en 1970, por Saul Needleman y Christian Wunsch. Se trata de un ejemplo típico deprogramación dinámica. El algoritmo funciona del mismo modo independientemente de la complejidad o longitud de las secuencias y garantiza la obtención del mejor alineamiento. Las dos secuencias a alinear, llamadas A y B en los ejemplos, de longitud y , están formadas por elementos de un alfabeto finito de símbolos.El algoritmo necesita saber qué símbolos son diferentes entre sí y cuáles son iguales. Podemos utilizar una matriz cuadrada (S) para este propósito, en la que cada elemento indique la similitud entre los elementos i y j del alfabeto usado. Si nuestro alfabeto de símbolos no fuese finito, en vez de una matriz podríamos usar una función que tuviese como parámetros ambos símbolos a comparar y cuya salida fuese la similitud entre ambos. También se necesita otro parámetro (d) que nos indique cómo vamos a valorar que un símbolo no quede alineado con otro y que en su lugar se utilice un hueco. Por ejemplo podemos definir la siguiente matriz: Y entonces el siguiente alineamiento: AGACTAGTTACCGA---GACGT con una penalización por hueco de nos devolvería como solución óptima: Para determinar la puntuación óptima y poder reconstruir el alineamiento que devolvería esa puntuación se necesita otra matriz, F, que almacena los resultados parciales de cada posible alineamiento. Las dimensiones de la matriz F son el número de elementos en la secuencia A y el de B. En cada iteración del algoritmo recibe valor un elemento de la matriz F. El valor que recibe el elemento representa la puntuación obtenida al alinear de forma óptima los primeros i elementos de A y los primeros j de B. Cuando el algoritmo termine, el último elemento de F contendrá la puntuación para el alineamiento óptimo de ambas secuencias. Inicio del algoritmo: Recursión para obtener el siguiente elemento de forma óptima: La matriz F se calcula con el siguiente algoritmo: for i=0 to length(A)-1 F(i,0) <- d*i for j=0 to length(B)-1 F(0,j) <- d*j for i=1 to length(A) for j = 1 to length(B) { Choice1 <- F(i-1,j-1) + S(A(i), B(j)) Choice2 <- F(i-1, j) + d Choice3 <- F(i, j-1) + d F(i,j) <- max(Choice1, Choice2, Choice3) } Cuando el algoritmo acaba tenemos calculada la matriz F; el resultado es la puntuación devuelta por el mejor alineamiento posible, de acuerdo a los parámetros que hemos definido. Para obtener la secuencia se necesita ejecutar el siguiente algoritmo, que hace uso de la matriz F. Este algoritmo comienza por el último elemento, , y va retrocediendo hasta llegar a un elemento de la primera fila o la primera columna de F. En cada paso se comparan 3 elementos de F para ver cuál de ellos es el que se ha seguido en la solución óptima. Para cada debemos comparar y . Si el elemento usado es , entonces se ha alineado con un hueco; si es , entonces se ha alineado con un hueco; y si no, si el elemento elegido es , los elementos y han sido alineados. Es importante destacar que el que dos elementos sean alineados no implica necesariamente que sean iguales; significa que entre esa posibilidad, alinear con huecos o alinear símbolos diferentes, esa era la mejor opción. El pseudo-algoritmo que permite obtener el alineamiento correcto es el siguiente: AlignmentA <- "" AlignmentB <- "" i <- length(A) j <- length(B) while (i > 0 AND j > 0) { Score <- F(i,j) ScoreDiag <- F(i - 1, j - 1) ScoreUp <- F(i, j - 1) ScoreLeft <- F(i - 1, j) if (Score == ScoreDiag + S(A(i), B(j))) { AlignmentA <- A(i-1) + AlignmentA AlignmentB <- B(j-1) + AlignmentB i <- i - 1 j <- j - 1 } else if (Score == ScoreLeft + d) { AlignmentA <- A(i-1) + AlignmentA AlignmentB <- "-" + AlignmentB i <- i - 1 } otherwise (Score == ScoreUp + d) { AlignmentA <- "-" + AlignmentA AlignmentB <- B(j-1) + AlignmentB j <- j - 1 } } while (i > 0) { AlignmentA <- A(i-1) + AlignmentA AlignmentB <- "-" + AlignmentB i <- i - 1 } while (j > 0) { AlignmentA <- "-" + AlignmentA AlignmentB <- B(j-1) + AlignmentB j <- j - 1 } Se puede demostrar formalmente que tanto el tiempo de ejecución como el espacio necesario para ejecutar el algoritmo son de ordenO(nm). Para alguna aplicaciones, sobre todo en bioinformática, el requerimiento de espacio es prohibitivo, puesto que se alinean secuencias muy largas. Existe una optimización de este algoritmo, denominada , que solo necesita espacio del orden O(m+n), pero a costa de incrementar el tiempo de computación. (es)
- The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences. It was one of the first applications of dynamic programming to compare biological sequences. The algorithm was developed by Saul B. Needleman and Christian D. Wunsch and published in 1970. The algorithm essentially divides a large problem (e.g. the full sequence) into a series of smaller problems, and it uses the solutions to the smaller problems to find an optimal solution to the larger problem. It is also sometimes referred to as the optimal matching algorithm and the global alignment technique. The Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance. The algorithm assigns a score to every possible alignment, and the purpose of the algorithm is to find all possible alignments having the highest score. (en)
- L'algorithme de Needleman-Wunsch est un algorithme qui effectue un alignement global maximal de deux chaînes de caractères. Il est couramment utilisé en bio-informatique pour aligner des séquences de protéines ou de nucléotides. L'algorithme a été présenté en 1970 par et dans leur article A general method applicable to the search for similarities in the amino acid sequence of two proteins. L'algorithme de Needleman-Wunsch est un exemple de programmation dynamique, tout comme l'algorithme de Wagner et Fischer pour le calcul de la distance de Levenshtein auquel il est apparenté. Il garantit de trouver l'alignement de score maximal. Ce fut la première application de la programmation dynamique pour la comparaison de séquences biologiques. Les scores pour les caractères alignés sont spécifiés par une matrice de similarité. Ici, est la similarité des caractères i et j. Elle utilise une 'pénalité de trou', appelée ici d. (fr)
- Algorytm Needlemana-Wunscha – algorytm oparty na programowaniu dynamicznym, umożliwiający znalezienie optymalnego globalnego dopasowania dwóch sekwencji. Jest często wykorzystywany w bioinformatyce jako jedno z narzędzi do poszukiwania uliniowienia sekwencji nukleotydowych lub aminokwasowych. Został stworzony przez Saul B. Needleman’a i Christian D. Wunsch’a oraz opublikowany w roku 1970. Dzieli on większy problem obliczeniowy (np. całą sekwencję) na mniejsze problemy, i używa rozwiązań mniejszych problemów do znalezienia optymalnego rozwiązania dużego problemu. (pl)
- O algoritmo Needleman–Wunsch tem por objetivo realizar o alinhamento de seqüências global de duas seqüências (denominadas aqui de A e B). Este algoritmo é frequentemente utilizado em Bioinformática para alinhar seqüências de proteínas ou nucleotídeos. O algoritmo foi proposto na década de 1970 por Saul Needleman e Christian Wunsch. Este algoritmo é um exemplo de programação dinâmica e foi a primeira aplicação desta técnica a comparação de sequências biológicas. O primeiro elemento necessário é uma matriz de pesos (scores). Aqui, mede a similaridade entre os caracteres i e j. Usa-se uma penalidade para espaços (gap penalty) linear d. Um exemplo de matriz seria: então o alinhamento: AGACTAGTTAC CGA---GACGT com gap penalty de -5, deveria ter o score: Para encontrar o alinhamento com o maior score, uma matriz F é alocada. Há uma coluna para caractere da sequência A e uma linha para cada caractere da sequência B. À medida que o algoritmo avança, a matriz é preenchida com o score ótimo do alinhamento entre os i primeiros caracteres de A e os j primeiros de B. O princípio de optimização é aplicado como segue: Base: Recursão, baseada no princípio de otimização: O pseudo-código para o algoritmo que calcula F é como segue (índice 0 representa 1a posição): for i=0 to length(A)-1 F(i,0) ← d*i for j=0 to length(B)-1 F(0,j) ← d*j for i=1 to length(A) for j = 1 to length(B) { Choice1 ← F(i-1,j-1) + S(A(i-1), B(j-1)) Choice2 ← F(i-1, j) + d Choice3 ← F(i, j-1) + d F(i,j) ← max(Choice1, Choice2, Choice3) } Quando a matriz F é calculada, o elemento na posição do canto direito inferior da matriz é o score máximo para qualquer alinhamento. Para descobrir qual é o alinhamento que de fato dá este score, deve-se iniciar uma caminhada da posição direita inferior e ir-se comparando este valor com as 3 possíveis fontes (Choice1, Choice2, e Choice3 acima) para descobrir-se de onde este veio. Se veio de Choice1, então A(i) e B(i) estão alinhados. Se veio de Choice2 então A(i) está alinhado com um gap, e se veio de Choice3 então B(i) está alinhado com o gap. AlignmentA ← "" AlignmentB ← "" i ← length(A) j ← length(B) while (i > 0 AND j > 0) { Score ← F(i,j) ScoreDiag ← F(i - 1, j - 1) ScoreUp ← F(i, j - 1) ScoreLeft ← F(i - 1, j) if (Score == ScoreDiag + S(A(i-1), B(j-1))) { AlignmentA ← A(i-1) + AlignmentA AlignmentB ← B(j-1) + AlignmentB i ← i - 1 j ← j - 1 } else if (Score == ScoreLeft + d) { AlignmentA ← A(i-1) + AlignmentA AlignmentB ← "-" + AlignmentB i ← i - 1 } otherwise (Score == ScoreUp + d) { AlignmentA ← "-" + AlignmentA AlignmentB ← B(j-1) + AlignmentB j ← j - 1 } } while (i > 0) { AlignmentA ← A(i-1) + AlignmentA AlignmentB ← "-" + AlignmentB i ← i - 1 } while (j > 0) { AlignmentA ← "-" + AlignmentA AlignmentB ← B(j-1) + AlignmentB j ← j - 1 } (pt)
- Алгоритм Нидлмана — Вунша — это алгоритм для выполнения выравнивания двух последовательностей (будем называть их и ), который используется в биоинформатике при построении выравниваний аминокислотных или нуклеотидных последовательностей. Алгоритм был предложен в 1970 году и . Алгоритм Нидлмана — Вунша является примером динамического программирования, и он оказался первым примером приложения динамического программирования к сравнению биологических последовательностей. (ru)
- Алгоритм Нідлмана — Вунша (англ. Needleman–Wunsch algorithm) — один із алгоритмів вирівнювання послідовностей, який належить до динамічного програмування, та є глобальним вирівнюванням. Складається цей алгоритм із трьох послідовних етапів: 1. Побудова ініціюючої матриці Для цього дві порівнювані послідовності розташовують як верхній рядок і як нижні, тобто вони є заголовками матриці. Крім того перед кожною послідовністю виставляють пропуск. І заповнюють перший стовпчик і перший рядок. Заповнення відбувається за допомогою штафу за пенальті (так як найперше значення в рядку і стовпчику — це пропуск, отже, і перший рядок із стовпичок будуть заповнені від'ємними значеннями). [1] [Архівовано 13 серпня 2016 у Wayback Machine.] 2. Заповнення таблиці Заповнення комірки відбувається за такою математичною формулою: де — значення в певній комірці, — очки за збіжність амінокислоти x та амінокислоти y в певних рядках, d — штаф пенальті (заданий).[2] [Архівовано 13 серпня 2016 у Wayback Machine.] На основі цієї матриці будується матриця локалізації. Слідкують за тим, як відбувалося заповнення, тобто з якої комірки було отримано максимальне значення для наступної комірки. [3] [Архівовано 5 березня 2016 у Wayback Machine.] 3. Пошук максимального вирівнювання Пошук починають із останньої кутової комірки, а завершують завжди найпершою коміркою. Вирівнювання відбувається таким чином: необхідно на основі матриці локалізації створити шлях, який ґрунтується на «вказівках» кожної комірки. Буква D — діагональ, тобто необхідно перейти на комірку, що розташована по діагоналі, T — вершина, треба перейти на 1 комірку вгору (біологічно це означає, що у горизонтальній послідовності була делеція, або у вертикальній — інсерція), L — вліво, треба перейти до комірки, розташованої праворуч (біологічний сенс обернений до попереднього). Якщо комірка має два значення, то можливі два напрямки руху, три — три.[4] [Архівовано 5 березня 2016 у Wayback Machine.] Червона стрілка позначає вирівнювання, після якого послідовності розташовуються в два ряди разом із вирахуваними пропусками. Якщо є кілька маршрутів вирівнювання, то і вирівнювань буде стільки ж. (uk)
- 尼德曼-翁施算法（英語：Needleman-Wunsch Algorithm）是基于生物信息学的知识来匹配蛋白序列或者DNA序列的算法。这是将动态算法应用于生物序列的比较的最早期的几个实例之一。该算法是由 Saul B. Needlman和 Christian D. Wunsch 两位科学家于1970年发明的。本算法高效地解决了如何将一个庞大的数学问题分解为一系列小问题，并且从一系列小问题的解决方法重建大问题的解决方法的过程。该算法也被称为优化匹配算法和整体序列比较法。时至今日尼德曼-翁施算法仍然被广泛应用于优化整体序列比较中。 (zh)
|
| rdfs:comment
|
- L'algorisme de Needleman–Wunsch és un algorisme àmpliament utilitzat en bioinformàtica per a l'alineament global de seqüències proteiques o nucleotídiques. L'algorisme va ser proposar per primera per i el 1970. L'algorisme de Needleman–Wunsch és un exemple de programació dinàmica i es considera la primera aplicació de programació dinàmica en la comparació de seqüències biològiques. (ca)
- Needlemanův-Wunschův algoritmus je jedním ze základních algoritmů bioinformatiky. Provádí globální zarovnání sekvencí (tedy takové, ve kterém je v každé části zarovnání brán ohled na celou sekvenci) dovolující mezery, nejčastěji jde o sekvence nukleotidů v nukleových kyselinách či sekvence aminokyselin v proteinech. Jde o algoritmus dynamického programování, je to první algoritmus tohoto druhu použitý pro srovnávání biologických sekvencí. Byl sestaven v roce 1970 Saulem B. Needlemanem a Christianem D. Wunschem. (cs)
- Ο αλγόριθμος Νίντλμαν-Βουνς (Needleman-Wunsch) είναι ένας αλγόριθμος που χρησιμοποιείται για ολική στοίχιση ακολουθιών. Συγκεκριμένα χρησιμοποιείται για να υπολογιστεί η βέλτιστη ολική στοίχιση μεταξύ δύο ακολουθιών - συμβολοσειρών, μια διαδικασία ιδιαίτερα χρήσιμη σε διάφορους τομείς, όπως για παράδειγμα στη βιοπληροφορική. Ο συγκεκριμένος αλγόριθμος ανήκει στη φιλοσοφία αλγορίθμων δυναμικού προγραμματισμού. (el)
- Algorytm Needlemana-Wunscha – algorytm oparty na programowaniu dynamicznym, umożliwiający znalezienie optymalnego globalnego dopasowania dwóch sekwencji. Jest często wykorzystywany w bioinformatyce jako jedno z narzędzi do poszukiwania uliniowienia sekwencji nukleotydowych lub aminokwasowych. Został stworzony przez Saul B. Needleman’a i Christian D. Wunsch’a oraz opublikowany w roku 1970. Dzieli on większy problem obliczeniowy (np. całą sekwencję) na mniejsze problemy, i używa rozwiązań mniejszych problemów do znalezienia optymalnego rozwiązania dużego problemu. (pl)
- Алгоритм Нидлмана — Вунша — это алгоритм для выполнения выравнивания двух последовательностей (будем называть их и ), который используется в биоинформатике при построении выравниваний аминокислотных или нуклеотидных последовательностей. Алгоритм был предложен в 1970 году и . Алгоритм Нидлмана — Вунша является примером динамического программирования, и он оказался первым примером приложения динамического программирования к сравнению биологических последовательностей. (ru)
- 尼德曼-翁施算法（英語：Needleman-Wunsch Algorithm）是基于生物信息学的知识来匹配蛋白序列或者DNA序列的算法。这是将动态算法应用于生物序列的比较的最早期的几个实例之一。该算法是由 Saul B. Needlman和 Christian D. Wunsch 两位科学家于1970年发明的。本算法高效地解决了如何将一个庞大的数学问题分解为一系列小问题，并且从一系列小问题的解决方法重建大问题的解决方法的过程。该算法也被称为优化匹配算法和整体序列比较法。时至今日尼德曼-翁施算法仍然被广泛应用于优化整体序列比较中。 (zh)
- Der Needleman-Wunsch-Algorithmus ist ein Optimierungsalgorithmus aus der Bioinformatik. Dort wird er zum Vergleich zweier Nukleotid- bzw. Aminosäuresequenzen eingesetzt. Er berechnet anhand eines Modells den optimalen globalen Similarity-Score bzw. mit Hilfe von Backtracking ein oder mehrere optimale globale Alignments zwischen zwei Sequenzen. Der Similarity-Score ist ein Maß für die Ähnlichkeit zweier Sequenzen; je höher der Score, umso ähnlicher sind die Sequenzen unter dem angewendeten Scoring-Modell. Der Algorithmus optimiert den Score des Alignments. Dabei ist ein Alignment eine Folge von Editierschritten, um die erste Sequenz in die zweite zu überführen. Für zwei nichttriviale Sequenzen gibt es viele Alignments – ein optimales Alignment hat einen maximalen Similarity-Score. Der Algor (de)
- El algoritmo de Needleman-Wunsch sirve para realizar alineamientos globales de dos secuencias. Se suele utilizar en el ámbito de la bioinformática para alinear secuencias de proteínas o de ácidos nucleicos.Fue propuesto por primera vez en 1970, por Saul Needleman y Christian Wunsch. Se trata de un ejemplo típico deprogramación dinámica. El algoritmo funciona del mismo modo independientemente de la complejidad o longitud de las secuencias y garantiza la obtención del mejor alineamiento. Por ejemplo podemos definir la siguiente matriz: Y entonces el siguiente alineamiento: AGACTAGTTACCGA---GACGT (es)
- The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences. It was one of the first applications of dynamic programming to compare biological sequences. The algorithm was developed by Saul B. Needleman and Christian D. Wunsch and published in 1970. The algorithm essentially divides a large problem (e.g. the full sequence) into a series of smaller problems, and it uses the solutions to the smaller problems to find an optimal solution to the larger problem. It is also sometimes referred to as the optimal matching algorithm and the global alignment technique. The Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance. The algorithm assign (en)
- L'algorithme de Needleman-Wunsch est un algorithme qui effectue un alignement global maximal de deux chaînes de caractères. Il est couramment utilisé en bio-informatique pour aligner des séquences de protéines ou de nucléotides. L'algorithme a été présenté en 1970 par et dans leur article A general method applicable to the search for similarities in the amino acid sequence of two proteins. Les scores pour les caractères alignés sont spécifiés par une matrice de similarité. Ici, est la similarité des caractères i et j. Elle utilise une 'pénalité de trou', appelée ici d. (fr)
- O algoritmo Needleman–Wunsch tem por objetivo realizar o alinhamento de seqüências global de duas seqüências (denominadas aqui de A e B). Este algoritmo é frequentemente utilizado em Bioinformática para alinhar seqüências de proteínas ou nucleotídeos. O algoritmo foi proposto na década de 1970 por Saul Needleman e Christian Wunsch. Este algoritmo é um exemplo de programação dinâmica e foi a primeira aplicação desta técnica a comparação de sequências biológicas. então o alinhamento: AGACTAGTTAC CGA---GACGT com gap penalty de -5, deveria ter o score: (pt)
- Алгоритм Нідлмана — Вунша (англ. Needleman–Wunsch algorithm) — один із алгоритмів вирівнювання послідовностей, який належить до динамічного програмування, та є глобальним вирівнюванням. Складається цей алгоритм із трьох послідовних етапів: 1. Побудова ініціюючої матриці 2. Заповнення таблиці Заповнення комірки відбувається за такою математичною формулою: де — значення в певній комірці, — очки за збіжність амінокислоти x та амінокислоти y в певних рядках, d — штаф пенальті (заданий).[2] [Архівовано 13 серпня 2016 у Wayback Machine.] 3. Пошук максимального вирівнювання (uk)
|
