Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Automata-based algorithms for detecting minisatellites and satellites
Thesis (PhD(Computer Science))--University of Pretoria, 2019.
Saved in:
| Other Authors: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
University of Pretoria
2019
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613660776497152 |
|---|---|
| access_status_str | Open Access |
| author2 | Kourie, Derrick George |
| author_browse | Kourie, Derrick George |
| author_facet | Kourie, Derrick George |
| collection | Thesis |
| dc_rights_str_mv | © 2019 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. |
| description | Thesis (PhD(Computer Science))--University of Pretoria, 2019. |
| format | Thesis |
| id | oai:repository.up.ac.za:2263/72550 |
| institution | University of Pretoria (South Africa) |
| language | English |
| last_indexed | 2026-06-10T12:39:41.079Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UPSpace — University of Pretoria Institutional Repository |
| publishDate | 2019 |
| publishDateRange | 2019 |
| publishDateSort | 2019 |
| publisher | University of Pretoria |
| publisherStr | University of Pretoria |
| record_format | dspace |
| source_str | UPSpace — University of Pretoria Institutional Repository |
| spelling | oai:repository.up.ac.za:2263/72550 Automata-based algorithms for detecting minisatellites and satellites Kourie, Derrick George corne.algo@gmail.com De Ridder, Corne UCTD Tandem Repeats (TRs) FireSat algorithms Minisatellites Engineering, built environment and information technology theses SDG-03 Engineering, built environment and information technology theses SDG-09 Thesis (PhD(Computer Science))--University of Pretoria, 2019. This work is a significant extension of earlier research that was conducted in fulfilment of the requirements of an MSc degree in Computer Science at the University of Pretoria. The MSc research verified the hypothesis: Finite automata can detect microsatellites effectively in deoxyribonucleic acid (DNA). The purpose of this thesis is to extend the above hypothesis to minisatellites and satellites in particular with regards to accuracy. Microsatellites, minisatellites and satellites are subsets of tandem repeats (TRs). TRs refer to consecutive motifs contained by genomic sequences. A perfect TR is defined as a string of nucleotides which is consecutively repeated at least twice. An approximate TR is a string of nucleotides repeated at least twice, allowing for some differences between the instances. Recent articles dealing with TR detection report that current implemented TR detector algorithms are not exhaustive. Consequently TRs from several TR detectors should be combined to ensure reliable TR annotation. In order to verify the hypothesis Counting Finite Automata can detect minisatellites and satellites accurately in DNA four theoretically related algorithms, collectively referred to as FireSat, are proposed. Of these FireSat1, FireSat2 and FireSat3 have been implemented. There is reported on the latter whenever FireSat is compared against rivalry software. The underlying principles of FireSat2' have been implemented illustrating that it would detect the exact same TRs as FireSat3. Although FireSat has default values, the user has several parameters that can be used to fine-tune her search. The objective being to allow the user to do an exhaustive search within the statistical constraints of her problem domain. During the endeavour to develop an algorithm, using finite automata for minisatellite and satellite detection in DNA, new types of automata were discovered (coined counting automata) that have the following properties: • They can be used for tandem repeat detection to the same degree of accuracy as conventional finite automata. • The languages they define can be classified in the Chomsky hierarchy. • They can be implemented more efficiently than other finite automata, in terms of both space and time. Furthermore Counting Prototype Finite Automata (CPFAs) are defined. CPFAs are cascaded to determine a Levenshtein based distance between two genetic strings with less states than the traditional Levenshtein Distance Automaton. Within CPFAs deterministic state reduction and simplification enable the separation of mutation types. Respective CPFAs cater for small substrings of lengths between 1 and 4. Memory usage is decreased in such a manner that a field-programmable gate array implementation becomes viable. bs2026 Computer Science PhD(Computer Science) Unrestricted SDG-03: Good health and well-being SDG-09: Industry, innovation and infrastructure 2019-12-09T13:41:33Z 2019-12-09T13:41:33Z 2020 2019 Thesis * A2020 http://hdl.handle.net/2263/72550 en © 2019 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. application/pdf University of Pretoria |
| spellingShingle | UCTD Tandem Repeats (TRs) FireSat algorithms Minisatellites Engineering, built environment and information technology theses SDG-03 Engineering, built environment and information technology theses SDG-09 Automata-based algorithms for detecting minisatellites and satellites |
| title | Automata-based algorithms for detecting minisatellites and satellites |
| title_full | Automata-based algorithms for detecting minisatellites and satellites |
| title_fullStr | Automata-based algorithms for detecting minisatellites and satellites |
| title_full_unstemmed | Automata-based algorithms for detecting minisatellites and satellites |
| title_short | Automata-based algorithms for detecting minisatellites and satellites |
| title_sort | automata based algorithms for detecting minisatellites and satellites |
| topic | UCTD Tandem Repeats (TRs) FireSat algorithms Minisatellites Engineering, built environment and information technology theses SDG-03 Engineering, built environment and information technology theses SDG-09 |
| url | http://hdl.handle.net/2263/72550 |