Reconstruction of ancestral non-coding RNA sequences using sequential and structural information with tree decomposition

Simple item page
dc.contributor.authorHu, Songdi
dc.contributor.examiningcommitteeDurocher, Stephane (Computer Science)
dc.contributor.examiningcommitteeTurgeon, Maxime (Statistics)
dc.contributor.supervisorTremblay-Savard, Olivier
dc.date.accessioned2025-01-17T22:27:56Z
dc.date.available2025-01-17T22:27:56Z
dc.date.issued2024-12-31
dc.date.submitted2025-01-01T00:42:52Zen_US
dc.date.submitted2025-01-17T20:01:11Zen_US
dc.degree.disciplineComputer Science
dc.degree.levelMaster of Science (M.Sc.)
dc.description.abstractAncestral sequence reconstruction aims to infer what was the content of certain biological sequences of interest for ancestral species that do not exist anymore. This is accomplished by comparing and extracting similarities and differences from the sequences in extant (i.e. living) species. Since the search space is quite large, a lot of research has been devoted to the design of efficient and accurate methods to solve different variations of this problem. However, ancestral sequence reconstruction becomes even more complex when the goal is to reconstruct the ancestors of sequences that are not well conserved in extant species. This is the case with non-coding RNA (ncRNA) sequences, for which the structure (formed by base pairing) is more conserved than the actual sequences. One recent approach to tackle the ancestral reconstruction of ncRNA sequences involved considering the sequences of two related ncRNA families simultaneously. Although this helped avoid biases in the reconstruction, some cost calculations had to be simplified for efficiency. In this thesis, the goal was to improve the cost calculation of that approach by using a more advanced structural model and tree decomposition to partition the cost calculation into subproblems. Our results demonstrate an important gain in accuracy and a significant reduction in the number of optimal sequences inferred.
dc.description.noteFebruary 2025
dc.identifier.urihttp://hdl.handle.net/1993/38836
dc.language.isoeng
dc.subjectncRNA
dc.subjectancestral inference
dc.subjectsecondary structure
dc.subjecttree decomposition
dc.subjectphylogeny
dc.titleReconstruction of ancestral non-coding RNA sequences using sequential and structural information with tree decomposition
local.subject.manitobano
oaire.awardNumberRGPIN-2016-06051
oaire.awardTitleAnalysis of tRNA gene evolution in bacterial genomes
oaire.awardURIhttps://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749933
project.funder.identifierhttps://doi.org/10.13039/501100000038
project.funder.nameNatural Sciences and Engineering Research Council of Canada
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Hu_Songdi.pdf
Size:
1.32 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
770 B
Format:
Item-specific license agreed to upon submission
Description:
Download
Collections
FGS - Electronic Theses and Practica