Identifying duplications and lateral gene transfers simultaneously and rapidly

Zhi-Zhong Chen; Fei Deng; Lusheng Wang

doi:10.1142/S0219720021500335

Identifying duplications and lateral gene transfers simultaneously and rapidly

J Bioinform Comput Biol. 2022 Feb;20(1):2150033. doi: 10.1142/S0219720021500335. Epub 2021 Dec 9.

Authors

Zhi-Zhong Chen¹, Fei Deng², Lusheng Wang²

Affiliations

¹ Division of Information System Design, Tokyo Denki University, Hatoyama Saitama 350-0394, Japan.
² Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong.

PMID: 34895113
DOI: 10.1142/S0219720021500335

Abstract

This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree [Formula: see text] and a given gene tree [Formula: see text]. Previously, [Tofigh A, Hallett M, Lagergren J, Simultaneous identification of duplications and lateral gene transfers, IEEE/ACM Trans Comput Biol Bioinf 517-535, 2011.] gave a fixed-parameter algorithm for this problem that runs in [Formula: see text] time, where [Formula: see text] is the number of vertices in [Formula: see text], [Formula: see text] is the number of vertices in [Formula: see text], and [Formula: see text] is the minimum cost of an LCA-reconciliation between [Formula: see text] and [Formula: see text]. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within [Formula: see text] time. In the most interesting case where [Formula: see text], our algorithm is [Formula: see text] times faster.

Keywords: Phylogenetic trees; enumerate algorithms; fixed-parameter algorithms; reconciliations.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms
Evolution, Molecular*
Gene Duplication
Gene Transfer, Horizontal*
Phylogeny