Blog
About

56
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Approximating the Minimum Breakpoint Linearization Problem for Genetic Maps without Gene Strandedness

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          The study of genetic map linearization leads to a combinatorial hard problem, called the {\em minimum breakpoint linearization} (MBL) problem. It is aimed at finding a linearization of a partial order which attains the minimum breakpoint distance to a reference total order. The approximation algorithms previously developed for the MBL problem are only applicable to genetic maps in which genes or markers are represented as signed integers. However, current genetic mapping techniques generally do not specify gene strandedness so that genes can only be represented as unsigned integers. In this paper, we study the MBL problem in the latter more realistic case. An approximation algorithm is thus developed, which achieves a ratio of \((m^2+2m-1)\) and runs in \(O(n^7)\) time, where \(m\) is the number of genetic maps used to construct the input partial order and \(n\) the total number of distinct genes in these maps.

          Related collections

          Most cited references 2

          • Record: found
          • Abstract: not found
          • Article: not found

          Gene Maps Linearization Using Genomic Rearrangement Distances

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Revisiting the Minimum Breakpoint Linearization Problem

              Bookmark

              Author and article information

              Journal
              1502.07083

              Genetics

              Comments

              Comment on this article