Tue Oct 4 02:32:53 2022
EVENTS
 FREE
SOFTWARE
INSTITUTE

POLITICS
JOBS
MEMBERS'
CORNER

MAILING
LIST

NYLXS Mailing Lists and Archives
NYLXS Members have a lot to say and share but we don't keep many secrets. Join the Hangout Mailing List and say your peice.

DATE 2017-03-01

LEARN

2022-10-04 | 2022-09-04 | 2022-08-04 | 2022-07-04 | 2022-06-04 | 2022-05-04 | 2022-04-04 | 2022-03-04 | 2022-02-04 | 2022-01-04 | 2021-12-04 | 2021-11-04 | 2021-10-04 | 2021-09-04 | 2021-08-04 | 2021-07-04 | 2021-06-04 | 2021-05-04 | 2021-04-04 | 2021-03-04 | 2021-02-04 | 2021-01-04 | 2020-12-04 | 2020-11-04 | 2020-10-04 | 2020-09-04 | 2020-08-04 | 2020-07-04 | 2020-06-04 | 2020-05-04 | 2020-04-04 | 2020-03-04 | 2020-02-04 | 2020-01-04 | 2019-12-04 | 2019-11-04 | 2019-10-04 | 2019-09-04 | 2019-08-04 | 2019-07-04 | 2019-06-04 | 2019-05-04 | 2019-04-04 | 2019-03-04 | 2019-02-04 | 2019-01-04 | 2018-12-04 | 2018-11-04 | 2018-10-04 | 2018-09-04 | 2018-08-04 | 2018-07-04 | 2018-06-04 | 2018-05-04 | 2018-04-04 | 2018-03-04 | 2018-02-04 | 2018-01-04 | 2017-12-04 | 2017-11-04 | 2017-10-04 | 2017-09-04 | 2017-08-04 | 2017-07-04 | 2017-06-04 | 2017-05-04 | 2017-04-04 | 2017-03-04 | 2017-02-04 | 2017-01-04 | 2016-12-04 | 2016-11-04 | 2016-10-04 | 2016-09-04 | 2016-08-04 | 2016-07-04 | 2016-06-04 | 2016-05-04 | 2016-04-04 | 2016-03-04 | 2016-02-04 | 2016-01-04 | 2015-12-04 | 2015-11-04 | 2015-10-04 | 2015-09-04 | 2015-08-04 | 2015-07-04 | 2015-06-04 | 2015-05-04 | 2015-04-04 | 2015-03-04 | 2015-02-04 | 2015-01-04 | 2014-12-04 | 2014-11-04 | 2014-10-04

Key: Value:

Key: Value:

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

  1. 2017-03-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] neutal networks and pacman
  2. 2017-03-02 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Ultrametric networks: a new tool for phylogenetic analysis
  3. 2017-03-05 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] cost in evolution
  4. 2017-03-09 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] CatScan fossil files
  5. 2017-03-10 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] neural Networks and Quantum Mechanics
  6. 2017-03-12 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] I just found a GREAT video on partial derivatives
  7. 2017-03-13 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Contact DOJ and thell them to blow it out their ass
  8. 2017-03-14 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] CatScan fossil files
  9. 2017-03-14 Ramon Nagesan <ramon.nagesan-at-gmail.com> Re: [Learn] CatScan fossil files
  10. 2017-03-16 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] is this up
  11. 2017-03-16 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] hang out is down
  12. 2017-03-16 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] is this working
  13. 2017-03-16 Charlie Gonzalez <itcharlie-at-gmail.com> Subject: [Learn] Registration for The Perl Conference 2017 is now open!!
  14. 2017-03-16 From: "soledad.esteban" <soledad.esteban-at-icp.cat> Subject: [Learn] [dinosaur] Advanced course Geometric Morphometrics in R,
  15. 2017-03-17 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Advanced course Geometric Morphometrics in
  16. 2017-03-17 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] good news !
  17. 2017-03-18 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] circles
  18. 2017-03-20 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Alice
  19. 2017-03-20 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] hough transform - Lecture 9
  20. 2017-03-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Anyone understand this well
  21. 2017-03-21 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Fwd: [dinosaur] Digital mapping of dinosaurian tracksites
  22. 2017-03-22 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] ODBASE 2017 - The 16th International Conference on
  23. 2017-03-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Decision Tree
  24. 2017-03-24 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Genetic Modification with decent
  25. 2017-03-27 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] Fwd: Re: hough transform - Lecture 9
  26. 2017-03-27 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] MOOCS
  27. 2017-03-27 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Peter Novig learning and on line teaching
  28. 2017-03-28 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] computations
  29. 2017-03-29 Christopher League <league-at-contrapunctus.net> Re: [Learn] This is hard to understand what the logic is here
  30. 2017-03-29 Ruben Safir <ruben-at-mrbrklyn.com> Re: [Learn] This is hard to understand what the logic is here
  31. 2017-03-29 Christopher League <league-at-contrapunctus.net> Re: [Learn] This is hard to understand what the logic is here
  32. 2017-03-29 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] This is hard to understand what the logic is here
  33. 2017-03-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] perseptors
  34. 2017-03-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] This is hard to understand what the logic is here
  35. 2017-03-29 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] This is hard to understand what the logic is here
  36. 2017-03-30 Ruben Safir <mrbrklyn-at-panix.com> Re: [Learn] c arrays
  37. 2017-03-30 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] c arrays
  38. 2017-03-30 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] random weights
  39. 2017-03-30 Ruben Safir <mrbrklyn-at-panix.com> Subject: [Learn] randomize with commentary
  40. 2017-03-31 Ruben Safir <ruben-at-mrbrklyn.com> Subject: [Learn] Computational Paleo

NYLXS are Do'ers and the first step of Doing is Joining! Join NYLXS and make a difference in your community today!