BIOLOGI DAN FISIKA MEDIS

Rekayasa Biomedis

Bidang fisika biologi dan medis dan teknik biomedis yang luas, multidisiplin dan dinamis. Mereka berbaring di persimpangan perbatasan penelitian dalam fisika, biologi, kimia, dan kedokteran. Fisika Biologi dan Kedokteran, Seri Biomedical Engineering ini dimaksudkan untuk menjadi komprehensif, meliputi berbagai topik penting untuk mempelajari ilmu-ilmu fisik, kimia dan biologis. Tujuannya adalah untuk memberikan para ilmuwan dan buku pelajaran engineerswith, monograf, dan referensi bekerja untuk mengatasi meningkatnya kebutuhan informasi.
Buku dalam seri menekankan didirikan dan daerah muncul ilmu termasuk molekul, membran, dan biofisika matematika; pemanenan energi fotosintesis dan konversi, pengolahan informasi; prinsip-prinsip dasar genetika, komunikasi sensorik; jaringan automata, jaringan saraf, dan otomata selular. Sama pentingnya akan cakupan aspek diterapkan fisika biologi dan kedokteran dan teknik biomedis seperti komponen elektronik molekuler dan perangkat, biosensor, kedokteran, pencitraan, prinsip fisik dari produksi energi terbarukan, maju prostesis, dan pengendalian lingkungan dan rekayasa.

Kata pengantar

Bioinformatika adalah ilmu interdisipliner yang melibatkan biologi molekuler, kimia molekul, fisika, matematika, ilmu komputasi, dll Sebagian besar buku tentang biomathematics diterbitkan dalam sepuluh tahun terakhir telah terdiri dari koleksi masalah standar dan metode bioinformatika informasi, dan fokus terutama pada logistik menerapkan dan memanfaatkan berbagai situs, database, paket perangkat lunak dan platform melayani. Sementara jenis buku melakukan memperkenalkan beberapa metode matematika dan komputasi di samping paket perangkat lunak, mereka kurang dalam pengobatan sistematis dan profesional matematika di balik metode ini.

Hal ini penting dalam bidang bioinformatika bahwa tidak hanya jumlah data yang meningkat secara eksponensial, tetapi kolaborasi juga baik pelebaran dan pendalaman di antara ahli biologi, kimia, fisika, matematikawan, dan ilmuwan komputer. Tipis volume masalah dan database mengharuskan peneliti untuk terus mengembangkan paket perangkat lunak untuk memproses data dalam jumlah besar, memanfaatkan metode matematika terbaru. Maksud dari buku ini adalah untuk memberikan perawatan profesional dan mendalam satu topik matematika yang diperlukan dalam studi bioinformatika.

Meskipun telah ada kemajuan besar dalam bioinformatika penelitian, masalah yang sulit banyak yang masih harus dipecahkan. Beberapa yang paling terkenal antara lain: keselarasan urutan beberapa, prediksi struktur 3D dan pengakuan dari gen eukariot. Sejak Human Genome Project (HGP) dikembangkan, masalah struktur jaringan genom dan proteomes, serta peraturan dari sistem selular adalah sangat menarik. Meskipun masih banyak pekerjaan yang harus dilakukan sebelum masalah ini diselesaikan, adalah harapan kita bahwa kunci untuk memecahkan masalah ini terletak pada sebuah kolaborasi meningkat di antara disiplin ilmu yang berbeda untuk menggunakan metode matematika dalam bioinformatika.

Buku ini dibagi menjadi dua bagian: bagian pertama memperkenalkan mutasi dan teori keselarasan urutan, yang meliputi model umum dan teori untuk menggambarkan struktur mutasi dan keselarasan, algoritma cepat untuk penyelarasan berpasangan dan beberapa, serta diskusi berdasarkan pada output yang diberikan oleh beberapa keselarasan cepat. Bagian I berisi cukup maju
pengobatan, dan hal ini menunjukkan bagaimana matematika dapat berhasil digunakan dalam bioinformatika. Keberhasilan dicapai dengan menggunakan algoritma cepat penyelarasan beberapa menggambarkan peran penting matematika.

Bagian II menganalisis struktur protein, yang meliputi semantik dan analisis cluster berdasarkan struktur primer dan analisis struktur 3D untuk rantai utama dan rantai samping protein. Sudut Wiggly (sudut dihedral) digunakan ketika menganalisis konfigurasi protein, membuat deskripsi konfigurasi yang lebih tepat. Menganalisa konfigurasi berbeda dari prediksi struktur sekunder atau 3D. Kami mengumpulkan semua kantong, alur, dan saluran pada protein sebagai karakteristik konfigurasi, menganalisis struktur karakteristik ini, dan memberikan algoritma untuk menghitung mereka.

Bagian I dan II menawarkan perawatan independen biologi dan matematika. Divisi ini nyaman, karena pembaca dapat mempelajari keduanya secara terpisah. Pada setiap bagian kita termasuk hasil dan referensi dari pengalaman kita sendiri penelitian. Kami mengusulkan beberapa konsep baru, misalnya, struktur modulus, ruang keselarasan, analisis semantik untuk urutan protein, dan metode geometris untuk menghitung karakteristik konfigurasi protein, dll Studi konsep-konsep ini masih dalam masa pertumbuhan dan ada banyak yang masih dieksplorasi. Ini merupakan harapan kami bahwa masalah ini terus diperiksa secara matematis sehingga mereka tetap di garis depan, baik dalam matematika dan bioinformatika.

Kami menyadari pentingnya mempertimbangkan aspek komputasi sambil memperkenalkan teori-teori matematika. Kumpulan contoh-contoh komputasi telah dimasukkan dalam buku ini sehingga hasil teoritis kita dapat diuji, dan agar pembaca dapat melihat teori-teori yang sesuai digambarkan. Selain itu, beberapa contoh ini memiliki implikasi yang dapat diterapkan untuk biologi secara langsung, dan bisa di-download dari situs [99] sebagai data terlalu besar untuk dimasukkan dalam buku ini. (Sebagai contoh, ketika memeriksa keselarasan dari gen HIV, ukurannya m = 405, n = 10.000 pb.)

Pemahaman tentang dasar-dasar probabilitas, statistik, grafik teori kombinatorial, dan biologi molekuler diasumsikan, serta kemampuan pemrograman. Agar pembaca dapat memperkuat pemahaman mereka, masalah telah ditambahkan pada akhir setiap bab, dengan petunjuk untuk membantu memulai, Ini merupakan harapan kami bahwa buku ini akan berguna dalam bidang bioinformatika baik sebagai buku teks dan sebagai referensi buku.

Ucapan Terima Kasih

Buku ini adalah produk dari sebuah kolaborasi antara kelompok Cina dan Kanada. Selain dua penulis, banyak anggota kedua kelompok membuat kontribusi penting. Shiyi Shen asisten Gang Hu, KuiWang, Liuhuan Dong, Hua Zhang (kandidat doktor), Zhonghua Wu (kandidat doktor), dan Guogen Shan membantunya untuk mengumpulkan dan menganalisis data, bersama dengan karya-karya lain dalam rangka menciptakan edisi Cina ini bekerja. Dr Jishou Ruan dan mahasiswa pascasarjana nya memberikan terjemahan awal dari edisi Cina ke non-pribumi-speaker bahasa Inggris, dan kemudian memeriksa-pribumi pembicara Edisi bahasa Inggris untuk mengkonfirmasi bahwa arti aslinya dipertahankan. Siswa-siswa ini adalah Guangyue Hu, Tuo Zhang, Guoxiang Lu, Gao Jianzhao, Yubing Shang, Shengqi Li, dan Hanzhe Chen. Naskah itu diterjemahkan ke asli-speaker bahasa Inggris oleh asisten Jack Tuszynski, Michelle Hanlon. Para penulis mengakui dan berterima kasih kepada semua yang terlibat atas kerja keras yang masuk ke proyek ini.

Kelompok Shen mengucapkan terima kasih kepada Chun-Ting Zhang (Fellow dari Akademi Ilmu Pengetahuan China) yang mendorong kerja Shiyi Shen pada bioinformatika. Kelompok ini juga mengucapkan terima kasih kepada Pusat Liuhui untuk Matematika Terapan, Universitas Tianjin dan program Universitas Nankai bersama, NSFC (hibah NSFC10271061), dan Ilmu Pengetahuan dan program Teknologi Tianjin (STPT 04318511-17) untuk menyediakan dana untuk proyek ini. Kami juga ingin berterima kasih kepada Institut Chern Matematika, yang menawarkan banyak bantuan, termasuk komputer dan kantor.

Kedua penulis ingin mengucapkan terima kasih Angela Lahee dari Springer-Verlag untuk bimbingan dan dorongan.

Menguraikan
Buku ini membahas beberapa isu penting termasuk metode matematis dan komputasi dan aplikasi mereka untuk bioinformatika.

Buku ini berisi dua bagian. Bagian I memperkenalkan mutasi urutan dan teori struktur data yang digunakan dalam keselarasan. Model stokastik keselarasan dan teori aljabar diperkenalkan sebagai alat untuk menggambarkan struktur data. Algoritma pemrograman dinamis dan algoritma keputusan statistik untuk penyelarasan urutan berpasangan, algoritma keselarasan cepat, dan analisis dan aplikasi output sequence aligment beberapa juga diperkenalkan. Bagian II mencakup pengenalan analisis frekuensi, analisis klaster dan analisis semantik dari urutan utama, pengenalan analisis 3D-struktur rantai utama dan rantai samping, dan pengenalan analisis konfigurasi.
Banyak teori matematika disajikan dalam risalah ini, seperti analisis stokastik, teori grafik kombinasional, geometri dan aljabar, informatika, komputasi cerdas, dll Sejumlah besar algoritma dan paket perangkat lunak yang bersangkutan menggunakan teori ini, yang telah dikembangkan untuk menangani dengan sejumlah besar data biologis dan klinis yang memainkan peran penting dalam bidang bioinformatika, biomedis, dan sebagainya.
Buku ini memiliki tiga tujuan utama. Yang pertama adalah untuk memperkenalkan teori-teori matematika klasik dan metode dalam konteks keadaan saat ini matematika, seperti yang biasa digunakan di bidang biologi molekuler dan bioinformatika. Yang kedua adalah untuk membahas persyaratan matematika potensi dalam studi biologi molekuler dan bioinformatika, yang akan mendorong pengembangan teori-teori baru dan metode. Gol ketiga kami adalah untuk mengusulkan suatu kerangka kerja yang bioinformatika dapat dikombinasikan dengan matematika.
Dalam setiap bab, kami telah memasukkan hasil dan referensi dari pengalaman penelitian kita sendiri, untuk mengilustrasikan poin kami. Ini merupakan harapan kami bahwa buku ini akan berguna sebagai buku teks untuk mahasiswa sarjana maupun pascasarjana, serta referensi bagi guru atau peneliti di bidang bioinformatika atau matematika, atau mereka yang tertarik dalam memahami hubungan antara keduanya.

Bagian 1

Mutasi dan keberpihakan

1. Pengenalan

1,1 Mutasi dan Keselarasan

1.1.1 Klasifikasi Urutan Biologi

The "urutan biologis" istilah umumnya digunakan untuk merujuk pada urutan DNA, RNA dan urutan urutan protein. Dalam arti biologi molekuler, urutan biologis terdiri dari makromolekul banyak, semua dengan fungsi biologis tertentu dalam kondisi tertentu. Selain itu, makromolekul itu sendiri dapat dibagi menjadi sejumlah besar micromolecules fungsional dengan cara tertentu. Biasanya, urutan DNA (atau RNA urutan) didasarkan pada empat nukleotida, sedangkan protein adalah berdasarkan 20 asam amino. Jika kita mempertimbangkan dari urutan nukleotida DNA atau asam amino pada protein menjadi unit dasar, maka urutan biologis hanyalah sebuah kombinasi dari unit-unit dasar.

Definisi dan Notasi untuk Urutan Biologi

Ada banyak cara di mana untuk merepresentasikan struktur dari urutan biologis. Yang paling populer adalah untuk menjelaskan (atau tiga dimensi) primer, sekunder, dan tersier struktur. Untuk protein, struktur utama menggambarkan kombinasi dari asam amino yang membentuk protein. Dalam DNA (atau RNA) urutan, struktur utama menentukan nukleotida komponen. Kita umumnya menggunakan deskripsi berikut urutan biologis:

A = (a1, a2, • • •, ana), B = (b1, b2, • • •, BnB), C = (c1, c2, • • •, cnc), (1.1)

mana huruf A, B, C mewakili urutan, dan ai, bi, ci merupakan unit dasar dari urutan, pada posisi i, yang unsur-unsurnya yang diperoleh dari set Vq = {0, 1, • • •, q - 1}. Biasanya, q = 4 dan V4 = {a, c, g, t} (atau {a, c, g, u}) jika A, B dan C adalah DNA (atau RNA) urutan. q = 20 dan Vq adalah himpunan dari 20 asam amino yang paling umum jika A, B, dan C adalah urutan protein. Pada (1.1), na, nb, nc adalah panjang urutan A, B, C.

Secara umum, urutan beberapa (atau kelompok urutan) akan dinotasikan sebagai:
A = {A1, A2, • • •, Am}, (1,2)

di mana setiap Seperti urutan terpisah didefinisikan pada Vq, dan ekspresi lengkap adalah
Sebagai = (seperti, 1, sebagai, 2, • • •, seperti, ns), s = 1, 2, • • •, m, (1,3)

mana ns adalah panjang urutan As, dan m adalah jumlah urutan dalam setiap kelompok.

Klasifikasi Urutan Biologi

Struktur primer dari urutan biologis menentukan komponen nukleotida atau asam amino. Struktur tersier atau tiga dimensi dari urutan biologis menggambarkan susunan tiga dimensi (koordinat posisi) dari atom konstituen dalam molekul. Struktur sekunder dari urutan biologis menggambarkan sifat lokal. Sebagai contoh, struktur sekunder protein menunjukkan struktur khusus (motif) setiap segmen protein, di mana sebuah helix, untai atau struktur mungkin ada. Struktur Supersecondary juga sering digunakan untuk menggambarkan suatu keadaan peralihan antara struktur sekunder dan struktur tersier, yang terdiri dari beberapa kelompok yang lebih besar molekul kompak (domain).

Biologi molekuler modern mengatakan kepada kita bahwa DNA (atau RNA) urutan dan urutan protein merupakan unit dasar yang terlibat dalam fungsi biologis khusus. Karakteristik fungsional mereka tidak hanya melibatkan struktur utama mereka, tetapi juga tiga dimensi mereka bentuk. Sebagai contoh, kantong pengikatan protein yang memainkan peran penting dalam mengendalikan fungsinya. Dengan demikian, bentuk yang dibentuk oleh sekuens asam amino dalam ruang tiga dimensi dapat menjadi sangat relevan dengan perawatan klinis yang melibatkan mutasi genetik serius hadir dalam penyakit. Kami akan menggunakan konfigurasi protein untuk menggantikan bentuk protein dalam ruang tiga dimensi. Karena mutasi dari perubahan urutan biologis konfigurasinya dan oleh karena itu dapat mempengaruhi fungsinya, dan karena keselarasan adalah metode yang paling populer untuk pemindaian posisi mutasi, kita mulai dengan membahas karakteristik dasar mutasi, serta metode alignment untuk sekuens biologis.

1.1.2 Definisi Mutasi dan keberpihakan

Keberhasilan kloning menunjukkan bahwa urutan DNA berisi informasi lengkap mengenai pembangunan suatu bentuk kehidupan. Namun, ada proses yang kompleks yang harus terjadi ketika membangun struktur dari DNA ke RNA, RNA ke protein, protein untuk organel, organel ke sel dan, akhirnya, dari sel ke organisme. Beberapa dari proses ini meliputi transkripsi, terjemahan, dan duplikasi. Dalam proses ini, mekanisme pengakuan, peraturan kontrol, dan masih belum sepenuhnya jelas. Masih ada sejumlah besar fenomena biologis yang tidak dapat dijelaskan saat ini. Misalnya, mekanisme mutasi dalam urutan biologis belum sepenuhnya dieksplorasi. Mutasi dapat menyebabkan pertumbuhan dan kematian sel, dan juga dapat menyebabkan penyakit. Sequence aligment merupakan perangkat yang penting dalam analisis posisi dan jenis mutasi tersembunyi di urutan biologis, dan memungkinkan perbandingan yang tepat. Bukti awal bahwa mutasi dapat menyebabkan pertumbuhan tumor ditemukan pada tahun 1983, ketika ditunjukkan bahwa kanker adalah hasil dari pertumbuhan sel yang tidak terkendali pada suatu organisme dan bahwa pertumbuhan ini sering disebabkan oleh mutasi. Keselarasan urutan juga penting karena dapat digunakan untuk penelitian penyakit genetik dan epidemi. Sebagai contoh, adalah mungkin untuk menentukan asal, variasi, varians, difusi, dan pengembangan epidemi, dan kemudian menemukan virus dan bakteri yang bertanggung jawab dan obat yang sesuai. Dengan demikian, keselarasan urutan sangat penting di bidang bioinformatika dan biomedis baik karena fungsi kuat prediksinya. Untuk mendapatkan yang lebih baik tingkat tinggi algoritma alignment, teori-teori matematika yang lebih diperlukan.
Sequence aligment memiliki banyak aplikasi di bioinformatika selain digunakan langsung dalam membandingkan struktur protein. Beberapa aplikasi khas terdaftar sebagai berikut:

Gene Positioning dan Gene Pencarian

Untuk gen yang diberikan dalam organisme tertentu, kita harus mempertimbangkan apakah gen yang sama (atau gen serupa) dapat ditemukan dalam organisme lain. Ini adalah masalah dasar pencarian gen dan posisi gen berdasarkan database GenBank. Gene posisi dan pencarian gen adalah dasar dari analisis gen. Metode yang lebih baik dari pencarian gen akan memungkinkan pengembangan algoritma keselarasan yang lebih akurat. Paket keselarasan Banyak perangkat lunak telah dikembangkan berdasarkan prinsip-prinsip pencarian gen dan posisi gen, dan sering digunakan dalam bioinformatika, seperti BLAST [3, 67] dan FASTA [73-75]. Menurut beberapa laporan, BLAST dikunjungi oleh lebih dari 100.000 pengunjung per hari, pinjaman kepercayaan kepada pernyataan bahwa keselarasan urutan banyak digunakan dalam studi bioinformatika.

Gene Mengulang dan Gene Crossing dan Penyambungan

Gene mengulangi dan splicing gen sering terjadi dalam genom organisme yang sama, yang telah menjadi jelas sebagai genom berbagai organisme (termasuk manusia) yang diurutkan. Gene mengulangi mengacu pada pengulangan dari segmen DNA yang panjang dalam genom yang sama. Panjang beberapa segmen mungkin dalam jutaan pasangan basa (pb), dan jumlah pengulangan juga mungkin dalam jutaan. Ini pengulangan mungkin tidak identik, tetapi biasanya serupa. Oleh karena itu mereka dapat ditemukan melalui algoritma keselarasan. Gen biasanya terdiri dari segmen gen yang berbeda. Segmen tersebut disebut ekson, dan interval disebut intron. Ketika gen diterjemahkan menjadi protein, intron dipotong, dan array ekson dalam urutan terbalik. Fenomena ini dikenal sebagai gen persimpangan, dan analisis perusahaan juga tergantung pada algoritma keselarasan.

Genom Penyambungan

Dalam proses sekuensing gen, urutan panjang kromosom pertama kali dipotong-potong, segmen DNA individu tersebut kemudian diurutkan secara mandiri, sedangkan segmen akan dirakit bersama. Artinya, nukleotida dari seluruh kromosom tidak diurutkan secara bersamaan. Untuk merakit segmen dengan benar, banyak salinan genom dipotong menjadi segmen acak, yang kemudian diurutkan secara independen. Informasi umum (ditemukan melalui alignment) kemudian digunakan untuk asemble genom lengkap.

Aplikasi Lainnya

Sulit untuk mengidentifikasi dan mencari intron dan ekson dari eukariot sementara mengidentifikasi dan mencari gen regulasi. Akibatnya, metode identifikasi banyak yang muncul. Di antaranya, keselarasan berbasis metode yang sangat signifikan.
Secara ringkas, penting untuk dicatat bahwa mutasi dan keberpihakan tidak digunakan hanya untuk mempelajari evolusi biologis tetapi juga dapat digunakan untuk mempelajari hubungan antara gen, protein dan struktur makromolekul biologis dalam sistem kehidupan.

1.1.3 Perkembangan Algoritma Alignment dan masalah yang harus diselesaikan

Para peneliti saat ini melakukan keberpihakan urutan dan pencarian basis data milyaran kali per hari. Karena pentingnya, metode alignment harus akrab dengan semua ahli biologi dan peneliti di bidang bioinformatika. Metode alignment juga harus terus diperbarui untuk menghadapi tantangan baru yang muncul di bidang ilmu pengetahuan. Kami secara singkat meninjau kemajuan dalam algoritma sequence aligment, serta tantangan yang terlibat.

Kemajuan dalam Alignment Urutan Berpasangan

Metode dinamis pemrograman berbasis keselarasan pertama kali diusulkan oleh Needleman dan Wunsch [69]. Ini melibatkan menggambar grafik dengan satu urutan tertulis di halaman dan yang lainnya di sisi kiri, mencetak pertandingan antara urutan (atau hukuman bagi ketidaksesuaian) dan menghubungkan dengan simbol virtual yang dimasukkan. Penyesuaian dengan tertinggi (atau terendah) skor mungkin didefinisikan sebagai keselarasan yang optimal. Pada tahun 1980, Smith dan Waterman [95] mengembangkan modifikasi penting dari algoritma pemrograman berbasis dinamis, disebut sebagai penyelarasan yang optimal lokal atau algoritma Smith-Waterman. Segmen ini keselarasan yang optimal lokal dapat ditentukan secara independen, dan keselarasan urutan global yang optimal diperoleh dengan menghubungkan segmen. Meskipun kedua pendekatan yang dinamis pemrograman berbasis algoritma, algoritma Smith-Waterman sangat menyederhanakan algoritma Needleman-Wunsch.

Mengikuti perkembangan dari algoritma Smith-Waterman, keselarasan urutan menjadi topik penting dalam bioinformatika. Banyak makalah diterbitkan, yang tidak hanya meningkatkan algoritma Smith-Waterman, tetapi juga diadaptasi untuk diterapkan pada urutan protein. Akibatnya, berbagai jenis perangkat lunak diterapkan berdasarkan algoritma keselarasan dikembangkan, dan ada saat ini sebagai alat bioinformatika kuat. Penjajaran sekuens protein lebih kompleks dari penyelarasan sekuens gen karena jauh lebih sulit untuk mengembangkan matriks penilaian (yang mengukur kesamaan antara urutan) untuk urutan protein. Para peneliti telah diusulkan berbagai jenis sistem skoring untuk memproduksi matriks penilaian, seperti sistem PAM dan sistem BLOSUM. Untuk matriks penilaian dari sistem PAM, probabilitas mutasi berdasarkan waktu evolusi dari keluarga homolog ditentukan pertama, diikuti oleh perkembangan dari matriks penilaian. Matriks penilaian dari sistem BLOSUM menemukan probabilitas mutasi berdasarkan daerah konservatif dari keluarga homolog, kemudian mengembangkan matriks penilaian. Oleh karena itu, tergantung pada kebutuhan mereka, pengguna dapat memilih matriks penilaian mereka berdasarkan baik sistem PAM atau sistem BLOSUM, kemudian menggabungkan scoring matriks dengan algoritma pemrograman dinamis untuk menghitung fungsi skor tertinggi. Kami akan masuk ke lebih rinci nanti mengenai matriks mencetak dari sistem PAM dan sistem BLOSUM. Pembaca juga disebut literatur [24, 40] untuk informasi lebih lanjut tentang topik ini.

Selain diadaptasi untuk digunakan dengan protein, ada aplikasi lain dari algoritma keselarasan. Saat ini, lebih dari sepuluh jenis paket perangkat lunak ada untuk tujuan mencari database. Di antara mereka, BLAST dan FASTA adalah yang paling populer yang tersedia sebagai download gratis.
Algoritma pemrograman berbasis dinamis harus selaras sepanjang kedua sumbu vertikal dan sumbu horisontal. Pertama harus menetapkan nilai hukuman (atau nilai yang sesuai) pada entri silang berpotongan dengan kedua sumbu vertikal dan sumbu horisontal, dan link dioptimalkan. Oleh karena itu, kompleksitas komputasi algoritma ini tidak boleh kurang dari O (n2) (dimana n adalah panjang dari urutan selaras). Untuk urutan lagi, keselarasan dan pencarian adalah tugas yang sulit, meskipun mereka mudah direalisasikan dengan menggunakan metode ilmu komputasi. Sebagai contoh, algoritma ini penyelarasan saat ini tidak dapat dilakukan pada PC jika panjang dari urutan melebihi 100 kbp. Untuk panjang melebihi 10Mbp, algoritma keselarasan tidak dapat dilakukan oleh setiap komputer saat ini ada. Pada tahun 2002, algoritma keselarasan probabilitas dan statisticsbased diusulkan oleh Universitas Nankai kelompok, yang disebut algoritma keselarasan Super berpasangan (SPA algoritma untuk pendek) [90]. Untuk homolog urutan, kompleksitas komputasi dari SPA hanya O (n), yaitu, berbanding lurus dengan panjang urutan. Hal ini membuat algoritma berjalan lebih cepat, dan memungkinkan penyelarasan dan pencarian super-panjang urutan.

Ini mungkin tampak seolah-olah masalah yang melekat dalam metode penyelarasan berpasangan semuanya telah ditangani oleh dinamis pemrograman berbasis algoritma dan statistik keputusan berbasis algoritma. Namun, ada banyak ruang untuk perbaikan, dan untuk aplikasi lebih untuk dikembangkan. Sebagai contoh, algoritma SPA adalah algoritma optimal, meskipun ia mampu menangani urutan superlong. Ia masih memiliki potensi untuk menjadi lebih ditingkatkan, karena akurasinya lebih rendah dibandingkan dengan solusi optimal dalam 0,1-1%. Selain itu, untuk proses super-panjang urutan (yaitu, ketika panjang melebihi 100Mbp), sebuah "jangkar" harus dimasukkan ke dalam algoritma.

Beberapa Alignment Algoritma

Dibandingkan dengan keselarasan berpasangan, keselarasan beberapa jauh lebih sulit. Solusi optimal dari masalah ini dianggap sebagai salah satu masalah yang belum terpecahkan biologi komputasi dan bioinformatika selama periode antara 2000 dan 2002. Hal ini kadang-kadang disebut dalam sastra sebagai "masalah NPcomplete" atau "NP-keras masalah" [15,36,46,104,106]. Pentingnya keselarasan beberapa telah mendorong pengembangan paket perangkat lunak yang mampu menangani algoritma keselarasan ganda. Paket perangkat lunak ini tidak mencari solusi yang optimal secara teoritis, melainkan, mereka membuat perbandingan berdasarkan beberapa indeks tertentu. Dalam Chap. 5, kita akan memeriksa indeks mengikuti penyelarasan beberapa:

1.      Ruang lingkup keselarasan ganda. Jenis yang sama urutan dapat disejajarkan dengan keberpihakan beberapa, yaitu, urutan nukleotida dibandingkan dengan urutan nukleotida lain, dan urutan asam amino yang lain dibandingkan dengan sekuens asam amino. Hal ini umumnya diharapkan bahwa ada beberapa kesamaan antara urutan lanjut untuk dibandingkan, karena keberpihakan beberapa digunakan untuk membandingkan urutan homolog.

2.      Skala penyelarasan ganda. Biarkan (m, n) menyatakan panjang dan jumlah urutan disejajarkan. Ukuran maksimum (m, n) diizinkan oleh keberpihakan beberapa kemudian disebut sebagai lingkup keselarasan ganda. Kita akan daftar beberapa paket perangkat lunak yang bersangkutan dengan skala keselarasan beberapa di Chap. 5.

3.      Kecepatan komputasi. Waktu yang diperlukan untuk menentukan keselarasan beberapa urutan skala (m, n) disebut sebagai kecepatan komputasi.

4.      Indeks-indeks mengoptimalkan. Dalam literatur, beberapa indeks mengoptimalkan keberpihakan beberapa seperti "fungsi SP-angka" dan "fungsi entropi" yang sering disebutkan. Dalam Chap. 5, kami memperkenalkan dua indeks baru: "kesamaan" dan Kami akan membahas indeks secara lebih rinci pada saat itu "tingkat penyisipan.".
Kami juga akan memperkenalkan beberapa keselarasan super (SMA) [89] metode dalam Chap. 5. Kompleksitas komputasi SMA hanya O (m • n), dan skala, kecepatan, dan indeks lebih unggul dengan yang HMMER [78]. Berdasarkan HIV-1, kita membandingkan metode SMA dengan kedua metode SMA dan HMMER untuk semua indeks dan menampilkan hasil akhir dalam Tabel 5.1 dan 5.2. HIV-1 adalah genom yang diketahui dari virus AIDS, dan menurut GenBank, skala adalah (m, n) = (706, 10.000). Dibutuhkan 40min untuk melakukan penyelarasan beberapa pada PC yang menggunakan SMA, yang lebih baik dan lebih cepat daripada HMMER.

Analisis dan Penerapan Hasil Alignment Beberapa

Sebagai hasil dari keselarasan berpasangan atau alignment beberapa diproduksi, masalah utama baik dalam teori dan praktek menjadi analisis dan penggunaan hasil tersebut. Masalah yang paling mendesak adalah analisis hasil keselarasan ganda, yang kami jelaskan di sini.

Kami telah disebutkan bahwa tujuan keselarasan beberapa adalah untuk menentukan hubungan antara urutan mutasi. Jadi, pertama-tama perlu untuk menemukan daerah konservasi umum, yang disederhanakan dengan penggunaan kesejajaran ganda. Korelasi antara mutasi pada urutan yang berbeda kemudian menjadi masalah utama. Metode tradisional analisis untuk menentukan hubungan timbal balik disebut analisis clustering. Metode yang paling klasik adalah "sistem pohon evolusi" atau "minimum pohon jarak" (yang akan dibahas dalam Bab. 6). "Sistem pohon evolusi" atau "jarak minimum pohon" metode adalah hubungan pengelompokan didirikan oleh jarak mutasi ditentukan oleh urutan selaras yang berbeda. Dengan demikian, struktur adalah terukur, dan sebagian mencerminkan tingkat yang "jauh" atau Namun, tidak komprehensif, "dekat." Dan beberapa informasi yang berguna yang tidak terjawab jika analisis didasarkan hanya pada "pohon sistem evolusi" dan "pohon jarak minimum."

Saat ini, untuk menganalisis hasil pelurusan beberapa, kami mengusulkan "urutan mutasi teori jaringan beberapa" ("mutasi jaringan" untuk pendek). Teorinya adalah bahwa kita dapat mengganti "struktur topologi metrik" oleh "struktur modulus" berdasarkan keselarasan ganda. Ini merupakan metode yang efektif untuk menggambarkan mutasi, dan diperkenalkan dalam Bab. 3. Penentuan struktur modulus melibatkan serangkaian operasi aljabar. "Jaringan mutasi" adalah kombinasi dari "grafik topologi" dan "struktur modulus," dan dengan demikian, terdiri dari deskripsi lengkap dari pelurusan. Kita kemudian dapat memberkati jaringan mutasi dengan hukum operasional seperti dekomposisi, kombinasi dan sebagainya. Akibatnya, teori jaringan mutasi adalah alat penting untuk menganalisis hasil keselarasan.

1.1.4 Masalah Matematika Didorong oleh Alignment dan Analisis Struktural

Sehubungan dengan pemodelan, komputasi, dan analisis, keselarasan berpasangan dan keselarasan beberapa dapat dilihat sebagai masalah matematika yang khas, bukan masalah biologis. Banyak teori matematika dan metode yang terlibat, beberapa yang tercantum di bawah ini:

Stokastik Analisis

Analisis stokastik adalah dasar dari probabilitas dan analisis statistik dan proses stokastik yang digunakan dalam pemodelan keselarasan, penciptaan algoritma cepat, dan analisis hasil. Setelah dari mekanisme mutasi, kita tahu bahwa mutasi di setiap lokasi secara berurutan mematuhi aliran Poisson. Dengan demikian, struktur dari berbagai jenis mutasi harus menjadi proses pembaharuan. Kita juga dapat mengatakan bahwa jenis-aku struktur bermutasi mematuhi aliran Poisson berdasarkan pengamatan urutan banyak.
Analisis stokastik adalah dasar dari analisis mutasi struktur, dan memungkinkan kita untuk memahami karakter data secara keseluruhan, berdasarkan semua urutan yang diberikan. Ini juga memainkan peran penting dalam pengembangan algoritma alignment dan perhitungan indeks (seperti estimasi kompleksitas, estimasi kesalahan dan nilai-nilai mengoptimalkan indeks).

Struktur Aljabar

Untuk menggambarkan karakter struktural keberpihakan mutasi dan urutan, dalam Chap. 3 kami mengusulkan operasi aljabar untuk struktur molekul. Teori ini mendefinisikan jenis struktur modulus berbagai representasi setara dan operasi aljabar. Operasi aljabar struktur modulus merupakan kunci dalam pengembangan cepat algoritma keselarasan berganda dan analisis hasil.

Kombinasional Grafik Teori

Grafik teori kombinatorial merupakan perangkat yang penting, baik ketika membangun algoritma cepat keselarasan ganda dan ketika menganalisis output keselarasan. Menggunakan grafik teori kombinatorial, analisis kelompok dimungkinkan. Ini adalah dasar untuk menganalisis keselarasan output ganda untuk membangun pohon sistemik dan pohon jarak minimum, dan juga untuk membangun jaringan mutasi.

Alignment Ruang Teori

Ruang Alignment adalah ruang data teori yang didasarkan pada kesalahan mutasi, dan merupakan konsep baru yang diusulkan oleh kelompok Universitas Nankai. Ruang Alignment adalah ruang metrik nonlinier, dan merupakan dasar teoritis untuk penyelarasan. Akibatnya, aplikasi akan jauh jangkauannya.
Masalah matematika yang disebutkan di atas sangat penting untuk pembangunan algoritma alignment dan analisis output. Kombinasi matematika dan biologi masih dalam masa pertumbuhan, dan banyak masalah menunggu diskusi yang lebih dalam. Ada ruang jelas jauh untuk pengembangan selanjutnya.

1,2 Konsep Dasar Alignment dan Model Matematika

Demi kesederhanaan, kita membatasi pembahasan kita pada DNA (atau RNA) urutan kecuali dinyatakan khusus. Untuk urutan protein, kita hanya perlu mengganti V4 oleh V20 dan kemudian ikuti argumen serupa. Mari kita mulai dengan memperkenalkan masalah dasar dan model matematika yang akan digunakan dalam keselarasan dan analisis mutasi.

1.2.1 Mutasi dan Keselarasan Klasifikasi Mutasi

Dalam biologi molekuler, mutasi beberapa molekul kecil 'urutan nya A akan menyebabkan A untuk mengubah urutan urutan ke B B. kemudian disebut sebagai mutasi (urutan) dari A. Mutasi urutan DNA dapat diklasifikasikan menjadi empat jenis sebagai berikut :
Tipe I: mutasi disebabkan oleh perubahan nukleotida dari satu ke yang lain, yaitu "a" berubah menjadi "g."

Tipe II: mutasi disebabkan oleh segmen nukleotida permuting posisinya, yaitu segmen "accgu" permutes ke segmen "guacc."

Tipe III: mutasi disebabkan dengan memasukkan segmen baru ke urutan yang ada, yaitu, memasukkan "aa" ke posisi tengah segmen "gguugg" sehingga menjadi segmen baru "gguaaugg."
Tipe IV: mutasi disebabkan oleh segmen nukleotida tidak dihapus dari urutan yang ada, yaitu, menghapus nukleotida "ag" dari segmen "acaguua," kita dibiarkan dengan segmen "acuua."
Karena tipe I dan II tidak mengubah posisi semua nukleotida, mutasi ini disebut mutasi substitusi. Jenis III dan IV mengubah posisi semua nukleotida, dan mutasi ini disebut mutasi perpindahan. Masalah dasar keselarasan adalah untuk mencari situs yang bermutasi dan memutuskan mana daerah dilestarikan dan yang telah berubah. Hubungan evolusi dan perubahan dari kedua struktur dan fungsi dalam proses evolusi kemudian dapat ditentukan. Alignment jelas merupakan alat penting dalam proses bioinformatika.

Definisi 1. Jika B urutan adalah urutan mutasi dari A urutan, dan mereka memiliki arti biologis yang sama, maka mereka homolog urutan.

Dalam analisis urutan, jika kita tahu bahwa B adalah urutan mutasi dari A tetapi kita tidak tahu apakah mereka memiliki arti biologis yang sama (yaitu, apakah perbedaan disebabkan oleh kesalahan dangding), kemudian kita mengatakan bahwa dua urutan saling serupa. Istilah "homolog urutan" dan "urutan serupa" yang sering digunakan dalam pembahasan analisis urutan, dan catatan harus diambil dari perbedaan itu.

Definisi Alignment

Untuk mengkonfirmasi hubungan antara mutasi, pendekatan umum adalah untuk membandingkan perbedaan dalam keluarga urutan, yang dapat dilihat sebagai operasi dalam arti matematis. Hal ini disebut sebagai keselarasan urutan atau keselarasan untuk pendek. Kunci untuk sequence aligment adalah memutuskan pada mutasi perpindahan. Misalkan A, B menjadi dua urutan didefinisikan dalam (1.1). Memasukkan simbol virtual "-" menjadi A, B sehingga mereka menjadi dua sekuens baru A_, B_, unsur-unsur A_, B_ tersebut kemudian di kisaran V5 = {0, 1, 2, 3, 4} = {a , c, g, t, -} dimana, V4 dan V5 disebut set kuaterner dan set lima elemen, masing-masing.
Definisi 2.

1.      Urutan A_ adalah urutan ekspansi virtual (ekspansi, untuk pendek) urutan A, jika seluruh A_ hanya urutan tua A dengan simbol penyisipan "-" tambahnya.

2.      Urutan A_ = (a_1, a_2, • • •, a_n_a), B_ = (b_1, b_2, • • •, b_n_b) disebut ekspansi urutan ganda A, B, jika A_, B_ adalah ekspansi dari A, B , masing-masing.

3.      Urutan kelompok A_ = {A_s, s = 1, 2, • • •, M} disebut perluasan beberapa urutan A, jika setiap A_s dari A_ adalah perluasan As.

4.      A disebut urutan asli dari A_ A_ jika urutan beberapa merupakan perluasan dari A. Kita kemudian menunjukkan urutan di A_ oleh
A_ s = _a _S, 1, a_s, 2, • • •, a_s, ns_, a_s, j ∈ V5. (1.4)
Dalam A_ ekspansi dari A, nilai data 4 terkait dengan data penyisipan virtual (atau simbol) dan nilai-nilai data 0, 1, 2, 3 sesuai dengan data nukleotida muncul di urutan A.

5.      Urutan kelompok A_ disebut urutan keselarasan kelompok (alignment untuk pendek) dari A jika panjang urutan dalam A_ adalah sama, jika mereka ekspansi dari A dan jika a_1, j, a_2, j, • • •, a_
M, j tidak 4 simultan sama pada setiap posisi j.
Definisi dekompresi dan kompresi dari urutan akan diberikan dalam Sect. 3.1.

Mengoptimalkan Prinsip Keselarasan

Tujuan dari sequence aligment adalah untuk menemukan A_ perluasan kelompok tertentu A sehingga semua urutan dalam A_ memiliki lebih rendah "perbedaan" atau yang lebih tinggi Dalam bioinformatika, "perbedaan" biasanya diukur menggunakan "matriks hukuman" atau "kesamaan." " mencetak matriks. "
Dasar dari fungsi penalti adalah matriks penalti. Singkatan dari tingkat perbedaan dari setiap unit molekul (seperti asam nukleotida atau amino) dalam urutan biologis. Hal ini biasanya dinyatakan dalam bentuk matriks sebagai berikut:
D = (d (a, b)) a, b ∈ V5. (1.5)

Dalam bioinformatika, matriks hukuman keselarasan urutan DNA biasanya ditentukan oleh matriks Hamming atau WT-matriks. Matriks Hamming pada V5 didefinisikan sebagai berikut:

Nilai matriks penilaian adalah maksimum jika b =. Secara umum, matriks penilaian dinotasikan dengan G = [g (a, b)] a, b ∈ V5. Entri dalam matriks penilaian yang berlawanan nilai ke nilai yang sesuai dalam matriks penalti. Sebagai contoh, matriks penilaian dari matriks Hamming adalah g (a, b) = 1
Matriks hukuman (atau matriks penilaian) digunakan untuk mengoptimalkan hasil pelurusan. Dengan demikian, kedua matriks disebut sebagai matriks mengoptimalkan dan dilambangkan dengan W = [w (a, b)] a, b ∈ V5.
Fungsi mengoptimalkan mengukur nilai optimal dari dua sekuens.
Di masa depan, kita tidak akan membedakan antara fungsi dan mengoptimalkan tingkat optimal rata-rata, dan pembaca diharapkan untuk membedakan mana yang tersirat menurut konteksnya. Fungsi mengoptimalkan paling sering digunakan dalam keselarasan beberapa adalah SP-fungsi. Jika A adalah beberapa urutan yang diberikan oleh (1,2), dan A_ adalah ekspansi dari A diberikan dalam Definisi 2, maka SP-fungsi didefinisikan oleh:
Kemudian, WSP (A_) menunjukkan fungsi mengoptimalkan, atau mengoptimalkan pengukuran, untuk menyelaraskan A_ beberapa urutan.

Definisi 3. Keselarasan yang optimal dari beberapa urutan adalah situasi di mana, untuk beberapa urutan yang diberikan A, perluasan a_0 memenuhi fungsi mengoptimalkan SP-fungsi di (1,9). Atau, jika kita menemukan perluasan A_ 0 dari A sedemikian sehingga

Penyesuaian optimal a_0 ditentukan oleh fungsi SP-disebut solusi SPoptimal atau solusi SP-fungsi berbasis optimal. Proses untuk menemukan solusi ini SP-optimal dikenal sebagai metode SP-. Keselarasan Berpasangan adalah kasus yang paling sederhana keselarasan ganda. Kami akan membahas kriteria optimal untuk penyelarasan beberapa di Chap. 7.

Contoh 1. Kami membahas urutan berikut:

Kita bisa melihat bahwa B adalah urutan mutasi dari A, dan A_, B_ adalah ekspansi urutan A, B, masing-masing. Kemudian dH (A

Oleh karena itu, hukuman (a_0, B_0) lebih kecil dibandingkan dengan (A_, B_).

Untuk penyelarasan urutan protein, biasanya kita mengadopsi matriks penilaian. Karena urutan gen protein adalah kompleks, matriks PAM dan BLOSUM digunakan untuk mendapatkan matriks penilaian yang diperlukan. Kami akan membahas ini dalam bab-bab yang sesuai untuk penyelarasan protein urutan. Kami harus dicatat bahwa keberpihakan yang optimal mungkin tidak unik untuk urutan tertentu (A, B) di bawah W. matriks diberikan optimal Hal ini ditunjukkan dalam adalah keberpihakan (A, B) dengan nilai hukuman minimum. Karena skor hukuman mereka adalah sama jelas bahwa kita tidak dapat menemukan alignment dengan skor penalti lebih kecil.

Untuk mempermudah, di bawah ini, alignment jangka selalu mengacu pada keselarasan penalti berbasis minimum kecuali dinyatakan khusus. Jelas, kesimpulan yang sesuai juga berlaku untuk penyelarasan penilaian berbasis maksimal.

1,3 Dinamis Pemrograman Berbasis Algoritma untuk Alignment Berpasangan

1.3.1 Pengantar Pemrograman Dinamis Berbasis Algoritma

Dinamis pemrograman berbasis algoritma merupakan metode yang biasa untuk memecahkan masalah yang optimal dan secara luas diterapkan di berbagai bidang. Validitas dari algoritma pemrograman berbasis dinamis tergantung pada apakah atau tidak masalah yang harus dipecahkan memiliki substruktur optimal. Artinya, itu tergantung pada apakah atau tidak masalah memenuhi prinsip mengoptimalkan. Yang disebut substruktur optimal adalah mereka substruktur yang setiap solusi yang optimal dari masalah yang optimal seluruh (terbatas ini substruktur) juga merupakan solusi optimal. Dalam masalah optimal untuk pelurusan, substruktur ini ada. Sebagai contoh, mari
menjadi keselarasan yang optimal dari pasangan urutan yang diberikan
A = (a1, a2, • • •, ana), B = (b1, b2, • • •, BnB).
Kemudian skor penalti didefinisikan (lihat (1,8))
sebagai minimum, dimana w (a_
i) adalah skor hukuman a_
penalti matriks. Biasanya, untuk posisi tetap n0, hukuman diberikan oleh
Oleh karena itu, sepasang subsequence
juga merupakan suatu keselarasan yang optimal. Jika tidak, optimalitas dari A_ dan B_ tidak akan benar. Dengan demikian, kita dapat menggunakan algoritma pemrograman berbasis dinamis untuk mencari keselarasan yang optimal.
Dinamis pemrograman berbasis algoritma telah berhasil digunakan dalam bioinformatika untuk melakukan penyelarasan untuk waktu yang lama. Pada tahun 1970, Needleman dan Wunsch mengusulkan algoritma keselarasan global [69]. Pada tahun 1981, Smith dan Waterman memberikan bukti matematis [95] dan ditingkatkan algoritma untuk diterapkan pada keselarasan lokal. Kompleksitas waktu dan kompleksitas ruang kedua adalah O (n2). Meskipun kompleksitas waktu masih tidak dapat dikurangi, algoritma perbaikan banyak telah diusulkan [16-19] yang sangat mungkin mengurangi kompleksitas ruang, dari O (n2) menjadi O (n).

1.3.2 Algoritma Needleman-Wunsch, maka Algoritma Alignment global
Algoritma Needleman-Wunsch adalah algoritma keselarasan global untuk sepasang urutan. Prosedur adalah sebagai berikut:
Susun Dua Urutan dalam Tabel Dua-Dimensi
Jika urutan yang
A = (a1, a2, • • •, sebuah), B = (b1, b2, • • •, bm)
maka tabel dua dimensi dibangun seperti pada Tabel 1.1, di mana elemen s (i, j) pada tabel dua dimensi dihitung pada langkah 2.
Tabel 1.1. Dua dimensi tabel urutan A, B

Hitung Elemen s (i, j) dari Tabel Dua Dimensi
Setiap elemen s (i, j) dari tabel dua dimensi ditentukan oleh tiga unsur; s (i-1, j-1) di sudut kiri atas, s (i-1, j) pada sisi kiri dan s (i, j - 1) di atas. Pertama-tama, kita menentukan nilai s marjinal (i, 0) dan s (0, j). Untuk mempermudah, kita mengasumsikan bahwa skor penalti dari serangkaian simbol virtual d × | simbol maya | jika skor penalti dari simbol virtual adalah d, dimana, | maya simbol | adalah panjang dari string simbol virtual. Dengan demikian,
s (0, j) =-j × d, s (i, 0) =-i × d, membiarkan s (0, 0) = 0.
Kemudian, kita menghitung s (i, j) dengan rumus:
s (i, j) = max {s (i - 1, j - 1) + s (ai, bj), s (i - 1, j) - d, s (i, j - 1) - d}.
(1.11)
Gambar 1.1 mengilustrasikan perhitungan s (i, j).
Sementara menghitung s (i, j), kita juga harus menyimpan tiga tetangga s (i, j), yang akan digunakan untuk memproduksi jalur mundur dari algoritma traceback pada langkah berikutnya.

Traceback Algoritma
Nilai terakhir s (n, m) adalah nilai maksimum urutan (A, B) setelah selaras dan s (n, m) adalah titik awal dari jalur belakang. Untuk
Gambar. 1.1. Perhitungan S (i, j)
setiap s (i, j), jalur mundur dicatat dalam proses menghitung Tabel 1.1. Misalnya, jika s (i, j) = s (i-1, j-1) + s (ai, bj), kemudian jalur mundur adalah (i, j) - → (i - 1, j - 1) . Proceeding dari s (n, m) kembali ke akhir s (0, 0), kita menemukan jalur mundur. Kami mungkin memulihkan keselarasan dari urutan sesuai dengan jalur mundur sebagai berikut: Untuk elemen s (i, j) pada jalur mundur:
1. Catat pasangan yang sesuai dari asam nukleat ai, bi jika arah mundur adalah dari ai, bi ke sudut kiri.
2. Masukkan simbol virtual di urutan vertikal dan catatan (ai, -) jika arah horizontal.
3. Masukkan simbol virtual di urutan horizontal dan catatan (-, bi) jika arah vertikal.
4. Akhirnya, kami mendapatkan keselarasan yang optimal dari dua sekuens.
Pembaca harus mencatat bahwa kadang-kadang jalur mundur mungkin tidak unik karena metode backward itu sendiri mungkin tidak unik. Bahkan, adalah mungkin untuk memiliki keberpihakan yang optimal beberapa dengan skor yang optimal yang sama.
Contoh 3. Perhatikan urutan
Kita akan menggunakan algoritma pemrograman berbasis dinamis untuk mendapatkan pelurusan. Jika skor penalti adalah 5 untuk pencocokan, -3 karena tidak cocok, dan -7 untuk memasukkan simbol virtual, yaitu,
1. Membangun sebuah tabel dua dimensi dan menghitung nilai dari setiap elemen.
Nilai dari elemen dalam baris pertama didefinisikan oleh s (i, 0) =-i × d
dan nilai-nilai elemen pada kolom pertama didefinisikan oleh s (0, j) =
-J × d. Menurut langkah-langkah untuk menghitung s (i, j), kita dapat memperoleh nilai
dari semua (i, j) dan merekam arah mundur. Sebagai contoh, s (1, 1) =
max (0-3, -7 - 7, -7 - 7) = -3 dan arah mundur adalah (1, 1) - →
(0, 0). Hasilnya ditunjukkan pada Tabel 1.2.
Setelah dari Tabel 1.2, nilai elemen terakhir adalah 1, sehingga skor
dari keselarasan yang optimal urutan A, B adalah 1.
2. Traceback: Kami pergi ke belakang dari s (9, 8). Sebagai nilai s (8, 9) = 1 adalah
diperoleh dari elemen teratas yang kiri (7, 8), s (8, 9) = s (7, 8) + s (c, t) =
4-3 = 1, pertama kita mundur ke elemen teratas kiri (7, 8), (8, 9) - → (7, 8).
Ini diulang sampai jalan backtracking mencapai s (0, 0).
1,3 Dinamis Pemrograman Berbasis Algoritma untuk Alignment Berpasangan 21
Tabel 1.2. Dua dimensi tabel dibentuk oleh urutan A, B
Gambar. 1.2. Backtracking jalan
Jalur mundur adalah (8, 9) - → (7, 8) - → (6, 7) - → (5, 6) - →
(4, 5) - → (4, 4) - → (3, 3) - → (2, 2) - → (1, 1) - → (0, 0).
Gambar 1.2 menunjukkan representasi skematik jalur backtracking.
Menurut jalur belakang, kita dapat memulihkan hasil
keselarasan sebagai berikut:
A_ = (aaat-tagc),
B_ = (gtatatact).
1.3.3 Algoritma Smith-Waterman
Dalam bioinformatika, peran yang dimainkan oleh keselarasan global terbatas karena
kompleksitas urutan biologis. Sejak algoritma optimasi global yang selalu
mengabaikan sifat lokal, kadang-kadang kita prihatin dengan sifat global yang tidak
tapi dengan apakah dua sekuens memiliki daerah konservasi yang sama.
22 1 Pendahuluan
Sebagai contoh, dua sekuens dengan kesamaan global yang rendah mungkin memiliki domain
yang sangat homolog. Oleh karena itu, menemukan algoritma keselarasan yang
menargetkan "domain" dengan skor minimal hukuman akan lebih berguna dalam
praktek.
Algoritma Smith-Waterman adalah jenis algoritma keselarasan lokal.
Meskipun itu hanya mungkin tampak perbaikan yang dinamis pemrograman-
algoritma berbasis yang cocok keselarasan lokal, akan sangat banyak berguna dalam bioinformatika.
Sebagai contoh, BLAST, paket perangkat lunak terkenal, telah
dikembangkan berdasarkan algoritma ini. Dua aspek dari Smith-Waterman
algoritma yang masih dapat diperbaiki dinyatakan sebagai berikut.
Perhitungan Nilai dalam Tabel Dua-Dimensi
Algoritma Smith-Waterman menambahkan 0 sementara menghitung s (i, j). Dengan demikian,
nilai yang negatif tidak akan pernah terjadi dalam algoritma Smith-Waterman. Itu
keuntungan dari hal ini akan menjadi jelas ketika membangun jalur mundur.
s (i, j) = max
⎧ ⎪ ⎪ ⎨
⎪ ⎪ ⎩
0,
s (i - 1, j - 1) + s (xi, yj),
s (i - 1, j) - d,
s (i, j - 1) - d.
(1.12)
Traceback Algoritma
Titik awal dan akhir backtrace dari algoritma Smith-Waterman
berbeda dari algoritma keselarasan global. Titik awal dapat
dipilih secara sewenang-wenang dalam teori dan kami biasanya memilih elemen dengan lebih tinggi
skor. Titik akhir adalah elemen pertama dengan nilai 0 dalam proses
backtrace. Jika tujuan keselarasan adalah untuk menemukan keselarasan yang optimal dari dua
urutan, algoritma Smith-Waterman harus backdate dari elemen
dengan nilai maksimum dan tidak boleh berakhir pada elemen pertama dimana
nilai 0 muncul bukan s (0, 0). Titik awal dengan skor maksimal
menjamin skor maksimal sequence aligment lokal, dan titik akhir
adalah elemen pertama dengan nilai 0, memastikan segmen yang tidak terlampaui. Di
saat ini, segmen yang sesuai dengan jalur mundur adalah segmen
dengan hukuman maksimal.
Kami menggunakan contoh yang sama
_A = Aaattagc,
B = gtatatact,
untuk menemukan subsequence keselarasan yang optimal. Skor penalti adalah 5 untuk pencocokan,
-3 Untuk mismatching dan d = 3. Pembangunan dua dimensi
tabel dan perhitungan penyelarasan dua sekuens diberikan seperti yang ditunjukkan pada
Gambar. 1,3.
1,3 Dinamis Pemrograman Berbasis Algoritma untuk Alignment Berpasangan 23
Gambar. 1,3. Backtracking jalan
Skor maksimum dalam tabel ini adalah 13. Jadi, kita mulai dari yang sesuai
elemen s (6, 7) dan berhenti di s (2, 2) yang merupakan elemen pertama dengan nilai 0.
Kami kemudian mendapatkan jalur mundur sebagai berikut:
(8, 9) - → (6, 7) - → (5, 6) - → (4, 5) - → (4, 4) - → (3, 3) - → (2, 2).
Menurut ini jalur belakang, kita memperoleh penyelarasan berikut
segmen dengan skor penalti maksimal:
di-ta
atata
Diskusi Pemrograman Dinamis Berbasis Algoritma
Beberapa catatan tentang pemrograman berbasis algoritma dinamis diberikan di bawah ini:
1. Matriks hukuman yang berbeda menghasilkan keberpihakan yang berbeda. Jadi pilihan
matriks penalti yang tepat sangat penting untuk pemrograman dinamis
algoritma. Beberapa matriks hukuman sesuai untuk keselarasan dunia
dan beberapa untuk keselarasan lokal. Dalam kasus ekstrim di mana tidak ada
hukuman negatif dan simbol virtual juga tidak memberikan penalti (memilih
matriks penalti Hamming), hasil dari algoritma keselarasan lokal
hampir sama dengan algoritma keselarasan global.
2. Untuk sepasang urutan yang panjang adalah n dan m, masing-masing, kita menemukan
bahwa kompleksitas ruang dan kompleksitas waktu berdua O (nm). Jika
panjang dari dua sekuens kira-kira sama, maka kompleksitas
yang dekat dengan O (n2). Oleh karena itu, kompleksitas komputasi diperbolehkan
jika urutan lebih pendek. Namun, untuk urutan lagi, seperti
24 1 Pendahuluan
sebagai urutan genom, ini kompleksitas komputasi membuat masalah
komputasi intractble untuk masa kini komputer. Jika banyak berpasangan
keberpihakan harus dilakukan saat melakukan keberpihakan ganda, ruang lingkup
aplikasi dari algoritma pemrograman berbasis dinamis dibatasi.
Fakta bahwa kompleksitas waktu tidak akan dikurangi adalah kerugian besar
dari algoritma pemrograman berbasis dinamis, meskipun banyak
algoritma ditingkatkan [16-19] dapat mengurangi kompleksitas ruang ke level
sebagai O (n).
3. Salah satu tujuan buku ini adalah untuk menunjukkan bagaimana untuk membuat alignment
algoritma menggunakan analisis stokastik, sehingga kompleksitas waktu mungkin
dikurangi menjadi sesedikit O (n) untuk penyelarasan berpasangan. Oleh karena itu, kami akan
tidak membahas pemrograman dinamis berbasis algoritma lebih lanjut. Pembaca
disebut literatur yang relevan untuk wawasan lebih lanjut.
1,4 Notasi lain
Ada beberapa notasi yang sering muncul dalam buku ini ketika membahas alignment, dan kami akan membahas secara spesifik sekarang.
1.4.1 Korelasi Fungsi Urutan Lokal
Urutan Lokal
Misalkan A, B, C menjadi tiga urutan yang diberikan dalam (1.1), dan membiarkan na, nb, nc menjadi panjang mereka, masing-masing. Mari Na = {1, 2, • • •, na} adalah sebuah himpunan bilangan bulat yang merupakan set subskrip dari A. I subskrip ∈ Na Na adalah subscript (atau posisi untuk pendek) dari A. Jika urutan subset dari Na diwakili oleh α, β,
kemudian
α = {i1, i2, • • •, ik} (1.13)
adalah subset dari Na diatur dari yang terbesar ke nomor terkecil, 1 ≤ i1 <
i2 <• • • <ik ≤ N. Kemudian,
aα = {ai1, ai2, • • •, aik
} (1.14)
adalah subsequence dari A dalam α wilayah.
Jika Na dan α keduanya diberikan, maka kita menunjukkan αc = Na-α sebagai komplemen dari himpunan α dan αc sebagai subset dari himpunan Na. Dengan demikian, aαc adalah subsequence dari A dan A = (aα, aαc) disebut sebagai dekomposisi dari A. Dalam kasus khusus, membiarkan
α = [i, j], atau (i, j), [i, j), (i, j], dalam hal ini,
[I, j] = (i, i + 1, • • •, j), (i, j) = (i + 1, i + 1, • • •, j - 1),
[I, j) = (i, i + 1, • • •, j - 1), (i, j] = (i + 1, i + 1, • • •, j).
1,4 Notasi lain 25
Ini adalah interval tertutup, interval terbuka atau setengah terbuka interval Na, masing-masing. Vektor-vektor yang sesuai adalah kemudian
a [i, j] = (ai, ai +1, • • •, aj), a (i, j) = (ai +1, ai +1, • • •, aj-1),
a [i, j) = (ai, ai +1, • • •, aj-1), a (i, j] = (ai +1, ai +1, • • •, aj). (1.15)
Para subsequence dari (1.15) disebut sebagai vektor lokal didefinisikan pada interval [i, j], (i, j) atau [i, j), (i, j] Kami menggunakan. Notasi berikut untuk vektor lokal .
¯ = ai ai = (ai +1, +2 ai, • • •, ai + k), (1.16)
di mana saya menunjukkan posisi pertama dari vektor ¯ ai dan k menunjukkan panjang ¯ ai. Untuk mempermudah, kita pertimbangkan tiga simbol ¯, sebuah dan (k) untuk menjadi setara. Panjang vektor ¯ dan adalah selalu k kecuali dinyatakan khusus.
Korelasi Fungsi
Fungsi korelasi lokal urutan A, B berdasarkan hukuman matriks w didefinisikan sebagai berikut:
w (A, B; i, j, n) =
n
_
k = 1
w (ai + k, bj + k), i + n ≤ na, j + n ≤ nb. (1.17)
Dalam hal B = A, fungsi korelasi lokal di (1.17) menjadi fungsi autokorelasi lokal dari A.
1.4.2 Matriks Alignment Berpasangan antara Urutan Beberapa
Kami telah disebutkan di atas bahwa algoritma hukuman minimum untuk penyelarasan beberapa urutan adalah masalah yang belum terpecahkan dalam bioinformatika, meskipun algoritma cepat keselarasan berpasangan telah ditentukan. Oleh karena itu, kita membahas keselarasan berpasangan dalam beberapa urutan sebelum pindah ke keberpihakan ganda. Membiarkan
B = {B, t, s, t = 1, 2, • • •, M} = (B, t) s, t = 1,2, • • •, m (1.18)
adalah matriks urutan, di mana, masing-masing B, t = (bs, t; 1, bs, t, 2, • • •, bs, t; ns, t) adalah vektor lima dimensi. Artinya, untuk setiap s, t, j, ada bs, t j ∈ V5.
Definisi 4.
1. B matriks dalam (1.18) disebut sebagai perluasan berpasangan urutan beberapa A, jika (B, t, Bt, s) adalah perluasan dari pasangan berurutan (As, Pada) untuk setiap s, t.
2. Matrix = Bo (Bo s, t) s, t = 1,2, • • •, m (1.18) disebut sebagai matrik minimal hukuman keselarasan berpasangan untuk urutan beberapa A, jika Bo adalah matriks berpasangan ekspansi dari A dan (Bo s, t, Bo
t, s) adalah keselarasan urutan hukuman minimal (As, Pada) untuk semua s, t. Di sini, w (Bo s, t, Bo
t, s) = min {w (B; Bt): (B, Bt) adalah penyelarasan (As, Pada)}

Setelah algoritma keselarasan cepat berpasangan, kita dapat menentukan minimum matriks berpasangan keselarasan penalti Bo untuk urutan beberapa A. Salah satu tujuan dari buku ini adalah untuk menunjukkan bagaimana menggunakan Bo untuk membangun keselarasan hukuman minimum dari A.
1,5 Keterangan
Metode matematika diperkenalkan dalam buku ini cocok untuk bioinformatika dan siswa biologi komputasi. Selain itu, buku ini juga mengacu pada beberapa database penting, seperti GenBank [10], PDB [13], PDB-Pilih [41], Swiss-Prot [8, 33]. Pembaca diasumsikan akrab dengan database ini dalam aspek berikut:
1. Tahu situs Web yang menyediakan database dan mengetahui situasi memperbarui database ini.
2. Mengetahui isi dari database ini. Misalnya, representasi struktur primer, struktur sekunder, dan struktur 3D dapat ditemukan dalam database PDB; representasi gen, intron, dan ekson dalam GenBank, dll
3. Mengetahui cara mendapatkan data yang dibutuhkan saat menggunakan komputer untuk analisis, misalnya, tahu bagaimana menggunakan komputer untuk mendapatkan struktur primer, struktur sekunder, dan koordinat ruang dari atom diberikan berdasarkan database PDB.
4. Tahu cara menggunakan database yang sesuai untuk persyaratan lainnya [99].
Selain database, pembaca juga harus tahu cara menggunakan beberapa paket perangkat lunak populer, misalnya, BLAST [3], FASTA [73-75] dan paket perangkat lunak lain khusus (seperti paket perangkat lunak untuk penyelarasan beberapa) yang akan disebut kemudian. Untuk perangkat lunak visual, kami sarankan RASWIN [83], yang dapat digunakan untuk mencari konfigurasi 3D protein. Fungsinya lebih unggul paket lain dalam beberapa aspek seperti berputar, bergerak dan menandai objek. Ini tersedia sebagai download gratis dari situs Web-nya [76].
1,6 Latihan, Analisis, dan Komputasi
Latihan 1. Untuk urutan RNA E.co dan B.st diberikan dalam Tabel 4.5, menggunakan algoritma pemrograman berbasis dinamis untuk menghitung denda minimal mereka keselarasan berdasarkan matriks penalti Hamming.
Latihan 2. Untuk Mc urutan RNA. vanniel dan Mb. tautotr diberikan dalam Tabel 4.5, menggunakan algoritma pemrograman berbasis dinamis untuk menentukan urutan keselarasan optimal berdasarkan persyaratan sebagai berikut:
1. Hitung keselarasan hukuman minimal berdasarkan matriks penalti Hamming dan matriks WT-penalti, masing-masing.
2. Jika dH (a, b), a, b ∈ V5 adalah matriks penalti Hamming, maka GH (a, b) = 1 - dH (a, b), a, b ∈ V5 adalah matriks penilaian yang sesuai. Hitung keselarasan skor maksimal.
3. Bandingkan hasil komputasi dari keselarasan hukuman minimal dan penyelarasan skor maksimal.
Latihan 3. Melanjutkan dari Latihan 2, untuk Mc urutan RNA. vanniel dan Mb.tautotr, menghitung keselarasan yang optimal dengan menggunakan algoritma pemrograman berbasis dinamis, berdasarkan tiga kriteria dari matriks penalti Hamming, matriks WT-penalti dan matriks penilaian Hamming, masing-masing. Bandingkan hasil yang sesuai.
Latihan 4. Untuk sepasang sewenang-wenang dari urutan dengan panjang yang berbeda, menghitung keselarasan yang optimal menggunakan algoritma pemrograman berbasis dinamis, berdasarkan matriks penalti dan matriks penilaian, masing-masing.
Latihan 5. Uji dinamis pemrograman berbasis algorithmfor keselarasan berpasangan optimal sesuai dengan indeks berikut:
1. Untuk data dengan panjang 1 kbp, seperti Mc.vanniel urutan dan Mb.tautotr diberikan dalam Tabel 4.5, visual memeriksa apakah mereka tiba di sasaran.
2. Untuk data dengan panjang 1-100 kbp (seperti urutan 1-10 diberikan dalam Tabel 4.4), gunakan dinamis pemrograman berbasis algoritma untuk menguji hubungan antara panjang urutan dan waktu CPU yang dibutuhkan untuk perhitungan.
3. Menganalisis hubungan antara kesamaan dan waktu CPU yang dibutuhkan untuk perhitungan.
Mengisyaratkan
1. Data untuk dua urutan Mc.vanniel dan Mb.tautotr diberikan dalam Tabel 4.5 dapat didownload dari situs Web [99].
2. Algoritma pemrograman dinamis untuk penyelarasan yang optimal dari pasangan urutan yang harus dilakukan Sekte berikut. 1,3. Jika ini terbukti terlalu sulit, algoritma dari situs Web kami [99] bisa di-download, dan program Anda mungkin akan didasarkan pada itu.