Use of traveling salesman problem solvers in the construction of genetic linkage maps
| dc.contributor.author | Allen, Zachariah A., author | |
| dc.contributor.author | Whitley, Darrell, advisor | |
| dc.contributor.author | McConnell, Ross M., committee member | |
| dc.contributor.author | McKay, John, committee member | |
| dc.date.accessioned | 2016-01-11T15:14:00Z | |
| dc.date.available | 2016-01-11T15:14:00Z | |
| dc.date.issued | 2015 | |
| dc.description.abstract | Construction of genetic linkage maps is an important tool for Biology. Researchers use a variety of laboratory techniques to extract genetic marker data from an experimental cross of a species of interest and then use these data to group the markers into chromosomes, and then construct maps of the locations of the markers within the chromosomes. This in turn allows them to determine which sections of the chromosomes are responsible for variation in agricultural, medical or other traits of interest. The current methods of constructing genetic linkage maps are tedious and time-consuming. This thesis presents a method of utilizing the Hamiltonian path problem (HPP) to solve the problem of genetic linkage mapping. Since solvers already exist for the traveling salesman problem (LKH and Concorde), by casting the linkage mapping problem as a HPP we can use these solvers to efficiently find the solution. To do this, the recombination frequencies between genetic markers are treated as internode weights and the TSP solution gives the lowest-cost path through the markers. By adding a dummy marker with zero weight to all other markers, the TSP solution is made equivalent to a HPP. The primary difficulty in constructing a linkage map is the fact that all data sets are noisy: errors in laboratory techniques create uncertainty in the relationships between genetic markers, so a straightforward HPP solution is not sufficient. This thesis describes a method of using the HPP to separate the raw data into clusters so that the researcher can be sure that the chromosomes are well-separated, the clusters can then be assembled into complete chromosomes using existing TSP solvers. The results show that this method produces results which are equally as good as the prevalent software in the field, while drastically decreasing the time required to run an analysis. | |
| dc.format.medium | born digital | |
| dc.format.medium | masters theses | |
| dc.identifier | Allen_colostate_0053N_13374.pdf | |
| dc.identifier.uri | http://hdl.handle.net/10217/170397 | |
| dc.language | English | |
| dc.language.iso | eng | |
| dc.publisher | Colorado State University. Libraries | |
| dc.relation.ispartof | 2000-2019 | |
| dc.rights | Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright. | |
| dc.subject | genetic linkage | |
| dc.subject | linkage map | |
| dc.subject | travelling salesman problem | |
| dc.subject | TSP | |
| dc.title | Use of traveling salesman problem solvers in the construction of genetic linkage maps | |
| dc.type | Text | |
| dcterms.rights.dpla | This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Colorado State University | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science (M.S.) |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Allen_colostate_0053N_13374.pdf
- Size:
- 2.52 MB
- Format:
- Adobe Portable Document Format