Алгоритм Нидлмана — Вунша

Алгоритм Нидлмана — Вунша — это алгоритм для выполнения выравнивания двух последовательностей (будем называть их и ), который используется в биоинформатике при построении выравниваний аминокислотных или нуклеотидных последовательностей. Алгоритм был предложен в 1970 году Солом Нидлманом и Кристианом Вуншем[1].

Алгоритм Нидлмана — Вунша является примером динамического программирования, и он оказался первым примером приложения динамического программирования к сравнению биологических последовательностей.

Современное представление

Соответствие выровненных символов задается матрицей схожести. Здесь  — похожесть символов и . Также используется линейный штраф за разрыв, называемый здесь .

Например, если матрица похожести задается таблицей

- A G C T
A 10 -1 -3 -4
G -1 7 -5 -3
C -3 -5 9 0
T -4 -3 0 8

то выравнивание:

 GTTAC‒‒
 G‒‒ACGT

со штрафом за разрыв будет иметь следующую оценку:

Для нахождения выравнивания с наивысшей оценкой назначается двумерный массив (или матрица) , содержащая столько же строк, сколько символов в последовательности , и столько же столбцов, сколько символов в последовательности . Запись в строке и столбце обозначается далее как . Таким образом, если мы выравниваем последовательности размеров и , то количество требуемой памяти будет . (Алгоритм Хиршберга[англ.] позволяет вычислять оптимальное выравнивание, используя количество памяти, но примерно вдвое большее время счета.)

В процессе работы алгоритма величина будет принимать значения оптимальной оценки для выравнивания первых символов в и первых символов в . Тогда принцип оптимальности Беллмана может быть сформулирован следующим образом:

  Базис:
  
  
  Рекурсия, основанная на принципе оптимальности:
  

Псевдо-код алгоритма для вычисления матрицы F представлен ниже:

  for i=0 to length(A)
    F(i,0) ← d*i
  for j=0 to length(B)
    F(0,j) ← d*j
  for i=1 to length(A)
    for j = 1 to length(B)
    {
      Match ← F(i-1,j-1) + S(Ai, Bj)
      Delete ← F(i-1, j) + d
      Insert ← F(i, j-1) + d
      F(i,j) ← max(Match, Insert, Delete)
    }

Когда матрица рассчитана, её элемент дает максимальную оценку среди всех возможных выравниваний. Для вычисления самого выравнивания, которое получило такую оценку, нужно начать с правой нижней клетки и сравнивать значения в ней с тремя возможными источниками (соответствие, вставка или удаление), чтобы увидеть, откуда оно появилось. В случае соответствия и выровнены, в случае удаления выровнено с разрывом, а в случае вставки с разрывом выровнено уже . (В общем случае может быть более одного варианта с одинаковым значением, которые приведут к альтернативным оптимальным выравниваниям.)

  AlignmentA ← ""
  AlignmentB ← ""
  i ← length(A)
  j ← length(B)
  while (i > 0 or 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(Ai, Bj))
    {
      AlignmentA ← Ai + AlignmentA
      AlignmentB ← Bj + AlignmentB
      i ← i - 1
      j ← j - 1
    }
    else if (Score == ScoreLeft + d)
    {
      AlignmentA ← Ai + AlignmentA
      AlignmentB ← "-" + AlignmentB
      i ← i - 1
    }
    otherwise (Score == ScoreUp + d)
    {
      AlignmentA ← "-" + AlignmentA
      AlignmentB ← Bj + AlignmentB
      j ← j - 1
    }
  }
  while (i > 0)
  {
    AlignmentA ← Ai + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  while (j > 0)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← Bj + AlignmentB
    j ← j - 1
  }

Исторические замечания

Нидлман и Вунш описали свой алгоритм в явном виде для случая, когда оценивается только соответствие или несоответствие символов, но не разрыв (). В оригинальной публикации[1] от 1970 года предлагается рекурсия

Соответствующий алгоритм динамического программирования требует кубического времени для расчета. В статье также указывается, что рекурсия может быть адаптирована и на случай любой формулы для штрафа за разрыв:

Штраф за разрыв — число, вычитаемое за каждый разрыв, — может рассматриваться, как помеха появлению разрывов в выравнивании. Величина штрафа за разрыв может быть функцией размера и/или направления разрыва. [стр. 444]

Более быстрый алгоритм динамического программирования с квадратичным временем выполнения для той же задачи (нет штрафа за разрыв) был впервые предложен[2] Давидом Санкофф в 1972. Аналогичный квадратичный по времени алгоритм был независимо открыт Т. К. Винцюком[3] в 1968 для обработке речи (динамическое предыскажение шкалы) и Робертом А. Вагнером и Майклом Дж. Фишером[4] в 1974 для сопоставления строк.

Нидлман и Вунш сформулировали свою задачу в терминах максимизации похожести. Другая возможность заключается в минимизации редакционного расстояния между последовательностями, предложенной В. Левенштейном, однако было показано[5], что две эти задачи эквивалентны.

В современной терминологии «Нидлман — Вунш» относится к алгоритму выравнивания последовательностей квадратичному по времени для линейного или аффинного штрафа за разрыв.

См. также

Примечания

  1. 1 2 Needleman, Saul B.; and Wunsch, Christian D. A general method applicable to the search for similarities in the amino acid sequence of two proteins (англ.) // Journal of Molecular Biology[англ.] : journal. — 1970. — Vol. 48, no. 3. — P. 443—453. — doi:10.1016/0022-2836(70)90057-4. — PMID 5420325. Архивировано 26 апреля 2018 года.
  2. Sankoff, D. Matching sequences under deletion/insertion constraints (англ.) // Proceedings of the National Academy of Sciences of the United States of America : journal. — 1972. — Vol. 69, no. 1. — P. 4—6. Архивировано 24 сентября 2015 года.
  3. Vintsyuk, T. K. Speech discrimination by dynamic programming (неопр.) // Kibernetika. — 1968. — Т. 4. — С. 81—88.
  4. Wagner, R. A. and Fischer, M. J. The string-to-string correction problem (англ.) // Journal of the ACM : journal. — 1974. — Vol. 21. — P. 168—173. — doi:10.1145/321796.321811.
  5. Sellers, P. H. On the theory and computation of evolutionary distances (англ.) // SIAM Journal on Applied Mathematics[англ.] : journal. — 1974. — Vol. 26, no. 4. — P. 787—793.

Ссылки

Read other articles:

American actor Justin KirkKirk at the 2017 WonderConBorn (1969-05-28) May 28, 1969 (age 54)Salem, Oregon, U.S.EducationCircle in the Square Theatre SchoolOccupationActorYears active1990–present Justin Kirk (born May 28, 1969[1]) is an American actor. He gained prominence for his roles as Prior Walter in the HBO miniseries Angels in America (2003), for which he received a nomination for the Primetime Emmy Award for Outstanding Supporting Actor in a Miniseries or a Movie, an...

 

Voce principale: Novara Calcio. AC NovaraStagione 1970-1971 Sport calcio Squadra Novara Allenatore Carlo Parola Comm. straordinario Santino Tarantola Serie B11º Coppa ItaliaSpareggio di qualificazione Maggiori presenzeCampionato: F. Pulici (38)Totale: F. Pulici (42) Miglior marcatoreCampionato: Jacomuzzi (8)Totale: Gabetto, Jacomuzzi (8) 1969-1970 1971-1972 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'Associazione Calcio Novara nelle co...

 

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

1931 book by Ruth Plumly Thompson Pirates in Oz Cover of Pirates in Oz.AuthorRuth Plumly ThompsonIllustratorJohn R. NeillCountryUnited StatesLanguageEnglishSeriesThe Oz BooksGenreChildren's novelPublisherReilly & LeePublication date1931Media typePrint (Hardcover)Preceded byThe Yellow Knight of Oz Followed byThe Purple Prince of Oz  Children's literature portalNovels portal Pirates in Oz (1931) is the twenty-fifth in the series of Oz books created by L. Frank Baum ...

 

Coordinate: 18°57′43″S 22°29′04″E / 18.961944°S 22.484444°E-18.961944; 22.484444 Disambiguazione – Se stai cercando altri significati, vedi Kavango. Okavango (Cubango)Stati Angola Namibia Botswana SuddivisioniHuambo (Angola)Bié (Angola)Cuando Cubango (Angola)Kavango (Namibia)Zambesi (Namibia)Distretto Nordoccidentale (Botswana) Lunghezza1 600 km Portata media500 m³/s Bacino idrografico530 000 km² NasceSierra de Moco, Angola SfociaDelta...

 

English football referee Scott Duncan Duncan refereeing in 2014Born Newcastle upon Tyne, EnglandDomesticYears League Role2008–2012 Football Conference Referee2010–2012 The Football League Assistant referee2012–2020 The Football League Referee Scott Duncan is an English former association football referee who officiated in the Football League. He first refereed in the Football Conference in 2008, and became an assistant referee in the Football League two years later. Duncan began referee...

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题,请协助参考外语维基百科扩充条目。请勿直接提交机械翻译,也不要翻译不可靠、低品质内容。依版权协议,译文需在编辑摘要注明来源,或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌:《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

 

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

 

Halaman ini berisi artikel tentang kabupaten. Untuk kecamatan bernama sama, lihat Kecamatan Ngawi. Ngawi beralih ke halaman ini. Untuk kegunaan lain, lihat Ngawi (disambiguasi). NgawiKabupatenTranskripsi bahasa daerah • Hanacarakaꦔꦮꦶ • Pegonڠاوي • Alfabet JawaNgawìDari atas ke bawah: Monumen Soerjo, Patung Gajah di Museum Trinil, Kebun teh Jamus, Benteng Van den Bosch, Air terjun Srambang di Jogorogo, Waduk Pondok di Bringin BenderaLambangJu...

Application allowing for the conversion of files to PDFs PDFCreatorDeveloper(s)pdfforge GmbHStable release4.4[1] (September 1, 2021; 2 years ago (2021-09-01)) [±] Repositorygithub.com/pdfforge/PDFCreator Written inC#Operating systemMicrosoft WindowsAvailable inMultilingual[2]TypePDF printer/creator/ AdwareLicenseMixed proprietary and open-source:[3] GNU AGPL Ghostscript: GNU GPL pdfcmon.dll: pdfforge Freeware License iTextSharp.dll: GNU A...

 

Pemberian antiserum meningitis Antiserum merupakan sebuah sediaan yang berisi antibodi dan antigen yang umumnya berupa mikroorganisme yang telah dilemahkan atau dimatikan.[1] Antiserum biasanya diberikan pada saat imunisasi, yang dilakukan bila seseorang terkena penyakit infeksius yang berbahaya seperti rabies.[1] Antiserum menyediakan perlindungan yang cepat untuk melawan mikroorganisme infeksius ketika pembentukan imun sedang berkembang, sedangkan vaksinasi memerlukan proses...

 

British Whig politician The Right HonourableThe Viscount EversleyGCB PCLord Eversley, 1875 portraitSpeaker of the House of Commonsof the United KingdomIn office27 May 1839 – 30 April 1857MonarchVictoriaPrime MinisterWilliam LambJohn RussellEdward Smith-StanleyGeorge Hamilton-GordonHenry John TemplePreceded byHon. James AbercrombySucceeded bySir Evelyn Denison Personal detailsBorn22 February 1794 (1794-02-22)London, EnglandDied28 December 1888(1888-12-28) (aged 94)Politica...

Antonio Grilli Deputato della Repubblica ItalianaLegislaturaIII, IV, VI GruppoparlamentareMSI CollegioAncona Sito istituzionale Dati generaliPartito politicoMSI (III-IV), MSI-DN (VI) Titolo di studioLicenza media superiore Professionedirigente scolastico Antonio Grilli (Ascoli Piceno, 26 dicembre 1922 – 8 settembre 2005) è stato un politico italiano. Indice 1 Biografia 2 Incarichi 3 Note 4 Altri progetti 5 Collegamenti esterni Biografia Fu parlamentare nella terza e quarta e...

 

1996 compilation album by Sarah McLachlanRarities, B-Sides & Other StuffCompilation album by Sarah McLachlanReleased17 June 1996Recorded1988–1995GenrePopLength56:00LabelNettwerkProducerPierre Marchand, Greg Reely, Sarah McLachlan, Gary StokesSarah McLachlan chronology The Freedom Sessions(1994) Rarities, B-Sides & Other Stuff(1996) Surfacing(1997) Professional ratingsReview scoresSourceRatingAllmusic[1] Rarities, B-Sides & Other Stuff is a 1996 album by Sarah Mc...

 

Jamné nad OrlicíComune Jamné nad Orlicí – Veduta LocalizzazioneStato Rep. Ceca Regione Pardubice DistrettoÚstí nad Orlicí AmministrazioneSindacoJosef Černohous TerritorioCoordinate50°02′23″N 16°37′58″E50°02′23″N, 16°37′58″E (Jamné nad Orlicí) Altitudine596 m s.l.m. Superficie10,59[1] km² Abitanti693[2] (1-1-2011) Densità65,44 ab./km² Altre informazioniCod. postale561 65 e 561 64 Fuso orarioUTC+1 Codice ČS�...

Duo komedi Razor Ramon HG dan Razor Ramon RG Owarai (お笑いcode: ja is deprecated ) adalah kata yang digunakan untuk mendeskripsikan komedi Jepang seperti yang terlihat di televisi. Kata owarai adalah bentuk honorifik dari kata warai (dengan menambahkan awalan o-), yang berarti tawa atau senyum. Owarai sering dijumpai pada acara ragam Jepang dan para komediannya disebut sebagai owarai geinin atau owarai tarento. Karakteristik Lihat pula: Daftar istilah owarai Manzai (漫才), sebuah bentuk...

 

Village in Guam, United StatesYigo, GuamVillageRitidian Point, the northernmost point on Guam, in the Guam National Wildlife RefugeLocation of Yigo within the Territory of Guam.CountryUnited StatesTerritoryGuamGovernment • MayorAnthony Tony P. Sanchez (R) • Vice MayorLoreto V. Leones (R)Area • Total35 sq mi (90 km2)Elevation587 ft (179 m)Population (2020)[1] • Total19,339Time zoneUTC+10 (ChST) Yigo, Guam (Ch...

 

2007 video game 2007 video gameAce Combat 6: Fires of LiberationDeveloper(s)Project AcesPublisher(s)Namco Bandai GamesDirector(s)Natsuki IsakiProducer(s)Hiroyuki IchiyanagiDesigner(s)Toshiyuki IshiiWriter(s)Toshiyuki IshiiComposer(s)Tetsukazu NakanishiRyuichi TakadaKeiki KobayashiHiroshi OkuboJunichi NakatsuruSeriesAce CombatPlatform(s)Xbox 360ReleaseNA: October 23, 2007JP: November 1, 2007EU: November 23, 2007AU: December 13, 2007Genre(s)Air combat simulationMode(s)Single-player, multiplayer...

Political party in Spain Galician Nationalist Bloc Bloque Nacionalista GalegoSpokespersonAna PontónFounded1982 (1982)Merger ofGalician People's UnionGalician National-Popular AssemblyGalician Socialist PartyIndependentsHeadquartersAv. de Rodríguez de Viguri, 16, 15703, Santiago de CompostelaNewspaperBenegá ao díaStudent wingErguer-Estudantes da GalizaYouth wingGaliza NovaMembership (2019) 7,800[1][2]IdeologyMajority:Galician nationalism[3][4]...

 

Christian teachings of Anglican churches Part of a series onAnglicanism TheologyChristian theologyAnglican doctrineThirty-nine ArticlesBooks of HomiliesCaroline DivinesChicago–Lambeth QuadrilateralEpiscopal politySacramentsMary Ministry and worshipMinistryMusicEucharistKing James Version (Book of Common Prayer)Liturgical yearChurchmanship (High, Low, Central, Broad)MonasticismSaintsJesus Prayer ChristianityJesus ChristPaulChristian ChurchFirst seven ecumenical councils Background and histor...