On the minimum number of topologies explaining a sample of DNA sequences

Carsten Wiuf

doi:10.1016/S0040-5809(02)00004-7

On the minimum number of topologies explaining a sample of DNA sequences

Carsten Wiuf^*

^*Corresponding author for this work

7 Citations (Scopus)

Abstract

In this article I derive an alternative algorithm to Hudson and Kaplan's (Genetics 111, 147-165) algorithm that gives a lower bound to the number of recombination events in a sample's history. It is shown that the number, T _M, found by the algorithm is the least number of topologies required to explain a set of DNA sequences sampled under the infinite-site assumption. Let T=(T₁,⋯,T_r) be a list of topologies compatible with the sequences, i.e., T_k is compatible with an interval, I _k, of sites in the alignment. A characterization of all lists having T_M topologies is given and it is shown that T_M relates to specific patterns in the alignment, here called chain series. Further, a number of theorems relating general lists of topologies to the number T_M is presented. The results are discussed in relation to the true minimum number of recombination events required to explain an alignment.

Original language	English
Journal	Theoretical Population Biology
Volume	62
Issue number	4
Pages (from-to)	357-363
Number of pages	7
ISSN	0040-5809
DOIs	https://doi.org/10.1016/S0040-5809(02)00004-7
Publication status	Published - 1 Dec 2002
Externally published	Yes

Keywords

Algorithm
Recombination
SNP
Topology

Access to Document

10.1016/S0040-5809(02)00004-7

Cite this

@article{f179ed0706df4d40a02eb655b37288b1,

title = "On the minimum number of topologies explaining a sample of DNA sequences",

abstract = "In this article I derive an alternative algorithm to Hudson and Kaplan's (Genetics 111, 147-165) algorithm that gives a lower bound to the number of recombination events in a sample's history. It is shown that the number, T M, found by the algorithm is the least number of topologies required to explain a set of DNA sequences sampled under the infinite-site assumption. Let T=(T1,⋯,Tr) be a list of topologies compatible with the sequences, i.e., Tk is compatible with an interval, I k, of sites in the alignment. A characterization of all lists having TM topologies is given and it is shown that TM relates to specific patterns in the alignment, here called chain series. Further, a number of theorems relating general lists of topologies to the number TM is presented. The results are discussed in relation to the true minimum number of recombination events required to explain an alignment.",

keywords = "Algorithm, Recombination, SNP, Topology",

author = "Carsten Wiuf",

year = "2002",

month = dec,

day = "1",

doi = "10.1016/S0040-5809(02)00004-7",

language = "English",

volume = "62",

pages = "357--363",

journal = "Theoretical Population Biology",

issn = "0040-5809",

publisher = "Academic Press",

number = "4",

}

TY - JOUR

T1 - On the minimum number of topologies explaining a sample of DNA sequences

AU - Wiuf, Carsten

PY - 2002/12/1

Y1 - 2002/12/1

N2 - In this article I derive an alternative algorithm to Hudson and Kaplan's (Genetics 111, 147-165) algorithm that gives a lower bound to the number of recombination events in a sample's history. It is shown that the number, T M, found by the algorithm is the least number of topologies required to explain a set of DNA sequences sampled under the infinite-site assumption. Let T=(T1,⋯,Tr) be a list of topologies compatible with the sequences, i.e., Tk is compatible with an interval, I k, of sites in the alignment. A characterization of all lists having TM topologies is given and it is shown that TM relates to specific patterns in the alignment, here called chain series. Further, a number of theorems relating general lists of topologies to the number TM is presented. The results are discussed in relation to the true minimum number of recombination events required to explain an alignment.

AB - In this article I derive an alternative algorithm to Hudson and Kaplan's (Genetics 111, 147-165) algorithm that gives a lower bound to the number of recombination events in a sample's history. It is shown that the number, T M, found by the algorithm is the least number of topologies required to explain a set of DNA sequences sampled under the infinite-site assumption. Let T=(T1,⋯,Tr) be a list of topologies compatible with the sequences, i.e., Tk is compatible with an interval, I k, of sites in the alignment. A characterization of all lists having TM topologies is given and it is shown that TM relates to specific patterns in the alignment, here called chain series. Further, a number of theorems relating general lists of topologies to the number TM is presented. The results are discussed in relation to the true minimum number of recombination events required to explain an alignment.

KW - Algorithm

KW - Recombination

KW - SNP

KW - Topology

UR - http://www.scopus.com/inward/record.url?scp=0036885956&partnerID=8YFLogxK

U2 - 10.1016/S0040-5809(02)00004-7

DO - 10.1016/S0040-5809(02)00004-7

M3 - Journal article

C2 - 12427459

AN - SCOPUS:0036885956

SN - 0040-5809

VL - 62

SP - 357

EP - 363

JO - Theoretical Population Biology

JF - Theoretical Population Biology

IS - 4

ER -

On the minimum number of topologies explaining a sample of DNA sequences

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this