Name
Title | ||
|---|---|---|
Usefulness of Solution Algorithms of the Traveling Salesman Problem in the Typing of Biological Sequences in a Clinical Laboratory Setting |
Abstract | ||
|---|---|---|
Our concern is to solve the problem of the typing ofdeoxyribonucleic acid (DNA) sequences in alaboratory setting. Here we try to find solutionalgorithms for the classification of restriction patternswhich forms part of the above-mentioned problem, inorder to evaluate the amount of information generatedby a given restriction enzyme. A distance matrix isgenerated by comparison of each restriction patternand used to classify the patterns according to theirsimilarity. This problem can be mapped to theTraveling Salesman Problem (TSP). Several knownand new solution algorithms have been tested.Interestingly, a very simple and modified nearestneighbor analysis performed best for this kind ofproblem. However, when the distance matrix isreplaced by a "distinction matrix" (expresses directlywith the help of a threshold function the similarity (0)or dissimilarity (1) between restriction patterns) theresults of at least one local search algorithm aredramatically improved. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/ICECC.2004.1269584 | CONIELECOMP |
Keywords | Field | DocType |
solution algorithms,information generatedby,distinction matrix,restriction patternswhich forms part,salesman problem,restriction pattern,biological sequences,restriction enzyme,above-mentioned problem,clinical laboratory setting,distance matrix,restriction patternand,alaboratory setting,kind ofproblem,sequences,nearest neighbor,dna sequence,enzymes,dna,local search algorithm,traveling salesman problem,deoxyribonucleic acid | Bottleneck traveling salesman problem,Matrix (mathematics),Computer science,Algorithm,Typing,Travelling salesman problem,Distance matrix,Local search (optimization),Restriction enzyme,Nearest neighbor search | Conference |
ISSN | ISBN | Citations |
2474-9036 | 0-7695-2074-X | 0 |
PageRank | References | Authors |
0.34 | 2 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Javier Garcés Eisele | 1 | 0 | 0.34 |
| Carolina Yolanda Castañeda Roldán | 2 | 0 | 0.34 |
| Mauricio Osorio | 3 | 436 | 52.82 |
| Ma. del Pilar Gómez Gil | 4 | 0 | 0.34 |