{"id":65585,"date":"2018-03-09T22:53:41","date_gmt":"2018-03-09T22:53:41","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/novel-computational-methods-for-large-scale-genome-comparison\/"},"modified":"2018-03-09T22:53:41","modified_gmt":"2018-03-09T22:53:41","slug":"novel-computational-methods-for-large-scale-genome-comparison","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/informatica\/novel-computational-methods-for-large-scale-genome-comparison\/","title":{"rendered":"Novel computational methods for large scale genome comparison"},"content":{"rendered":"<h2>Tesis doctoral de <strong> Todd James Treangen <\/strong><\/h2>\n<p>The current wealth of available genomic data embodies a wide variety of species, spanning all domains of life, thus  providing an unprecedented opportunity to compare and contrast evolutionary histories of closely and distantly related  organisms. The identification of homologous dna is a fundamental building block of comparative genomic and  molecular evolution studies. To date, sequence alignment has proven to be a versatile tool for comparing closely and  distantly related organisms, nucleotide at a time.  For pairwise comparisons, optimal global and local alignment for a  given scoring scheme requires o (m x n) time and space with respect to the lengths m,n of the genomes. This  computational bottleneck becomes exponential for multiple genomes, o (nk ) for k genomes, making large scale  multiple genome alignment a daunting task using traditional methods.    the focus of this dissertation is on developing novel algorithms and software for efficient global and local comparison  of multiple genomes and the application of these methods for a biologically relevant case study. The thesis research  is organized following the main focus into three successive phases, specifically: (1) multiple genome alignment of  closely related species, (2) local multiple alignment of interspersed repeats, and finally, (3) a comparative genomics  case study of dna uptake sequences (dus) in nesseria.    in phase 1, we first develop an efficient algorithm and data structure for maximal substring match search in multiple  genome sequences. Our approach for searching for maximal unique substrings yields significant improvements, in  both time and space, over existing methods when dealing with multiple genome sequences. Specifically, given s1 &#8230;   sm genome sequences (where s1 is the smallest genome), we are able to find the maximal unique substrings among  all of the sequence in linear time o(|s1|+ &#8230; + Sm|) and linear space o(|s1|). We then implement these contributions  into an interactive multiple genome comparison and alignment tool, m-gcat, which can efficiently construct multiple  genome comparison frameworks in closely related species. In phase 2, we present a novel computational method for  local multiple alignment of interspersed repeats. Our method for local alignment of interspersed repeats features a  novel method for gapped extensions of chained seed matches, joining global multiple alignment with a homology test  based on a hidden markov model. We implement our method for local alignment of interspersed repeats into the open  source procrastalign software. In phase 3, using the results from the previous two phases we perform a case study of  neisserial genomes by tracking the propagation of repeat sequence elements in attempt to understand why the  important pathogens of the neisserial group have sexual exchange of dna by natural transformation.    in conclusion, our global contributions in this dissertation have focused on comparing and contrasting evolutionary  histories of related organisms via their genomes. We have proposed novel data structures, algorithms, and software  for active areas of research in comparative genomics. We have experimentally demonstrated the efficiency and  accuracy of the computational methods presented in this thesis for multiple alignment, and have implemented all data  structures and algorithms in freely available software.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Novel computational methods for large scale genome comparison<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Novel computational methods for large scale genome comparison <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Todd James Treangen <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Polit\u00e9cnica de catalunya<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 25\/06\/2008<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>Xavier Messeguer Peypoch<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: fernando Gonz\u00e1lez lagunas <\/li>\n<li>torbjorn Rognes (vocal)<\/li>\n<li>cedric Notredame (vocal)<\/li>\n<li>Mar\u00eda  del mar Alba soler (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Todd James Treangen The current wealth of available genomic data embodies a wide variety of species, spanning [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[36483,13880,15596],"tags":[119942,53948,84363,144613,144614,78936],"class_list":["post-65585","post","type-post","status-publish","format-standard","hentry","category-biologia-molecular","category-informatica","category-politecnica-de-catalunya","tag-cedric-notredame","tag-fernando-gonzalez-lagunas","tag-maria-del-mar-alba-soler","tag-todd-james-treangen","tag-torbjorn-rognes","tag-xavier-messeguer-peypoch"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/65585","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=65585"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/65585\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=65585"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=65585"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=65585"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}