Show simple item record

dc.contributor.advisorChambers, Desmond
dc.contributor.authorHealy, John
dc.description.abstractThe application of k-mer matching to problems in the field of bioinformatics is long established, with k-mer techniques underpinning standard heuristic approaches to sequence alignment and genome assembly. Despite their broad application, conventional k-mer matching techniques lack a native mechanism for accommodating sequence variability, requiring an exact match at pre-defined indices in a k-mer seed. This thesis presents a fuzzy approach for approximate k-mer matching and investigates its application to sequence alignment and comparative assembly. By combining the speed of hashing with the sensitivity of dynamic programming, fuzzy k-mers unify the two phases of the 'seed and extend' strategy into a single operation that executes in average constant time. In contrast with existing methods of k-mer matching, fuzzy k-mers provide native support for string variability. The fuzzy approach has been implemented in a prototype sequence aligner and genome assembler called Ferox. In addition to their exploitation for sequence alignment, the prototype directly integrates fuzzy k-mer alignments into the contig construction process by combining models of de novo and comparative genome assembly.en_US
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 Ireland
dc.subjectFuzzy hash mapsen_US
dc.subjectComparative assemblyen_US
dc.subjectFuzzy k-mersen_US
dc.subjectEngineering & Informaticsen_US
dc.titleFuzzy k-mers and their application to comparative genome assemblyen_US
dc.local.noteThis thesis describes how fuzzy string matching can be applied to the problems of sequence alignment and genome assembly, providing the sensitivity of approximate string matching with the execution speed of an exact search.en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Ireland
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Ireland