Identifying duplications and lateral gene transfers simultaneously and rapidly

Zhi-Zhong Chen; Fei Deng; Lusheng Wang

doi:10.1109/CIBCB.2013.6595398

Identifying duplications and lateral gene transfers simultaneously and rapidly

Zhi-Zhong Chen, Fei Deng, Lusheng Wang

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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 S and a given gene tree G. Previously, Tofigh et al. [20] gave a fixed-parameter algorithm for this problem that runs in O(m + 3^k n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between Sand G. 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 O(mn² + 3^k) time. © 2013 IEEE.

Original language	English
Title of host publication	Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
Pages	128-135
DOIs	https://doi.org/10.1109/CIBCB.2013.6595398
Publication status	Published - 2013
Event	10th Annual IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 - Singapore, Singapore Duration: 16 Apr 2013 → 19 Apr 2013

Conference

Conference	10th Annual IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
Country/Territory	Singapore
City	Singapore
Period	16/04/13 → 19/04/13

Access Output

10.1109/CIBCB.2013.6595398

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Z.-Z., Deng, F., & Wang, L. (2013). Identifying duplications and lateral gene transfers simultaneously and rapidly. In Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 (pp. 128-135). Article 6595398 https://doi.org/10.1109/CIBCB.2013.6595398

@inproceedings{84683aa021eb4e35971bce61ffdf66dd,

title = "Identifying duplications and lateral gene transfers simultaneously and rapidly",

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 S and a given gene tree G. Previously, Tofigh et al. [20] gave a fixed-parameter algorithm for this problem that runs in O(m + 3k n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between Sand G. 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 O(mn2 + 3k) time. {\textcopyright} 2013 IEEE.",

author = "Zhi-Zhong Chen and Fei Deng and Lusheng Wang",

year = "2013",

doi = "10.1109/CIBCB.2013.6595398",

language = "English",

isbn = "9781467358750",

pages = "128--135",

booktitle = "Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013",

note = "10th Annual IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 ; Conference date: 16-04-2013 Through 19-04-2013",

}

Chen, Z-Z, Deng, F & Wang, L 2013, Identifying duplications and lateral gene transfers simultaneously and rapidly. in Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013., 6595398, pp. 128-135, 10th Annual IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013, Singapore, Singapore, 16/04/13. https://doi.org/10.1109/CIBCB.2013.6595398

Identifying duplications and lateral gene transfers simultaneously and rapidly. / Chen, Zhi-Zhong; Deng, Fei; Wang, Lusheng.
Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013. 2013. p. 128-135 6595398.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Identifying duplications and lateral gene transfers simultaneously and rapidly

AU - Chen, Zhi-Zhong

AU - Deng, Fei

AU - Wang, Lusheng

PY - 2013

Y1 - 2013

N2 - 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 S and a given gene tree G. Previously, Tofigh et al. [20] gave a fixed-parameter algorithm for this problem that runs in O(m + 3k n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between Sand G. 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 O(mn2 + 3k) time. © 2013 IEEE.

AB - 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 S and a given gene tree G. Previously, Tofigh et al. [20] gave a fixed-parameter algorithm for this problem that runs in O(m + 3k n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between Sand G. 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 O(mn2 + 3k) time. © 2013 IEEE.

U2 - 10.1109/CIBCB.2013.6595398

DO - 10.1109/CIBCB.2013.6595398

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781467358750

SP - 128

EP - 135

BT - Proceedings of the IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013

T2 - 10th Annual IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013

Y2 - 16 April 2013 through 19 April 2013

ER -

Identifying duplications and lateral gene transfers simultaneously and rapidly

Abstract

Conference

Access Output

Other Access Options

Permanent Link

Fingerprint

Cite this