MESSAGE
| DATE | 2017-03-02 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [Learn] Ultrametric networks: a new tool for phylogenetic analysis
|
From learn-bounces-at-nylxs.com Thu Mar 2 02:09:50 2017
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.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)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.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: "learn-at-nylxs.com"
From: Ruben Safir
Message-ID: <4f3219a3-f1cf-6ba3-3442-a3b96ccbb56b-at-mrbrklyn.com>
Date: Thu, 2 Mar 2017 02:09:46 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.6.0
MIME-Version: 1.0
Subject: [Learn] Ultrametric networks: a new tool for phylogenetic analysis
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
Ultrametric networks: a new tool for phylogenetic analysis
https://almob.biomedcentral.com/articles/10.1186/1748-7188-8-7
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/1748-7188-8-7=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=97|V|=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 setR|V|=C3=97|V|of all |V|=C3=97|V|=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.brooklyn-living.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
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
|
|
