File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-319-59575-7_4
- Scopus: eid_2-s2.0-85020737619
- WOS: WOS:000434328000004
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Reconstructing One-Articulated Networks with Distance Matrices
Title | Reconstructing One-Articulated Networks with Distance Matrices |
---|---|
Authors | |
Keywords | Gall |
Issue Date | 2017 |
Publisher | Springer. |
Citation | The 13th International Symposium on Bioinformatics Research and Applications (ISBRA), Honolulu, HI, 30 May-2 June 2017. In Cai, Z, Daescu, O and Li, M (Eds.). Bioinformatics Research and Applications, p. 34-45. Cham: Springer, 2017 How to Cite? |
Abstract | Given a distance matrix M that represents evolutionary distances between any two species, an edge-weighted phylogenetic network N is said to satisfy M if between any pair of species, there exists a path in N with length equal to the corresponding entry in M. In this paper, we consider a special class of networks called 1-articulated network which is a proper superset of galled trees. We show that if the distance matrix M is derived from an ultrametric 1-articulated network N (i.e., for any species X and Y, the entry M(X, Y) is equal to the shortest distance between X and Y in N), we can re-construct an network that satisfies M in O(n2)O(n2) time, where n denotes the number of species; furthermore, the reconstructed network is guaranteed to be the simplest, in a sense that the number of hybrid nodes is minimized. In addition, one may easily index a 1-articulated network N with minimum number of hybrid nodes in O(n) space, such that on given any phylogenetic tree T, we can determine if T is contained in N (i.e., if a spanning subtree T′T′ of N is a subdivision of T) in O(n) time. |
Persistent Identifier | http://hdl.handle.net/10722/245450 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
ISI Accession Number ID | |
Series/Report no. | Lecture Notes in Computer Science book series (LNCS, volume 10330) |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chang, KY | - |
dc.contributor.author | Cui, Y | - |
dc.contributor.author | Yiu, SM | - |
dc.contributor.author | Hon, WK | - |
dc.date.accessioned | 2017-09-18T02:10:56Z | - |
dc.date.available | 2017-09-18T02:10:56Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | The 13th International Symposium on Bioinformatics Research and Applications (ISBRA), Honolulu, HI, 30 May-2 June 2017. In Cai, Z, Daescu, O and Li, M (Eds.). Bioinformatics Research and Applications, p. 34-45. Cham: Springer, 2017 | - |
dc.identifier.isbn | 978-3-319-59574-0 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/245450 | - |
dc.description.abstract | Given a distance matrix M that represents evolutionary distances between any two species, an edge-weighted phylogenetic network N is said to satisfy M if between any pair of species, there exists a path in N with length equal to the corresponding entry in M. In this paper, we consider a special class of networks called 1-articulated network which is a proper superset of galled trees. We show that if the distance matrix M is derived from an ultrametric 1-articulated network N (i.e., for any species X and Y, the entry M(X, Y) is equal to the shortest distance between X and Y in N), we can re-construct an network that satisfies M in O(n2)O(n2) time, where n denotes the number of species; furthermore, the reconstructed network is guaranteed to be the simplest, in a sense that the number of hybrid nodes is minimized. In addition, one may easily index a 1-articulated network N with minimum number of hybrid nodes in O(n) space, such that on given any phylogenetic tree T, we can determine if T is contained in N (i.e., if a spanning subtree T′T′ of N is a subdivision of T) in O(n) time. | - |
dc.language | eng | - |
dc.publisher | Springer. | - |
dc.relation.ispartof | Bioinformatics Research and Applications | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science book series (LNCS, volume 10330) | - |
dc.subject | Gall | - |
dc.title | Reconstructing One-Articulated Networks with Distance Matrices | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Cui, Y: yuncui@hku.hk | - |
dc.identifier.email | Yiu, SM: smyiu@cs.hku.hk | - |
dc.identifier.authority | Yiu, SM=rp00207 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/978-3-319-59575-7_4 | - |
dc.identifier.scopus | eid_2-s2.0-85020737619 | - |
dc.identifier.hkuros | 276750 | - |
dc.identifier.hkuros | 275725 | - |
dc.identifier.spage | 34 | - |
dc.identifier.epage | 45 | - |
dc.identifier.eissn | 1611-3349 | - |
dc.identifier.isi | WOS:000434328000004 | - |
dc.publisher.place | Cham | - |
dc.identifier.issnl | 0302-9743 | - |