Genome Assembly as Shortest Superstring (Rosalind)

    

   

Halo teman-teman, apa kabar? Kali ini saya ingin membahas sedikit tentang salah satu problem yang ada di web rosalind.info. Judulnya ialah "Genome Assembly as Shortest Superstring". Sebagai acuan, teman-teman bisa cek dahulu problem yang akan kita bahas (disini). 

Fragment assembly: menyusun kembali DNA yang terpisah.

Overview 

Di problem ini kita akan disajikan bebarapa string (sebut saja array string S[]) dalam format FASTA. Tugas kita ialah mencari superstring dari string-string S[]. Superstring ialah, analoginya, jika kumpulan substring bersatu menjadi string, maka kumpulan string bersatu menjadi superstring. 

Ide dari penyelesaiannya ialah, pertama, mengurutkan string-string S[] berdasarkan prefix dan suffix-nya. Setelah urut, hapus bagian yang overlapping dari string S[] untuk mencegah double writing. 

Kode Pengerjaan

Berikut kode pengerjaannya dalam bahasa java :

1. static class Data {
2. int ances = -1;
3. int success = -1;
4. int diambil = 0;
5. String strand;
6. Data (String s) {
7. this.strand = s;
8. }
9. }
10. static void dirajang (Vector<Data> vStrand, Map<String, Vector<Integer>> cekPrev, Map<String, Vector<Integer>> cekSuff, int giliran) {
11. String s = vStrand.lastElement().strand;
12. int n = s.length();
13. String prev = "";
14. String suff = "";
15. int diambil = 1;
16. for (int i = 0; i < n / 2; i++) {
17. prev += s.charAt(i);
18. suff = s.charAt(n - 1 - i) + suff;
19. }
20. for (int i = n / 2; i < n; i++) {
21. if (cekSuff.containsKey(prev += s.charAt(i))) {
22. int cekSuffInt = cekSuff.get(prev).get(0);
23. vStrand.lastElement().ances = cekSuffInt;
24. vStrand.get(cekSuffInt).success = giliran;
25. vStrand.lastElement().diambil = i + 1;
26. cekSuff.get(prev).remove(0);
27. }
28. if (cekPrev.containsKey(suff = s.charAt(n - 1 - i) + suff)) {
29. int cekPrevInt = cekPrev.get(suff).get(0);
30. vStrand.lastElement().success = cekPrevInt;
31. vStrand.get(cekPrevInt).ances = giliran;
32. vStrand.get(cekPrevInt).diambil = i + 1;
33. cekPrev.get(suff).remove(0);
34. }
35. if (!cekPrev.containsKey(prev)) cekPrev.put(prev, new Vector<>());
36. cekPrev.get(prev).add(giliran);
37. if (!cekSuff.containsKey(suff)) cekSuff.put(suff, new Vector<>());
38. cekSuff.get(suff).add(giliran);
39. diambil++;
40. }
41. }
42. static void slashAndPrint (Data data) {
43. for (int i = data.diambil; i < data.strand.length(); i++) {
44. out.print(data.strand.charAt(i));
45. }
46. }
47. static void solve() {
48. Scanner sc = new Scanner(System.in);
49. Map<String, Vector<Integer>> cekPrev = new HashMap<>();
50. Map<String, Vector<Integer>> cekSuff = new HashMap<>();
51. Vector<Data> vStrand = new Vector<>();
52. int giliran = 0;
53. sc.next();
54. while (sc.hasNext()) {
55. String s = "";
56. while (sc.hasNext()) {
57. String masuk = sc.next();
58. if (masuk.charAt(0) == '>') break;
59. s += masuk;
60. }
61. vStrand.add(new Data(s));
62. dirajang(vStrand, cekPrev, cekSuff, giliran);
63. giliran++;
64. }
65. for (int i = 0; i < vStrand.size(); i++) {
66. if (vStrand.get(i).ances == -1) {
67. int pvt = i;
68. do {
69. slashAndPrint(vStrand.get(pvt));
70. pvt = vStrand.get(pvt).success;
71. } while (pvt != -1);
72. }
73. }
74. } 
    

Penjelasan Kode

Kita mulai dari baris 47 (static void solve()). Pertama, kita masukkan dahulu string S[] (baris 54-64). Sembari memasukkan string, kita bisa sekalian mencari prefix dan suffix mana yang cocok dan bisa digabungkan (baris 62). 

Di fungsi static void dirajang() (baris 10-41) saya memberi tanda urutan (1, 2, 3, ...) pada string-string S[]. Angka tersebut berfungsi sebagai penanda urutan sewaktu men-print jawabannya. 

Langkah terakhir ialah men-print jawaban. Susun string-string S[] berdasarkan penanda urutan. Gabungkan semua menjadi 1 superstring. Dalam men-print jawaban, jangan lupa menghapus bagian-bagian DNA yang overlapping atau bertumpukan pada superstring. 

Input dan Output

Seperti yang teman-teman lihat; disini, saya memakai fungsi next() (baris 57) untuk meng-input data string. Saya menggunakan hasNext() (baris 56) dikarenakan fungsi tersebut mampu meng-input data yang tidak diketahui jumlahnya. Fungsi tersebut sangat cocok jika dipakai untuk menangani input dengan format FASTA. 

Sedangkan untuk output-nya saya memakai fungsi out.print() (baris 44). Fungsi tersebut adalah modifikasi dari fungsi System.out.print() yang merupakan fungsi default di java. Untuk lebih jelasnya, teman-teman bisa melihat kode tambahan untuk memodifikasi fungsi tersebut (input maupun output) di versi lengkap kode saya di github. 

Sekian dari saya. Jika teman-teman ingin menanyakan sesuatu, teman-teman bisa menulisnya di kolom komentar. Semoga bermanfaat dan sampai jumpa di artikel berikutnya!

Referensi :

Sumber gambar 1: https://www.facebook.com/ProjectRosalind/

Sumber gambar 2: https://www.researchgate.net/figure/DNA-assemblyDNA-assembly-1st-step-The-DNA-is-purified-and-extracted-2nd-step-DNA-is_fig9_252323690