Wyniki wyszukiwania - BazTech

1

Computational Aspects of DNA Sequencing by Hybridization : a Survey

Kwarciak K., Radom M., Formanowicz P.

Computational Methods in Science and Technology

|

2018

|

Vol. 24, No. 4

259--271

EN

Sequencing by hybridization (SBH) is a method of reading DNA sequence from its smaller fragments. Such a method has been proposed in late 1980s and until the emergence of the new generation sequencing it has been widely used and improved. Since the initial, classical approach to SBH, many modifications and enhancements was proposed, aimed at improving the preciseness and the length of sequences which can be unambiguously read. Even now, for some DNA sequences sequencing by hybridization can still be used effectively and at a low cost. In this paper many different approaches to the SBH will be described, mainly from the points of view of algorithms and computational complexity.

2

A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions

Kwarciak K., Formanowicz P.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2011

|

Vol. 59, nr 1

111-115

EN

In this paper a greedy algorithm for some variants of the sequencing by hybridization method is presented. In the standard version of the method information about repetitions is not available. In the paper it is assumed that a partial information of this type is a part of the problem instance. Here two simple but realistic models of this information are taken into consideration. The first one assumes it is known if a given element of a spectrum appears in the target sequence once or more than once. The second model uses the knowledge is a given element of a spectrum occurs in the analyzed sequence once, twice or at least three times. The proposed greedy algorithm solves the variant of the problem with positive and negative errors. Results of a computational experiment are reported which, among others, confirm that the additional information leads to the improvement of the obtained solutions. They also show that the more precise model of information increases the quality of reconstructed sequences.

3

Sekwencjonowanie DNA z błędami negatywnymi oraz informacją o powtórzeniach

Kwarciak K., Radom M., Formanowicz P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 151

215-222

PL

W pracy przedstawiony jest algorytm typu podziału i ograniczeń dla problemu sekwencjonowania przez hybrydyzację z błędami negatywnymi oraz częściową informacją o powtórzeniach. Uwzględnienie tego rodzaju informacji możliwe jest ze względu na rozwój technologii stosowanej w eksperymencie hybrydyzacyjnym. Prowadzi ono do rozszerzenia standardowej wersji metody sekwencjonowania przez hybrydyzację oraz do polepszenia jakości uzyskiwanych rozwiązań.

EN

In this paper a branch and bound algorithm for sequencing by hybridization problem with negative errors and partial information about repetitions is presented. Taking into account information of this type is possible because of the development of the technology used in the hybridization experiment. It leads to an extension of the standard sequencing by hybridization method and to an improvement of the quality of the obtained results.