Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/6/817 |
| _version_ | 1797240151322132480 |
|---|---|
| author | Konstantin Gorbunov Vassily Lyubetsky |
| author_facet | Konstantin Gorbunov Vassily Lyubetsky |
| author_sort | Konstantin Gorbunov |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-24T18:02:52Z |
| format | Article |
| id | doaj.art-a43e697892b342f38d19072d3ea0fb26 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-04-24T18:02:52Z |
| publishDate | 2024-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-a43e697892b342f38d19072d3ea0fb262024-03-27T13:53:00ZengMDPI AGMathematics2227-73902024-03-0112681710.3390/math12060817Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High ExactnessKonstantin Gorbunov0Vassily Lyubetsky1Institute for Information Transmission Problems of the Russian Academy of Sciences, 127051 Moscow, RussiaInstitute for Information Transmission Problems of the Russian Academy of Sciences, 127051 Moscow, RussiaThe 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.https://www.mdpi.com/2227-7390/12/6/817combinatorial optimizationexact graph algorithmgenome as a structuregenome reconstructionpath-cycle graph reconstructionphylogenetic network |
| spellingShingle | Konstantin Gorbunov Vassily Lyubetsky Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness Mathematics combinatorial optimization exact graph algorithm genome as a structure genome reconstruction path-cycle graph reconstruction phylogenetic network |
| title | Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness |
| title_full | Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness |
| title_fullStr | Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness |
| title_full_unstemmed | Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness |
| title_short | Algorithms for the Reconstruction of Genomic Structures with Proofs of Their Low Polynomial Complexity and High Exactness |
| title_sort | algorithms for the reconstruction of genomic structures with proofs of their low polynomial complexity and high exactness |
| topic | combinatorial optimization exact graph algorithm genome as a structure genome reconstruction path-cycle graph reconstruction phylogenetic network |
| url | https://www.mdpi.com/2227-7390/12/6/817 |
| work_keys_str_mv | AT konstantingorbunov algorithmsforthereconstructionofgenomicstructureswithproofsoftheirlowpolynomialcomplexityandhighexactness AT vassilylyubetsky algorithmsforthereconstructionofgenomicstructureswithproofsoftheirlowpolynomialcomplexityandhighexactness |