Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

DNA Sekanslama

Graf Algoritmaları başlığı altında ele alınan DNA problarının sekanslamasını konu alır
by

Ömer Talha

on 28 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of DNA Sekanslama

Sekanslamaya Hamilton yaklaşımı
Sekanslamaya Euler yaklaşımı
Kaynaklar
Shortest Superstring
Amaç
DNA Sekanslama
Grafları dizileme
Doğanaksoy, A., 1993, Graf Teorisi,
Matematik Dünyası,
http://bit.ly/1pAnANO
Jones, N.C., Pevzner, P.A.,
An Introduction to Bioinformatics Algorithms,
http://bit.ly/1nBggVS
How does the city of Königsberg relate to graph theory?,
Stemsims, http://bit.ly/1sFT0Wm
Eulerian path
, http://en.wikipedia.org/wiki/Eulerian_path
Önsoy, C., 2012, DNA Hibridizasyonu,
Türkiye'nin Biyoloji Günlügü
, http://bit.ly/1lbpuD9
Tomkins, J., Bergman, J., 2012,
Genomic monkey business—estimates of nearly identical human–chimp DNA similarity re-evaluated using omitted data
, http://creation.com/human-chimp-dna-similarity-re-evaluated
DNA Sekanslama
Biyoinformatik Algoritmalarına Giriş
Yrd. Doç Dr. Çigdem Selçukcan Erol
Ömer Talha Gülmezer
Istanbul Üniversitesi Enformatik Ana Bilim Dalı 2014
talhagulmezer@gmail.com
Königsberg Köprüleri
18. yy'nin ortalarında Königsberg şehri Pregel nehrinin iki yakası ve nehirdeki iki ada üzerine kurulmuştu. Bu adalar 7 köprü ile birbirlerine bağlanmışlardı.
Graf Algoritmaları
Graf oluşturma
DNA problarını düzene koyma
Birbirini takip diziler oluşturma
Karmaşıklığı giderme
Soru: Herhangi bir noktadan harekete başlayıp yedi köprünün hepsinden bir ve yalnızca bir kez geçip şehrin bütün bölümlerini dolaştıktan sonra başlangıç noktasına varılabilir mi?
Leonhard Euler
(1707-1783)
Düğüm
Kiriş
DerA=3
math

Graf
V={V1, V2, ..., Vn} köşe noktaları kümesi,
E={ViVj=(Vi, Vj) | i<>j
her i, j = 1,2,..,n} ayrıtlar kümesi o.ü.
G=G(V,E)'ye Graf denir.
Köprü Saplantı Problemi
'n' ada ve 'm' köprüden oluşmuş bir şehirde her köprüden yalnızca bir kere geçerek başlangıç noktasına gelinebilecek bir yol bulun.
Euler Çember Problemi
Herhangi bir kenarından bir kere geçilebilecek graf içeren bir çember bulunuz.
Yol: 1-2-3-4-5-6-3-7-2-9-11-8-7-12-11-10-9-1
Hamilton Çemberi
Bir grafın tüm köşelerini yalnızca bir kere içeren çemberlerdir.
Iki gen örnegi tipi
ve grafları
Hibridizasyon
Sentetik olarak çogaltılmış ve DNA probları olarak hazırlanmış spesifik DNA parçalarının, sekansı araştırılacak olan hedef DNA molekülü ile birleştirilmesi
TATCCGTTT
Hedef DNA
ATAGGCAAA
Tamamlayıcı DNA
Hibridizasyon
ATGCAGGTCC
Çoklu sekanslamaya Hamilton yaklaşımı
indegree(v) = outdegree(v)
Königsberg
Baglı graf
Baglı olmayan graf
Graflar birleştirilebilir
Spectrum(s,l)
= {ATG, GGT, GTG, TAT, TGC, TGG}
Spectrum
8 uzunluklu
s
= TATGGTGC dizisi
l=3'er gruplandırılmış
n
uzunluklu
s
dizisi
Her bir grupta
l
kadar nükleotit bazı
Full transcript