{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"id":[{"id":"https:\/\/ror.org\/03mb6wj31","id-type":"ROR","asserted-by":"publisher"},{"id":"https:\/\/www.isni.org\/000000041937028X","id-type":"ISNI","asserted-by":"publisher"},{"id":"https:\/\/www.wikidata.org\/entity\/Q1640731","id-type":"wikidata","asserted-by":"publisher"}],"name":"Universitat Polit\u00e8cnica de Catalunya","acronym":["UPC"]}],"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T18:50:34Z","timestamp":1768762234138,"version":"3.49.0"},"reference-count":0,"publisher":"Universitat Polit\u00e8cnica de Catalunya","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Les seq\u00fc\u00e8ncies s\u00f3n una de les estructures de dades m\u00e9s vers\u00e0tils que existeixen. De forma relativament senzilla, en una seq\u00fc\u00e8ncia de s\u00edmbols es pot emmagatzemar informaci\u00f3 de qualsevol tipus. L'an\u00e0lisi sistem\u00e0tic de seq\u00fc\u00e8ncies es un \u00e0rea molt rica de l'algor\u00edsmica amb numeroses aproximacions desenvolupades amb \u00e9xit. En concret, la comparaci\u00f3 de seq\u00fc\u00e8ncies mitjan\u00e7ant l'alineament d'aquestes \u00e9s una de les eines m\u00e9s potents. Una de les aproximacions m\u00e9s populars i eficients per alinear dues seq\u00fc\u00e8ncies es l'\u00fas de la programaci\u00f3 din\u00e0mica. Malgrat la seva evident utilitat, un alineament de dues seq\u00fc\u00e8ncies no \u00e9s sempre la millor opci\u00f3 per a caracteritzar la seva funci\u00f3. Moltes vegades, les seq\u00fc\u00e8ncies codifiquen la informaci\u00f3 en diferents nivells (meta-informaci\u00f3). &lt;br\/&gt;\u00c9s llavors quan la comparaci\u00f3 directa entre dues seq\u00fc\u00e8ncies no es capa\u00e7 de revelar aquelles estructures d'ordre superior que podrien explicar la relaci\u00f3 establerta entre aquestes seq\u00fc\u00e8ncies.&lt;br\/&gt;&lt;br\/&gt;Amb aquest treball hem contribu\u00eft a millorar la forma en que dues seq\u00fc\u00e8ncies poden ser comparades, desenvolupant una fam\u00edlia d'algorismes d'alineament de la informaci\u00f3 d'alt nivell codificada en seq\u00fc\u00e8ncies biol\u00f2giques (meta-alineaments). Inicialment, hem redissenyat un antic algorisme, basat en programaci\u00f3 din\u00e0mica, que \u00e9s capa\u00e7 d'alinear dues seq\u00fc\u00e8ncies de meta-informaci\u00f3, procedint despr\u00e9s a introduir-hi v\u00e0ries millores per accelerar la seva velocitat. A continuaci\u00f3 hem desenvolupat un algorisme de meta-aliniament capa\u00e7 d'alinear un n\u00famero m\u00faltiple de seq\u00fc\u00e8ncies, combinant l'algorisme general amb un esquema de clustering jer\u00e0rquic. A m\u00e9s, hem estudiat les propietats dels meta-alineaments produ\u00efts, modificant l'algorisme per tal d'identificar alineaments amb una configuraci\u00f3 no necess\u00e0riament col.lineal, el que permet llavors la detecci\u00f3 de permutacions en els resultats.&lt;br\/&gt;&lt;br\/&gt;La vida molecular \u00e9s un exemple paradigm\u00e1tic de la versatilitat de les seq\u00fc\u00e8ncies. Les comparaciones entre genomes, ara que la seva seq\u00fc\u00e8ncia est\u00e0 disponible, permeten identificar numerosos elements biol\u00f2gicament funcionals. La seq\u00fc\u00e8ncia de nucle\u00f2tids de molts gens, per exemple, es troba acceptablement conservada entre diferents esp\u00e8cies. En canvi, les seq\u00fc\u00e8ncies que regulen la activaci\u00f3 dels propis gens s\u00f3n m\u00e9s curtes i variables. Aix\u00ed l'activaci\u00f3 simult\u00e0nea d'un conjunt de gens es pot explicar nom\u00e9s a partir de la conservaci\u00f3 de configuracions comunes d'elements reguladors d'alt nivell i no pas a partir de la simple conservaci\u00f3 de les seves seq\u00fc\u00e8ncies. Per tant, hem entrenat els nostres programes de meta-alineament en una s\u00e8rie de conjunts de regions reguladores recopilades per nosaltres mateixos de la literatura i despr\u00e8s, hem provat la utilitat biol\u00f2gica de la nostra aproximaci\u00f3, caracteritzant autom\u00e0ticament de forma exitosa les regions activadores de gens humans conservats en altres esp\u00e8cies.<\/jats:p>\n                <jats:p>The sequences are very versatile data structures. In a straightforward manner, a sequence of symbols can store any type of information. Systematic analysis of sequences is a very rich area of algorithmics, with lots of successful applications. The comparison by sequence alignment is a very powerful analysis tool. Dynamic programming is one of the most popular and efficient approaches to align two sequences. However, despite their utility, alignments are not always the best option for characterizing the function of two sequences. Sequences often encode information in different levels of organization (meta-information). In these cases, direct sequence comparison is not able to unveil those higher-order structures that can actually explain the relationship between the sequences.&lt;br\/&gt;&lt;br\/&gt;We have contributed with the work presented here to improve the way in which two sequences can be compared, developing a new family of algorithms that align high level information encoded in biological sequences (meta-alignment). Initially, we have redesigned an existent algorithm, based in dynamic programming, to align two sequences of meta-information, introducing later several improvements for a better performance. Next, we have developed a multiple meta-alignment algorithm, by combining the general algorithm with the progressive schema. In addition, we have studied the properties of the resulting meta-alignments, modifying the algorithm to identify non-collinear or permuted configurations.&lt;br\/&gt;&lt;br\/&gt;Molecular life is a great example of the sequence versatility. Comparative genomics provide the identification of numerous biologically functional elements. The nucleotide sequence of many genes, for example, is relatively well conserved between different species. In contrast, the sequences that regulate the gene expression are shorter and weaker. Thus, the simultaneous activation of a set of genes only can be explained in terms of conservation between configurations of higher-order regulatory elements, that can not be detected at the sequence level. We, therefore, have trained our meta-alignment programs in several datasets of regulatory regions collected from the literature. Then, we have tested the accuracy of our approximation to successfully characterize the promoter regions of human genes and their orthologs in other species.<\/jats:p>","DOI":"10.5821\/dissertation-2117-93965","type":"dissertation","created":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T01:26:15Z","timestamp":1696641975000},"approved":{"date-parts":[[2006,7,21]]},"source":"Crossref","is-referenced-by-count":0,"title":["Meta-alignment of biological sequences"],"prefix":"10.5821","author":[{"sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrique","family":"Blanco Garc\u00eda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3865","container-title":[],"original-title":[],"deposited":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T06:29:42Z","timestamp":1768717782000},"score":1,"resource":{"primary":{"URL":"https:\/\/hdl.handle.net\/2117\/93965"}},"subtitle":[],"editor":[{"given":"Xavier","family":"Messeguer Peypoch","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Roderic","family":"Guig\u00f3 Serra","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.5821\/dissertation-2117-93965","relation":{},"subject":[]}}