Characterizing the reconstruction and enumerating the patterns of DNA sequences with repeats |
| |
Authors: | Hsun-Wen Chang Pei-Fang Tsai |
| |
Institution: | (1) Department of Applied Mathematics, Tatung University, Taipei, 104, Taiwan |
| |
Abstract: | A repeat in a DNA sequence is a substring that appears more than once. In DNA sequencing, the occurrence of repeats may hinder
the unique reconstruction. In addition, the number of possible reconstructions depends on the pattern of repeats in a DNA
sequence. Arratia et al. studied the patterns of DNA sequences with twofold repeats that result in k-way reconstructions. In this paper, multiple-fold repeats, including twofold repeats, are considered. For each pattern of
DNA repeats, the possible reconstructions of the DNA sequence are enumerated by its reduced digraph. Then the reconstructions
of DNA sequences with repeats are characterized using the pattern graphs. Finally, for DNA sequences with n repeats, the patterns of DNA repeats resulting in k-way reconstruction are enumerated.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. |
| |
Keywords: | DNA sequencing Repeat DNA digraph Reduced digraph Pattern graph Combinatorial enumeration Catalan number |
本文献已被 SpringerLink 等数据库收录! |
|