Identifying Linkage Groups by Nonlinearity/Non-monotonicity Detection
Masaharu Munetomo · 1999
This paper presents and discusses direct linkage identification procedures based on nonlinearity/non-monotonicity detection. The algorithm we propose checks arbitrary nonlinearity/non-monotonicity of fitness change by perturbations in a pair of loci to detect their linkage. We first discuss condition of the linkage identification by nonlinearity check (LINC) procedure (Munetomo & Goldberg, 1998) and its allowable nonlinearity. Then we propose another condition of the linkage identification by nonmonotonicity detection (LIMD) and prove its equality to the LINC with allowable nonlinearity (LINC-AN). The procedures can identify linkage groups for problems with at most order-k difficulty by checking O(2 k ) strings and the computational cost for each string is O(l 2 ) where l is the string length. 1 Introduction The definition of linkage in genetics is `the tendency for alleles of different genes to be passed together from one generation to the next' (Winter, Hickey...