title: A multilevel ant colony optimization algorithm for classical and isothermic DNA sequencing by hybridization with multiplicity information available.
abstract: The classical sequencing by hybridization takes into account a binary information about sequence composition. A given element from an oligonucleotide library is or is not a part of the target sequence. However, the DNA chip technology has been developed and it enables to receive a partial information about multiplicity of each oligonucleotide the analyzed sequence consist of. Currently, it is not possible to assess the exact data of such type but even partial information should be very useful. Two realistic multiplicity information models are taken into consideration in this paper. The first one, called "one and many" assumes that it is possible to obtain information if a given oligonucleotide occurs in a reconstructed sequence once or more than once. According to the second model, called "one, two and many", one is able to receive from biochemical experiment information if a given oligonucleotide is present in an analyzed sequence once, twice or at least three times. An ant colony optimization algorithm has been implemented to verify the above models and to compare with existing algorithms for sequencing by hybridization which utilize the additional information. The proposed algorithm solves the problem with any kind of hybridization errors. Computational experiment results confirm that using even the partial information about multiplicity leads to increased quality of reconstructed sequences. Moreover, they also show that the more precise model enables to obtain better solutions and the ant colony optimization algorithm outperforms the existing ones. Test data sets and the proposed ant colony optimization algorithm are available on: http://bioserver.cs.put.poznan.pl/download/ACO4mSBH.zip.
authors.affiliation: Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland. Electronic address: Kamil.Kwarciak@cs.put.poznan.pl.
authors.forename: Kamil
authors.initials: K
authors.lastname: Kwarciak
authors.affiliation: Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland. Electronic address: Marcin.Radom@cs.put.poznan.pl.
authors.forename: Marcin
authors.initials: M
authors.lastname: Radom
authors.affiliation: Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland; Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznan, Poland. Electronic address: Piotr.Formanowicz@cs.put.poznan.pl.
authors.forename: Piotr
authors.initials: P
authors.lastname: Formanowicz
mesh_terms: D000465:Algorithms; D000818:Animals; D001000:Ants / Q000502:physiology*; D004247:DNA / Q000235:genetics*; D009693:Nucleic Acid Hybridization
chemical_list: D004247:DNA
keywords: Ant colony optimization; Isothermic oligonucleotide libraries; Multiplicity information; Sequencing by hybridization; Substring repetitions