Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js
Research article Special Issues

Survey of Metaheuristics and Statistical Methods for Multifactorial Diseases Analyses

  • The identification of the interactions of polymorphisms with other genetic or environmental factors for the detection of multifactorial diseases has now become both a challenge and an objective for geneticists. Unlike monogenic Mendelian diseases, the classical methods have not become too efficient for the identification of these interactions, especially with the exponential increase in the number of genetic interactions as well as the number of combinations of genotypes. Several methods have been proposed for the detection of susceptibility variants such as metaheuristics and statistical methods. Using metaheuristics, we focus on the feature selection of variables, and more precisely on the determination of the genes that increase the susceptibility to the disease, especially as these methods are more suitable for the description of complex data. Statistical methods are divided into two submethods including linkage studies and association studies. Generally these two methods are used one after the other since they are complementary. The linkage study is used initially because its objective is the localization of the chromosomal regions containing the gene(s) involved in the disease. Then, in a second step, the association study is set up to specify precisely the location of the gene. In this paper, we will present a survey of metaheuristics and statistical methods integrated in the field of human genetics and specifically multifactorial diseases in order to help genetics to find interaction between genes and environemental factor involved in those diseases.

    Citation: Hend Amraoui, Faouzi Mhamdi, Mourad Elloumi. Survey of Metaheuristics and Statistical Methods for Multifactorial Diseases Analyses[J]. AIMS Medical Science, 2017, 4(3): 291-331. doi: 10.3934/medsci.2017.3.291

    Related Papers:

    [1] M. M. Bhatti, Efstathios E. Michaelides . Oldroyd 6-constant Electro-magneto-hydrodynamic fluid flow through parallel micro-plates with heat transfer using Darcy-Brinkman-Forchheimer model: A parametric investigation. Mathematics in Engineering, 2023, 5(3): 1-19. doi: 10.3934/mine.2023051
    [2] Delyan Zhelyazov . Numerical spectral analysis of standing waves in quantum hydrodynamics with viscosity. Mathematics in Engineering, 2024, 6(3): 407-424. doi: 10.3934/mine.2024017
    [3] Roberto Feola, Felice Iandoli, Federico Murgante . Long-time stability of the quantum hydrodynamic system on irrational tori. Mathematics in Engineering, 2022, 4(3): 1-24. doi: 10.3934/mine.2022023
    [4] Hao Zheng . The Pauli problem and wave function lifting: reconstruction of quantum states from physical observables. Mathematics in Engineering, 2024, 6(4): 648-675. doi: 10.3934/mine.2024025
    [5] G. Gaeta, G. Pucacco . Near-resonances and detuning in classical and quantum mechanics. Mathematics in Engineering, 2023, 5(1): 1-44. doi: 10.3934/mine.2023005
    [6] Giuseppe Procopio, Massimiliano Giona . Bitensorial formulation of the singularity method for Stokes flows. Mathematics in Engineering, 2023, 5(2): 1-34. doi: 10.3934/mine.2023046
    [7] Gauthier Delvoye, Olivier Goubet, Frédéric Paccaut . Comparison principles and applications to mathematical modelling of vegetal meta-communities. Mathematics in Engineering, 2022, 4(5): 1-17. doi: 10.3934/mine.2022035
    [8] Federico Bernini, Simone Secchi . Existence of solutions for a perturbed problem with logarithmic potential in R2. Mathematics in Engineering, 2020, 2(3): 438-458. doi: 10.3934/mine.2020020
    [9] Greta Chiaravalli, Guglielmo Lanzani, Riccardo Sacco, Sandro Salsa . Nanoparticle-based organic polymer retinal prostheses: modeling, solution map and simulation. Mathematics in Engineering, 2023, 5(4): 1-44. doi: 10.3934/mine.2023075
    [10] Emilia Blåsten, Fedi Zouari, Moez Louati, Mohamed S. Ghidaoui . Blockage detection in networks: The area reconstruction method. Mathematics in Engineering, 2019, 1(4): 849-880. doi: 10.3934/mine.2019.4.849
  • The identification of the interactions of polymorphisms with other genetic or environmental factors for the detection of multifactorial diseases has now become both a challenge and an objective for geneticists. Unlike monogenic Mendelian diseases, the classical methods have not become too efficient for the identification of these interactions, especially with the exponential increase in the number of genetic interactions as well as the number of combinations of genotypes. Several methods have been proposed for the detection of susceptibility variants such as metaheuristics and statistical methods. Using metaheuristics, we focus on the feature selection of variables, and more precisely on the determination of the genes that increase the susceptibility to the disease, especially as these methods are more suitable for the description of complex data. Statistical methods are divided into two submethods including linkage studies and association studies. Generally these two methods are used one after the other since they are complementary. The linkage study is used initially because its objective is the localization of the chromosomal regions containing the gene(s) involved in the disease. Then, in a second step, the association study is set up to specify precisely the location of the gene. In this paper, we will present a survey of metaheuristics and statistical methods integrated in the field of human genetics and specifically multifactorial diseases in order to help genetics to find interaction between genes and environemental factor involved in those diseases.


    The Euler numbers En are defined by the exponential generating function

    1+n1Enxnn!=tanx+secx.

    This is the sequence A000111 in [20]. In 1877 Seidel [19] defined the triangular array (En,k) by the recurrence

    En,k=En,k1+En1,n+1k(nk2) (1)

    with E1,1=1, En,1=0 (n2), and proved that En=kEn,k, i.e., the Euler number En is the sum of the entries of the n-th row of the following triangle:

    E1,1E2,1E2,2E3,3E3,2E3,1E4,1E4,2E4,3E4,4=1011100122 (2)

    The first few values of En,k are given in Table 1.

    Table 1.  The Entringer numbers En,k for 1kn7 and Euler numbers En=nk=1En,k.
    nk 1 2 3 4 5 6 7 En
    1 1 1
    2 0 1 1
    3 0 1 1 2
    4 0 1 2 2 5
    5 0 2 4 5 5 16
    6 0 5 10 14 16 16 61
    7 0 16 32 46 56 61 61 271

     | Show Table
    DownLoad: CSV

    André [1] showed in 1879 that the Euler number En enumerates the alternating permutations of [n]:={1,2,,n}, i.e., the permutations σ1σ2σn of 12n such that σ1>σ2<σ3>σ4<. Let DUn be the set of (down-up) alternating permutations of [n]. For example,

    DU4={2143,3142,3241,4132,4231}.

    In 1933 Kempener [14] used the boustrophedon algorithm (2) to enumerate alternating permutations without refering to Euler numbers. Since Entringer [7] first found the combinatorial interpretation of Kempener's table (En,k) in terms of André's model for Euler numbers, the numbers En,k are then called Entringer numbers.

    Theorem 1 (Entringer). The number of the (down-up) alternating permutations of [n] with first entry k is En,k, i.e., En,k=#DUn,k, where

    DUn,k:={σDUn:σ1=k}.

    According to Foata-Schützenberger [9] a sequence of sets (Xn) is called an André complex if the cardinality of Xn is equal to En for n1. Several other André complexs were introduced also in [9] such as André permutations of first and second kinds, André trees or increasing 1-2 trees and Rodica Simion and Sheila Sundaram [23] discovered the Simsun permutations; see Section 2. A sequence of sets (Xn,k) is called an Entringer family if the cardinality of Xn,k is equal to En,k for 1kn. During the last two decades of the twentieth century, Poupard worked out several Entringer families in a series of papers [15,16,17]. Stanley [22,Conjecture 3.1] and Hetyei [12] introduced more Entringer families by refining of Purtill's result [18,Theorem 6.1] about the cd-index of André and Simsun permutations with fixed last letter.

    The Springer numbers Sn are defined by the exponential generating function [21]

    1+n1Snxnn!=1cosxsinx.

    Arnold [2,p.11] showed in 1992 that Sn enumerates a signed-permutation analogue of the alternating permutations. Recall that a signed permutation of [n] is a sequence π=(π1,,πn) of elements of [±n]:={1,,n}{1,,n} such that |π|=(|π1|,,|πn|) is a permutation of [n]. We write Bn for the set of all signed permutations of [n]. Clearly the cardinality of Bn is 2nn!. An (down-up) alternating permutation of type Bn is a signed permutation πBn such that π1>π2<π3>π4 and a snake of type Bn is an alternating permutation of type Bn starting with a positive entry. Let DUn(B) be the set of (down-up) alternating permutations of type Bn and Sn the set of snakes of type Bn. Clearly the cardinality of DUn(B) is 2nEn. Arnold [2] showed that the Springer number Sn enumerates the snakes of type Bn. For example, the 11 snakes of S3 are as follows:

    1ˉ23,1ˉ32,1ˉ3ˉ2,213,2ˉ13,2ˉ31,2ˉ3ˉ1,312,3ˉ12,3ˉ21,3ˉ2ˉ1,

    where we write ˉk for k. Arnold [2] introduced the following pair of triangles to compute the Springer numbers:

    S1,1S2,2S2,1S3,3S3,2S3,1S4,4S4,3S4,2S4,112102316161411S1,1S2,1S2,2S3,1S3,2S3,3S4,1S4,2S4,3S4,411034411840

    where Sn,k is defined by S1,1=S1,1=1, Sn,n=0 (n2), and the recurrence

    Sn,k={Sn,k1+Sn1,k+1if nk>1,Sn,1if n>k=1,Sn,k1+Sn1,kif 1k>n. (3)

    Theorem 2 (Arnold). For all integers 1kn, the number of the snakes of type Bn starting with k is Sn,k, i.e., Sn,k=#Sn,k with Sn=k>0#Sn,k, where

    Sn,k:={σSn:σ1=k}.

    Moreover, for all integers nk1, it holds that

    Sn,k=#{σDUn(B):σ1=k}.

    Similarly, the numbers Sn,k are called Arnold numbers and a sequence of sets (Xn,k) is called an Arnold family if the cardinality of Xn,k is equal to Sn,k for 1|k|n. The first values of Arnold and Springer numbers are given in Table 2. The aim of this paper is to provide some new Entringer families and new Arnold families by refining known combinatorial models for Euler and Springer numbers. To this end we shall build bijections between these new Entringer (resp. Arnold) families with the known ones. We refer the reader to the more recent papers [23,11,4,13,8] related to the combinatorics of Euler numbers and Springer numbers.

    Table 2.  The Arnold numbers Sn,k for 1|k|n6 and Springer numbers Sn=nk=1Sn,k.
    nk -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 Sn
    1 1 1 1
    2 0 1 1 2 3
    3 0 2 3 3 4 4 11
    4 0 4 8 11 11 14 16 16 57
    5 0 16 32 46 57 57 68 76 80 80 361
    6 0 80 160 236 304 361 361 418 464 496 512 512 2763

     | Show Table
    DownLoad: CSV

    This paper is organized as follows. In Section 2, we shall give the necessary definitions and present our main results. The proof of our theorems will be given in Sections 3-4. In Section 5, we shall give more insightful description of two important bijections. More precisely, Chuang et al.'s constructed a ϕ:Tn+1RSn in [4], we show that ϕ can be factorized as the compositions of two of our simpler bijections, and then give a direct description of Gelineau et al.'s bijection ψ:DUnTn in [11].

    Let V be a finite subset of N. An increasing 1-2 tree on V is a vertex labeled rooted tree with at most two (upward) branchings at any vertex and vertex labels in increasing order on any (upward) path from the root, see Figure 2. In what follows, when one draws an increasing 1-2 tree, let's designate the left child if its parent has a unique child or it is smaller than the other sibling and the others, except of the root, are designate the right child.

    Figure 1.  increasing 1-2 trees on [4].
    Figure 2.  Sixteen type B increasing 1-2 trees on [3].

    For each vertex v of a binary tree, by exchanging the left and right subtrees of v, we obtain another binary tree. This operation is called a flip. If two binary trees can be connected by a sequence of flips, we say that these two trees are flip equivalent. Since flip equivalence is obviously an equivalence relation, we are able to define the equivalence classes of binary trees, which are corresponding to increasing 1-2 trees; see [23,Section 3.2] in detail.

    Definition 3. Given an increasing 1-2 tree T, the minimal path of T is the unique sequence (v1,,v) of vertices where v1 is the root, vk+1 is the left child of vk (1k<), and v is a leaf. The vertex v is called the minimal leaf of T and denoted by Leaf(T). Similarly, the unique path (v1,,v) from v1=v to a leaf v of T is called the maximal path from v if vk+1 is the right child of vk for 1k<.

    Let TV be the set of increasing 1-2 trees on V with Tn:=T[n] and

    Tn,k={TTn:Leaf(T)=k}.

    Donaghey [5] (see also [3]) proved bijectively that the Euler number En enumerates the binary increasing trees in Tn and Poupard [15] showed that the sequence (Tn,k) is an Entringer family. In a previous work Gelineau et al. [11] proved bijectively Poupard's result by establishing a bijection between DUn and Tn.

    Theorem 4 (Gelineau-Shin-Zeng). There is an explicit bijection ψ:DUnTn such that

    Leaf(ψ(σ))=First(σ)

    for all σDUn, where First(σ) is the first entry of σ.

    Let Sn be the group of permutations on [n]. For a permutation σ=σ1σnSn, a descent (resp. ascent) of σ is a pair (σi,σi+1) with σi>σi+1 (resp. σi<σi+1) and 1in1, a double descent of σ is a triple (σi,σi+1,σi+2) with σi>σi+1>σi+2 and 1in2, and a valley of σ is a triple (σi,σi+1,σi+2) with σi>σi+1<σi+2 and 1in2.

    Hetyei [12,Definition 4] defined recursively André permutation of second kind if it is empty or satisfies the following:

    (ⅰ) σ has no double descents.

    (ⅱ) (σn1,σn) is not descent, i.e., σn1<σn.

    (ⅲ) For all 2in1, if (σi1,σi,σi+1) is a valley of σ, then the minimum letter of w2 is larger than the minimum letter of w4 for the σi-factorization (w1,w2,σi,w4,w5) of σ, where the word w1w2σiw4w5 is equal to σ and w2 and w4 are maximal consecutive subwords of σ satisfies its all letters are greater than σi.

    It is known that the above definition for André permutation of second kind is simply equivalent to the following definition. Let σ[k] denote the subword of σ consisting of 1,,k in the order they appear in σ.

    Definition 5. A permutation σSn is called an André permutation if σ[k] has no double descents and ends with an ascent for all 1kn.

    For example, the permutation σ=43512 is not André since the subword σ[4]=4312 contains a double descent (4,3,1), while the permutation τ=31245 is André since there is no double descent in the subwords:

    τ[1]=1,τ[2]=12,τ[3]=312,τ[4]=3124,τ[5]=31245.

    Foata and Schützenberger [10] proved that the Euler number En enumerates the André permutations in Sn. Let An be the set of André permutations in Sn. For example,

    A4={1234,1423,3124,3412,4123}.

    Remark. Foata and Schützenberger in [10] introduced augmented André permutation is a permutation σSn, if σ has no double descents, σn=n, and, for 1<j<kn satisfying

    σj1=max{σj1,σj,σk1,σk}andσk=min{σj1,σj,σk1,σk},

    there exists such that j<<k and σ<σk.

    Definition 6. A permutation σSn is called a Simsun permutation if σ[k] has no double descents for all 1kn.

    By definition, an André permutations is always a Simsun permutation, but the reverse is not true. For example, the permutation σ=25134 is Simsun but not André, because τ[2]=21 ends with an descent:

    τ[1]=1,τ[2]=21,τ[3]=213,τ[4]=2134,τ[5]=25134.

    Let RSn be the set of Simsun permutations in Sn. For example,

    RS3={123,132,213,231,312}.

    As for DUn,k, we define two similar refinements of André permutations and Simsun permutations as

    An,k:={σAn:σn=k},RSn,k:={σRSn:σn=k}.

    Some examples are shown in Table 3.

    Table 3.  The sets DU4,k, A4,k, and RS3,k1 for 2k4.
    k DU4,k A4,k RS3,k1
    2 {2143} {3412} {231}
    3 {3142,3241} {1423,4123} {132,312}
    4 {4132,4231} {1234,3124} {123,213}

     | Show Table
    DownLoad: CSV

    Foata and Han [8,Theorem 1 (ⅲ)] proved that An,k is an Entringer family by constructing a bijection between DUn,k and An,k. We shall give an easier proof of their result by constructing a simpler bijection ω between Tn,k and An,k. Of course, combining ψ (cf. Theorem 4) and ω we obtain another bijection between DUn,k and An,k.

    Theorem 7. For positive integer n1, there is a bijection ω:TnAn such that

    Leaf(T)=Last(ω(T)) (4)

    for all TTn, where Last(σ) is the last entry of σ. In words, for all 1kn, the mapping ω is a bijection from Tn,k onto An,k.

    Whereas one can easily show that the cardinality #DUn,k of (down-up) alternating permutations of length n with first entry k satisfies (1), it seems hard to show that the cardinality #An,k of André permutations of length n with last entry k or the cardinality #RSn1,k1 of Simsun permutations of length n1 with last entry k1 does. Thus, in order to show (4) and (6), we shall construct a bijection between DUn,k, An,k, RSn1,k1, and other known Entringer families in [11].

    Stanley [22,Conjecture 3.1] conjectured a refinement of Purtill's result [18,Theorem 6.1] about the cd-index of André and Simsun permutations with fixed last letter. In this conjecture, he mentioned three kinds of André permutations: (ⅰ) Augmented André permutations in Remark 2, (ⅱ) André permutations in Definition 5, and (ⅲ) augmented Sundaram permutations, where the third corresponds to Simsun permutations in Definition 6 by removing last letter. Hetyei [12] proved the conjecture for the second and the third by verifying that both sides satisfy the same recurrence. In particular, he proves the following result.

    Theorem 8 (Hetyei). For all 1kn, we have that two cardinalities of An,k and RSn1,k1 are same, that is,

    #An,k=#RSn1,k1. (5)

    In the next theorem, we give a bijective proof of the conjecture of Stanley by constructing an explicit bijection.

    Theorem 9. For positive integer n1, there is a bijection φ:AnRSn1 such that

    Last(σ)1=Last(φ(σ)) (6)

    for all σAn. In words, the mapping φ is a bijection from An,k onto RSn1,k1. Moveover, the bijection φ preserves the cd-index of André and Simsun permutation.

    Given a permutation σBn, denote σ[k] the subword of σ consisting of k smallest entries in the order they appear in σ. A signed André permutation of [n] is a permutation σBn such that σ[k] has no double descents and ends with an ascent for all 1kn. Let A(B)n be the set of signed André permutations of [n] and A(B)n,k be the set of signed André permutations σ in A(B)n ending with entry k. For example, the permutation σ=2ˉ4ˉ135 is Andŕe due to

    σ[1]=ˉ4,σ[2]=ˉ4ˉ1,σ[3]=2ˉ4ˉ1,σ[4]=2ˉ4ˉ13,σ[5]=2ˉ4ˉ135.

    Some examples of A(B)3,k are shown in Table 4.

    Table 4.  The sets S3,k, A(B)3,k, A(H)4,5k, and RS(B)3,4k for 1k3.
    k S3,k A(B)3,k A(H)4,5k RS(B)3,4k
    1 {1ˉ23,1ˉ32,1ˉ3ˉ2} {3ˉ21,ˉ3ˉ21,2ˉ31} {1234,3124,ˉ3124} {123,213,ˉ213}
    2 {213,2ˉ13,2ˉ31,2ˉ3ˉ1} {312,ˉ312,3ˉ12,ˉ3ˉ12} {1423,1ˉ423,4123,ˉ4123} {132,1ˉ32,312,ˉ312}
    3 {312,3ˉ12,3ˉ21,3ˉ2ˉ1} {ˉ213,ˉ2ˉ13,123,ˉ123} {3412,ˉ3412,3ˉ412,ˉ3ˉ412} {231,ˉ231,2ˉ31,ˉ2ˉ31}

     | Show Table
    DownLoad: CSV

    Definition 10. A type B increasing 1-2 tree on [n] is a binary tree with n signed labels in {±1,±2,,±n} such that the absolute values of signed labels are distinct and any vertex is greater than its children.

    For example, all type B increasing 1-2 trees on [3] are given in Figure 2. Let T(B)n be the set of type B increasing 1-2 trees on n vertices and T(B)n,k be the set of trees T in T(B)n with leaf k as the end of minimal path. Clearly we have T(B)n=|k|>0T(B)n,k.

    Our second aim is to show that these two refinements are new Arnold families. Recall that the sequence Sn,k is an Arnold family for 1|k|n as

    Sn,k:={σDUn(B):σ1=k}.

    Theorem 11. For all 1|k|n, there are two bijections

    ψB:Sn,kT(B)n,k, (7)
    ωB:T(B)n,kA(B)n,k. (8)

    Thus, for all 1|k|n,

    Sn,k=#A(B)n,k=#T(B)n,k. (9)

    In particular, the two sequences A(B)n,k and T(B)n,k are Arnold families for 1|k|n.

    Hetyei[12,Definition 8] defined another class of signed André permutations.

    Definition 12 (Hetyei). A signed André permutation is a pair (ε,π), where π is an André permutation such that ε(i)=1 if πi=min{πi,πi+1,,πn}.

    We write A(H)n (resp. A(H)n,k) for the set of the signed André permutations (resp. ending with entry k) in Bn. Some examples of A(H)4,k are shown in Table 4. We have the following conjecture.

    Conjecture 13. For all 1kn, we have

    Sn,k=#A(H)n+1,n+2k.

    Since the last entry of any permutation in the family A(H)n is always positive, even if Conjecture 13 is true, it covers only the half of Table 2. Now we define signed Simsun permutations corresponding to Heytei's signed André permutations.

    Definition 14. A permutation π in Bn is a signed Simsun permutation if |π1||π2||πn| is a Simsun permutation and πi>0 for all |πi|=min{|πi|,|πi+1|,,|πn|}.

    Let RS(B)n be the set of signed Simsun permutations in Bn and RS(B)n,k the set of signed Simsun permutations in RS(B)n with last entry k. Some examples of RS(B)3,k are shown in Table 4.

    Theorem 15. For positive integer n1, there is a bijection φ(B):A(H)nRS(B)n1 such that

    Last(σ)1=Last(φ(B)(σ)) (10)

    for all σA(H)n. In words, the mapping φ(B) is a bijection from A(H)n,k onto RS(B)n1,k1.

    Remark. Ehrenborg and Readdy [6,Section 7] gave a different definition of signed Simsun permutation as follows: A signed permutation σ of length n is a Simsun permutation if σ[k] have no double descents for all 1kn, where σ[k] is obtained by removing the (nk) entries ±(k+1),,±n from σ. Beacuse all eight signed permutations of length 2

    12,21,ˉ12,2ˉ1,1ˉ2,ˉ21,ˉ1ˉ2,ˉ2ˉ1

    are Simsun permutations, we note that it is not an Arnold family.

    First of all, we prove Theorem 7, in order to show that (An,k)1kn is a Entringer family, that is, En,k=#An,k. We construct a bijection ω between Tn,k and An,k in Section 3.1. Hence the map ωψ is a bijection from the set DUn,k of (down-up) alternating permutations with first entry k to the set An,k of André permutations with last entry k. Also, in order to show that (RSn1,k1)1kn is a Entringer family, that is En,k=#RSn1,k1, we construct a bijection between An,k and RSn1,k1 in Section 3.2 and then two sets An,k and RSn1,k1 have the same cardinality.

    Given TTn,k, write down the word σ of the vertices of the tree T in inorder, namely, for any vertex v in T, the left child of v and its descendants precede the vertex v and the vertex v precede the right child of v and its descendants. Since T is an increasing tree, we can recover T from σ by finding minimum in subwords in σ successively. The word σ has no double ascents because no vertex in T has only a right child. The leaf p(T) of the minimal path of T is σ1 and the parent of σ1 is σ2, so σ starts with a decent, that is, σ1>σ2. Similarly, since the subgraph of T consisting of 1,,k, for any k, is also well-defined an increasing 1-2 subtree, the subwords of σ consisting of 1,,k has also no double ascents and starts with a decent. Thus the word σR, which is the reverse word of σ, is an André permutation of n and let ω(T)=σR.

    For example, if the tree T is given by the following figure with a corresponding word σ,

    12,21,ˉ12,2ˉ1,1ˉ2,ˉ21,ˉ1ˉ2,ˉ2ˉ1

    then ω(T)=σR=684512937 as reading reversely vertices of T in inorder.

    Given σ:=σ1σnAn,k, let i1<<i be the positions of the right-to-left minima of σ. Clearly σi1=1, i1=n1 and i=n with σn=k. Let φ(σ)=π, where π=π1π2πn1 is defined by

    πi={σi1ifi{i1,,i},σik1ifi=ik1fork=2,,. (11)

    We show that πRSn1,k1. Suppose π[i] has a double descent for some 1in. There exists a triple (a,b,c) such that 1a<b<cn, iπa>πb>πc, and πa+1,,πb1, πb+1,,πc1 are greater than i, which yields πc=min{πj:ajc}. Then πc could be a right-to-left minimum in π and the others πa,πa+1,,πc1 are not in π. As φ(σ)=π, we have

    σa=πa+1,σa+1=πa+1+1,,σc1=πc1+1, and σcπc+1.

    Hence a triple (σa,σb,σc) is a double descent in σ[i], which contradicts that σ is an André permutation. As this procedure is clearly reversible, the mapping φ is a bijection.

    Consider the running example σ=684512937. The right-to-left minimums of σ are 1, 2, 3, 7. So after removing 1 from σ, the entries 2, 3, 7 are moved to the positions of 1, 2, 3, respectively, and we get the permutation ˆπ=68452397, and then φ(σ)=π=57341286, which is a Simsun permutation of length 8 with last entry 6.

    Remark. Considering the bijection ψ in Theorem 4, the map φωψ is a bijection from the set of (down-up) alternating permutations of length n with first entry k to the set of Simsun permutations of length n1 with last entry k1. Namely we have the diagram in Figure 3. For example, if τ=739154826DU9,7, then

    ψ(τ)=TT9,7,ω(T)=σ=684512937A9,7,φ(σ)=π=57341286RS8,6,
    Figure 3.  Bijections between Entringer families and Arnold families.

    where T is the increasing 1-2 tree given in Section 3.1.

    One can extend the above mapping φ defined on An to a mapping φ(B) on A(H)n. It is also bijective between A(H)n,k and RS(B)n1,k1, but the description of φ(B) and a proof of bijectivity are omitted, because it is very similar in Section 3.2.

    Remark. This bijection preserves the cd-indices between André permutations and Simsun permutations. The variation of a permutation π=π1πn is given by ab-monomial u1un1 such that ui=a if πi<πi+1 and ui=b if πi>πi+1. The reduced variation of André permuation is defined by replacing each ba with d and then replacing each remaining a by c. For example, the variation and reduced variation of André permutation σ=684512937 is

    ababaaba=cddcd.

    For the cd-index of a Simsun permutation σ, we consider augmented Simsun permutation by adding σ(0)=0. Here, the reduced variation of augmented Simsun permuations is defined by replacing each ab with d and then replacing each remaining a by c. So the variation and reduced variation of augmented Simsun permutation 057341286 by adding 0 to φ(σ)=57341286 is

    aababaab=cddcd.

    Given a σSn,k, there is a unique order-preserving map πσ, say just π, from {σ1,,σn} to [n]. In other words, π replaces the i-th smallest entry in σ by i. The permutation τ=πσ belongs to DUn,k and ψ(τ)=ψ(πσ) in Tn,k. Then π1(ψ(τ)) means the tree with vertex labelings {σ1,,σn} instead of [n] and it should belong to T(B)n,k. So we construct the bijection ψB from Sn,k to T(B)n,k by

    ψB(σ)=π1(ψ(πσ))

    through the unique order-preserving map π. Hence, it yields (7).

    For example, in the case of σ=6ˉ39ˉ82ˉ17ˉ45, the order-preserving map πσ is

    π=(ˉ8ˉ4ˉ3ˉ125679123456789).

    So we have τ=πσ=739154826 and ψ(τ)=ψ(πσ) and ψB(σ)=π1(ψ(πσ)) are illustrated as

    π=(ˉ8ˉ4ˉ3ˉ125679123456789).

    In Subsection 3.1, we define the bijection ω from Tn,k to An,k. Given a tree T in T(B)n,k, there is a unique order-preserving map πT, say just π, from V(T) to [n]. In other words, π replaces the i-th smallest V(T) by i. After relabeling on vertices of T by π, we obtain the tree π(T) which belongs to Tn,k and ω(π(T)) is in An,k. Then π1(ω(π(T))) should belong to A(B)n,k. So we construct the bijection ωB from T(B)n,k to A(B)n,k by

    ωB(T)=π1(ω(π(T)))

    through the unique order-preserving map π. Such the map ωB can be described simply, as same as ω, by reading reversely vertices of T in inorder. Hence, it yields (8).

    For example, in the case of T illustrated as

    ωB(T)=π1(ω(π(T)))

    we obtain ωB(T)=σR=57ˉ12ˉ8ˉ49ˉ36 by reading reversely vertices of T in inorder. So bijections for type A and type B commute in the diagram of Figure 3.

    We summarize four interpretations for Entringer numbers E4,k, k{2,3,4} in Table 5 and left three interpretations for Arnold number S3,k, k{1,2,3} in Table 6. In every column, the corresponding elements are described via the different bijections mentioned in the paper.

    Table 5.  Three bijections between Entringer families with n=4 and 2k4.
    k τDU4,k ψ(τ)T4,k ω(ψ(τ))A4,k φ(ω(ψ(τ)))RS3,k1
    2 2143 3412 231
    3 3241 1423 132
    3142 4123 312
    4 4231 1234 123
    4132 3124 213

     | Show Table
    DownLoad: CSV
    Table 6.  Three bijections between Arnold families with n=3 and 1k3.
    τS3,k ψ(B)(τ)T(B)3,k ω(B)(ψ(B)(τ))A(B)3,k k σA(H)4,5k φ(B)(σ)RS(B)3,4k
    1ˉ23 3ˉ21 1 1234 123
    1ˉ32 2ˉ31 3124 213
    1ˉ3ˉ2 ˉ3ˉ21 ˉ3124 ˉ213
    213 312 2 1423 132
    2ˉ13 3ˉ12 1ˉ423 1ˉ32
    2ˉ31 ˉ312 4123 312
    2ˉ3ˉ1 ˉ3ˉ12 ˉ4123 ˉ312
    312 123 3 3412 231
    3ˉ12 ˉ123 ˉ3412 ˉ231
    3ˉ21 ˉ213 3ˉ412 2ˉ31
    3ˉ2ˉ1 ˉ2ˉ13 ˉ3ˉ412 ˉ2ˉ31

     | Show Table
    DownLoad: CSV

    In 2012, Chuang et al. [4] construct a bijection ϕ:Tn+1RSn. If x has only one child then it is the right child of x. They described the bijection ϕ between increasing 1-2 trees and Simsun permutations using the following algorithm.

    Algorithm A.

    (A1) If T consists of the root vertex then T is associated with an empty word.

    (A2) Otherwise, the word ρ(T) is defined inductively by the factorization

    ρ(T)=ωρ(T),

    where the subword ω and the subtree T are determined as follows.

    (a) If the root of T has only one child x then let ω=x (consisting of a single letter x), let T=τ(x) (i.e, obtained from T by deleting the root of T), and relabel the vertex x by 1.

    (b) If the root of T has two children u, v with u>v then traverse the right subtree τ(u) reversely in inorder, put down the word ω of the vertices of τ(u) and let T=Tτ(u).

    As deleted only 1 in ρ(T), every permutation ρ(T)=a1a2an is a Simsun permutation on {2,3,,n+1}. Thus we get a Simsun permutation ϕ(T)=b1b2bn on [n] with bi=ai1 for all 1in.

    Remark. Originally, in [4], the increasing 1-2 trees on n vertices are labeled with 0,1,,n1 instead of 1,2,,n and was drawn in a canonical form such that if a vertex x has two children u, v with u>v then u is the left child, v is the right child.

    Theorem 16. The bijection ϕ:Tn,kRSn1,k1 is the composition of φ and ω; i.e., ϕ=φω.

    Proof. Suppose that we let ω be the root of T without relabeling the vertex x in (A2a), it is obvious that Algorithm A follow the bijeciton ω, i.e., reading the vertex of T reversely in inorder. So it is enough to show that the change in two rules of (A2a) follows φ.

    The root of T becomes to the left-child of the root of T after (A2a) and the root of T is same with the root of T in (A2b). So Algorihm A executes the step (A2a) only when a vertex on the minimal path of an original tree becomes the root of its subtree.

    To record the left-child x instead of the root 1 with relabeling the vertex x by 1 in each of (A2a)'s means to exchange x and 1 sequentially according to the minimal path from the root 1 of the original tree T.

    It is clear that all vertices in the minimal path in a tree become the right-to-left minimums in a permutation under ω. So each right-to-left minimums is recorded in the position of the previous right-to-left minimums in a permutation obtained from a tree by ω. Since all elements are decreased by 1 in the last step, it satisfies (11), then Algorithm A follows φω.

    The bijection ψ between DUn,k and Tn,k was constructed as a composition of two bijections via the set ESn,k of encoding sequences in [11]. In this section, we just give directly another description of this bijection ψ from DUn,k to Tn,k, which does not use encoding sequences.

    Given an increasing 1-2 tree TTn, by convention, if a vertex x of T has two children u, v with u<v then u is the left child and v is the right child. By convention, if x has only one child then it is the left child of x.

    Algorithm B. Gelineau et al. described the bijection ψ between alternating permutations and increasing 1-2 trees using the following algorithm. Due to, for n=1 or 2,

    |DUn|=|Tn|=1,

    we can define trivially ψ. For n3, given πDUn,k (k=π1), we define the mapping ψ:DUn,kTn,k recursively as follows:

    (B1) If π2=k1, then define π=π1π2πn2DUn2,i2 by deleting k1 and k from π and relabeling by [n2] where i>k, that is, for all 1jn2

    πj={πj+2,if πj+2<k1,πj+22,if πj+2>k.

    We get T=ψ(π)Tn2,i2. Relabel T by {1,,k2,k+1,,n} keeping in the order of labels, denoted by T. Let m be the smallest vertex greater than k in the minimal path of T'' and \ell the parent of m in T'' . Then insert a vertex k-1 in the middle of the edge (\ell,m) and graft k as the left-child of k-1 .

    \pi'_{j} = \begin{cases} \pi_{j+2}, &\text{if $\pi_{j+2} < k-1$,}\\ \pi_{j+2}-2, &\text{if $\pi_{j+2} > k$.} \end{cases}

    We get the tree T = \psi(\pi) \in {{\mathcal{T}}_{n,k}} .

    (B2) If \pi_2<k-1 , then define \pi' = (k-1\; k)\pi \in {{\mathcal{DU} }}_{n,k-1} by exchanging k-1 and k in \pi . We get T' = \psi(\pi') \in {\mathcal{T}}_{n,k-1} .

    (a) If k is a not sibling of k-1 in T' , then we get the tree T = \psi(\pi) \in {{\mathcal{T}}_{n,k}} exchanging the labels k-1 and k in T' .

    \pi'_{j} = \begin{cases} \pi_{j+2}, &\text{if $\pi_{j+2} < k-1$,}\\ \pi_{j+2}-2, &\text{if $\pi_{j+2} > k$.} \end{cases}

    (b) If k is a sibling of k-1 in T' , then we get the tree T = \psi(\pi) \in {{\mathcal{T}}_{n,k}} modifying as follows:

    \pi'_{j} = \begin{cases} \pi_{j+2}, &\text{if $\pi_{j+2} < k-1$,}\\ \pi_{j+2}-2, &\text{if $\pi_{j+2} > k$.} \end{cases}

    Algorithm C. We define another bijection \psi' : {{{\mathcal{DU} }}_{n,k}} \to {{\mathcal{T}}_{n,k}} by the following algorithm. Given \sigma = \sigma_1 \dots \sigma_n \in {{{\mathcal{DU} }}_{n,k}} , denote by d_i(\sigma) = (\sigma_{2i-1}, \sigma_{2i}) with \sigma_{2i-1} > \sigma_{2i} for 1 \le i \le m , where m = \lfloor (n+1)/2\rfloor , but d_{m}(\sigma) = (\sigma_{n}) if n is odd. We shall construct a series of trees T^{(m)}, \ldots, T^{(1)} by reading the pairs d_m(\sigma) , \ldots, d_1(\sigma) in this order.

    If n is odd, so d_{m} (\sigma) = (\sigma_n) , define T^{(m)} to be the tree with only root \sigma_n . If n is even, so d_{m}(\sigma) = (\sigma_{n-1}, \sigma_{n}) with \sigma_{n-1} > \sigma_{n} , define T^{(m)} to be the tree with the root \sigma_{n} and its left child \sigma_{n-1} . We note that the vertex \sigma_{2m-1} is the minimal leaf of T^{(m)} .

    For 1 \le i \le m-1 , assuming that we have a tree T^{(i+1)} of which the minimal leaf is \sigma_{2i+1} , read d_i(\sigma) = (\sigma_{2i-1}, \sigma_{2i}) . As \sigma_{2i} < \sigma_{2i+1} , the smallest vertex, say a^{(i)} , greater than \sigma_{2i} in the minimal path of T^{(i+1)} is well-defined. By removing all left edges from the increasing 1-2 tree T^{(i+1)} , we have several paths, each connected component of which is called a maximal path consisting only right edges.

    (C1) If a^{(i)} < \sigma_{2i-1} , the largest vertex, say b^{(i)} , less than \sigma_{2i-1} in the maximal path from a^{(i)} of T^{(i+1)} is well-defined. For some j\ge 1 , let (v_1, v_1, \ldots, v_j) be the path from a^{(i)} to b^{(i)} with v_1 = a^{(i)} and v_j = b^{(i)} . The vertices v_1, \dots, v_{j-1} should have left child u_1, \dots, u_{j-1} , but v_j may not, with

    \begin{align*} v_1 < u_1 < v_2 < u_2 < \dots < v_{j-1} < u_{j-1} < v_j \end{align*}

    Decomposing by the maximal path from a^{(i)} to b^{(i)} , we write S_1, \ldots, S_{j} the left-subtrees of the vertices v_1, \ldots, v_{j} and S_{j+1} the right-subtree of b^{(i)} . Since each of u_1, \dots, u_{j-1} lies on each of S_1, \dots, S_{j-1} , S_1, \dots, S_{j-1} should not be empty, but two trees S_{j} and S_{j+1} may be empty. Then, the tree T^{(i)} is obtained from T^{(i+1)} by the following operations:

    ● Graft \sigma_{2i} so that a^{(i)} is its left-child;

    ● Flip the tree at vertex a^{(i)} ;

    ● Transplant the trees S_1, \ldots, S_{j+1} as right-subtrees of the vertices \sigma_{2i} , a^{(i)} , v_2, \ldots, v_{j-1} , b^{(i)} ;

    ● Graft \sigma_{2i-1} as the left-child of b^{(i)} .

    We can illustrate the above transformation by

    \begin{align*} v_1 < u_1 < v_2 < u_2 < \dots < v_{j-1} < u_{j-1} < v_j \end{align*}

    (C2) If \sigma_{2i-1}<a^{(i)} , then b^{(i)} does not exist. Let S be the subtree with root a^{(i)} of T^{(i+1)} , then the tree T^{(i)} is defined as follows.

    ● Graft \sigma_{2i} so that a^{(i)} is its right-child;

    ● Transplant the trees S as the right-subtree of the vertex \sigma_{2i} ;

    ● Graft \sigma_{2i-1} as the left-child of \sigma_{2i} .

    We can illustrate this transformation by the following

    \begin{align*} v_1 < u_1 < v_2 < u_2 < \dots < v_{j-1} < u_{j-1} < v_j \end{align*}

    We note that the vertex \sigma_{2i-1} is the minimal leaf of T^{(i)} for 1 \le i \le m-1 . And then, we define \psi'(\sigma) = T^{(1)} .

    Example. We run the new algorithm to the examples \sigma = 748591623 in Example 3.2 and Fig. 2 in [11]. As n = 9 , we have five pairs

    \begin{align*} d_5(\sigma) & = (3),& d_4(\sigma) & = (6,2),& d_3(\sigma) & = (9,1),& d_2(\sigma) & = (8,5),& d_1(\sigma) & = (7,4). \end{align*}

    By Algorithm C, we get five trees sequentially

    \begin{align*} d_5(\sigma) & = (3),& d_4(\sigma) & = (6,2),& d_3(\sigma) & = (9,1),& d_2(\sigma) & = (8,5),& d_1(\sigma) & = (7,4). \end{align*}

    with

    \begin{align*} a^{(4)}& = 3, & a^{(3)}& = 2, & a^{(2)}& = 9, & a^{(1)}& = 5,\\ b^{(4)}& = 3, & b^{(3)}& = 2, & b^{(2)}&\text{ does not exist}, & b^{(1)}& = 5. \end{align*}

    Thus, the increasing 1-2 tree T^{(1)} obtained from \sigma under \psi' is the same with the tree obtained from \sigma under \psi in Example 3.2 and Fig. 2 in [11].

    Theorem 17. The two bijections \psi and \psi' from {{{\mathcal{DU} }}_{n,k}} to {{\mathcal{T}}_{n,k}} are equal.

    Proof. It is clear that (C2) is equivalent to (B1). Since the rule (B2a) just exchange two labels, but does not change the tree-structure, it is enough to show that (C1) is produced recursively from (B1) and (B2b).

    Assume that \sigma_{2i-1} > a^{(i)} > \sigma_{2i} for some 1 \le i \le m-1 . We obtain the right tree in the following by applying (B1) to the tree T^{(i+1)} .

    \begin{align*} a^{(4)}& = 3, & a^{(3)}& = 2, & a^{(2)}& = 9, & a^{(1)}& = 5,\\ b^{(4)}& = 3, & b^{(3)}& = 2, & b^{(2)}&\text{ does not exist}, & b^{(1)}& = 5. \end{align*}

    Due to \sigma_{2i-1} > v_1 ( = a^{(i)}) , it is not an increasing 1-2 tree and we apply (B2b) to the above tree as follows.

    \begin{align*} a^{(4)}& = 3, & a^{(3)}& = 2, & a^{(2)}& = 9, & a^{(1)}& = 5,\\ b^{(4)}& = 3, & b^{(3)}& = 2, & b^{(2)}&\text{ does not exist}, & b^{(1)}& = 5. \end{align*}

    Since \sigma_{2i-1} > v_j > \dots > v_2 , until we have an increasing 1-2 tree, repeat to apply (B2b) as follows.

    \begin{align*} a^{(4)}& = 3, & a^{(3)}& = 2, & a^{(2)}& = 9, & a^{(1)}& = 5,\\ b^{(4)}& = 3, & b^{(3)}& = 2, & b^{(2)}&\text{ does not exist}, & b^{(1)}& = 5. \end{align*}

    Since (C2a) is produced from the rule (B1) and (B2b), then Algorithm C follows Algorithm B.

    The first author's work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. 2017R1C1B2008269).

    [1] Campion D (2001) Dissection génétique des maladies à hérédité complexe'. médecine/sciences 17: 1139-1148. doi: 10.1051/medsci/200117111139
    [2] Hodge SE, Hager VR, Greenberg DA (2016) Using Linkage Analysis to Detect Gene-Gene Interactions. 2. Improved Reliability and Extension to More-Complex Models', Plos one 11: e0146240.
    [3] Onouchi Y (2017) Identification of Novel Kawasaki Disease Susceptibility Genes by Genome-Wide Association Studies. In: Kawasaki Disease. Springer Japan: 23-29.
    [4] Morton NE (1955) Sequential tests for the detection of linkage. Am J Hum Genet 7: 277.
    [5] Clerget-Darpoux F, Bonaiti-Pellie C, Hochez J (1986) Effects of misspecifying genetic parameters in lod score analysis. Biometrics: 393-399.
    [6] Savard N (2005) Méthode d'analyse de liaison génétique pour des familles dans lesquelles il ya de l'hétérogénéité non-allélique intra-familiale. Université Laval.
    [7] Haseman J, Elston R (1972) The investigation of linkage between a quantitative trait and a marker locus. Behav Genet 2: 3-19. doi: 10.1007/BF01066731
    [8] Costantino F, Chaplais E, Leturcq T, et al. (2016) Whole-genome single nucleotide polymorphism-based linkage analysis in spondyloarthritis multiplex families reveals a new susceptibility locus in 13q13. Ann Rheum Dis 75: 1380-1385. doi: 10.1136/annrheumdis-2015-207720
    [9] Hu H., Roach JC, Coon H, et al. (2014) A unified test of linkage analysis and rare-variant association for analysis of pedigree sequence data. Nat Biotechnol 32: 663-669. doi: 10.1038/nbt.2895
    [10] Greenwood TA, Swerdlow NR, Gur RE, et al. (2013) Genome-wide linkage analyses of 12 endophenotypes for schizophrenia from the Consortium on the Genetics of Schizophrenia. Am J Psychiat 170: 521-532. doi: 10.1176/appi.ajp.2012.12020186
    [11] Cochran WG (1954) Some methods for strengthening the common χ 2 tests'. Biometrics 10: 417-451. doi: 10.2307/3001616
    [12] Armitage P (1955) Tests for linear trends in proportions and frequencies. Biometrics 11: 375-386. doi: 10.2307/3001775
    [13] Wang L, Ni H, Yang R, et al. (2013) Feature selection based on meta-heuristics for biomedicine. Optim Method Softw 29: 703-719.
    [14] Talbi EG, Jourdan L, Garcia-Nieto J, et al. (2008) Comparison of population based metaheuristics for feature selection: Application to microarray data classification. Computer Systems and Applications. AICCSA 2008. IEEE/ACS International Conference on. IEEE: 45-52.
    [15] Yusta SC (2009) Different metaheuristic strategies to solve the feature selection problem. Pattern Recogn Lett 30: 525-534. doi: 10.1016/j.patrec.2008.11.012
    [16] Amarnath B, alias Balamurugan SA (2016) Metaheuristic Approach for Efficient Feature Selection: A Data Classification Perspective. Indian J Sci Technol 9.
    [17] Carrizosa E, Martin-Barragan B, Romero Morales D (2012) Variable neighborhood search for parameter tuning in support vector machines. Tech. rep.
    [18] Chan K, Zhu H, Aydin M, et al. (2008) An integrated approach of support vector machine and variable neighborhood search for discovering combinational gene signatures in predicting chemo-response of osteosarcoma. Proceedings of the international multiconference of engineers and computer scientists. 1: 121-125.
    [19] García-Torres M, Gómez-Vela F, Melián-Batista B, et al. (2016) High-dimensional feature selection via feature grouping: A Variable Neighborhood Search approach. Inform Sciences 326: 102-118. doi: 10.1016/j.ins.2015.07.041
    [20] Belacel N, Čuperlović-Culf M, Laflamme M, et al. (2004) Fuzzy J-Means and VNS methods for clustering genes from microarray data. Bioinformatics 20: 1690-1701. doi: 10.1093/bioinformatics/bth142
    [21] Cahon S, Melab N, Talbi EG (2004) Paradiseo: A framework for the reusable design of parallel and distributed metaheuristics. J Heuristics 10: 357-380. doi: 10.1023/B:HEUR.0000026900.92269.ec
    [22] García-Torres M, Armañanzas R, Bielza C, et al. (2013) Comparison of metaheuristic strategies for peakbin selection in proteomic mass spectrometry data. Inform Sciences 222: 229-246. doi: 10.1016/j.ins.2010.12.013
    [23] Feo TA, Resende MGC, Smith SH (1994) A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set. Oper Res 42: 860-878. doi: 10.1287/opre.42.5.860
    [24] Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by Simulated Annealing. Science 220: 671-680. doi: 10.1126/science.220.4598.671
    [25] Glover F (1989) Tabu search-part I. ORSA Journal on computing 1: 190-206. doi: 10.1287/ijoc.1.3.190
    [26] Papadimitriou CH, Steiglitz K (1982) Combinatorial optimization: algorithms and complexity. Courier Corporation.
    [27] Papadimitriou CH (1976) The complexity of combinatorial optimization problems.
    [28] Schlosberg CE, Schwantes-An TH, Duan W, et al. (2011) Application of Bayesian network structure learning to identify causal variant SNPs from resequencing data. BMC Proceedings 5 Suppl 9: S109-S109.
    [29] Nithya R, Venkateswaran N (2015) Analysis of Segmentation Algorithms in Colour Fundus and OCT Images for Glaucoma Detection. Indian J Sci Technol 8.
    [30] Bhardwaj A, Tiwari A, Varma MV, et al. (2015) An Analysis of Integration of Hill Climbing in Crossover and Mutation operation for EEG Signal Classification. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. ACM: 209-216.
    [31] Metropolis N, Rosenbluth AW, Rosenbluth MN, et al. (1953) Equation of state calculations by fast computing machines. J Chem Phys 21: 1087-1092. doi: 10.1063/1.1699114
    [32] Iossifov I, Zheng T, Baron M, et al. (2008) Genetic-linkage mapping of complex hereditary disorders to a whole-genome molecular-interaction network. Genome Res 18: 1150-1162. doi: 10.1101/gr.075622.107
    [33] Wirdefeldt K, Burgess CE, Westerberg L, et al. (2003) A linkage study of candidate loci in familial Parkinson's Disease. BMC Neurol 3: 6. doi: 10.1186/1471-2377-3-6
    [34] Sartakhti JS, Zangooei MH, Mozafari K (2012) Hepatitis disease diagnosis using a novel hybrid method based on support vector machine and simulated annealing (SVM-SA). Comput Meth Prog Bio 108: 570-579. doi: 10.1016/j.cmpb.2011.08.003
    [35] Goyal M, Dhanjal JK, Goyal S, et al. (2014) Development of dual inhibitors against Alzheimer's disease using fragment-based QSAR and molecular docking. Bio med Res Int: 2014.
    [36] Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13: 533-549. doi: 10.1016/0305-0548(86)90048-1
    [37] Glover F (1977) Heuristics for integer programming using surrogate constraints. Decision Sci 8: 156-166. doi: 10.1111/j.1540-5915.1977.tb01074.x
    [38] Shen Q, Shi WM, Kong W (2008) Hybrid particle swarm optimization and tabu search approach for selecting genes for tumor classification using gene expression data. Comput Biol Chem 32: 53-60. doi: 10.1016/j.compbiolchem.2007.10.001
    [39] Wang S, Kong W, Zeng W, et al (2016) Hybrid Binary Imperialist Competition Algorithm and Tabu Search Approach for Feature Selection Using Gene Expression Data. Biomed Res Int: 2016.
    [40] Nguyen T, Khosravi A, Creighton D, et al. (2015) Fuzzy system with tabu search learning for classification of motor imagery data. Biomed Signal Proces 20: 61-70. doi: 10.1016/j.bspc.2015.04.007
    [41] Darwin C (1968) On the origin of species by means of natural selection. 1859. London: Murray Google Scholar.
    [42] Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press:1992.
    [43] Goldberg DE (1989) Genetic Algorithms in Search, Optimization, and Machine Learning.
    [44] Goldberg DE, Deb K (1991) A comparative analysis of selection schemes used in genetic algorithms. Foundations of Genetic Algorithms 1: 69-93.
    [45] Blickle T, Thiele L (1995) A Mathematical Analysis of Tournament Selection. ICGA: 9-16.
    [46] Sergii K, Yurii S, Tatyana V, et al. (2016) Feature Selection for Time-Series Prediction in Case of Undetermined Estimation. In: Biologically Inspired Cognitive Architectures (BICA) for Young Scientists. Springer, Cham: 85-97.
    [47] Underwood DJ, Zhang J, Denton BT, et al. (2012) Simulation optimization of PSA-threshold based prostate cancer screening policies. Health Care Manag Sci 15: 293-309. doi: 10.1007/s10729-012-9195-x
    [48] Beheshti I, Demirel H, Matsuda H, et al. (2017) Classification of Alzheimer's disease and prediction of mild cognitive impairment-to-Alzheimer's conversion from structural magnetic resource imaging using feature ranking and a genetic algorithm. Comput Biol Med 83: 109-119. doi: 10.1016/j.compbiomed.2017.02.011
    [49] Singh J, Kaur R (2016) Cardio Vascular Disease Classification Ensemble Optimization using Genetic Algorithm and Neural Network. Indian J Sci Technol 9: S1.
    [50] Paul AK, Shill PC, Rabin MRI, et al. (2016) Genetic algorithm based fuzzy decision support system for the diagnosis of heart disease. In: Informatics, Electronics and Vision (ICIEV), 2016 5th International Conference on. IEEE: 145-150.
    [51] Sachnev V, Suresh S, Choi YS (2016) Bio-marker Detector and Parkinson's disease diagnosis Approach based on Samples Balanced Genetic Algorithm and Extreme Learning Machine. 한국디지털콘텐츠학회논문지 17: 509-521.
    [52] Paul D, Su R, Romain M, et al. (2016) Feature selection for outcome prediction in oesophageal cancer using genetic algorithm and random forest classifier. Comput Med Imag Grap.
    [53] López FG, Torres MG, Batista BM, et al. (2006) Solving feature subset selection problem by a parallel scatter search. Eur J Oper Res 169: 477-489. doi: 10.1016/j.ejor.2004.08.010
    [54] Nepomuceno JA, Troncoso A, Aguilar-Ruiz JS (2015) Scatter search-based identification of local patterns with positive and negative correlations in gene expression data. Appl Soft Comput 35: 637-651. doi: 10.1016/j.asoc.2015.06.019
    [55] Lin SW, Chen SC (2012) Parameter determination and feature selection for C4. 5 algorithm using scatter search approach. Soft Comput 16: 63-75.
    [56] Chen SC, Lin SW, Chou SY (2011) Enhancing the classification accuracy by scatter-search-based ensemble approach. Appl Soft Comput 11: 1021-1028. doi: 10.1016/j.asoc.2010.01.024
    [57] Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection, MIT press.
    [58] Sohn A, Olson RS, Moore JH (2017) Toward the automated analysis of complex diseases in genome-wide association studies using genetic programming. arXiv preprint arXiv: 1702.01780.
    [59] Vyas R, Bapat S, Goel P, et al. (2016) Application of Genetic Programming (GP) formalism for building disease predictive models from protein-protein interactions (PPI) data. IEEE/ACM Transactions on Computational Biology and Bioinformatics.
    [60] Hasan MK, Islam MM, Hashem M (2016) Mathematical model development to detect breast cancer using multigene genetic programming. Informatics, Electronics and Vision (ICIEV), 2016 5th International Conference on. IEEE: 574-579.
    [61] Deneubourg JL, Pasteels JM, Verhaeghe JC (1983) Probabilistic behaviour in ants: a strategy of errors?. J Theor Biol 105: 259-271. doi: 10.1016/S0022-5193(83)80007-1
    [62] Deneubourg JL, Goss S (1989) Collective patterns and decision-making. Ethol Ecol Evol 1: 295-311. doi: 10.1080/08927014.1989.9525500
    [63] Husain NP, Arisa NN, Rahayu PN, et al. (2017) Least Squares Support Vector Machines Parameter Optimization Based on Improved Ant Colony Algorithm For Hepatitis Diagnosis. Jurnal Ilmu Komputer dan Informasi 10: 43-49. doi: 10.21609/jiki.v10i1.428
    [64] Asad AH, Azar AT, Hassanien AE (2017) A new heuristic function of ant colony system for retinal vessel segmentation. In: Medical Imaging: Concepts, Methodologies, Tools, and Applications. IGI Global: 2063-2081.
    [65] Eberhart R, Kennedy J (1995) A new optimizer using particle swarm theory. Micro Machine and Human Science, 1995. MHS'95., Proceedings of the Sixth International Symposium on. IEEE: 39-43.
    [66] Sali R, Shavandi H, Sadeghi M (2016) A clinical decision support system based on support vector machine and binary particle swarm optimisation for cardiovascular disease diagnosis. Int J Data Min Bioin 15: 312-327. doi: 10.1504/IJDMB.2016.078150
    [67] Shahsavari MK, Rashidi H, Bakhsh HR (2016) Efficient classification of Parkinson's disease using extreme learning machine and hybrid particle swarm optimization. Control, Instrumentation, and Automation (ICCIA), 2016 4th International Conference on. IEEE: 148-154.
    [68] Jothi N (2016) Prediction of Generalized Anxiety Disorder Using Particle Swarm Optimization. Advances in Information and Communication Technology: Proceedings of the International Conference, ICTA 2016. Springer, 538: 480.
    [69] Kumar GK (2016) An Optimized Particle Swarm Optimization based ANN Model for Clinical Disease Prediction. Indian J Sci Technol 9.
    [70] Yang CH, Weng ZJ, Chuang LY, et al. (2017) Identification of SNP-SNP interaction for chronic dialysis patients. Comput Biol Med 83: 94-101. doi: 10.1016/j.compbiomed.2017.02.004
    [71] Gunasundari S, Janakiraman S, Meenambal S (2016) Velocity Bounded Boolean Particle Swarm Optimization for improved feature selection in liver and kidney disease diagnosis. Expert Syst Appl 56: 28-47. doi: 10.1016/j.eswa.2016.02.042
    [72] Muthanantha Murugavel A, Ramakrishnan S (2014) Optimal feature selection using PSO with SVM for epileptic EEG classification. Int J Data Min Bioin 16: 343-358.
    [73] Farmer JD, Packard NH, Perelson AS (1986) The immune system, adaptation, and machine learning. Physica D: Nonlinear Phenomena 22: 187-204. doi: 10.1016/0167-2789(86)90240-X
    [74] De Castro LN, Timmis J (2002) Artificial immune systems: a new computational intelligence approach. Springer Science & Business Media.
    [75] Polat K, Şahan S, Güneş S (2007) Automatic detection of heart disease using an artificial immune recognition system (AIRS) with fuzzy resource allocation mechanism and k-nn (nearest neighbour) based weighting preprocessing. Expert Syst Appl 32: 625-631. doi: 10.1016/j.eswa.2006.01.027
    [76] Chikh MA, Saidi M, Settouti N (2012) Diagnosis of diabetes diseases using an artificial immune recognition system2 (AIRS2) with fuzzy k-nearest neighbor. J Med Syst 36: 2721-2729. doi: 10.1007/s10916-011-9748-4
    [77] Zhao W, Davis CE (2011) A modified artificial immune system based pattern recognition approach-An application to clinical diagnostics. Artif Intell Med 52: 1-9. doi: 10.1016/j.artmed.2011.03.001
    [78] Baluja S (1994) Population-based incremental learning. a method for integrating genetic search based function optimization and competitive learning. Carnegie-Mellon Univ Pittsburgh Pa Dept Of Computer Science.
    [79] Mühlenbein H, Paass G (1996) From recombination of genes to the estimation of distributions I. Binary parameters. Parallel problem solving from nature-PPSN IV: 178-187.
    [80] Inza I, Merino M, Larrañaga P, et al. (2001) Feature subset selection by genetic algorithms and estimation of distribution algorithms: A case study in the survival of cirrhotic patients treated with TIPS. Artif Intell Med 23: 187-205. doi: 10.1016/S0933-3657(01)00085-9
    [81] Armananzas R, Saeys Y, Inza I, et al. (2011) Peakbin selection in mass spectrometry data using a consensus approach with estimation of distribution algorithms. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8: 760-774. doi: 10.1109/TCBB.2010.18
    [82] Funayama M, Ohe K, Amo T, et al. (2015) CHCHD2 mutations in autosomal dominant late-onset Parkinson's disease: a genome-wide linkage and sequencing study. Lancet Neurol 14: 274-282. doi: 10.1016/S1474-4422(14)70266-2
    [83] Wotton CJ, Goldacre MJ (2014) Record-linkage studies of the coexistence of epilepsy and bipolar disorder. Soc Psych Psych Epid 49: 1483-1488. doi: 10.1007/s00127-014-0853-9
  • Reader Comments
  • © 2017 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(5772) PDF downloads(1141) Cited by(3)

Figures and Tables

Figures(5)  /  Tables(5)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog