Title :
Algorithms for the Typing of Related DNA Sequences
Author :
Rodríguez, Rocío Santillán ; Roldán, Carolina Yolanda Castaneda ; Eisele, Javier Garcés ; Gil, Pilar Gómez ; Galindo, Mauricio Javier Osorio
Author_Institution :
Dept. of Comput. Sci., Univ. de las Americas, Puebla, Mexico
Abstract :
This article presents an approach to solve the typing problem using algorithms for set covering. Two algorithms to solve this problem were designed and compared. The typing problem consists of distinguishing all sequences using the least possible reagents. For each reagent, their capacity to distinguish between pairs of sequences is represented in a matrix and then mapped to the set-covering problem. In [1], a proof of the equivalence of this problem with the set covering problem is presented; here, the results of an exact algorithm to solve the set-covering problem are presented. This algorithm uses a branch and bound method based on some intuitive properties of the solution, applying recursion as the final resource. Two approximation algorithms were also implemented and tested. One is an improved greedy algorithm and the other is based on dynamic programming. Real as well as randomly created instances were used to test the algorithms.
Keywords :
DNA; biology computing; dynamic programming; greedy algorithms; recursive functions; sequences; set theory; tree searching; NP-complete problems; approximation algorithms; branch and bound method; dynamic programming; greedy algorithm; matrix; recursion; related DNA sequence typing; sequence pair distinguishing reagents; set covering algorithms; Biochemistry; Biology; Chemistry; Computer science; DNA; Gas insulated transmission lines; Logic programming; Probes; Sequences; Testing;
Conference_Titel :
Electronics, Communications and Computers, 2005. CONIELECOMP 2005. Proceedings. 15th International Conference on
Print_ISBN :
0-7695-2283-1
DOI :
10.1109/CONIEL.2005.17