DNA sequencing and information sources

摘要

DNA sequencing is a very well known problem of computational biology. It consists in determining a long DNA molecule from a large amount of its shorter fragments obtained by suitable laboratory techniques. The corresponding mathematical problem is known as the Shortest Common Superstring Problem (SCSP), for which the goal is that of finding a shortest possible string containing as substring every string from a given set. Due to the large variety of applications of SCSP, an extensive literature on the construction of the shortest length superstrings has been recently produced. We consider SCSP in the context of recovering as much information as possible from experimental data while sequencing DNA fragments. The basic idea is that of upgrading heuristic algorithms, which are in routine use for this task, by means of additional measurements aimed at the evaluation and the contextual improvement of the substring quality implicated in the reconstruction of the candidate superstring. The experimental results obtained from algorithms supported by such a criterion confirm the adequacy of the idea and encourage further investigations of similar race while assembling actual DNA sequences.