Biyoinformatik | Algoritma - 2
Ayşegül MURAT - Ege Üniversitesi Sağlık Biyoinformatiği A.B.D., Doktora Öğrencisi
Bilgisayar programları çeşitli biyoinformatik problemleri çözmek için gereklidir, çünkü milyonlarca işlemin gerçekleşmesi gerekebilir. Program tarafından kullanılan algoritma, programın işlemlerinin otomatikleştirilmesi için araçlar sağlar. Bir bilgisayar programı bir problemi çözmek için bir veya birden çok algoritmayı kullanan bir dizi talimattır. Bu sebeple algoritma, bir bilgisayar programında yapılandırılmış bir prosedür olarak tanımlanmıştır. İkili hizalama için kullandığımız BLAST programı dizi (sekans) hizalamalarını gerçekleştirmek için bir dizi algoritma kullanılır. Filogenetik ağaçları oluşturmak, ikili veya çoklu dizi hizalamak, sıralama, arama gibi problemleri çözmek için oldukça fazla sayıda algoritmalar vardır. Bir protein dizisini diğeriyle karşılaştırmak için yararlı olan bir algoritma, bir dizinin 10 milyon protein dizisi içeren bir veri tabanıyla karşılaştırmada işe yaramayabilir. Bunun sebebi, iki diziyi karşılaştırmak için yararlı olan algoritmanın 10 milyon diziyi karşılaştırmak için gerekli olan karmaşıklığın çözümüne sahip olamaması, tüm olasılıkları hızlıca hesaplamaya yatkın olmayışı olabilir. Hesaplama yaparken küçük bir bellek ve düşük işlemcili bilgisayar iki diziyi hizalayabilirken 10 milyon dizi hizalanmasında muazzam belleğe sahip bir bilgisayar ihtiyacımız ve algoritmanın yeniden hesaplanmasına ihtiyacımız olabilir.[1]
Algoritma 1 yazımın devamı olan bu yazımda algoritmanın özelliklerini temel olarak giriş (input), belirlilik (definiteness), çıktı (output), etkililik (efficiency) ve sınırlılık (boundedness) olarak beş ana başlığa ayırmıştık. Şimdi bunlar ne demekmiş bir göz atalım.
1.Girdi (Input)
Girdi olarak bir değer ya da değer kümesi alan algoritma, girdiyi çıktıya dönüştüren bir dizi hesaplama aşamasıdır. Örneğin, bir sayı dizisini azalan veya artan sıraya göre sıralamamız gerekebilir.[2] Burada girdimiz 1,5,390,45, 292, 23, 8 gibi sayısal değerler olmalıdır. Diğer örnekte isimlerin alfabetik olarak sıralanması olabilir ve burada sözel bir ifade ile ismin elma, kiraz, muz, karpuz gibi girdiler olması gerekir.
2. Belirlilik (Definiteness)
Algoritma oluşturulurken hangi adımda hangi işlemin yapılacağı kesin bir şekilde ifade edilmelidir. Her adım içinde belirsizlik olmadan yapılacak işlem açıklanmalıdır.[3]
3. Çıktı (Output)
Girdi örneğimizde programa verdiğimiz input değerlerin sıralanmış halini programdan çıktı olarak alırız. Çıktı değeri bir ya da birden fazla olabilir. Normal kod çalıştırılırken python için print fonksiyonunda program sonucu ekrana yazdırılır. Eğer siz işlemi bir .txt, .doc, .xlx uzantılı bir dosya içerisinde yazdırmak isterseniz bunu da yine ek satır kodlarla yapabilirsiniz. Burda bilmemiz gereken girdi ile çıktı arasında bir bağlantı olmasıdır. Girdiniz rakamlardan oluşuyor ve siz yapılacak işlemi belirlilik kısmında açıkça sıralanma istediğinizi belli ettikten sonra çıktı olarak sıralanmış rakamlara ulaşmış olursunuz.[2,3]
4. Etkiliik (Efficiency)
Aynı problemi çözmek için tasarlanan farklı algoritmalar, verimlilik açısından genellikle çarpıcı biçimde farklılık gösterirler ve bunlar donanım ya da yazılımdan kaynaklanan farklılıklardan çok daha önemli olabilir. Önemli olan kısım ise hafızada az yer tutan ve hızlı çalışan bir algoritma tasarlamak. İki sıralama algoritmasını karşılaştırdığımızda birinin n öğeyi sıralamak için n2 (n kare) sürede işlem yaptığını görürken, diğerinin log (n) ile orantılı olarak zaman aldığını görebiliriz.[2] Varsayalım bu iki teknik arasında donanımsal hiçbir fark olmadan karşılaştıracağız, log (n) olan bir algoritma, n2 (n kare) daha etkili çalışır. Log (n) aynı bilgisayarda bir işi saat bazında yaparken, n2 aynı işi gün bazında yaparak zamansal olarak düşük etkilikte kalacaktır. Algoritmanın etkililiği için genelde göreceğimiz ifadeler şunlar lg n (log n), kök n, n, n log(n), n2, n3, 2 üzeri n, n! (n faktöriyel)dir.
Şekil 1: Algoritmanın çalışma süresini ifade eden Big-O-Notasyonu karşılaştırılması.[4]
Big-O-Notasyonu
Bu kısımda algoritmanın karmaşıklığının büyüme hızını anlatan Big-O notasyonu kavramından da bahsetsek iyi olacaktır. Bilgisayar bilimcileri bir algoritmanın çalışma süresini tanımlamak için bu kavramı kullanırlar. Bir algoritmanın çalışma süresinin ikinci dereceden veya “0 (n2)” (n’2 – n kare) olduğunu söylersen bu, algoritmanın çalışma süresinin “n” büyüklüğünde bir girdi üzerinde çalışma süresinin n’nin ikinci dereceden bir fonksiyonu ile sınırlı olduğu anlamına gelir. 99.7n’2 ve 5n’2+3.2n+99993 şeklinde tanımlanan iki fonksiyon içinde aynı karmaşıklık sınıfında olduğunu söyleyebilir. Fakat 5n’2 (5n kare) ve 1.2n’3 (1.2 n küp) fonksiyonlarının karmaşıklık sınıfı farklıdır. Burada önemli olan önde gelen sabiti görmezden gelerek yalnızca en hızlı büyüyen terime dikkat etmek. Yani n kare olan bir fonksiyonu, n küp olan bir fonksiyona tercih ederiz ya da aynı sınıf içindeysek (99.7n’2 ve 5n’2+3.2n+99993 için) en hızlı büyüyen terimin (bu örnekte n kare) başındaki sabit sayının küçüklüğü bizim için önemlidir. [3] Bir algoritmanın verimliliği en kötü durumdaki etkinliği olarak belirlenmelidir. Bir algoritmanın en kötü durum verimliliğini göz önünde bulundurmanın avantajı, algoritmanın sizin tahmininizden daha kötü bir durumda davranmayacağının garantisidir. Verimliliği n! Olan bir algoritma iyileşerek 2n-n’3-n’2-n(log)n-n-log(n) olarak iyileştirilebilir fakat daha kötüsüne gidemez.[3,4]
5. Sınırlılık (Boundedness)
Bu kavramda aklımıza gelmesi gereken şey input olarak verdiğimiz bir değerin işlem sonucunda çıktı olarak almamız arasında verimli ve hafızada az yer kaplamasının yanı sıra algoritmanın sınırlı sayıda çalışan adımlarla birlikte bitmesi gerektiği. Yani bir sıralama işlemi yapılacağında algoritma çalıştığında n sayıda adımda bunu yapacağını sonra da işlemi sonlandıracağını bilmeliyiz. Sonsuz döngüde çalıştırılan bir algoritma sonuç vermeyecektir. Bir yerlerde bir zamansal hata verir ama sonuç vermez. Mesela aynı işlemi yapan bir sıralama algoritmasının birincisi bu işlemi 200 adımda yaparken diğeri 50 adımda yapıyor olsun. Amaç büyükten küçüğe sıralanmış rakamlara çıktı olarak ulaşmaksa her zaman tercihimiz az adımdan yana olur. Bu hem alandan, zamandan hem performanstan kar demektir. Yani bir algoritma mümkün olan en az adımla işlem yapmalıdır.[2,3]
Referanslar
1. Pevsner, J. (2015). Bioinformatics and functional genomics. John Wiley & Sons.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.
3. Jones, N. C., Pevzner, P. A., & Pevzner, P. (2004). An introduction to bioinformatics algorithms. MIT press.
4. Danziger, P. (2010). Big o notation. Source internet: http://www. scs. ryerson. ca/mth110/Handouts/PD/bigO. pdf, Retrieve: April.