African origin of modern humans in East Asia: A tale of 12,000 Y chromosomes

To test the hypotheses of modern human origin in East Asia, we sampled 12,127 male individuals from 163 populations and typed for three Y chromosome biallelic markers (YAP, M89, and M130). All the individuals carried a mutation at one of the three sites.

Global distribution of Y-chromosome haplogroup C reveals the prehistoric migration routes of African exodus and early settlement in East Asia

The regional distribution of an ancient Y-chromosome haplogroup C-M130 (Hg C) in Asia provides an ideal tool of dissecting prehistoric migration events. We identified 465 Hg C individuals out of 4284 males from 140 East and Southeast Asian populations. We genotyped these Hg C individuals using 12 Y-chromosome biallelic markers and 8 commonly used Y-short tandem repeats (Y-STRs), and performed phylogeographic analysis in combination with the published data. The results show that most of the Hg C subhaplogroups have distinct geographical distribution and have undergone long-time isolation, although Hg C individuals are distributed widely across Eurasia. Furthermore, a general south-to-north and east-to-west cline of Y-STR diversity is observed with the highest diversity in Southeast Asia. The phylogeographic distribution pattern of Hg C supports a single coastal 'Out-of-Africa' route by way of the Indian subcontinent, which eventually led to the early settlement of modern humans in mainland Southeast Asia. The northward expansion of Hg C in East Asia started similar to 40 thousand of years ago (KYA) along the coastline of mainland China and reached Siberia similar to 15 KYA and finally made its way to the Americas. Journal of Human Genetics (2010) 55, 428-435; doi:10.1038/jhg.2010.40; published online 7 May 2010

On equations for regular languages, finite automata, and sequential networks

We consider systems of equations of the form where A is the underlying alphabet, the Xi are variables, the Pi,a are boolean functions in the variables Xi, and each δi is either the empty word or the empty set. The symbols υ and denote concatenation and union of languages over A. We show that any such system has a unique solution which, moreover, is regular. These equations correspond to a type of automation, called boolean automation, which is a generalization of a nondeterministic automation. The equations are then used to determine the language accepted by a sequential network; they are obtainable directly from the network.

practical type checking of functions defined on context-free languages

A type checking method for the functional language LFC is presented. A distinct feature of LFC is that it uses Context-Free (CF) languages as data types to represent compound data structures. This makes LFC a dynamically typed language. To improve efficiency, a practical type checking method is presented, which consists of both static and dynamic type checking. Although the inclusion relation of CF.languages is not decidable,a special subset of the relation is decidable, i.e., the sentential form relation, which can be statically checked.Moreover, most of the expressions in actual LFC programs appear to satisfy this relation according to the statistic data of experiments. So, despite that the static type checking is not complete, it undertakes most of the type checking task. Consequently the run-time efficiency is effectively improved. Another feature of the type checking is that it converts the expressions with implicit structures to structured representation. Structure reconstruction technique is presented.

pattern matching compilation of functions defined in context-free languages

LFC is a functional language based on recursive functions defined in context-free languages. In this paper, a new pattern matching algorithm for LFC is presented, which can represent a sequence of patterns as an integer by an encoding method. It is a rather simple method and produces efficient case-expressions for pattern matching definitions of LFC. The algorithm can also be used for other functional languages, but for nested patterns it may become complicated and further studies are needed.

facilitating formal specification acquisition by using recursive functions on context-free languages

Although formal specification techniques are very useful in software development, the acquisition of formal specifications is a difficult task. This paper presents the formal specification language LFC, which is designed to facilitate the acquisition and validation of formal specifications. LFC uses context-free languages for syntactic aspect and relies on a new kind of recursive functions, i.e. recursive functions on context-free languages, for semantic aspect of specifications. Construction and validation of LFC specifications are machine-aided. The basic ideas behind LFC, the main aspects of LFC, and the use of LFC and illustrative examples are described.

on string languages generated by spiking neural p systems

We continue the study of spiking neural P systems by considering these computing devices as binary string generators: the set of spike trains of halting computations of a given system constitutes the language generated by that system. Although the "direct" generative capacity of spiking neural P systems is rather restricted (some very simple languages cannot be generated in this framework), regular languages are inverse-morphic images of languages of finite spiking neural P systems, and recursively enumerable languages are projections of inverse-morphic images of languages generated by spiking neural P systems.