Reconstructing a Phylogenetic Level-1 Network from Quartets
Tóm tắt
We describe a method that will reconstruct an unrooted binary phylogenetic level-1 network on
$$n$$
taxa from the set of all quartets containing a certain fixed taxon, in
$$O(n^3)$$
time. We also present a more general method which can handle more diverse quartet data, but which takes
$$O(n^6)$$
time. Both methods proceed by solving a certain system of linear equations over the two-element field
$$\mathrm{GF}(2)$$
. For a general dense quartet set, i.e. a set containing at least one quartet on every four taxa, our
$$O(n^6)$$
algorithm constructs a phylogenetic level-1 network consistent with the quartet set if such a network exists and returns an
$$O(n^2)$$
-sized certificate of inconsistency otherwise. This answers a question raised by Gambette, Berry and Paul regarding the complexity of reconstructing a level-1 network from a dense quartet set, and more particularly regarding the complexity of constructing a cyclic ordering of taxa consistent with a dense quartet set.
Tài liệu tham khảo
Artin M (1991) Algebra. Prentice Hall Inc, Englewood Cliffs ISBN 0-13-004763-5
Bandelt H-J, Dress A (1986) Reconstructing the shape of a tree from observed dissimilarity data. Adv Appl Math 7(3):309–343 ISSN 0196-8858
Bandelt H-J, Dress A (1993) A relational approach to split decomposition. In: Studies in classification, data analysis and knowledge organization, pp 123–131
Bard GV (2009) Algebraic cryptanalysis. Springer, Dordrecht
Berry V, Gascuel O (2000) Inferring evolutionary trees with strong combinatorial evidence. Theor Comput Sci 240(2):271–298 ISSN 0304-3975. Computing and combinatorics (Shanghai, 1997)
Coppersmith D (1994) Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math Comput 62(205):333–350 ISSN 0025-5718
Erdös PL, Steel MA, Székely LA, Warnow TJ (1999) A few logs suffice to build (almost) all trees. I. Random Struct Algorithms 14(2):153–184 ISSN 1042-9832
Gambette P, Berry V, Paul C (2012) Quartets and unrooted phylogenetic networks. JBCB 10(4):1250004.1–1250004.23.doi:10.1142/S0219720012500047
Grünewald S, Huber KT, Wu Q (2008) Two novel closure rules for constructing phylogenetic super-networks. Bull Math Biol 70(7):1906–1924
Grünewald S, Moulton V, Spillner A (2009) Consistency of the QNet algorithm for generating planar split networks from weighted quartets. Discrete Appl Math 157(10):2325–2334 ISSN 0166-218X
Heyting A (1980) Axiomatic projective geometry. Bibliotheca Mathematica [Mathematics Library], 2nd edn. V. Wolters-Noordhoff Scientific Publications Ltd., Groningen ISBN 0-444-85431-2
Huntington EV (1924) A new set of postulates for betweenness, with proof of complete independence. Trans Am Math Soc 26(2):257–282 ISSN 0002-9947
Huson DH, Rupp R, Scornavacca C (2010) Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press, Cambridge
Jansson J, Sung W-K (2006) Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theor Comput Sci 363(1):60–68 ISSN 0304-3975
Jansson J, Nguyen NB, Sung W-K (2006) Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM J Comput 35(5):1098–1121 ISSN 0097-5397
Semple C, Steel M (2003) Phylogenetics, volume 24 of Oxford lecture series in mathematics and its applications. Oxford University Press, Oxford ISBN 0-19-850942-1
Semple C, Steel M (2004) Cyclic permutations and evolutionary trees. Adv Appl Math 32(4):669–680 ISSN 0196-8858
Sonke W (2013) Fylogenetica. 2013a. url:http://filedir.com/company/willem-sonke/
Sonke W (2013) Reconstructing a level-1-network from quartets. 2013b. url:http://alexandria.tue.nl/extra1/afstversl/wsk-i/sonke2013.pdf
Steel M (1992) The complexity of reconstructing trees from qualitative characters and subtrees. J Classif 9(1):91–116 ISSN 0176-4268
Stein W et al. (2014) Sage Mathematics Software, (Version 6.2). The Sage Development Team, 2014. url:http://www.sagemath.org
To T-H, Habib M (2009) Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time. In Proceedings of the 20th annual symposium on combinatorial pattern matching, CPM ’09. Berlin, Heidelberg, 2009. Springer, pp 275–288. ISBN 978-3-642-02440-5
Van Iersel L, Kelk S (2011) Constructing the simplest possible phylogenetic network from triplets. Algorithmica 60(2):207–235 ISSN 0178-4617
Van Iersel L, Keijsper J, Kelk S, Stougie L, Hagen F, Boekhout T (2009) Constructing level-2 phylogenetic networks from triplets. IEE/ACM Trans Comp Biol Bioinform 6(4):667–681
Wiedemann DH (1986) Solving sparse linear equations over finite fields. IEEE Trans Inform Theory 32(1):54–62 ISSN 0018-9448