POLISH ACADEMY of SCIENCES
TECHNICAL SCIENCES
Electronics
| BULLETIN
of the
POLISH ACADEMY of SCIENCES TECHNICAL SCIENCES |
|
|||
|---|---|---|---|---|
| Volume
56, Issue 1, March 2008
Electronics |
||||
| 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 65 - 70 |
|---|
|
Graph reduction and its application to DNA sequence assembly |
|---|
| J. BŁAZEWICZ and M. KASPRZAK |
| The results presented here are twofold. First, a heuristic algorithm is proposed which, through removing some unnecessary arcs from a digraph, tends to reduce it into an adjoint and thus simplifies the search for a Hamiltonian cycle. Second, a heuristic algorithm for DNA sequence assembly is proposed, which uses a graph model of the problem instance, and incorporates two independent procedures of reducing the set of arcs - one of them being the former algorithm. Finally, results of tests of the assembly algorithm on parts of chromosome arm 2R of Drosophila melanogaster are presented. |
| Key words: |
|
directed graphs, adjoints, Hamiltonian cycle, reduction of arcs, DNA sequence assembly, heuristics |
|
|
| 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
30 March 2007, site prepared by KZ |
|---|