Constructing an Evolutionary Tree and Path–Cycle Graph Evolution along It

Konstantin Gorbunov () and Vassily Lyubetsky
Additional contact information
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

Mathematics, 2023, vol. 11, issue 9, 1-39

Abstract: The paper solves the problem of constructing an evolutionary tree and the evolution of structures along it. This problem has long been posed and extensively researched; it is formulated and discussed below. As a result, we construct an exact cubic-time algorithm which outputs a tree with the minimum cost of embedding into it and of embedding it into a given network (Theorem 1). We construct an algorithm that outputs a minimum embedding of a tree into a network, taking into account incomplete linear sorting; the algorithm depends linearly on the number of nodes in the network and is exact if the sorting cost is not less than the sum of the duplication cost and the loss cost (Theorem 3). We construct an exact approximately quadratic-time algorithm which, for arbitrary costs of SCJ operations, solves the problem of reconstruction of given structures on any two-star tree (Theorem 4). We construct an exact algorithm which reduced the problem of DCJ reconstruction of given structures on any star to a logarithmic-length sequence of SAT problems, each of them being of approximately quadratic size (Theorem 5). The theorems have rigorous and complete proofs of correctness and complexity of the algorithms, and are accompanied by numerical examples and numerous explanatory illustrations, including flowcharts.

Keywords: exact algorithm; low computation complexity algorithm; discrete optimization; discrete evolution; tree reconciliation; path-cycle graph reconstruction; minimum embedding of a tree into a network (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/9/2024/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/9/2024/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:9:p:2024-:d:1131678

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().