IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i6p817-d1354836.html
   My bibliography  Save this article

Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness

Author

Listed:
  • Konstantin Gorbunov

    (Institute for Information Transmission Problems of the Russian Academy of Sciences, 127051 Moscow, Russia)

  • Vassily Lyubetsky

    (Institute for Information Transmission Problems of the Russian Academy of Sciences, 127051 Moscow, Russia)

Abstract

The mathematical side of applied problems in multiple subject areas (biology, pattern recognition, etc.) is reduced to the problem of discrete optimization in the following mathematical method. We were provided a network and graphs in its leaves, for which we needed to find a rearrangement of graphs by non-leaf nodes, in which the given functional reached its minimum. Such a problem, even in the simplest case, is NP-hard, which means unavoidable restrictions on the network, on graphs, or on the functional. In this publication, this problem is addressed in the case of all graphs being so-called “structures”, meaning directed-loaded graphs consisting of paths and cycles, and the functional as the sum (over all edges in the network) of distances between structures at the endpoints of every edge. The distance itself is equal to the minimal length of sequence from the fixed list of operations, the composition of which transforms the structure at one endpoint of the edge into the structure at its other endpoint. The list of operations (and their costs) on such a graph is fixed. Under these conditions, the given discrete optimization problem is called the reconstruction problem. This paper presents novel algorithms for solving the reconstruction problem, along with full proofs of their low error and low polynomial complexity. For example, for the network, the problem is solved with a zero error algorithm that has a linear polynomial computational complexity; and for the tree the problem is solved using an algorithm with a multiplicative error of at most two, which has a second order polynomial computational complexity.

Suggested Citation

  • Konstantin Gorbunov & Vassily Lyubetsky, 2024. "Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness," Mathematics, MDPI, vol. 12(6), pages 1-26, March.
  • Handle: RePEc:gam:jmathe:v:12:y:2024:i:6:p:817-:d:1354836
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/6/817/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/12/6/817/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. J. N. Hooker, 1986. "Karmarkar’s Linear Programming Algorithm," Interfaces, INFORMS, vol. 16(4), pages 75-90, August.
    2. Konstantin Gorbunov & Vassily Lyubetsky, 2020. "Linear Time Additively Exact Algorithm for Transformation of Chain-Cycle Graphs for Arbitrary Costs of Deletions and Insertions," Mathematics, MDPI, vol. 8(11), pages 1-30, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Konstantin Gorbunov & Vassily Lyubetsky, 2023. "Constructing an Evolutionary Tree and Path–Cycle Graph Evolution along It," Mathematics, MDPI, vol. 11(9), pages 1-39, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:12:y:2024:i:6:p:817-:d:1354836. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.