|
Published Articles >> Table of Contents >> Abstract
14th International Conference on Electronics, Communications and Computers
p. 264
Usefulness of Solution Algorithms of the Traveling Salesman Problem in the Typing of Biological Sequences in a Clinical Laboratory Setting
Eisele Eisele, Universidad de las Américas, Puebla
Carolina Yolanda Castaneda Roldan, Universidad de las Américas, Puebla
Mauricio Osorio Galindo, Universidad de las Américas, Puebla
Gil Gil, Universidad de las Américas, Puebla
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICECC.2004.1269584
Send link to a friend
| Abstract |
|
Our concern is to solve the problem of the typing of deoxyribonucleic acid (DNA) sequences in a laboratory setting. Here we try to find solution algorithms for the classification of restriction patterns which forms part of the above-mentioned problem, in order to evaluate the amount of information generated by a given restriction enzyme. A distance matrix is generated by comparison of each restriction pattern and used to classify the patterns according to their similarity. This problem can be mapped to the Traveling Salesman Problem (TSP). Several known and new solution algorithms have been tested. Interestingly, a very simple and modified nearest neighbor analysis performed best for this kind of problem. However, when the distance matrix is replaced by a "distinction matrix" (expresses directly with the help of a threshold function the similarity (0) or dissimilarity (1) between restriction patterns) the results of at least one local search algorithm are dramatically improved.
|
 Additional Information
|
Citation:
Eisele Eisele, Carolina Yolanda Castaneda Roldan, Mauricio Osorio Galindo, Gil Gil,
"Usefulness of Solution Algorithms of the Traveling Salesman Problem in the Typing of Biological Sequences in a Clinical Laboratory Setting,"
conielecomp,
p. 264,
14th International Conference on Electronics, Communications and Computers,
2004
|
|
