4

私の問題:セットのセットからすべてのばらばらの(重複しない)セットを見つける必要があります。

背景: 私は鳥類の形質進化を研究するために比較系統学的手法を使用しています。私は〜300種の木を持っています。このツリーは、サブクレード (サブツリー) に分割できます。2 つのサブクレードが種を共有しない場合、それらは独立しています。各サブクレードに10を超える分類群があり、すべてが独立している可能性のあるすべてのサブクレードパーティションを見つけるアルゴリズム(および可能であればR実装)を探しています。各サブクレードはセットと見なすことができ、2 つのサブクレードが独立している (種を共有していない) 場合、これらのサブクレードはばらばらのセットになります。

これが明確で、誰かが助けてくれることを願っています。

乾杯、 グレン

次のコードは、サンプル データセットを生成します。subclades は、セットの長さが Y である X 個の互いに素なセットをサンプリングしたいすべての可能なサブクレード (セット) のリストです。

###################################
# Example Dataset
###################################

    library(ape)
    library(phangorn)
    library(TreeSim)
    library(phytools)

    ##simulate a tree

    n.taxa <- 300
    tree <- sim.bd.taxa(n.taxa,1,lambda=.5,mu=0)[[1]][[1]]
    tree$tip.label <- seq(n.taxa)

    ##extract all monophyletic subclades

    get.all.subclades <- function(tree){
    tmp <- vector("list")
    nodes <- sort(unique(tree$edge[,1]))
    i <- 282
    for(i in 1:length(nodes)){
    x <- Descendants(tree,nodes[i],type="tips")[[1]]
    tmp[[i]] <- tree$tip.label[x]
    }
    tmp
    }
    tmp <- get.all.subclades(tree)

    ##set bounds on the maximum and mininum number of tips of the subclades to include

    min.subclade.n.tip <- 10
    max.subclade.n.tip <- 40


    ##function to replace trees of tip length exceeding max and min with NA

    replace.trees <- function(x, min, max){
    if(length(x) >= min & length(x)<= max) x else NA
    }


    #apply testNtip across all the subclades

    tmp2 <- lapply(tmp, replace.trees, min = min.subclade.n.tip, max = max.subclade.n.tip)

    ##remove elements from list with NA, 
    ##all remaining elements are subclades with number of tips between 
##min.subclade.n.tip and max.subclade.n.tip

    subclades <- tmp2[!is.na(tmp2)]

    names(subclades) <- seq(length(subclades))
4

2 に答える 2

2

リスト要素の各ペアの重複がないかどうかをテストし、重複していないすべてのペアのインデックスを抽出する方法の例を次に示します。

findDisjointPairs <- function(X) {
    ## Form a 2-column matrix enumerating all pairwise combos of X's elements
    ij <- t(combn(length(X),2))    
    ## A function that tests for zero overlap between a pair of vectors
    areDisjoint <- function(i, j) length(intersect(X[[i]], X[[j]])) == 0     
    ## Use mapply to test for overlap between each pair and extract indices 
    ## of pairs with no matches
    ij[mapply(areDisjoint, ij[,1], ij[,2]),]
}

## Make some reproducible data and test the function on it
set.seed(1)
A <- replicate(sample(letters, 5), n=5, simplify=FALSE)    
findDisjointPairs(A)
#      [,1] [,2]
# [1,]    1    2
# [2,]    1    4
# [3,]    1    5
于 2013-05-21T17:11:31.773 に答える