2

我有蛋白质 3D creo-EM 扫描，因此它包含一条在自身周围弯曲和扭曲的链 - 并且在 3 维空间中具有 2 个链末端（如连续绳索）。我需要在给定的立方体空间中检测两个或可能是 2 个结尾的倍数的 (x,y,z) 位置。扫描的立方体空间由扫描 EM 显微镜提供的每个体素（范围 0 到 1）中的密度表示，这样“现有物质”的值接近 1，而“无物质”的密度值接近 0。我需要一种检测蛋白质“绳索”边缘的方法（可能的“绳索末端”定义是在某些缠结的方向上缺乏连续性。直觉上，我认为可能至少有两种方法：1）图论中的某些方法（我无法指定确切地说——如果你知道一个——请说出或描述它。2）解析代数的导数——但我又不能指定具体的态度——所以请说出或解释一个。请指定建议方法的计算复杂度。我的项目是用 Python 实现的。请帮忙。提前致谢。

4

2 回答 2

1

一种方法是选择阈值密度，将低于该阈值的所有体素转换为 0，将高于它的所有体素转换为 1，然后在所有 1体素对中寻找最短路径最长的 1 体素对。这两个体素应该靠近最长的“绳索”的末端，不管绳索的确切形状如何。

您可以定义一个图，其中每个 1 体素都有一个顶点，每个 1 体素与其 6 个（或可能 14 个）邻居之间有一条边。然后，您可以使用广度优先搜索在 O(|V|) 时间和空间中计算某个给定顶点 u 和所有其他顶点之间的最短路径的长度（我们在这里不需要 Dijkstra 或 Floyd-Warshall，因为每条边都有权重1）。对每个可能的起始顶点 u 重复此操作会得到 O(|V|^2) 时间的算法。执行此操作时，请跟踪迄今为止最远的一对。

如果您的体素空间有 w*h*d 单元格，则图中可能有 w*h*d 个顶点（如果每个体素都是 1 体素），因此这可能需要 O(w^2*h^2* d^2) 最坏情况下的时间，这可能很多。幸运的是，如果你能负担得起一个稍微不精确的答案，有很多方法可以加快速度：

  • 仅计算从位于边界处的起始顶点开始的最短路径——即那些具有少于 6 个（或 14 个）邻居的顶点。（我相信这不会牺牲最佳解决方案。）
  • 或者，首先通过反复删除所有此类边界顶点来“骨架化”图形，这些边界顶点的移除不会断开图形的连接。
  • 选择起始顶点的一个好的顺序是首先选择任何顶点，然后总是选择一个与最后一个顶点有最大可能距离的顶点（当然，还没有尝试过）。这应该让您在 3 次迭代后非常接近最长的最短路径：距起始顶点最远的顶点将靠近两个绳索末端之一，而距该顶点最远的顶点将靠近另一端！

注意：如果绳索上由于弯曲而彼此靠近的远点之间没有完整的体素间隙，则最短路径将通过这些错误连接“短路”，并可能降低精度。您可以通过增加阈值来改善这一点。OTOH，如果阈值太高，则绳索可能会断开。我希望您希望选择仅导致 1 个连接组件的最高阈值。

于 2016-08-17T04:07:38.437 回答
0

如果您想在 3D 扫描中枚举每条连续路径（从而获得每条路径的末端），您可以针对每个位置应用基本的深度优先搜索，例如：

//applied at some voxel
dfs(...)
    for each surrounding voxel 
        dfs(...)

或详细：

class coordinate{
    x
    y
    z
    visited
}

initialize pathList
initialize coords

add all coordinates which contain "matter" to coords

dfs(coordinate,path)
    coordinate.visited = TRUE
    isEnd = TRUE
    FOR each coordinate
        //check each of the 26 possible locations (total 26 conditionals)
        IF coordinate.get(x-1,y-1,z+1) IN coords AND 
           NOT coordinate.get(x-1,y-1,z+1).visited THEN
            isEnd = FALSE
            path += coordinate.get(x-1,y-1,z+1)
            dfs(coordinate.get(x-1,y-1,z+1),path)
        ...
        IF coordinate.get(x+1,y+1,z-1) IN coords AND 
           NOT coordinate.get(x+1,y+1,z-1).visited THEN 
            isEnd = FALSE
            path += coordinate.get(x+1,y+1,z-1) 
            dfs(coordinate.get(x+1,y+1,z-1),path)
    IF isEnd THEN
        add path to pathList
    remove coordinate from coords

WHILE coords isn't empty
    dfs(coords.get(0),"")

一般过程（dfs）在其他几十个站点上都有很好的记录，但是如果你想测试它，这里有一些粗略的 java（我对 python 不太熟悉），它反映了上面的内容：

public class C {

    ArrayList<Coordinate> coords = new ArrayList<>();
    ArrayList<String> paths = new ArrayList<>();



    static class Coordinate {
        int x, y, z;
        boolean visited;
        Coordinate(int x,int y,int z){
            this.x = x;
            this.y = y;
            this.z = z;
            visited = false;
        }

        public String toString() {
            return "("+x+","+y+","+z+")";
        }
    }



    void dfs(Coordinate c,String path) {
        c.visited=true;
        path+=c.toString();
        boolean isEnd = true;
        //apply dfs to 26 possible neighbors
        for(int x = c.x-1; x <= c.x+1; x++) {
            for (int y = c.y-1; y <= c.y+1; y++) {
                for (int z = c.z+1; z >= c.z-1; z--) {
                    Coordinate coord = getCoordinate(x,y,z);
                    //if coord exists and it's not been visited
                    if(coord!=null && !coord.visited && !coord.equals(c)) {
                        isEnd = false;
                        dfs(coord, path);
                    }
                }
            }
        }
        if(isEnd) paths.add(path);

        coords.remove(c);
    }

    Coordinate getCoordinate(int x,int y,int z){
        for(Coordinate b: coords){
            if(x==b.x && y==b.y && z==b.z) return b;
        }
        return null;
    }


    void search(){
        //while there are points in 3d space extend a path from one
        while(!coords.isEmpty()){
            dfs(coords.get(0),"");
        }
    }




    public static void main(String[] args) {

        C coord = new C();

        //for each place where there exists matter
        //create a coordinate object and add to coords
        // for example:
        coord.coords.add(new Coordinate(0,0,0));
        coord.coords.add(new Coordinate(-1,1,1));
        coord.coords.add(new Coordinate(1,1,1));
        coord.coords.add(new Coordinate(-1,2,2));
        coord.coords.add(new Coordinate(-1,0,2));
        coord.coords.add(new Coordinate(1,2,2));
        coord.coords.add(new Coordinate(1,0,2));

        coord.search();
        //print out each path on separate line, 
        //the path endings can easily be obtained from this 
        for(String s:coord.paths) System.out.println(s);

    }
}
于 2016-08-17T10:22:03.810 回答