Kwarciak Kamil, Radom Marcin, Formanowicz Piotr
Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland.
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.
Comput Biol Chem. 2016 Apr;61:109-20. doi: 10.1016/j.compbiolchem.2016.01.010. Epub 2016 Jan 28.
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.
经典的杂交测序考虑了序列组成的二元信息。寡核苷酸文库中的给定元素是或不是目标序列的一部分。然而，DNA芯片技术已经得到发展，它能够获取关于被分析序列所包含的每个寡核苷酸多重性的部分信息。目前，不可能评估此类的确切数据，但即使是部分信息也应该非常有用。本文考虑了两种现实的多重性信息模型。第一种称为“一与多”，假设能够获取给定寡核苷酸在重构序列中出现一次或多次的信息。根据第二种模型，称为“一、二与多”，能够从生化实验中获取给定寡核苷酸在被分析序列中出现一次、两次或至少三次的信息。已经实现了一种蚁群优化算法来验证上述模型，并与利用额外信息的现有杂交测序算法进行比较。所提出的算法解决了任何类型的杂交错误问题。计算实验结果证实，即使使用关于多重性的部分信息也会提高重构序列的质量。此外，结果还表明，更精确的模型能够获得更好的解决方案，并且蚁群优化算法优于现有算法。测试数据集和所提出的蚁群优化算法可在以下网址获取：http://bioserver.cs.put.poznan.pl/download/ACO'4mSBH.zip。
