Using PQ structures for genomic rearrangement phylogeny.

@article{citeulike:2169739, abstract = {Various international efforts are underway to catalog the genomic similarities and variations in the human population. Some key discoveries such as inversions and transpositions within the members of the species have also been made over the years. The task of constructing a phylogeny tree of the members of the same species, given this knowledge and data, is an important problem. In this context, a key observation is that the "distance" between two members, or member and ancestor, within the species is small. In this paper, we pose the tree reconstruction problem exploiting some of these peculiarities. The central idea of the paper is based on the notion of minimal consensus PQ tree T of sequences. We use a modified PQ structure (termed oPQ) and show that both the number and size of each T is O(1). We further show that the tree reconstruction problem is statistically well-defined (Theorem 7) and give a simple scheme to construct the phylogeny tree and the common ancestors. Our preliminary experiments with simulated data look very promising.}, address = {Computational Biology Center, IBM T.J.Watson Research Center, Yorktown Heights, New York 10598, USA. parida@us.ibm.com}, author = {Parida, L. }, citeulike-article-id = {2169739}, doi = {10.1089/cmb.2006.13.1685}, issn = {1066-5277}, journal = {J Comput Biol}, month = {December}, number = {10}, pages = {1685--1700}, posted-at = {2007-12-26 10:31:08}, priority = {2}, title = {Using PQ structures for genomic rearrangement phylogeny.}, url = {http://dx.doi.org/10.1089/cmb.2006.13.1685}, volume = {13}, year = {2006} }

TY - JOUR ID - citeulike:2169739 L3 - citeulike-article-id:2169739 TI - Using PQ structures for genomic rearrangement phylogeny. JF - J Comput Biol VL - 13 IS - 10 SP - 1685 EP - 1700 AD - Computational Biology Center, IBM T.J.Watson Research Center, Yorktown Heights, New York 10598, USA. parida@us.ibm.com SN - 1066-5277 N2 - Various international efforts are underway to catalog the genomic similarities and variations in the human population. Some key discoveries such as inversions and transpositions within the members of the species have also been made over the years. The task of constructing a phylogeny tree of the members of the same species, given this knowledge and data, is an important problem. In this context, a key observation is that the "distance" between two members, or member and ancestor, within the species is small. In this paper, we pose the tree reconstruction problem exploiting some of these peculiarities. The central idea of the paper is based on the notion of minimal consensus PQ tree T of sequences. We use a modified PQ structure (termed oPQ) and show that both the number and size of each T is O(1). We further show that the tree reconstruction problem is statistically well-defined (Theorem 7) and give a simple scheme to construct the phylogeny tree and the common ancestors. Our preliminary experiments with simulated data look very promising. AU - Parida, L PY - 2006/12// UR - http://dx.doi.org/10.1089/cmb.2006.13.1685 ER -