Pairwise whole genome alignment using locally consistent parsing
Yerel tutarlı ayrısştırma kullanarak ikili tüm genom hizalama
- Tez No: 993239
- Danışmanlar: DOÇ. DR. CAN ALKAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2026
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- Yeraltı kömür gazlaştırma prosesinin nümerik ve laboratuvar simulasyonu geri ve ileri yanma teknikleri
Numerical and laboratory simulation of underground coal gasification process-reverse and forward combustion techniques
FÜSUN F. OKUTAN
- İkili topolojik (bitopolojik) uzaylarda bazı yeni ayırma aksiyomları
Some new separation axioms in bitopological spaces
ALEV KANIBİR
- The Study of the conformational statistics and dynamics of polymer chains using the rotational isomeric state formalism
Başlık çevirisi yok
TÜRKAN HALİLOĞLU
