Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
Honors_Paper_submission.pdf (3.89 MB)
ETD Abstract Container
Abstract Header
Drawing DNA Sequence Networks
Author Info
Olivieri, Julia
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1466511242
Abstract Details
Year and Degree
2016, BA, Oberlin College, Mathematics.
Abstract
We explore methods for drawing a graph of DNA sequences on a digital canvas such that the Euclidean distances between sequences on the canvas suggest the distances between the sequences as calculated from pairwise sequence alignment. We use data from three plant taxa, the genus
Castilleja
as well as the families Caryophyllaceae and Cactaceae, to test our methods. We discuss different possible measures of the cost of a drawing, and analyze heuristic approaches to the problem including random assignment, greedy assignment, the iterated hill-climber, and simulated annealing. We find that our hill-climbing method tends to return superior drawings. Our simulated annealing method also returns drawings with low costs, but in much less time than the hill-climbing method for large datasets.
Committee
Robert Bosch (Advisor)
Pages
21 p.
Subject Headings
Applied Mathematics
;
Biology
;
Mathematics
Keywords
Quadratic Assignment Problem
;
QAP
;
discrete optimization
;
simulated annealing
;
hill climbing
;
DNA sequence representation
Recommended Citations
Refworks
EndNote
RIS
Mendeley
Citations
Olivieri, J. (2016).
Drawing DNA Sequence Networks
[Undergraduate thesis, Oberlin College]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1466511242
APA Style (7th edition)
Olivieri, Julia.
Drawing DNA Sequence Networks.
2016. Oberlin College, Undergraduate thesis.
OhioLINK Electronic Theses and Dissertations Center
, http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1466511242.
MLA Style (8th edition)
Olivieri, Julia. "Drawing DNA Sequence Networks." Undergraduate thesis, Oberlin College, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1466511242
Chicago Manual of Style (17th edition)
Abstract Footer
Document number:
oberlin1466511242
Download Count:
538
Copyright Info
© 2016, some rights reserved.
Drawing DNA Sequence Networks by Julia Olivieri is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. Based on a work at etd.ohiolink.edu.
This open access ETD is published by Oberlin College Honors Theses and OhioLINK.