DNA sequencing remains one of the most important problems in molecular and computational biology. One of the methods used for this purpose is sequencing by hybridization. In this approach usually DNA chips composed of a flul library of oligonucleotides of a given length are used, but in principle it is possible to use another types of chips. Isothermic DNA chips, being one of them, when used for sequencing may reduce hybridization error rate. However, it was not clear if a number of errors following from subsequence repetitions is also reduced in this case. In this paper a method for estimating resolving power of isothermic DNA chips is described which allows for a comparison of such chips and the classical ones. The analysis of the resolving power shows that the probability of sequencing errors caused by subsequence repetitions is greater in the case of isothermic chips in comparison to their classical counterparts of a similar cardinality. This result suggests that isothermic chips should be chosen carefully since in some cases they may not give better results than the classical ones.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W pracy przedstawiono formalne definicje różnych wariantów problemu izotermicznego sekwencjonowania przez hybrydyzację z dodatkową informacją o powtórzeniach. W większośći przypadków podano złożoność obliczeniową oraz sformuowano odpowiedniki grafowe rozważanych problemów.
EN
In the paper formal definitions of many variants of the isotherimc sequencing by hybridization problem with additional information about repetitions are presented. For most of the problems their computational complexity is determined and graph theoretical counterparts are also formulated.