MESSAGE
DATE  20170302 
FROM  Ruben Safir

SUBJECT  Subject: [Learn] Ultrametric networks: a new tool for phylogenetic analysis

From learnbouncesatnylxs.com Thu Mar 2 02:09:50 2017 ReturnPath: XOriginalTo: archiveatmrbrklyn.com DeliveredTo: archiveatmrbrklyn.com Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82]) by mrbrklyn.com (Postfix) with ESMTP id CEBAC161313; Thu, 2 Mar 2017 02:09:49 0500 (EST) XOriginalTo: learnatnylxs.com DeliveredTo: learnatnylxs.com Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62]) by mrbrklyn.com (Postfix) with ESMTP id 82C87160E77 for ; Thu, 2 Mar 2017 02:09:46 0500 (EST) To: "learnatnylxs.com" From: Ruben Safir MessageID: <4f3219a3f1cf6ba33442a3b96ccbb56batmrbrklyn.com> Date: Thu, 2 Mar 2017 02:09:46 0500 UserAgent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.6.0 MIMEVersion: 1.0 Subject: [Learn] Ultrametric networks: a new tool for phylogenetic analysis XBeenThere: learnatnylxs.com XMailmanVersion: 2.1.17 Precedence: list ListId: ListUnsubscribe: , ListArchive: ListPost: ListHelp: ListSubscribe: , ContentType: text/plain; charset="utf8" ContentTransferEncoding: quotedprintable ErrorsTo: learnbouncesatnylxs.com Sender: "Learn"
Ultrametric networks: a new tool for phylogenetic analysis
https://almob.biomedcentral.com/articles/10.1186/1748718887
Ultrametric networks: a new tool for phylogenetic analysis Alberto Apostolico, Matteo CominEmail author, Andres Dress and Laxmi Parida Algorithms for Molecular Biology20138:7 DOI: 10.1186/1748718887=C2=A9 Apostolico et al.; licensee BioMed Central Ltd. 2013 Received: 15 October 2012Accepted: 18 February 2013Published: 5 March 2013 Abstract
Background The large majority of optimization problems related to the inference of distance=E2=80=90based trees used in phylogenetic analysis and classificati= on is known to be intractable. One noted exception is found within the realm of ultrametric distances. The introduction of ultrametric trees in phylogeny was inspired by a model of evolution driven by the postulate of a molecular clock, now dismissed, whereby phylogeny could be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves. Both, molecular clocks and rooted ultrametric trees, fell out of fashion as credible representations of evolutionary change. At the same time, ultrametric dendrograms have shown good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. Most of these approximations are still intractable, but the problem of finding the nearest ultrametric distance matrix to a given distance matrix with respect to the L =E2=88=9E distance has been long known to be solvable in polynomial time, the solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.
Results This paper expands this subdominant ultrametric perspective by studying ultrametric networks, consisting of the collection of all edges involved in some minimum spanning tree. It is shown that, for a graph with n vertices, the construction of such a network can be carried out by a simple algorithm in optimal time O(n2) which is faster by a factor of n than the direct adaptation of the classical O(n3) paradigm by Warshall for computing the transitive closure of a graph. This algorithm, called UltraNet, will be shown to be easily adapted to compute relaxed networks and to support the introduction of artificial points to reduce the maximum distance between vertices in a pair. Finally, a few experiments will be discussed to demonstrate the applicability of subdominant ultrametric networks.
Availability http://www.dei.unipd.it/~ciompin/main/Ultranet/Ultranet.html
Keywords
Phylogenetic network Ultrametric distance STR data analysis Background
As is well known, most optimization problems related to the inference of distance=E2=80=90based trees used in phylogenetic analysis and classificati= on are intractable (see [1, 2] for a pertinent discussion). One notable exception is found within the realm of ultrametric distances (cf. [3]). The introduction of such distances in phylogeny was inspired by a model of evolution, now largely abandoned, driven by the postulate of a molecular clock whereby the amount of phylogenetic change observable between any two extant species is directly related to the amount of time that elapsed since their last common ancestor roamed this planet, implying that phylogenetic distances could simply be represented by a weighted tree in which the sum of the weights of the edges separating any given leaf from the root is the same for all leaves.
Both molecular clocks and rooted ultrametric trees fell out of fashion as credible representations of evolutionary change. At the same time, a rooted dated tree is still the =E2=80=9Cobject of desire=E2=80=9D in taxono= my and Tree=E2=80=90of=E2=80=90Life research, and ultrametric dendrograms have sho= wn good potential for purposes of classification in so far as they have proven to provide good approximations for additive trees. While finding the =E2=80=9Cbest=E2=80=9D such approximation is, in most cases, still intracta= ble, the problem of finding an ultrametric distance matrix that is closest to a given distance matrix with respect to the L =E2=88=9E distance has long been known to be solvable in polynomial time, its solution being incarnated in any minimum spanning tree for the weighted graph subtending to the matrix.
Applications of minimum spanning trees in connection with problems of population classification and genetics are as old as any other of their numerous applications. An application to taxonomic problems related to species interrelationship dates back to [4]. And as early as 1964, Edwards and Cavalli Sforza [5] used MSTs to approximate evolutionary trees reconstructed from gene frequencies in blood groups from fifteen contemporary human populations.
Most approximation problems arising in this context fall within the framework of the following
Closest Metric Problem: Given a setMof metrics C defined on a set V, an V=C3=97V=E2=88=92m a t r i x M, and a distance functionD:(M=E2=80=B2,M= =E2=80=B2=E2=80=B2)=E2=86=92R=E2=89=A50defined on the setRV=C3=97Vof all V=C3=97V=E2=88=92m a t r i c e s, find a met= ricC=E2=88=88Mwith minimum distance to M relative to D.
The basic facts are summarized in Table 1.
 =
So many immigrant groups have swept through our town that Brooklyn, like Atlantis, reaches mythological proportions in the mind of the world  RI Safir 1998 http://www.mrbrklyn.com
DRM is THEFT  We are the STAKEHOLDERS  RI Safir 2002 http://www.nylxs.com  Leadership Development in Free Software http://www2.mrbrklyn.com/resources  Unpublished Archive http://www.coinhangout.com  coins! http://www.brooklynliving.com
Being so tracked is for FARM ANIMALS and and extermination camps, but incompatible with living as a free human being. RI Safir 2013 _______________________________________________ Learn mailing list Learnatnylxs.com http://lists.mrbrklyn.com/mailman/listinfo/learn

