Jelaskan Perataan urutan dari Pemrograman dinamis

Dalam genetika, perataan urutan adalah aplikasi penting di mana pemrograman dinamis sangat penting.  Biasanya, masalahnya terdiri dari mengubah satu urutan menjadi urutan lain menggunakan operasi edit yang mengganti, menyisipkan, atau menghapus elemen.  Setiap operasi memiliki biaya terkait, dan tujuannya adalah menemukan urutan pengeditan dengan total biaya terendah.

Masalahnya dapat dinyatakan secara alami sebagai rekursi, urutan A diedit secara optimal menjadi urutan B dengan baik:

memasukkan karakter pertama B, dan melakukan penyelarasan optimal A dan ekor B

menghapus karakter pertama A, dan melakukan penyelarasan optimal pada ekor A dan B

mengganti karakter pertama A dengan karakter pertama B, dan melakukan penjajaran optimal pada ekor A dan B.

Perataan parsial bisa ditabulasi dalam matriks, di mana sel (i,j) berisi biaya penyelarasan yang optimal A[1..i] ke B[1..j].  Biaya dalam sel (i,j) dapat dihitung dengan menambahkan biaya operasi yang relevan dengan biaya sel tetangganya, dan memilih yang optimal.

Ada varian yang berbeda, lihat algoritma Smith – Waterman dan algoritma Needleman – Wunsch.

King, Ian, 2002 (1987), "A Simple Introduction to Dynamic Programming in Macroeconomic Models." Pengantar pemrograman dinamis sebagai alat penting dalam teori ekonomi.

Dynamic Programming: from novice to advanced sebuah artikel TopCoder.com oleh Dumitru tentang Pemrograman Dinamis

Algebraic Dynamic Programming – kerangka kerja formal untuk pemrograman dinamis, termasuk kursus tingkat awal kepada DP, University of Bielefeld

Dreyfus, Stuart, "Richard Bellman on the birth of Dynamic Programming. "