Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
The Footprint Sorting Problem
Claudia Fried, Wim Hordijk, Sonja J. Prohaska, Claus R. Stadler, Peter F. Stadler
Download
Status: Published
J.Chem.Inf.Comput.Sci. 44: 332-338 (2004)
Abstract
Phylogenetic footprints are short pieces of non-coding DNA sequence in the vicinity of a gene that are conserved between evolutionary distant species. A seemingly simple problem is to sort footprints in their order along the genomes. It is complicated by the fact that not all footprints are co-linear: they may cross each other. The problem thus becomes the identification of the crossing footprints, the sorting of the remaining co-linear cliques, and finally the insertion of the non-colinear ones at ``reasonable'' positions. We show that solving the footprint sorting problem requires the solution of the ``Minimum Weight Vertex Feedback Set Problem'', which is known to be NP-complete and APX-hard. Nevertheless good approximations can be obtained for datasets of interest. The remaining steps of the sorting process are straight forward: computation of the transitive closure of an acyclic graph, linear extension of the resulting partial order, and finally sorting w.r.t.\ the linear extension. Alternatively, the footprint sorting problem can be rephrased as a combinatorial optimization problem for which approximate solutions can be obtained by means of general purpose heuristics. Footprint sortings obtained with different methods can be compared using a version of multiple sequence alignment that allows the identification of unambiguously ordered sub-lists.
Note
[ <a href=