POLISH ACADEMY of SCIENCES
TECHNICAL SCIENCES
| BULLETIN
of the
POLISH ACADEMY of SCIENCES TECHNICAL SCIENCES |
|
|||
|---|---|---|---|---|
| Volume
59, Issue 1, March 2011
|
||||
| Issue Index | Authors Index | Scope Index | Web Info | |
|
|
||||
| Aims&Scope, Subscription | Editors | Authors' guide | to read PDF files | mirror: http://fluid.ippt.gov.pl/~bulletin/ |
| pp 111 - 115 |
|---|
|
A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions |
|---|
| K. KWARCIAK and P. FORMANOWICZ |
| 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 if 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. |
| Key words: |
|
DNA sequencing, l-mer multiplicity, greedy algorithm, combinatorial problems |
|
|
| Issue Index | Authors Index | Scope Index | Web Info |
|---|---|---|---|
|
|
|||
| Aims&Scope, Subscription | Editors | Authors' guide | to read PDF files |
| Copyright ® Bulletin of the Polish Academy of Sciences: Technical Sciences |
|---|