Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries.
Comput Biol Chem
; 28(1): 11-9, 2004 Feb.
Article
em En
| MEDLINE
| ID: mdl-14871640
ABSTRACT
In this paper, a problem of isothermic DNA sequencing by hybridization (SBH) is considered. In isothermic SBH a new type of oligonucleotide libraries is used. The library consists of oligonucleotides of different lengths depending on an oligonucleotide content. It is assumed that every oligonucleotide in such a library has an equal melting temperature. Each nucleotide adds its increment to the oligonucleotide temperature and it is assumed that A and T add 2 degrees C and C and G add 4 degrees C. The hybridization experiment using isothermic libraries should provide data with a lower number of errors due to an expected similarity of melting temperatures. From the computational point of view the problem of isothermic DNA sequencing with errors is hard, similarly like its classical counterpart. Hence, there is a need for developing heuristic algorithms that construct good suboptimal solutions. The aim of the paper is to propose a heuristic algorithm based on tabu search approach. The algorithm solves the problem with both positive and negative errors. Results of an extensive computational experiment are presented, which prove the high quality of the proposed method.
Buscar no Google
Bases de dados:
MEDLINE
Assunto principal:
Algoritmos
/
Sequência de Bases
/
Biblioteca Gênica
Tipo de estudo:
Prognostic_studies
Idioma:
En
Revista:
Comput Biol Chem
Assunto da revista:
BIOLOGIA
/
INFORMATICA MEDICA
/
QUIMICA
Ano de publicação:
2004
Tipo de documento:
Article
País de afiliação:
Polônia