SPECIES TREES FORCING PARSIMONY TO FAIL
% \textsc{Vikenty Mikheev
\noindent The fact that Parsimony may fail is not new. However, here we proved that no mater of what topology the true 9-taxon and greater species tree is the only thing you need to fail Parsimony is to have in this tree three consecutive edges with lengths $T1,T2,T3$ of some proportions. Obviously, the probability to meet these lengths is growing in general with the size of species tree. Therefore, Parsimony can be applied only when one knows for sure that the described lengths cannot be met in the tree. {Key Words: Parsimony; MRP; coalescence theory; evolutionary trees; caterpillar tree; caterpillar subtree; caterpillar measure; caterpillar score; revolution number.
parsimony2017arxiv.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Journal Article

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

%\documentclass[twoside,twocolumn]{article}
\documentclass[twoside]{article}

\usepackage{multicol}

\usepackage{amsmath,amssymb,amsthm,graphicx,array} 
\usepackage{graphicx}
\usepackage{epstopdf}


\usepackage{hyperref}
\hypersetup{
	colorlinks=true,
	linkcolor=blue,
	filecolor=blue,%magenta,      
	urlcolor=blue,%cyan,
}

\usepackage[sc]{mathpazo} % Use the Palatino font
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\linespread{1.05} % Line spacing - Palatino needs more space between lines
\usepackage{microtype} % Slightly tweak font spacing for aesthetics

\usepackage[english]{babel} % Language hyphenation and typographical rules

\usepackage[hmarginratio=1:1,top=32mm,columnsep=20pt]{geometry} % Document margins
\usepackage[hang, small,labelfont=bf,up,textfont=it,up]{caption} % Custom captions under/above floats in tables or figures
\usepackage{booktabs} % Horizontal rules in tables

\usepackage{lettrine} % The lettrine is the first enlarged letter at the beginning of the text

\usepackage{enumitem} % Customized lists
\setlist[itemize]{noitemsep} % Make itemize lists more compact

\usepackage{abstract} % Allows abstract customization
\renewcommand{\abstractnamefont}{\normalfont\bfseries} % Set the "Abstract" text to bold
\renewcommand{\abstracttextfont}{\normalfont\small\itshape} % Set the abstract itself to small italic text

\usepackage{titlesec} % Allows customization of titles
\renewcommand\thesection{\Roman{section}} % Roman numerals for the sections
\renewcommand\thesubsection{\roman{subsection}} % roman numerals for subsections
\titleformat{\section}[block]{\large\scshape\centering}{\thesection.}{1em}{} % Change the look of the section titles
\titleformat{\subsection}[block]{\large}{\thesubsection.}{1em}{} % Change the look of the section titles

\usepackage{fancyhdr} % Headers and footers
\pagestyle{fancy} % All pages have headers and footers
\fancyhead{} % Blank out the default header
\fancyfoot{} % Blank out the default footer
\fancyhead[C]{Running title $\bullet$ May 2016 $\bullet$ Vol. XXI, No. 1} % Custom header text
\fancyfoot[RO,LE]{\thepage} % Custom footer text

\usepackage{titling} % Customizing the title section

%\usepackage{hyperref} % For hyperlinks in the PDF

% Theorem Formatting Commands.
\theoremstyle{plain}
\newtheorem{thm}{Theorem}%[section]
%\newtheorem{lemma}{Lemma}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{pr}[thm]{Problem}
\newtheorem{alg}[thm]{Algorithm}
\newtheorem{ques}[thm]{Question}

\theoremstyle{remark}
\newtheorem*{rmk}{Remark}
\newtheorem*{obs}{Observation}


% Math symbol shorthand
\newcommand{\RR}{{\mathbb R}}
\newcommand{\TT}{{\mathfrak T}}


%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\setlength{\droptitle}{-4\baselineskip} % Move the title up

\pretitle{\begin{center}\Huge\bfseries} % Article title formatting
\posttitle{\end{center}} % Article title closing formatting
\title{SPECIES TREES FORCING PARSIMONY TO FAIL} % Article title
\author{%
\textsc{Vikenty Mikheev }%\thanks{A thank you or further information} \\[1ex] % Your name
\normalsize \ Kansas State University \\ % Your institution
\normalsize \href{mailto:vikentym@ksu.edu}{vikentym@ksu.edu} % Your email address
\and % Uncomment if 2 authors are required, duplicate these 4 lines if more
\textsc{Serge E. Miheev}%\thanks{Corresponding author} \\[1ex] % Second author's name
\normalsize \ St.Petersburg State University \\ % Second author's institution
\normalsize \href{mailto:him2@mail.ru}{him2@mail.ru} % Second author's email address
}
\date{\today} % Leave empty to omit a date
\renewcommand{\maketitlehookd}{%
\begin{abstract}
\noindent The fact that Parsimony may fail is not new. However, here we proved that no mater of what topology the true 9-taxon and greater species tree is the only thing you need to fail Parsimony is to have in this tree three consecutive edges with lengths $T1,T2,T3$ of some proportions. Obviously, the probability to meet these lengths is growing in general with the size of species tree. 
Therefore, Parsimony can be applied only when one knows for sure that the described lengths cannot be met in the tree.

{\bf Key Words:} Parsimony; MRP; coalescence theory; evolutionary trees; caterpillar tree; caterpillar subtree; caterpillar measure; caterpillar score; revolution number.

\end{abstract}
}

%----------------------------------------------------------------------------------------

\begin{document}

% Print the title
\maketitle


\begin{multicols}{2}
\section{I{\sc NTRODUCTION}}

We have considered a tree $T$ of 5 species $a$, $b$, $c$, $d$ and $e$ with some parameters $T_1$, $T_2$, $T_3$ -- time in coalescence units between the branching points (see an example in fig. \ref{T5Coal}). 

%T5Coal

From the Coalescent model \cite{Rosenberg}, \cite{SempleSteel}, \cite{Wakeley}, \cite{Baum}  and the program COAL \cite{WangDegnan}, we have obtained the probabilities of all 15 possible unrooted gene trees for 5 genes $A$, $B$, $C$, $D$, $E$, such that $A$ is discovered in species $a$, $B$ is discovered in the species $b$ and so on.

There are also 15 different unrooted species trees or 105 rooted ones. In each species tree, one can fit any of 15 different gene trees. However, the amount of mutations needed for this will differ generally from one gene tree to another.
So, for each gene tree from these 15 and each species tree from the same 15 one can correspond some nonnegative integer number of mutations. These can be written in a $15\times 15 $ matrix $M$, where rows correspond to species trees and columns correspond to gene trees.


If one knows the frequencies of different gene trees $P=(p_1,...,p_{15})^T$, then the mathematical expectation of the number of mutations for each of 15 possible species trees can be calculated by multiplying the matrix $M$ by the vector-column $P$. 

One can assume that the most probable species tree for the given sample of gene trees (or 15 gene trees with assigned probabilities) corresponds to the minimal expectation of mutations. This is the idea of Parsimony method \cite{Allman}, its application to the problem of inferring species trees from gene trees is called Matrix Representation with Parsimony (MRP) \cite{WangDegnan}. 

Here is the main question: Does the species tree with the minimal expectation from $M*P$, where $P$ is the vector of probabilities (obtained, for example, from the Coalescent method (\cite{Degnan}) with given $T_1$, $T_2$, $T_3$ for the tree $T$) present the unrooted version of the original rooted tree $T$?

Note that we compare rooted tree with unrooted tree. It is because the Coalescent method works with rooted trees while parsimony gives only unrooted ones.

It appeared in our work that on the sample of gene trees obtained from a caterpillar species tree with some parameters $T_1$, $T_2$, $T_3$ by coalescence, the parsimony method gives an incorrect species tree. 

\end{multicols}
%\onecolumn
\begin{figure}[h]%[!p]
	\centering
	\hspace*{0.7cm} 
	\includegraphics[scale=0.7]{./T5speciesT1T2T3.eps}%
	\caption{A 5-taxon species tree with caterpillar topology.}
	\label{T5Coal}
\end{figure}
\begin{multicols}{2}




\enlargethispage{2pt}

\section{	N{\sc UMERICAL} E{\sc XPERIMENTS}. P{\sc ERFORMANCE} O{\sc F} U{\sc NROOTED} M{\sc RP} F{\sc OR} 5-T{\sc AXON} S{\sc PECIES}  T{\sc REE} I{\sc INFERENCE.}		}




Any 5 genes can be joined in one unrooted tree in 15 ways as given in the following list: %Table \ref{Tb_ListOf15Trees}.

\begin{center}%[h]%[!p]
	\begin{tabular}{cc}
		$\tau_1$: $((B,C),A,(D,E))$,\\
		$\tau_2$: $((C,D),A,(B,E))$,\\
		$\tau_3$: $((C,E),A,(B,D))$,\\
		
		$\tau_4$: $((A,E),B,(C,D))$,\\
		$\tau_5$: $((A,D),B,(C,E))$,\\
		$\tau_6$: $((A,C),B,(D,E))$,\\
		
		$\tau_7$: $((A,B),C,(D,E))$,\\
		$\tau_8$: $((A,D),C,(B,E))$,\\
		$\tau_9$: $((A,E),C,(B,D))$,\\
		
		$\tau_{10}$: $((A,B),D,(C,E))$,\\
		$\tau_{11}$: $((A,C),D,(B,E))$,\\
		$\tau_{12}$: $((A,E),D,(B,C))$,\\
		
		$\tau_{13}$: $((A,B),E,(C,D))$,\\
		$\tau_{14}$: $((A,C),E,(B,D))$,\\
		$\tau_{15}$: $((A,D),E,(B,C))$.\\
	\end{tabular}
%	\caption{15 topological 5-taxon trees.}
	\label{Tb_ListOf15Trees}
\end{center}

Each unrooted tree may be transformed into a rooted tree by introducing a root to an edge. As a result, we have 7 rooted versions for each unrooted tree.

{\bf Step 1.} Compute parsimony scores  by Fitch-Hartigan \cite{Hartigan} (Table \ref{table:pars15_15}).

%Table 2

Thus, if $\vec{N}=(N_1,N_2,...,N_{15})$ is the vector of counts of 15 topological trees in the input. $P$ is the matrix of entries in Table \ref{table:pars15_15} and $\vec{S}=(pars(\sigma_1),\ pars(\sigma_2),..., pars(\sigma_{15}))$ then $\vec{S}=P\vec{N}$.

{\bf Step 4.} We now pick the smallest entry or entries in $\vec{S}$ to determine the most parsimonious tree(s).

To study the 5-taxon case further we need to use Coalescent Theory.

The coalescent model, introduced by Kingman in \cite{Kingman}, describes the coalescence of lineages as we move backwards in time within a single species (Note that in biology the understanding of the word `species'  may vary. Here we use this word in the same meaning as `population'). By ``gluing" together such species or populations to form a tree, one gets the Multi-species Coalescent Model, which describes the production of gene trees within species trees.
\end{multicols}
\begin{table}[h]
	
	\centering % used for centering table 
	\begin{tabular}{||c || c | c |c |c |c |c |c |c |c |c |c |c |c |c |c ||}
		\hline\hline %inserts double horizontal lines 
		& $\tau_1$ & $\tau_2$ & $\tau_3$ & $\tau_4$ & $\tau_5$ & $\tau_6$ & $\tau_7$ & $\tau_8$ & $\tau_9$ & $\tau_{10}$ & $\tau_{11}$ & $\tau_{12}$ & $\tau_{13}$ & $\tau_{14}$ & $\tau_{15}$ \\ [0.5ex] % inserts table 
		%heading 
		\hline % inserts single horizontal line 
		%               1   2   3   4   5   6   7   8   9   10  11  12  13  14  15 
		$\sigma_1   $ & 2 & 4 & 4 & 4 & 4 & 3 & 3 & 4 & 4 & 4 & 4 & 3 & 4 & 4 & 3   \\ [1ex]
		$\sigma_2   $ & 4 & 2 & 4 & 3 & 4 & 4 & 4 & 3 & 4 & 4 & 3 & 4 & 3 & 4 & 4  \\ [1ex]
		$\sigma_3   $ & 4 & 4 & 2 & 4 & 3 & 4 & 4 & 4 & 3 & 3 & 4 & 4 & 4 & 3 & 4  \\ [1ex]
		$\sigma_4   $ & 4 & 3 & 4 & 2 & 4 & 4 & 4 & 4 & 3 & 4 & 4 & 3 & 3 & 4 & 4  \\ [1ex]
		$\sigma_5   $ & 4 & 4 & 3 & 4 & 2 & 4 & 4 & 3 & 4 & 3 & 4 & 4 & 4 & 4 & 3  \\ [1ex]
		$\sigma_6   $ & 3 & 4 & 4 & 4 & 4 & 2 & 3 & 4 & 4 & 4 & 3 & 4 & 4 & 3 & 4   \\[1ex]
		$\sigma_7   $ & 3 & 4 & 4 & 4 & 4 & 3 & 2 & 4 & 4 & 3 & 4 & 4 & 3 & 4 & 4  \\ [1ex]
		$\sigma_8   $ & 4 & 3 & 4 & 4 & 3 & 4 & 4 & 2 & 4 & 4 & 3 & 4 & 4 & 4 & 3  \\ [1ex]
		$\sigma_9   $ & 4 & 4 & 3 & 3 & 4 & 4 & 4 & 4 & 2 & 4 & 4 & 3 & 4 & 3 & 4  \\ [1ex]
		$\sigma_{10}$ & 4 & 4 & 3 & 4 & 3 & 4 & 3 & 4 & 4 & 2 & 4 & 4 & 3 & 4 & 4  \\ [1ex]
		$\sigma_{11}$ & 4 & 3 & 4 & 4 & 4 & 3 & 4 & 3 & 4 & 4 & 2 & 4 & 4 & 3 & 4   \\[1ex]
		$\sigma_{12}$ & 3 & 4 & 4 & 3 & 4 & 4 & 4 & 4 & 3 & 4 & 4 & 2 & 4 & 4 & 3  \\ [1ex]
		$\sigma_{13}$ & 4 & 3 & 4 & 3 & 4 & 4 & 3 & 4 & 4 & 3 & 4 & 4 & 2 & 4 & 4 \\ [1ex]
		$\sigma_{14}$ & 4 & 4 & 3 & 4 & 4 & 3 & 4 & 4 & 3 & 4 & 3 & 4 & 4 & 2 & 4  \\ [1ex]
		$\sigma_{15}$ & 3 & 4 & 4 & 4 & 3 & 4 & 4 & 3 & 4 & 4 & 4 & 3 & 4 & 4 & 2  \\[1ex] % [1ex] adds vertical space 
		\hline	\hline %inserts single line 
	\end{tabular} 
	\caption{The parsimony scores $pars_{\chi_\tau}(\sigma)$ for all 15 possible output trees $\sigma$ with respect to the matrix representation of all 15 possible input trees $\tau$.}
	\label{table:pars15_15} % is used to refer this table in the text
\end{table}

\begin{multicols}{2}

\begin{defn}
	Let  $g_{ij}(u)$ denote the probability that $i$ lineages (genes) at time $u=0$ have coalesced to exactly $j$ lineages at time $u$ under the coalescent model.
\end{defn}

General formulas for the $g_{ij}(u)$ were derived in \cite{Tavare}:
$$
g_{ij}(T)=\sum_{k=j}^ie^{-k(k-1)T/2}\frac{(2k-1)(-1)^{k-j}j_{(k-1)}i_{[k]}}{j! (k-j)!i_{(k)}},$$ 
where $a_{(k)}=a(a+1)\cdots (a+k-1)$ for $k\ge 1$ with $a_{(0)}=1$ (the partial permutation); and $a_{[k]}=a(a-1)\cdots (a-k+1)$ for $k\ge 1$ with $a_{[0]}=1$.

Some of these formulas for small indexes are
\begin{align*}
	g_{11}(T)&=1,\\
	g_{21}(T)&=1-e^{-T},\\
	g_{31}(T)&=1-(3/2)e^{-T}+(1/2)e^{-3T}, \\
	g_{22}(T)&=e^{-T},\\ g_{32}(T)&=(3/2)e^{-T}-(3/2)e^{-3T}, \\
	g_{33}(T)&=e^{-3T}, \\ 
	g_{41}(T)&=1-(9/5)e^{-T}+e^{-3T}-(1/5)e^{-6T}, \\
	g_{42}(T)&=(9/5)e^{-T}-3e^{-3T}+(6/5)e^{-6T},\\
	g_{43}(T)&=2e^{-3T}-2e^{-6T},\\
	g_{44}(T)&=e^{-6T}.
\end{align*}

We will consider 3 rooted species tree $\Sigma_1:=((((a,b)\text{:}T_1,c)\text{:}T_2,d)\text{:}T_3,e)$, $\Sigma_2:=(((a,b)\text{:}T_1,(c,d)\text{:}T_2)\text{:}T_3,e)$ and $\Sigma_3:=(((a,b)\text{:}T_1,c)\text{:}T_2,(d,e)\text{:}T_3)$, which are rooted versions of $\sigma_7, \sigma_{13}$ and $\sigma_7$ again, respectively (see Figure \ref{Fcoal3r5taxa}). Up to taxon names, these three are the only possible species trees. They are usually referred to  as the {\it caterpillar} ($\Sigma_1$), {\it pseudo-caterpillar} ($\Sigma_2$) and {\it pseudo-balanced}($\Sigma_3$) species trees.

\end{multicols}


%\onecolumn



\begin{figure}%[!p]
\centering   
\includegraphics{./fgCOAL3r5taxa.eps}
\caption{Three rooted 5-taxon species trees $\Sigma_1, \Sigma_2$ and $\Sigma_3$.}
\label{Fcoal3r5taxa}
\end{figure}

%\enlargethispage{-1pt}
\begin{multicols}{2}

\section{A{\sc N} E{\sc XPERIMENT} W{\sc  ITH} C{\sc ATERPILLAR}}


Using the program COAL \cite{Degnan} to get probabilities of rooted gene trees and the formulas for $g_{ij}$, we calculate the probabilities $p_i=p(\tau_i| \Sigma_1)$ for $i=\overline{1,15}$, which  are listed in Table \ref{Tb_Probs} ($X:=e^{-T_1},\ Y:=e^{-T_2}, \ Z:=e^{-T_3},$) after simplification in Maple 15.



\end{multicols}



\begin{table}[h]

\centering % used for centering table 
\begin{tabular}{||c | l |}
	\hline%\hline %inserts double horizontal lines 
	%to & write something \\ % [0.5ex] % inserts table 
	%	heading 
		
	$   p_1$ & $X/3 - (X Y)/3 + (X Y^3)/18 + 1/90 X Y^3 Z^6$\\  [1ex]
	$	p_2$ & $(X Y^3)/18 +  1/90 X Y^3 Z^6  $\\ [1ex]
	$	p_3$ & $(X Y^3)/18 + 1/90 X Y^3 Z^6  $\\ [1ex]
	$	p_4$ & $(X Y^3)/18 +   1/90 X Y^3 Z^6  $\\ [1ex]
	$	p_5$ & $(X Y^3)/18 + 1/90 X Y^3 Z^6 $\\ [1ex]
	$   p_6$  &$X/3 - (X Y)/3 + (X Y^3)/18 + 1/90 X Y^3 Z^6 $\\ [1ex]
	$   p_7$  &$1 - (2 X)/3 - (2 Y)/3 + (X Y)/3 + (X Y^3)/18 + 1/90 X Y^3 Z^6 $\\[1ex]
	$   p_8$  &$(  X Y^3)/18 + 1/90 X Y^3 Z^6  $\\[1ex]
	$   p_9$  &$(X Y^3)/18 + 1/90 X Y^3 Z^6   $\\ [1ex]
	$   p_{10}$ &$Y/3 - (X Y)/6 - (X Y^3)/9 + 1/90 X Y^3 Z^6 $\\ [1ex]
	$   p_{11}$ &$(X Y)/6 - (X Y^3)/9 +  1/90 X Y^3 Z^6 $\\ [1ex]
	$   p_{12}$ &$(X Y)/6 - (X Y^3)/9 + 1/90 X Y^3 Z^6        $\\ [1ex]
	$   p_{13}$ &$Y/3 - (X Y)/6 - (X Y^3)/18 - 2/45 X Y^3 Z^6 $\\[1ex]
	$   p_{14}$ &$(X Y)/6 - (X Y^3)/18 -   2/45 X Y^3 Z^6$\\ [1ex]
	$   p_{15}$ &$(X Y)/6 - (X Y^3)/18 - 2/45 X Y^3 Z^6 $\\[1ex] %adds vertical space 
	\hline %inserts single line 
\end{tabular} 
\caption{The probabilities $p_i=p(\tau_i| \Sigma_1)$ for $i=\overline{1,15}$, where $X=e^{-T_1}$,\ $Y=e^{-T_2}, \ Z=e^{-T_3}$.}
\label{Tb_Probs}
\end{table}

\begin{multicols}{2}
%\end{multicols}
Then we multiply the matrix $M$ from Table \ref{table:pars15_15} by the vector $\mathbf p:=(p_1,p_2,\cdots ,p_{15})$, obtaining the vector $\mathbf s^{cat}$, where each entry is the expected parsimony score of a possible output tree for MRP (see (\ref{Tb_ParsVector})).
\end{multicols}%
\begin{equation} \label{Tb_ParsVector}
\mathbf s^{cat}:=M\mathbf p=\begin{pmatrix} 
3 - X/3 + (2 Y)/3 + (X Y)/3 - (X Y^3)/18 - 1/90 X Y^3 Z^6\\
4 - Y/3 - ( X Y^3)/18 - 1/90 X Y^3 Z^6\\
4 - Y/3 - (X Y^3)/18 -  1/90 X Y^3 Z^6\\
4 - Y/3 - (X Y^3)/18 - 1/90 X Y^3 Z^6\\
4 - Y/3 - ( X Y^3)/18 - 1/90 X Y^3 Z^6\\
3 - X/3 + (2 Y)/3 + (X Y)/3 - ( X Y^3)/18 - 1/90 X Y^3 Z^6\\
2 + (2 X)/3 + (2 Y)/3 + (X Y)/3 - ( X Y^3)/18 - 1/90 X Y^3 Z^6\\
4 - (X Y)/3 - (X Y^3)/18 - 1/90 X Y^3 Z^6\\
4 - (X Y)/3 - (X Y^3)/18 - 1/90 X Y^3 Z^6\\
3 + ( 2 X)/3 - Y/3 + (X Y)/6 + (X Y^3)/9 - 1/90 X Y^3 Z^6\\
4 - X/3 - ( X Y)/6 + (X Y^3)/9 - 1/90 X Y^3 Z^6\\
4 - X/3 - (X Y)/6 + (X Y^3)/9 - 1/90 X Y^3 Z^6\\ 
3 + (2 X)/3 - Y/3 + (X Y)/6 + (X Y^3)/18 + 2/45 X Y^3 Z^6\\
4 - X/3 - (X Y)/6 + (X Y^3)/18 + 2/45 X Y^3 Z^6\\
4 - X/3 - (X Y)/6 + (X Y^3)/18 + 2/45 X Y^3 Z^6
\end{pmatrix}.
\end{equation}
%\caption{The vector of expected parsimony scores for $\sigma_i$, where $i=\overline{1,15}$ with %a caterpillar species tree $\Sigma_1$ as input.}

%Table 4
\begin{multicols}{2}
We see that in $\mathbf s^{cat}$ some entries are equal. Let's denote: $\alpha^{cat}:= s^{cat}_1= s^{cat}_6$, \  $\epsilon^{cat}:=s^{cat}_{10}$,
$$\beta^{cat}:= s^{cat}_2=s^{cat}_3=s^{cat}_4= s^{cat}_5, \ \ \gamma^{cat}:=s^{cat}_7$$  $$\delta^{cat}:=s^{cat}_8=s^{cat}_9, \  \ \ \zeta^{cat}:=s^{cat}_{11}=s^{cat}_{12},$$ $\eta^{cat}:=s^{cat}_{13}$, \ and \ $\theta^{cat}:=s^{cat}_{14}=s^{cat}_{15}$.

\smallskip The analytical comparison of these values we form in the following 

\begin{prop}
	For any $X,Y,Z\in (0,1)$, the following inequalities hold:  
	$\gamma^{cat}<\zeta^{cat}, \ \ \ \eta^{cat}<\theta^{cat},$
$\gamma^{cat}<\alpha^{cat}<\beta^{cat}, \ \ \gamma^{cat}<\delta^{cat},\ \ \gamma^{cat}<\epsilon^{cat}$.  
\end{prop}
\begin{proof}
	Consider the difference 
	
	\centerline{$\alpha^{cat}-\gamma^{cat}=s^{cat}_1-s^{cat}_7=-X+1.$}
	
	 Since \ $X\in (0,1)$, \ $\gamma^{cat}<\alpha^{cat}$. \ Similarly,
	 $$\alpha^{cat}-\beta^{cat}=s^{cat}_1-s^{cat}_2=$$ $$=-1+(1/3)XY-(1/3)X+Y=$$ $$=(1/3)(Y-1)(X+3)<0$$ implies $\alpha^{cat}<\beta^{cat}$.
		Let's  look at \ 
		$$\gamma^{cat}-\delta^{cat}=s^{cat}_7-s^{cat}_8-=$$ $$ -2+(2/3)XY+(2/3)X+(2/3)Y.$$ Since $X,Y$ and $X,Y$ have upper limit 1, $\gamma^{cat}-\delta^{cat}<0$.
	
	Observe that $\gamma^{cat}-\epsilon^{cat}=s^{cat}_7-s^{cat}_{10}=$ $$=-1+(1/6)XY-(1/6)XY^3+Y=$$ $ =-(1/6)(Y-1)(XY^2+XY-6)<0.$
	
\smallskip 	Thus, $\gamma^{cat}<\epsilon^{cat}$.	Consider 
	$$
	\gamma^{cat}-\zeta^{cat}=s^{cat}_7-s^{cat}_{11}=$$ $$=-2+(1/2)XY-(1/6)XY^3+X+(2/3)Y
	$$$$
	= -2+(1/2)XY(1-(1/3)Y^2)+X+(2/3)Y$$ $$<-2+(1/2)XY(2/3)+X+(2/3)Y
	$$$$
	<-2+(2/6)+1+(2/3) =0. 
	$$
	Thus, $\gamma^{cat}<\zeta^{cat}$.
	Finally,
$\eta^{cat}-\theta^{cat}=$ $$=s^{cat}_{13}-s^{cat}_{14}=-1+(1/3)XY+X-(1/3)Y=$$$$=(1/3)(Y+3)(X-1)<0,$$ i.e. $\eta^{cat}<\theta^{cat}$.
\end{proof}

%\end{table} 	
%\newpage
%\onecolumn

%\begin{multicols}{2}
	However, the 3D-graphs on Figures \ref{3Dgraph_cat} show that the expressions $\eta^{cat}$ and $\gamma^{cat}$ can not be put in one order for all $X,Y,Z \in (0,1)$.
	
	 There is a large region were $\gamma^{cat}<\eta^{cat}$ but, nevertheless, there is also a region where $\eta^{cat}<\gamma^{cat}$. The last defines the parameters $T_1,T_2,T_3$ where MRP will fail to recover the tree topology of the true species tree producing the gene tree distribution,  even when given an arbitrary large sample of gene trees. Figure \ref{3Dgraph_cat}.left shows that provided $Y$ is not too large, regardless of $X,Z$, MRP will return the correct species tree. To determine this cutoff for $Y$, we set $\eta^{cat}(1,Y,0)=\gamma^{cat}(1,Y,0)$ and solve to get $Y=0.935...$ (the solutions of \ $(1/3)Y^3-(7/2)Y+3 = 0$ are $Y_{1,2,3}\approx 2.670...,-3.605...,  0.935...$).
\end{multicols}	

\def\bax{\hskip 0mm {{\vbox
			{\boxmaxdepth=0mm \hsize=100.0mm \tolerance=1600
			%\begin{figure}[h]
				\includegraphics*[width=75mm, height=75mm, keepaspectratio=false]{./GC_caterpillar.eps} }}}
		%\end{figure}
}
\medskip
\
\def\baxx{\hskip 10mm {{\vbox
			{\boxmaxdepth=0mm \hsize=90.0mm \tolerance=1600
				\includegraphics*[width=65mm, height=65mm, 
				keepaspectratio=false]{./Pcat_7_13B.eps}}}}
}				



\vskip4mm
\begin{figure}[h]
\hskip1mm $ \bax$\vskip-78mm\hskip70mm$ \baxx$

\vskip5mm
\caption{Left: the surface $\eta^{cat}(X,Y,Z)=\gamma^{cat}(X,Y,Z)$. $\eta^{cat}>\gamma^{cat}$ on the large region including all those points, when $Y$ is near 0, while $\eta^{cat}<\gamma^{cat}$ on the small region. Right: Different angle on the same surface $\eta^{cat}(X,Y,Z)=\gamma^{cat}(X,Y,Z)$. }
\label{3Dgraph_cat}
\end{figure}
%\vskip21mm



\begin{multicols}{2}
	\section{A{\sc N} E{\sc XPERIMENT} W{\sc ITH}  P{\sc SEUDO }-C{\sc ATERPILLAR}}
	
	Let's consider now the pseudo-caterpillar species tree $\Sigma_{2}=(((a,b)\text{:}T_1,(c,d)\text{:}T_2)\text{:}T_3,e)$. 
	Again we use COAL, the formulas for $g_{ij}$ and Maple 15 to calculate the probabilities $p^{pc}_i=p(\tau_i| \Sigma_2)$ for $i=\overline{1,15}$. Their list is shown in Table \ref{Tb_Probs_2} after simplifications.
	

	\end{multicols}
	
	
	\begin{table}[tbh]
		\begin{align*}
		p^{pc}_1&=	p^{pc}_3=p^{pc}_5=p^{pc}_6=p^{pc}_8=p^{pc}_9=	p^{pc}_{11}=p^{pc}_{12}=(1/18)XY+(1/90)XYZ^6,\\
		p^{pc}_2&=	p^{pc}_4=p^{pc}_7=	p^{pc}_{10}=(1/90)XYZ^6+(1/3)Y-(5/18)XY, \\
		p^{pc}_{13}&=1-(2/45)XYZ^6+(4/9)XY-(2/3)X-(2/3)Y, \\
		p^{pc}_{14}&=	p^{pc}_{15}=-(2/45)XYZ^6+(1/9)XY.
		\end{align*}
		\caption{The probabilities $p^{pc}_i=p(\tau_i| \Sigma_2)$ for $i=\overline{1,15}$, where $X=e^{-T_1}$, \ $Y=e^{-T_2}, \ Z=e^{-T_3}$.}
		\label{Tb_Probs_2}
	\end{table} 

\vskip-90mm
		\begin{multicols}{2}
	Multiplying the matrix $M$  by the vector $\mathbf p^{pc}:=(p^{pc}_1,p^{pc}_2,\cdots ,p^{pc}_{15})$, gives the vector of expected parsimony scores of possible  output trees with a pseudo-caterpillar species tree as input (\ref{Tb_ParsVector2}).

\end{multicols}
%\onecolumn	
\begin{equation} 		\label{Tb_ParsVector2}
\mathbf s^{pc}:=M\mathbf p^{pc}=\begin{pmatrix} 
4-(1/90) X Y Z^6-(1/3) Y-(1/18) X Y \\
3-(1/90) X Y Z^6-(1/3) X+(2/3) Y+(5/18) X Y\\
4-(1/90) X Y Z^6-(1/3) Y-(1/18) X Y\\
3-(1/90) X Y Z^6-(1/3) X+(2/3) Y+(5/18) X Y\\
4-(1/90) X Y Z^6-(1/3) Y-(1/18) X Y\\
4-(1/90) X Y Z^6-(1/3) Y-(1/18) X Y\\
3-(1/90) X Y Z^6+(2/3) X-(1/3) Y+(5/18) X Y\\
4-(1/90) X Y Z^6-(1/3) X-(1/18) X Y\\
4-(1/90) X Y Z^6-(1/3) X-(1/18) X Y\\
3-(1/90) X Y Z^6+(2/3) X-(1/3) Y+(5/18) X Y\\
4-(1/90) X Y Z^6-(1/3) X-(1/18) X Y\\
4-(1/90) X Y Z^6-(1/3) X-(1/18) X Y\\
2+(2/45) X Y Z^6+(2/3) X+(2/3) Y+(2/9) X Y\\
4+(2/45) X Y Z^6-(4/9) X Y\\
4+(2/45) X Y Z^6-(4/9) X Y
\end{pmatrix}. 
%		\caption{The vector of expected parsimony scores for $\sigma_i$, where %$i=\overline{1,15}$ with a pseudo-caterpillar species tree $\Sigma_2$ as input.}
\end{equation}



%


\begin{multicols}{2}	

%\begin{multicols}{2}	
	
	Let's denote $\alpha^{pc}:=s^{pc}_1=s^{pc}_3=s^{pc}_5=s^{pc}_6$,\ $\beta^{pc}:=s^{pc}_2=s^{pc}_4$, \ $\gamma^{pc}:=s^{pc}_7=s^{pc}_{10}$, \ $\delta^{pc}:=s^{pc}_8=s^{pc}_9=s^{pc}_{11}=s^{pc}_{12}$,\ $\zeta^{pc}:=s^{pc}_{13}$, \ $\eta^{pc}:=s^{pc}_{14}=s^{pc}_{15}$.
	
	Let's compare these expressions.
	
	\begin{prop}
		For any $X,Y,Z\in (0,1)$, the following inequalities hold:  
		$$ \zeta^{pc}<\alpha^{pc}, \ \zeta^{pc}<\beta^{pc},\ \zeta^{pc}<\gamma^{pc},$$ $$ \ \zeta^{pc}<\delta^{pc}, \ \zeta^{pc}<\eta^{pc}.$$
	\end{prop}
	\begin{proof}
		
		Consider the difference $\alpha^{pc}-\zeta^{pc}=s^{pc}_1-s^{pc}_{13}=2-(1/18)XYZ^6-Y-(5/18)XY-(2/3)X$. It is easy to see that, since $X,Y,Z\in (0,1)$, \ $\alpha^{pc}-\zeta^{pc}>0$, i.e. $\alpha^{pc}>\zeta^{pc}$.
		
		Observe that 
		$$
		\beta^{pc}-\zeta^{pc}= s^{pc}_2-s^{pc}_{13}=$$ $$=1-(1/18)XYZ^6-X+(1/18)XY=
		$$
		$$
		1-X[(1/18)YZ^6+1-(1/18)Y]
		$$ 
		$$>1-(1/18)YZ^6-1+(1/18)Y=
		$$
		$$
		(1/18)Y[-Z^6+1]>0.
		$$
		Thus, $\beta^{pc}>\zeta^{pc}$.
				Similarly,
		$$
		\gamma^{pc}-\zeta^{pc}=s^{pc}_7-s^{pc}_{13}=
		$$
		$$
		1-(1/18)XYZ^6-Y+(1/18)XY$$ $$=1-Y[(1/18)XZ^6+1-(1/18)X]
		$$
		$$
		>-(1/18)XZ^6+(1/18)X$$ $$=(1/18)X[-Z^6+1]>0.
		$$
		Thus, $\gamma^{pc}>\zeta^{pc}$.
		Observe $\delta^{pc}-\zeta^{pc}=s^{pc}_8-s^{pc}_{13}=2-(1/18)XYZ^6-X-(5/18)XY-(2/3)Y>0$ and $\eta^{pc}-\zeta^{pc}=s^{pc}_{14}-s^{pc}_{13}=2-(2/3)XY-(2/3)X-(2/3)Y>0$, so $\delta^{pc}>\zeta^{pc}$ and  $\eta^{pc}>\zeta^{pc}$.
		
	\end{proof}
	


This implies that if the true species tree is 5-taxon pseudo-caterpillar, MRP, for a sufficiently large data set, will give with probability 1  the unrooted species tree topology for all $T_1,T_2,T_2\in (0,1)$.
	
	\section{A{\sc N} E{\sc XPERIMENT} W{\sc  ITH}
		P{\sc SUEDO}-B{\sc ALANCED}}
	
	The last tree we need to consider (since all other are just permutations of taxon names) is the pseudo-balanced species tree $\Sigma_{3}=(((a,b)\text{:}T_1,c)\text{:}T_2,(d,e)\text{:}T_3)$. 
	The same chain of actions give us the probabilities $p^{pb}_{ij}$ (Table \ref{Tb_Probs_3}).
		\end{multicols}
	\begin{table}[h]
		\begin{align*}
		p^{pb}_1&=p^{pb}_6=-(1/3)ZXY+(1/15)XY^3Z+(1/3)X,\\
		p^{pb}_2&=p^{pb}_3=p^{pb}_4=p^{pb}_5=(1/15)XY^3Z,\\
		p^{pb}_7&=1+(1/3)ZXY-(2/3)X+(1/15)XY^3Z-(2/3)ZY, \\
		p^{pb}_8&=p^{pb}_9=(1/15)XY^3Z,\\
		p^{pb}_{10}&=p^{pb}_{13}=(1/3)ZY-(1/6)ZXY-(1/10)XY^3Z, \\
		p^{pb}_{11}&=p^{pb}_{12}=p^{pb}_{14}=p^{pb}_{15}=(1/6)ZXY-(1/10)XY^3Z.
		\end{align*}
					\caption{The probabilities $p^{pb}_i=p(\tau_i| \sigma_{7})$ for $i=
				\overline{1,15}$, where $X=e^{-T_1}$,\ $Y=e^{-T_2}, \ Z=e^{-T_3}$.}
				\label{Tb_Probs_3}
	\end{table}
	
\begin{multicols}{2}	
	Again, multiplying the matrix $M$  by the vector $\mathbf p^{pb}:=(p^{pb}_1,p^{pb}_2,\cdots ,p^{pb}_{15})$, gives the vector of expected parsimony scores of possible output trees
	 (\ref{Tb_ParsVector3}) with a pseudo-balanced species tree $\Sigma_3$ as input.

\end{multicols}


	
	\begin{equation}
		\mathbf s^{pb}:=M\mathbf p^{pb}=\begin{pmatrix} 
		3+(1/3)ZXY-(1/3)X-(1/15)XY^3Z+(2/3)ZY\\
		4-(1/15)XY^3Z-(1/3)ZY\\ 
		4-(1/15)XY^3Z-(1/3)ZY \\
		4-(1/15)XY^3Z-(1/3)ZY \\
		4-(1/15)XY^3Z-(1/3)ZY \\
		3+(1/3)ZXY-(1/3)X-(1/15)XY^3Z+(2/3)ZY\\
		2+(1/3)ZXY+(2/3)X-(1/15)XY^3Z+(2/3)ZY \\
		4-(1/3)ZXY-(1/15)XY^3Z \\
		4-(1/3)ZXY-(1/15)XY^3Z \\
		3+(1/6)ZXY+(2/3)X+(1/10)XY^3Z-(1/3)ZY\\
		4-(1/6)ZXY-(1/3)X+(1/10)XY^3Z \\
		4-(1/6)ZXY-(1/3)X+(1/10)XY^3Z \\
		3+(1/6)ZXY+(2/3)X+(1/10)XY^3Z-(1/3)ZY \\
		4-(1/6)ZXY-(1/3)X+(1/10)XY^3Z \\
		4-(1/6)ZXY-(1/3)X+(1/10)XY^3Z
		\end{pmatrix}. 		\label{Tb_ParsVector3}
	%	\caption{The vector of expected parsimony scores for $\sigma_i$, where %$i=\overline{1,15}$ with a pseudo-balanced species tree $\Sigma_3$ as input.}
	\end{equation}
	
\begin{multicols}{2}	
	
	Let's denote $\alpha^{pb}:=s^{pb}_1=s^{pb}_6$, \ \ $\beta^{pb}:=s^{pb}_2=s^{pb}_3=s^{pb}_4=s^{pb}_5$, \ \ $\gamma^{pb}:=s^{pb}_7$, \ \ $\delta^{pb}:=s^{pb}_8=s^{pb}_9$,\ \ $\zeta^{pb}:=s^{pb}_{10}=s^{pb}_{13}$ \ and \ $\eta^{pb}:=s^{pb}_{11}=s^{pb}_{12}=s^{pb}_{14}=s^{pb}_{15}$.
	
	
	\begin{prop}
		For any $X,Y,Z\in (0,1)$, the following inequalities hold:  
		$ \alpha^{pb}>\gamma^{pb}, \ \beta^{pb}>\gamma^{pb}, \ \delta^{pb}>\gamma^{pb}, \ \zeta^{pb}>\gamma^{pb}, \ \eta^{pb}>\gamma^{pb}.$
	\end{prop}
	\begin{proof}
		
		Since $X\in (0,1)$, we immediately have that the difference $\alpha^{pb}-\gamma^{pb}=s^{pb}_1-s^{pb}_7=1-X>0$. So, $\alpha^{pb}>\gamma^{pb}$. Also $\beta^{pb}-\gamma^{pb}=s^{pb}_2-s^{pb}_7=2-ZY-(1/3)ZXY-(2/3)X>0$ and $\delta^{pb}-\gamma^{pb}=s^{pb}_8-s^{pb}_7=2-(2/3)ZXY-(2/3)X-(2/3)ZY>0$.
		Thus, $\beta^{pb}>\gamma^{pb}$ and $\delta^{pb}>\gamma^{pb}$.
		
		Consider 
		$$
		\zeta^{pb}-\gamma^{pb}=s^{pb}_{10}-s^{pb}_7=
		$$
		$$
		1-ZY(1+(1/6)X(1-Y^2))>$$ $$>1-Y(1+(1/6)X(1-Y^2))>
		$$
		$$
		1-Y(1+(1/6)(1-Y^2))=$$ $$=1-(7/6)Y+(1/6)Y^3=:h
		$$
		
		Since $h'=-(7/6)+(1/2)Y^2<0$ and $h(0)<0$, \ $h>0$ for all $Y\in (0,1)$. Thus, $\zeta^{pb}>\gamma^{pb}$.
		
		Finally, observe that
		$$\eta^{pb}-\gamma^{pb}=s^{pb}_{11}-s^{pb}_7=
		$$
		$$
		(2-x)-ZY((1/2)X-(1/6)XY^2+(2/3))$$ $$> 1-ZY((2/3)+X((1/2)-(1/6)Y^2))>
		$$
		$$
		1-Y((2/3)+X((1/2)-(1/6)Y^2))$$ $$>1-Y((2/3)+(1/2)-(1/6)Y^2)=
		$$$$
		1-(7/6)Y+(1/6)Y^3=h>0.
		$$
		So, $\eta^{pb}>\gamma^{pb}$.
	\end{proof}
	
	So, if the true species tree is 5-taxon pseudo-balanced $\Sigma_3$, MRP,  for a sufficiently large data set, will give with probability 1 the correct unrooted species tree topology for all $T_1,T_2,T_2\in (0,1)$.
	
	
	
	
	
	
	\section{Generalization of results.}
	
	\subsection{Caterpillar Subtree.}
	
	\begin{defn}
		There is a rooted tree $T$ with number of taxa equal to $|T|=:n$. Let $T_{cat}(T)$ be a caterpillar subtree of this tree. The number $\displaystyle Cat(T):= \max_{T_{cat}(T)\subset T}|T_{cat}(T)|$ for a particular tree $T$ is called {\it caterpillar score for the tree $T$}. 
		The number $\displaystyle cat(n):=\min_{|T|=n}\ Cat(T)$ is called {\it caterpillar measure}. 
	\end{defn}
	
	It is clear that $cat(n)$ is an increasing function with respect to $n$. 
	There are may be a few consecutive numbers $n$ such that $cat(n)=k$ for some given natural $k$.
	
	\begin{defn}
		Let's call number $\displaystyle r_k:=\min_{cat(n)=k} n$ the {\it revolution number}.
	\end{defn}
	
	Observe that for the caterpillar lengths $1,2,3$ their revolution numbers are $r_1=1,r_2= 2,r_3= 3$, because these trees are caterpillar themselves.
	
	Note, that the third and the second revolution numbers are connected by
	\begin{equation}
	r_3=2r_2-1.
	\label{eq1}
	\end{equation}
	
	
	\begin{prop}
		\label{prop1}
		For the caterpillar length $k> 3$ the revolution numbers $r_k$ may be calculated recursively $r_{k}=2r_{k-1}-1$.
	\end{prop}
	\begin{proof}
		
		Let $T$ be a $k$-taxon tree. Since $T$ is a binary tree, we can  think of $T$ as two subtrees $T',T''$ glued together only by two edges at the root (see Figure \ref{Tree1}). Observe that for any caterpillar subtree of $T'$ one of these $T',T''$ being transformed properly brings only one edge to the caterpillar.
		%So, if $n=2m$, where $m\in \mathbb{N}$, then the caterpillar %score of $T$ is not greater than 


	
		On the other hand, \ $r_k$ is an increasing function. So, the first bifurcation in the root will be the worst in the sense of caterpillar score for the tree $T$ when this bifurcation divides the tree into two subtrees $T'$ and $T''$ such that $|T'|=|T''|$ for even $|T|$, and $\bigl||T'|-|T''|\bigr|=1$ for odd $|T|$.
		
		Further, we use mathematical induction.
		
		{\bf The base of induction. } It is the formula (\ref{eq1})
		
		%Since $r_2=2$ and $r_3=3$, we have $r_3=2r_2-1$. So the %formula holds for $k=2$.
		
		{\bf The assumption of induction.}
		
		Let $r_3,...,r_k$ calculated recursively be revolution numbers.
		
		
		{\bf The inductive step.}
		
		We need to prove that $r_{k+1}=2r_k-1$ is the revolution number. Let us take a tree $T$ with $r_{k+1}$ taxa and consider the worst bifurcation in its root.
		
		As mentioned above, the worst bifurcation in the root of $T$ forms two subtrees $T'$ and $T''$ such that $|T'|=r_k-1,\ |T''|=r_k$. The induction assumption yields an existence of caterpillar in $T''$ with a length no less than $k$. One edge in $T'$ together with the caterpillar in $T''$ creates the caterpillar tree $C$ with $|C|=k+1$.
		So, the revolution number for $k+1$ is no greater than $2r_k-1$.
		
		% Since $k$ is the r-number, any tree presenting the second part of the tree $T''$ with the number of taxa $s< k$ will have a caterpillar score less than $T'$ and so will be transformed to an edge of the $c+1$-taxon caterpillar subtree of $T''$, which has at least $k$ taxa. Thus, for the caterpillar score $c+1$, the r-number is $2k-1$.
		
		If $|T|\in [r_k,2r_k-1)$, then  the worst bifurcation forms two subtrees $T'$ and $T''$ such that $|T'|,|T''|<r_k$. Since $r_k$ is a revolution number, there are $T'$ and $T''$ which have only caterpillars $C',C''$ and $C''$ with $|C'|,|C''|<r_k$. Therefore, $r_{k+1}$ is the revolution number.
		
	\end{proof}
\end{multicols}
%\onecolumn		
\begin{figure}[h]
\centering
\includegraphics[height=55mm]{./f1generalCat.eps}
\caption{}
\label{Tree1}
\end{figure}
\begin{multicols}{2}	
	Proposition \ref{prop1} allows to continue the sequence of the revolution numbers  for the caterpillar measures $3,4,5,6,7,...$ as $r_k=3, 5, 9, 17,33,...$, respectively. For trees with number of taxa in $[r_k,2r_k-1]$, the caterpillar measure is $k$.
	
	
	\subsection{Trees with the number of taxa greater than 5.}
	
	\begin{prop}
		\label{propSubTree}
		If a true species rooted tree $\hat G$ contains 5-taxon caterpillar subtree, then MRP may fail to obtain the unrooted version of $\hat G$ from the set of gene trees generated by Coalescent model from $\hat G$.
	\end{prop}
	\begin{proof}
		
		For the number of species greater than 5 and the same number of genes one can make the following construction.
		

		Take a caterpillar tree $\Gamma$ of 5 species $a$, $b$, $c$, $d$, $e$ with $T_1$, $T_2$, $T_3$ and root $\rho$, such that parsimony fails (fig. \ref{3Dgraph_cat}). Take an arbitrary tree $G$, where every edge is very close to 0 ($T_i\approx 0$, \ $i>4$). Connect $\Gamma$ to $G$ through its root $\rho$ and the edge $\epsilon$ with the length $T_4$. Make $T_4$ big enough so the genes  $A$, $B$, $C$, $D$, $E$ coalesce in $\epsilon$ if they didn't in $\Gamma$. No matter what is on the upper end of $\epsilon$, root of entire tree or inner node created by $\epsilon$ on some edge of $G$ .
		
		
		The numeration of $n$ possible gene trees we do in the following way: First 15 trees will have the same subtree $G$ and different topology or permutation of $A$, $B$, $C$, $D$, $E$. Other $n-16$ trees can be numerated in any order, and we set their probabilities $p_{16},..., p_{n}$ equal to zero, since $T_i$, \ $i\in \{5,..., n\}$, can be taken infinitively small. 
		
		Therefore, the set of gene trees is numerated and the probabilities of them	are presented by vector-column $p=(p_1,...,p_{15},p_{16},...,p_{n})^T$, where all the entries below 15-th equal zero and the first 15 are the same that obtained ones for 5-taxon experiment.
		
		The matrix $M_{n\times n}$ has dimension $n\times n$, but only submatrix  $M_{n\times 15}$ does participate in calculation of expectations of gene mutations due to	
		$p_{16},...,p_{n}=0$. 
		
		Moreover, the parsimony incorrect choice may be shown on submatrix $M_{15\times 15}$ in upper corner. Observe that the elements of $M_{15\times 15}$ are the sums of the elements of $M$ obtained earlier in performance of MRP for 5-taxon trees \ref{table:pars15_15} and some constant number generated by the constant subtree $G$ with coalesced gene $A+B+C+D+E$.
		This means that each of $s^{cat}_1$, $s^{cat}_2$, ... , $s^{cat}_{15}$ from Table \ref{Tb_ParsVector} must be increased by the constant value \ \ $V \sum_1^{15} p_{i}$, \ to be a new mathematical expectation for the new big tree. So, the minimum among the first 15 rows must be achieved in the same index.
		
		Therefore, being wrong for 5-taxon caterpillar species tree the parsimony becomes wrong for the constructed tree $\hat G$ as well.
		
	\end{proof}
	
	\begin{cor}
		If one applies MRP on a set of gene trees with 5 taxa or more, the result may be wrong. If one applies MRP on set of gene trees with 9 taxa or more, MRP may fail even more probably, since 9-taxon species tree always has a caterpillar subtree.
	\end{cor}
	
	%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	
	
	\section{C{\sc ONCLUSIONS}}
	
	The fact that Parsimony may fail is not new. However, here we proved that no mater of what topology the true 9-taxon and greater species tree is the only thing you need to fail Parsimony is to have in this tree three consecutive edges with lengths $T1,T2,T3$ of some proportions. Obviously, the probability to meet these lengths is growing in general with the size of species tree. 
	Therefore, Parsimony can be applied only when one knows for sure that the described lengths cannot be met in the tree.
	
	%\bibliography{Liter}
	\begin{thebibliography}{Wak08}
		
		\bibitem[AR09]{Allman}
		E.~S. Allman and J.~A. Rhodes.
		\newblock {\em Lecture Notes: The Mathematics of Phylogenetics}.
		\newblock University of Alaska Fairbanks, 2009.
		
		\bibitem[Bau92]{Baum}
		B.~R. Baum.
		\newblock Combining trees as a way of combining data sets for phylogenetic
		inference, and the desirability of combining gene trees.
		\newblock {\em Taxon}, 41:3 -- 10, 1992.
		
		\bibitem[DS05]{Degnan}
		J.~H. Degnan and L.~A. Salter.
		\newblock Gene tree distributions under the coalescent process.
		\newblock {\em Evolution}, 59(1):24 -- 37, 2005.
		
		\bibitem[Har73]{Hartigan}
		J.~A. Hartigan.
		\newblock Minimum mutation fits to a given tree.
		\newblock {\em Biometrics}, 29:53 -- 65, 1973.
		
		\bibitem[Kin82]{Kingman}
		J.~F.~C. Kingman.
		\newblock The coalescent.
		\newblock {\em Stoch. Process. Appl.}, 13:235 -- 248, 1982.
		
		\bibitem[Ros02]{Rosenberg}
		N.~A. Rosenberg.
		\newblock The probability of topological concordance of gene trees and species
		trees.
		\newblock {\em Theor. Pop. Biol.}, 61:225 -- 247, 2002.
		
		\bibitem[SS03]{SempleSteel}
		Charles Semple and Mike Steel.
		\newblock {\em Phylogenetics}, volume~24 of {\em Oxford Lecture Series in
			Mathematics and its Applications}.
		\newblock Oxford University Press, Oxford, 2003.
		
		\bibitem[Tav84]{Tavare}
		Simon Tavar{\'e}.
		\newblock Line-of-descent and genealogical processes, and their applications in
		population genetics models.
		\newblock {\em Theoret. Population Biol.}, 26(2):119--164, 1984.
		
		\bibitem[Wak08]{Wakeley}
		J.~Wakeley.
		\newblock {\em Coalescent Theory}.
		\newblock Roberts \& Company, Greenwood Village, CO, 2008.
		
		\bibitem[WD11]{WangDegnan}
		Yuancheng Wang and James~H. Degnan.
		\newblock Performance of matrix representation with parsimony for inferring
		species from gene trees.
		\newblock {\em Stat. Appl. Genet. Mol. Biol.}, 10:Art. 21, 41, 2011.
		
	\end{thebibliography}
	
	
	\bibliographystyle{alpha}
	
\end{multicols}
%----------------------------------------------------------------------------------------
%	ARTICLE CONTENTS
%----------------------------------------------------------------------------------------



%----------------------------------------------------------------------------------------
%	REFERENCE LIST
%----------------------------------------------------------------------------------------


%----------------------------------------------------------------------------------------

\end{document}

1703.05810.extracted_bib
[AR09]{Allman E.~S. Allman and J.~A. Rhodes. \newblock {\em Lecture Notes: The Mathematics of Phylogenetics. \newblock University of Alaska Fairbanks, 2009.
1703.05810.extracted_bib
[Bau92]{Baum B.~R. Baum. \newblock Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining gene trees. \newblock {\em Taxon, 41:3 -- 10, 1992.
1703.05810.extracted_bib
[DS05]{Degnan J.~H. Degnan and L.~A. Salter. \newblock Gene tree distributions under the coalescent process. \newblock {\em Evolution, 59(1):24 -- 37, 2005.
1703.05810.extracted_bib
[Har73]{Hartigan J.~A. Hartigan. \newblock Minimum mutation fits to a given tree. \newblock {\em Biometrics, 29:53 -- 65, 1973.
1703.05810.extracted_bib
[Kin82]{Kingman J.~F.~C. Kingman. \newblock The coalescent. \newblock {\em Stoch. Process. Appl., 13:235 -- 248, 1982.
1703.05810.extracted_bib
[Ros02]{Rosenberg N.~A. Rosenberg. \newblock The probability of topological concordance of gene trees and species trees. \newblock {\em Theor. Pop. Biol., 61:225 -- 247, 2002.
1703.05810.extracted_bib
[SS03]{SempleSteel Charles Semple and Mike Steel. \newblock {\em Phylogenetics, volume~24 of {\em Oxford Lecture Series in Mathematics and its Applications. \newblock Oxford University Press, Oxford, 2003.
1703.05810.extracted_bib
[Tav84]{Tavare Simon Tavar{\'e. \newblock Line-of-descent and genealogical processes, and their applications in population genetics models. \newblock {\em Theoret. Population Biol., 26(2):119--164, 1984.
1703.05810.extracted_bib
[Wak08]{Wakeley J.~Wakeley. \newblock {\em Coalescent Theory. \newblock Roberts \& Company, Greenwood Village, CO, 2008.
1703.05810.extracted_bib
[WD11]{WangDegnan Yuancheng Wang and James~H. Degnan. \newblock Performance of matrix representation with parsimony for inferring species from gene trees. \newblock {\em Stat. Appl. Genet. Mol. Biol., 10:Art. 21, 41, 2011.