Geri Dön

Pairwise whole genome alignment using locally consistent parsing

Yerel tutarlı ayrısştırma kullanarak ikili tüm genom hizalama

PDF İndir

  1. Tez No: 993239
  2. Yazar: ECEM İLGÜN
  3. Danışmanlar: DOÇ. DR. CAN ALKAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2026
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

İkili tam genom hizalama, evrimsel analiz, varyant keşfi ve karşılaştırmalı genomik alanlarında uygulamaları olan hesaplamalı biyolojide temel bir problemdir. Minimap2, Progressive Mauve ve Mummer4 gibi yerleşik araçlar önemli ilerlemeler kaydetmiş olsa da, referans kalitesindeki montajların artan uzunluğu ve karmaşıklığı önemli ölçekleme zorlukları ortaya çıkarmaktadır. Milyar baz çifti ölçeğinde, verimli hizalama tipik olarak genomları bölümleyen temsili özetlerin daha sonra hizalamayı yönlendirmek için enuygun bir zincirde birleştirildiği tohum-zincir-uzatma sezgisel yöntemine dayanır. Dağıtılmış ve paralelleştirilmiş çoklu genom hizalaması, bağımsız olarak işlenebilen daha küçük parçalara giriş genomlarının verimli bir şekilde bölümlenmesine dayanır. Mevcut bölümleme yöntemleri genellikle özetleme için maksimal tam eşleşmeler (MEM), maksimal benzersiz eşleşmeler (MUM) veya küçültücülere (İng., \textit{minimizer}) dayanır. Bununla birlikte, MEM/MUM'lar için, hizalama süreci, n boyutundaki bir dizgede m boyutundaki MEM'leri bulmak için gereken O(m*logn) zaman karmaşıklığı ile karmaşıklaşır. Benzer şekilde, küçültücüler kısa uzunlukları nedeniyle dağılım desenleri ve frekanslarında dezavantajlara sahiptir, bu da hesaplama ve iletişim yükü açısından alt optimal bölümlemeye yol açar. Küçültücülerle karşılaştırıldığında, Yerel Tutarlı Ayrıştırma (LCP), genomlar arasında tutarlı olarak bulunan ``çekirdekler'' veya kısa genomik dizileri tanımlayarak girdi verilerinin daha kapsamlı ve yoğun bir temsilini sunabilir. Hiyerarşik bir tohum-zincirleme-uzatma stratejisi kullanan, hızlı ve paralelleştirilebilir bir ikili genom hizalama çerçevesi geliştiriyoruz: Bir LCP seviyesinde tohumlama yapıp eşleşmeleri zincirleyerek birleştiriyor, hizalanmamış bölgeleri tespit ediyor ve her bir bölge için bir alt seviyede sadece o bölgeyi tohumlayarak minimum seviyeye ulaşana kadar işlemi özyinelemeli olarak tekrarlıyoruz. LCP çekirdekleri, doğrusal zamanda hiyerarşik olarak hesaplanabilmekte, bu da daha dengeli hesaplama yükleri sağlamaktadır. LCPtools'u ChainX-LCP zincirleme algoritmasıyla entegre ettik ve E. coli (K-12'ye karşı Sakai) ile insan (GRCh38'e karşı CHM13) genomları üzerinde değerlendirdik. İnsan genomunda tohumlama işlemimiz 68 saatte tamamlanırken, Mumemto 540 saat sonra hala çalışmaya devam ediyordu; bu durum, referans kalitesindeki birleştirmeler için ölçeklenebilirliği kanıtlamaktadır.

Özet (Çeviri)

Pairwise whole-genome alignment is a fundamental problem in computational biology, with applications in evolutionary analysis, variant discovery and comparative genomics. This work focuses on the massive scaling challenges in pangenome analysis by using a hierarchical sketching method based on Locally Consistent Parsing (LCP). On a scale of billions of base pairs, efficient alignment typically relies on the seed-chain-extend heuristic: find exact-matching sketches (seeds), chain them co-linearly, and extend into the gaps. Established tools use minimizers or maximal unique matches (MUMs); we instead use LCP cores, which offer complete coverage, consistent spacing, and fewer seeds at higher levels. Distributed and parallelized multiple genome alignment relies on efficiently partitioning the input genomes into smaller segments that can be processed independently. Existing partitioning methods often rely on maximal exact matches (MEMs), maximal unique matches (MUMs), or minimizers for sketching. However, for MEMs/MUMs, the alignment process is complicated by the O(m · log n) time required to find MEMs of size m in a string of size n. Similarly, minimizers exhibit drawbacks in their distribution patterns and frequencies due to their short length, leading to suboptimal partitioning in terms of computational and communication overhead. Compared to minimizers, Locally Consistent Parsing (LCP) can offer a more thorough and condensed representation of the input data by identifying“cores,”or brief genomic sequences that are consistently present across genomes. We develop a fast, parallelizable pairwise genome alignment framework that uses a seed-as-you-go strategy: seed at one LCP level, chain and merge matches, find unaligned regions, and, for each region, recurse by seeding only that region at the next lower level until a minimum level is reached. LCP cores can be computed hierarchically in linear time, leading to more balanced computational loads. We integrated LCPtools with the ChainX-LCP chaining algorithm and evaluated on E. coli (K-12 vs Sakai) and human (GRCh38 vs CHM13); on the human genome our seeding completed in 68 h while Mumemto was still running after 540 h, demonstrating scalability for reference-grade assemblies.

Benzer Tezler

  1. Tez No

    887096

    Phylogeography of the Savi's pipistrelle (Vespertilionidae, chiroptera) complex based on whole mitochondrial genome analysis

    Savi'nin cüce yarasası kompleksinin (Vespetilionidae, chiroptera) filocoğrafyasının tüm mitokondriyal genom ile analizi

    YELİZ ERGÖL

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Genetikİstanbul Teknik Üniversitesi

    İklim ve Deniz Bilimleri Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ EMRAH ÇORAMAN

  2. Tez No

    833655

    Türkiye'nin çeşitli bölgelerindeki ruminantlardan izole edilen Brucella türlerinin tüm genom dizileme temelli analizi

    Whole genome sequencing based analysis of Brucella species isolated from ruminants in various regions of Türkiye

    SONGÜL ÖTKÜN

    Doktora

    Türkçe

    Türkçe

    2023

    Veteriner HekimliğiHarran Üniversitesi

    Veterinerlik Mikrobiyolojisi Ana Bilim Dalı

    PROF. DR. SEVİL ERDENLİĞ GÜRBİLEK

  3. Tez No

    569804

    De novo SNP calling and demographic inference using trio genome data

    Trio verisi ile de novo SNP çağırma ve demografik geçmiş analizi

    ELİF BOZLAK

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    BiyolojiOrta Doğu Teknik Üniversitesi

    Sağlık Bilişimi Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AYBAR CAN ACAR

    DOÇ. DR. MEHMET SOMEL

  4. Tez No

    335216

    Fasulye (Phaseolus vulgaris L.)'de ekonomik öneme sahip bazı agronomik karakterleri kontrol eden dna markırlarının ilişki haritalaması ile saptanması

    Detection of dna markers controlling some economically important agronomic characters by association mapping in common bean (Phaseolus vulgaris L.)

    SEDA NEMLİ

    Doktora

    Türkçe

    Türkçe

    2013

    BiyoteknolojiEge Üniversitesi

    Biyoteknoloji Ana Bilim Dalı

    PROF. DR. M. BAHATTİN TANYOLAÇ

  5. Tez No

    309393

    Identification of disease related significant SNPs

    Bir hastalığa ilişkin önemli tekli nükleotid polimorfizmlerin belirlenmesi

    CEYDA SOL

    Yüksek Lisans

    İngilizce

    İngilizce

    2010

    BiyomühendislikSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OSMAN UĞUR SEZERMAN

    YRD. DOÇ. DR. NİLAY NOYAN

Geri Dön