Here=E2=80=99s a set of introductory slides on inference of phylogenetic=
trees.

pdf" class=3D"uri">http://www.cs.otago.ac.nz/cosc348/phylo/Lecture14_PhyloO=
ptim.pdf

Based on what I=E2=80=99ve learned today, =E2=80=9Csmall=E2=80=9D parsim=
ony algorithms like Fitch and Sankoff rely on labeling a given tre=
e shape (aka topology), so we already have to know (or hypothesize) the anc=
estral relationships. The algorithm just determines which labels (mutations=
) to assign to interior nodes. That=E2=80=99s really unsatisfying to me.

But the =E2=80=9Cbig=E2=80=9D parsimony techniques have to search the en=
tire tree space, which is ENORMOUS. The problem is formally NP-hard. Now =
=E2=80=93 people do manage to solve (or approximately solve) NP-hard proble=
ms every day by using piles of dirty tricks. When it comes to searching gig=
antic spaces, those dirty tricks are the classic techniques of artificial i=
ntelligence.

So the lecture slides get into techniques like greedy algorithms, hill-c=
limbing, simulated annealing, genetic algorithms, etc. Anyway, there could =
be a lot of meat here that fits under the heading of AI + phylogenetics. It=
=E2=80=99s much more accessible stuff than trying to automatically interpre=
t 3D model data to take measurements of maxillary bones.

CL

Ruben Safir ruben-at-mrbrklyn.com=
writes:

http://telliott99.blogspot.com/2010/03/fitch-and-sankoff-algorithms-for.=
html

=E2=80=9CThe Fitch algorithm considers the sites (or characters) one at =
a time. At each tip in the tree, we create a set containing those nucleotid=
es (states) that are observed or are compatible with the observation. Thus,=
if we see an A, we create the set {A}. If we see an ambiguity such as R, w=
e create the set {AG}. Now we move down the tree [away from the tips]. In a=
lgorithmic terms, we do a postorder tree traversal. At each interior node w=
e create a set that is the intersection of sets at the two descendant nodes=
. However, if that set is empty, we instead create the set that is the unio=
n of the two sets at the descendant nodes. Every time we create such a unio=
n, we also count one change of state.=E2=80=9D

https://en.wikipedia.org/wiki/Non-parametric Nonparametric statistics ar=
e statistics not based on parameterized families of probability distributio=
ns. They include both descriptive and inferential statistics. The typical p=
arameters are the mean, variance, etc. Unlike parametric statistics, nonpar=
ametric statistics make no assumptions about the probability distributions =
of the variables being assessed. The difference between parametric models a=
nd non-parametric models is that the former has a fixed number of parameter=
s, while the latter grows the number of parameters with the amount of train=
ing data.[1] Note that the non-parametric model does, counterintuitively, c=
ontain parameters: the distinction is that parameters are determined by the=
training data in the case of non-parametric statistics, not the model.

https://en.wikipedia.org/wiki/Fitch-Margoliash_algorithm Distance-matrix=
methods

Distance-matrix methods of phylogenetic analysis explicitly rely on a me=
asure of =E2=80=9Cgenetic distance=E2=80=9D between the sequences being cla=
ssified, and therefore they require an MSA (multiple sequence alignment) as=
an input. Distance is often defined as the fraction of mismatches at align=
ed positions, with gaps either ignored or counted as mismatches.[1] Distanc=
e methods attempt to construct an all-to-all matrix from the sequence query=
set describing the distance between each sequence pair. From this is const=
ructed a phylogenetic tree that places closely related sequences under the =
same interior node and whose branch lengths closely reproduce the observed =
distances between sequences. Distance-matrix methods may produce either roo=
ted or unrooted trees, depending on the algorithm used to calculate them. T=
hey are frequently used as the basis for progressive and iterative types of=
multiple sequence alignment. The main disadvantage of distance-matrix meth=
ods is their inability to efficiently use information about local high-vari=
ation regions that appear across multiple subtrees.[2]

=E2=80=93 So many immigrant groups have swept through our town that Broo=
klyn, like Atlantis, reaches mythological proportions in the mind of the wo=
rld - 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/reso=
urces - Unpublished Archive http://www.coinhangout.com - coins! http://www.=
brooklyn-living.com

Being so tracked is for FARM ANIMALS and and extermination camps, but in=
compatible with living as a free human being. -RI Safir 2013 ______________=
_________________________________ Learn mailing list Learn-at-nylxs.com http:/=
/lists.mrbrklyn.com/mailman/listinfo/learn